♦ Relazioni di equivalenza classi - insiemi quoziente

♦

♦ Relazioni di equivalenza classi - insiemi quoziente

♦

♦ Relazioni d’equivalenza e funzioni

♦

♦ Interi e razionali come insiemi quozienti

♦

♦ La congruenza

simbolo indicante argomento trattato e discusso in classe ma non riportato in queste slides

Rosalba Barattero

ESERCITAZIONE N.6

10 novembre 2009

ESERCIZIO 1.

Relazioni di equivalenza – Definizione formale di Z

In ùxù si consideri la relazione di relazione d’equiva- lenza (a,b)∼(c,d) ⇔ a+d=b+c

a) Descrivere le classi di equivalenza di (0,0), (1,0), (0,1), (3,2).

b) Provare che ogni classe di equivalenza contiene almeno una coppia (a,b) avente una componente nulla.

c) Provare che Z è in corrispondenza biunivoca con l'insieme quoziente ùxù/∼

a) Descrivere le classi di equivalenza di (0,0),(1,0),(0,1),(3,2).

^(0,0) = {(a,b) ∈ùxù | (a,b)∼(0,0)}

= {(a,b) ∈ùxù | a=b}

(1,0) = {(a,b) ∈ùxù | (a,b)∼(1,0)}

= {(a,b) ∈ùxù | a=b+1}

(0,1) = {(a,b) ∈ùxù | (a,b)∼(0,1)}

= {(a,b) ∈ùxù | a+1=b}

(3,2) = {(a,b) ∈ùxù | (a,b)∼(3,2)}

= {(a,b) ∈ùxù | a+2=b+3}

= {(a,b) ∈ùxù | a=b+1}

Oh ! (3,2) = (1,0) Ciò non deve stupire perché (3,2)∼(1,0) e in generale si ha: x = y ⇔ x ∼ y

Le classi di equivalenza sono le semirette uscenti

dall'origine e parallele alla bisettrice del I° e III° e il loro insieme forma l'insieme quoziente.

Le classi d'equivalenza sono a due a due disgiunte e la loro unione dà tutto l'insieme quoziente : formano una

partizione di ùxù

Inoltre notiamo che:

b)

(a, contiene (a-b,0) se a≥b contiene (0,b-a) se a≤b .

Questo ci consente di realizzare una c.b. tra l’insieme quoziente ùxù/∼ e Z .

Dunque vale c)

d) La figura illustra la c.b. tra l'insieme quoziente e Z: alla semiretta bisettrice del I° quadrante corrisponde lo zero di Z, alle semirette 'sotto' la bisettrice corrispondo-no gli interi positivi, a quelle 'sopra' gli interi negativi:

− +

≠

∈

→

≠

∈

→

→

Z : 0 n N, n n - n) (0,

Z : 0 n N, n n (n,0)

0 (0,0)

Si tratta poi di introdurre le operazioni su ùxù/∼

lo omettiamo x ora.

Discussione in classe sul significato matematico di questa introduzione formale di Z tramite i concetti già definiti di ù, prodotto cartesiano, relazione d’equivalenza.

ùxù/∼ Z ^{( 0 , 2 )} -2

) 1 , 0

( -1

) 0 , 0

( 0

) 0 , 1

( 1

etc.

ESERCIZIO 2.

Relazioni di equivalenza – Definizione formale di Q

Nel prodotto cartesiano ZxZ

si introduce la seguente relazione (a,b)~(c,d) ad=bc.

a) Provare che ~ è una relazione d’equivalenza b) Provare che l’insieme quoziente ( = l’insieme delle

classi di equivalenza) è in corrispondenza biunivoca con Q .

Con l’uso della nozione di relazione d’equivalenza e di Z si dà una definizione formale di Q (analogo a Ex1. per Z).

a) lasciato per esercizio

b) la figura illustra alcune classi di equivalenza in ZxZ

ossia alcuni elementi di Q ( secondo la c.b.).

3 ... 1 ) 3 , 1 ( ) 3 , 1 ( 2 ...

) 3 , 6 ( ) 1 , 2 ( 1 ...

) 3 , 3 ( ) 1 , 1

( = = ↔ = − − = ↔ − = − = ↔

Motivazione della rel. di equiv.

: ad bc d

c b

a _{= ⇔ =}

ESERCIZIO 3.

Relazioni di equivalenza e funzioni

Su Z si consideri la relazione a~b a e b divisi per 4 hanno lo stesso resto.

a) Provare che ~ è una relazione d’equivalenza b) Determinare il numero delle classi dell’insieme

quoziente Z/~

c) Determinare il più piccolo intero positivo x tale che la classe di x coincida con la classe di -21.

a) Quando nella definizione di equivalenza interviene il segno di uguaglianza, conviene controllare se la relazione data definita sull’insieme A coincide con la relazione asso- ciata ad una funzione f avente come dominio A.

Infatti se f:A→B è una funzione tra due insiemi, ad essa è associata la relazione R

così definita

a R

b f(a)=f(b) (1) che si prova essere una relazione d’equivalenza.

Il vantaggio è quindi quello di evitare le tre verifiche di rifl., simm, trans., a patto di individuare f !

Nel ns. caso f ha come dominio Z, la costruiamo in modo tale che sia

a R

b il resto di a diviso 4 = il resto di b diviso 4 (2) Dal confronto di (1) con (2) si ricava:

f(a) = il resto di a diviso 4

Non ci resta che individuare un possibile codominio per f , tenendo conto che deve avere tra i suoi elementi tutti i possibili resti di un intero diviso per 4.

Il resto della divisione di un intero per 4 sappiamo essere un intero positivo o nullo, dunque scegliamo come codo-minio N, o Z, o, come suggerisce lo studente [G.]

, l’insieme

{0,1,2,3}!

Così f:Z→N definita da f(a)=resto della divisione di a per 4 ci consente di dire che :

la relazione a~b a e b divisi per 4 hanno lo stesso resto è un’equivalenza !

b) Quante sono le classi di equivalenza A/~ ? Calcoliamo la classe di 0:

0 = {a∈Z | a~0} ( usiamo la def. di ~)

= {a∈Z | il resto di a diviso 4 = il resto di 0 diviso 4}

= {a∈Z | il resto di a diviso 4 è 0}

= {a=4n | n∈Z } = 4Z

Calcoliamo la classe di 1 :

1 = {a∈Z | a~1} ( usiamo la def. di ~)

= {a∈Z | il resto di a diviso 4 = il resto di 1 diviso 4}

= {a∈Z | il resto di a diviso 4 è 1}

= {a∈Z | a=4q+1, con q∈Z } = 4Z+1

…

2 = 4Z+2 , 3 = 4Z+3 e stop ! i resti possibili di un intero diviso per 4 sono 0,1,2,3 (il teorema della divisibilità in Z ).

Ecco il perché della risposta precedente (*) di [G].

Conclusioni le classi di equivalenza sono 4 : 0 , 1 , 2 , 3 .

Così Z per effetto della relazione ~ viene ′suddiviso′ in 4 insiemi a due a due disgiunti.

c)Determinare il più piccolo intero positivo x tale che la classe di x coincida con la classe di -21.

21 x = −

Quando sono uguali (coincidono) due classi?

Quando i due rappresentanti sono tra loro equivalenti !

Secondo la ns. def. di equivalenza x e -21 , divisi per 4 hanno lo stesso resto ( 0,opp.1,opp.2,opp. 3).

Dividiamo -21 per 4 :

facciamo prima 21:4 = 5 con resto 1, quindi 21= 5⋅ 4+1 , cambiamo i segni

-21 = -5⋅ 4 – 1 , ma così non va ! il resto r per def. è 0≤r<4 ! Basta aumentare il valore assoluto del quoziente di 1 , con l’aggiunta giusta in modo da non alterare

l’uguaglianza, così : -21 = (-5-1) ⋅ 4 – 1 +4

Quindi : -21 = -6⋅ 4 +3 , ora il quoziente è -6 e il resto è 3 >0 ! E si conclude -21∈ 4Z+3 = ³ , ma vedremo la prossima volta che si può fare anche diversamente …

Insieme partizionato in 4 classi di equivalenza a due a due disgiunte

Discussione in classe su partizioni e relazioni d’equivalenza

Passiamo quindi dalle classi agli interi che le rappresen- tano:

21

x = − x~ -21

Il calcolatore ad orologio di Gauss

1, 13, -11 , … sono tra loro equivalenti ( modulo 12 )

• Sono le 3 e se aggiungiamo 5 ore , l'orologio indicherà le 8 . Scriviamo 3+5 =8.

Sono le 9 e aggiungiamo 5 ore, l'orologio indicherà le 2.

Scriviamo 9+5=2.

Ogni volta che passiamo dallo zero ( le 12) , ricomincia-

mo a contare le ore da 1 .

Tutti i multipli di 12 equivalgono a 0.

• Quindi per convertire numeri interi ai numeri equivalenti modulo 12 ( 0, 1, 2, 3, 4,..., 11) , dividiamo per 12 il

numero e prendiamo il resto, che è l'unico che ci interessa, ed è UNICO ! ( per la divisibilità ! )

• Dunque in modulo 12 usiamo solo i numeri : 0,1,2,3,4,5,6,7,8,9,10,11 ( il resto della divisione di qualunque intero per 12 )

• Siamo partiti da Z che è un insieme infinito e siamo arrivati a Z

, un insieme finito di 12 elementi.

Ogni numero intero è rappresentato da un UNICO numero compreso tra 0 e 11.

Formalizziamo come fa Gauss:

DEFINIZIONE DI CONGRUENZA MODULO

n

Sia n ∈ ù, n>1. Due numeri interi a, b ∈ Z si dicono congruenti modulo n, in simboli

a≡b (mod n)

se n divide la differenza a-b,ossia se vale a-b=kn con k∈Z.

La congruenza è una relazione di equivalenza e si può esprimere anche così :

a, b ∈ Z sono congruenti modulo n

se hanno lo stesso resto quando vengono divisi per n

Scriviamo le classi di equivalenza modulo

12:

Per ogni x∈Z vale x ≡ r ( x congruo ad r) dove r è il resto della divisione x:12.

• I resti possibili sono 0,1,2,3,4,…,11, quindi ci sono 12 classi di equivalenza (con la notazione seguente):

0 = {tutti gli elementi congruenti a 0}

= {…,-24,-12,0,12,24,… } = {12k |al variare di k in Z}

1 = {tutti gli elementi congruenti a 1}

= {…,-23,-11,1,13,25,… } etc.

= {12k+1 |al variare di k in Z}

( n=12k+1 ⇔ n diviso per 12 dà come quoziente k e come resto 1 (teorema di divisibilità, Eserc.N.2,pag. 1,2)) …

11 = = {12k+11 |al variare di k in Z}

L’insieme quoziente ( l’insieme delle classi di equiv.) è : Z

= { 0 ,1 ,2 , 3 , 4 ,…,11 }.

Ma gli orologi con 12 ore non hanno nulla di speciale ! Gauss crea così l’aritmetica modulare ( ′orologi′ con un n. qualsiasi di ore), in cui le def. di somma e prodotto sono …

(*) "I feel fine today modulo a slight headache. ( Oggi mi sento bene modulo un leggero mal di testa. ) - The Hacker’s Dictionary "

Discussione in classe sul significato di questa umoristica citazione