Relazioni
Relazioni d’ d ’equivalenza equivalenza - - Aritmetica Aritmetica modulare modulare
Relazioni d’ Relazioni d ’equivalenza equivalenza
L L ’ ’ insieme quoziente insieme quoziente
L L ’ ’ aritmetica in Z aritmetica in Z
nnEsercitazione N
Esercitazione N .5 .5
ESERCIZIO 1.
Relazioni di equivalenza
a) Dire quali delle seguenti sono relazioni di equivalenza:
1. In B= {n∈N | n >1}: x ∼ y ⇔ x e y hanno un fattore comune più grande di 1.
2. In Z: a ∼ b ⇔ a=b oppure a=-b 3. In R: a ∼ b ⇔ a≥b.
4. In ZxZ: (a,b) ∼ (c,d) ⇔ 8a+9b=8c+9d
b) Nel caso 2. stabilire se le classi di equivalenza hanno lo stesso numero di elementi.
c) Nel caso 4. trovare 3 diversi elementi di ZxZ equivalenti a (-1,1).
a) 1. Vale la riflessiva a ∼ a : a è fattore di se stesso Vale la simmetrica : a ∼ b ⇒ b ∼ a Sì !
Vale la transitiva? a ∼ b & b ∼ c ⇒ a ∼ c ?
2 ∼ 6 , 6 ∼ 3 , ma 2 ∼ 3 , quindi non vale la trans.
2. In Z sia a ∼ b ⇔ a=b oppure a=-b
…in modo equivalente si può scrivere a ∼ b⇔ |a|=|b|
Quindi ∼ è rel. di equiv.: l'uguaglianza in N è rel.di equiv.
3. In R sia a ∼ b ⇔ a≥b Non vale la simmetrica :
3 ∼ 2 perché 3≥2, ma 2 ∼ 3.
4.
Un caso in cui è rapido verificare l’equivalenza di una relazione è quando la relazione coincide con la relazione d’equivalenza associata ad una funzione.Se f:A→B è una funzione, la relazione d’equivalenza associata ad f è
R
f :In A x
R
fy ⇔ f(x) =f(y).
Si tratta di individuare f .
In ZxZ: (a,b) ∼ (c,d) ⇔ 8a+9b=8c+9d
La funzione ′giusta′ è f:ZxZ
→Z t.c. f(x,y)= 8x+9y ( 8x+9y è intero, essendo interi x,y,8,9),f(a,b) = 8a+9b, f(c,d)=8c+9d
(a,b)∼(c,d)⇔
f(a,b)=f(c,d).Quindi la relazione
∼ coincide con R
fed è quindi
una relazione d’equivalenza.
b) In Z: a ∼ b ⇔ a=b oppure a=-b Sappiamo che ∼ è una rel. di equiv.
Descriviamo qualche classe, ad esempio
1
(classe di 1)1 = {x∈Z | x∼ 1}= {x∈Z | x=1 oppure x=-1}= {1,-1}
2
- = {x∈Z | x∼ 2}= {x∈Z | x=2 oppure x=-2}= {2,-2}
0 = {x∈Z | x∼ 0} = {0}
1
-
= {x∈Z | x∼ -1} ………. inutile proseguire ! - 1 = 1 perchè 1 ∼ -1
0 1 - 2 . . . le classi
Le classi sono a due a due disgiunte e l’unione dà l’insieme quoziente : sono una partizione di Z.
Le classi hanno tutte due elementi, tranne la classe
0 che ne ha uno.
L’insieme delle classi si chiama insieme quoziente . Ad ogni relazione di equivalenza è associata una parti- zione e viceversa.
0 1 -1
2 -2
c)
Cerchiamo ora 3 diversi elementi di ZxZ equivalenti a (-1,1).(x,y)
∼
(-1,1)⇔ 8x+9y= -8+9= 1.
Cerchiamo quindi 3 soluzioni distinte intere di 8x+9y=1.
Abbiamo il vantaggio di sapere già che (-1,1) è equivalen- te a se stesso, ossia che (-1,1) è una soluzione particolare di 8x+9y=1 !
Aggiungendo le soluzioni dell’omogenea associata troviamo che la soluzione generale dell’equazione è (-1+9t,1-8t), t∈Z
Assegniamo a t due valori distinti non nulli ( altrimenti ritroviamo (-1,1)).
t = 1 (8,-7) t = -1 (-10,9)
I tre elementi trovati, equivalenti a (-1,1) sono : (-1,1), (8,-7), (-10,9).
ESERCIZIO 2.
Relazioni di equivalenza
In ùxù si consideri la relazione (a,b)∼(c,d) ⇔ a+d=b+c.
a) Provare che ∼ è una relazione di equivalenza b) Descrivere le classi di equivalenza di (0,0), (1,0),
(0,1), (3,2).
c) Provare che ogni classe di equivalenza contiene al- meno una coppia (a,b) avente una componente nul- la.
d) Determinare un 'noto' insieme in corrispondenza biunivoca con l'insieme quoziente ùxù/∼ ?
a) Riflessiva: (a,b)∼(a,b) ∀ (a,b)∈ùxù
Verifichiamolo:
(a,b)∼(a,b) ⇔ a+b=b+a
Ma a+b=b+a è vera in ù per la proprietà commutati-
va dell'addizione e quindi è vero che (a,b)∼(a,b) per ogni (a,b)∈ùxù
Simmetrica:(a,b)∼(c,d)⇒(c,d)∼(a,b) ∀(a,b),(c,d)∈ùxù Verifica:
Per la definizione di ∼ sappiamo che
(a,b)∼(c,d) ⇔ a+d=b+c
(c,d)∼(a,b) ⇔ c+b=d+a
Se proviamo l'implicazione di destra allora vale 'automa-
ticamente' l'implicazione di sinistra.
E ciò è vero perché
a+d=b+c ⇒ d+a=c+b
(propr. comm. di ù )⇒ c+b=d+a
(propr.comm.dell'uguaglianza di ù )Quindi (a,b)∼(c,d)⇒(c,d)∼(a,b).
c) Transitiva: se (a,b)∼(c,d) e (c,d)∼(e,f) allora (a,b)∼(e,f) ∀ (a,b), (c,d), (e,f) ∈ùxù
Verifica:
⎩⎨
⎧
+
= +
+
=
⇒ +
⎩⎨
⎧
∼
∼
e d f c
c b d a
f) (e, d) (c,
d) (c, b)
(a,
somma m. a m.
a+d+c+f=b+c+d+e, cioè
a+f=b+e a+f=b+e ⇔(a,b)∼(e,f)
o.k. tesi provata
b)
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 gene- rale si ha:
x = y ⇔ x ∼ y
Le classi di equivalenza sono le semirette uscenti dall'origi- ne 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 parti- zione di ùxù
Inoltre notiamo che:
b)
(a, contiene (a-b,0) se a≥b contiene (0,b-a) se a≤b .
d) La figura illustra la c.b. tra l'insieme quoziente e Z:
alla semiretta bisettrice del I° quadrante corrisponde lo ze- ro, alle semirette 'sotto' la bisettrice corrispondono gli inte- ri positivi, a quelle 'sopra' gli interi negativi.
Dunque vale c)
ESERCIZIO 3.
L’orologio: la congruenza modulo 12
a) Per ciascuno dei numeri seguenti determinare il minimo intero positivo modulo 12 a cui è congruente:
19, -11, 149.
b) Se adesso sono le ore 14 (= 2 P.M.) che ora del giorno ( o della notte) sarà tra 1000 ore ?
c) Se lo scorso anno Natale era di Domenica, in che giorno cadrà Natale quest’anno e nel 2020 ?
a) Ricordiamo la
DEFINIZIONE DI CONGRUENZA MODULO
n
Sia n ∈ ù. 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.
19 ≡ ? (mod 12)
19 = 12+7 ⇒ ⇒ 19≡7 (mod 12) (pensare all’orologio!)
-11≡ ? (mod 12)
-11 = -12+1 ⇒ -11≡1 (′giriamo in senso antiorario′)
149 ≡ ? (mod 12) 149 =12⋅12 +5 ⇒ 149≡5
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
Per ogni x∈Z vale x ≡ r dove r è il resto della divisione x:n Poiché i resti possibili sono 0,1,2,3,4,…,n-1 ci sono n clas- si di equivalenza.
Nel caso n=12
0 = {tutti gli elementi congruenti a 0}
= {…,-24,-12,0,12,24,… }
1 = {tutti gli elementi congruenti a 1}
= {…,-23,-11,1,13,25,… } etc.
Le classi sono in tutto 12 : Z
12= { 0 , 1 , 2 , 3 , 4 ,…, 11 }.
b
) Se adesso sono le ore 14 (= 2 P.M.) che ora del giorno (o della notte) sarà tra 1000 ore ?Dovremo determinare quel numero x , 0≤ x <24 tale che
x = 14 + 1000 mod (24).
x = 1014 = 42 ⋅ 24 + 6 = 6
1014: 24 = 42,
con resto 6 Risposta: saranno quindi le 6 del mattino.c)
Se lo scorso anno Natale era di Domenica, in che giorno cadrà Natale quest’anno? e nel 2020 ?Diciamo che quest’anno Natale cadrà di lunedì, non essendo il 2006 bisestile. Ma giustifichiamolo con l’aritmetica modulare.
La durata del 2006, è stata di 365 giorni.Possiamo porre:
0 = domenica , 1= lunedì, 2=martedì,3=mercoledì, 4= giovedì, 5= venerdì, 6= sabato
Troviamo x, 0≤ x <6 tale che
x
=0 + 365
mod 7x
=365 = 7 ⋅ 52 + 1
( 365=7⋅52+1 in Z), quindix
=1
. Allora quest’anno Natale cade di Lunedì.Per il 2020 attenti al n° di anni bisestili (quelli divisibili per 4 ossia le ultime due cifre sono divisibili per 4: ce ne sono 4)
x
=1+365⋅14+4=… =5 ⇒ Natale 2020 cade di venerdìO
SSERVAZIONEPer effettuare il calcolo 1 + 365 ⋅ 14 + 4 = 5
Non occorre fare il calcolo ′sotto’ la barra, trovare
5115
, e poi la divisione di 5115 per 7 stabilendo così che il resto è 5 !Si può procedere più rapidamente così
= +
⋅
+ 365 14 4
1 1 + ( 365 ⋅ 2 ⋅ 7 ) + 4 = 1 + 4 = 5
Multiplo di 7: da elidereQuesto é lecito farlo perché in Z
nvalgono tutte le buone proprietà di Z
• def. di somma in Z
n: a + b = a + b
• def. di prodotto in Z
n: a ⋅b = a ⋅ b
• 0 è l’el. neutro risp. alla somma in Z
ncioè a + 0 = a per ogni a ∈ Z
n, con
0
={...-2n,-n,0,n,2n,...} e quindi
0
=
n=
2n=...=
knper ogni k∈Z
• 1 è l’el. neutro risp. al prodotto
• a ha opposto ( risp. alla somma) − a ( = - a )
• potenza in Z
n: a
n= a
n• Proprietà comm., ass. rispetto alla somma, etc.
C
URIOSITÀI
N QUALE GIORNO X DELLA SETTIMANA SONO NATO/
A?
x = a a s 2 s
4 4
10 26 1)
g (m −
⎥⎦ ⎥
⎢⎣ ⎢
⎥⎦ +
⎢⎣ ⎥ + ⎢
⎥⎦ +
⎢⎣ ⎥
⎢ + ⋅
+ mod 7
g= giorno del mese m= mese
a= anno ( solo le due ultime cifre) s= secolo ( solo le prime due cifre)
⎣ ⎦ y = max int ero ≤ y
1= Domenica, 2= Lunedì, 3=Martedì, 4=Mercoledì,5=Giovedì, 6=
Venerdì, 0 = Sabato
Eccezioni : gennaio viene indicato 13, febbraio 14 e i rispettivi anni vengono diminuiti di 1.
[Christian Zeller, Kalender Formeln, 1886]
Esempio: Che giorno della settimana è il 25 dicembre 2006? (…lunedì ! ) g=25,m=12, a=6, s=20
