Le relazioni di equivalenza e le funzioni
C'è un legame molto stretto tra le funzioni e le relazioni di equivalenza.
A ogni funzione f con dominio X posso associare una relazione di equivalenza rf definita in X. E' detta reazione di equivalenza associata a f.
E viceversa
A ogni relazione di equivalenza r definita in X, posso associare una funzione con dominio X tale che la relazione associata a f coincida con r.
Spiegazione
Ho una funzione f tra due insiemi A e B.
Definisco una relazione r tra due elementi a di A e b di B tale che f(a)=f(b)
$$ arb \Leftrightarrow f(a)=f(b) $$
La relazione r è una relazione associata alla funzione f.
Si tratta di una relazione di equivalenza.
Per ogni elemento b di B, se b è un'immagine di f allora
$$ b \in Im \: f \Rightarrow f^{-1}(\{b\})=[a] $$
Dove [a] è una classe di equivalenza modulo r di un qualsiasi elemento a di A tale che f(a)=b.
Il sottoinsieme f-1({b}) è detto fibra dell'elemento b.
Nota. Se invece b non è immagine di f, invece, si ha $$ b \notin Im \: f \Rightarrow f^{-1}(\{b\})=Ø $$
L'insieme delle fibre degli elementi di A compone la partizione dell'insieme A in base alla relazione r.
Quindi, l'insieme delle fibre è l'insieme quoziente A/r.
D'altra parte, vale anche il processo inverso.
Se ho una relazione di equivalenza arb definita sull'insieme A, allora esiste un'applicazione p che lega ogni elemento di A con gli elementi [a] dell'insieme quoziente A/r.
$$ p:A \rightarrow A/r $$
Esempio
Ho una funzione f:Z->Z per ogni elemento a di Z.
Dove f(a) è il resto della divisione dell'elemento a per 4.
L'immagine della funzione f è la seguente:
$$ Im(f) = \{ 0, 1, 2, 3 \} $$
Due elementi a e b di Z hanno la stessa immagine Im(f) soltanto se la divisione per 4 ha lo stesso resto.
Ad esempio, prendo l'elemento 8 di Z e lo divido per 4.
La divisione 8/4 ha resto 0.
Ottengo lo stesso resto prendendo altri elementi multipli di 4 ( es. 4, 8, 12, 16, ecc.)
L'elemento 7 diviso 4 ha invece un resto pari a 3.
L'elemento 6 diviso 4 ha un resto uguale a 2.
L'elemento 5 diviso 4 ha un resto uguale a 1.
Nota. Lo stesso resto 1 hanno anche gli elementi 9, 13, 17, 21, ecc.
Quindi, ogni elemento di Z è associato a una classe di equivalenza di Z/r.
La relazione r corrisponde alla una congruenza modulo 4.
E così via.
