Matematica Discreta I
Lezione del giorno 3 dicembre 2007
Come visto nell’ultimo esempio, elementi diversi possono rappresentare classi di equivalenza uguali. Il criterio per stabilire quando ciò avviene è il seguente:
Teorema. Sia definita nell’insieme A una relazione di equivalenza R.
Allora dati a,bA si ha:
[a ] = [b] aRb Dimostrazione:
(): per ipotesi [a] = [b]; l’elemento a [a] (per la proprietà riflessiva), e dunque a[b], ossia aRb (tesi).
(): per ipotesi aRb; la tesi [a]=[b] richiede la dimostrazione di una doppia inclusione [a] [b] e [a] [b].
Dimostriamo che [a] [b] : preso un generico elemento x[a] si ha xRa; da xRa e dall’ipotesi aRb si ha bRx (per la proprietà transitiva), dunque x [b], e si può concludere che [a] [b].
Viceversa dimostriamo che [b] [a]: preso un generico elemento x[b] si ha xRb; dall’ipotesi aRb segue bRa (per la proprietà simmetrica); da xRb e da bRa si ha xRa (per la proprietà transitiva), dunque x [a], e si può concludere che [b] [a].
Le classi di equivalenza hanno una importante proprietà:
Teorema. Sia definita nell’insieme A una relazione di equivalenza R.
Allora le classi di equivalenza distinte formano una partizione dell’insieme A.
Dimostrazione:
Dimostriamo le proprietà che caratterizzano una partizione di A
1) Le classi di equivalenza sono sottoinsiemi non vuoti di A: questo è già stato notato prima, sfruttando la proprietà riflessiva (la classe rappresentata da a contiene almeno l’elemento a)
2) Date 2 generiche classi distinte [a]≠[b], esse sono disgiunte, ossia hanno intersezione vuota: per assurdo supponiamo che abbiano un elemento in comune x; dunque xRa (perché x[a]) e anche xRb (perché x[b]). Ma allora da aRx segue xRa (per la simmetrica) e da aRx e xRb segue aRb (per la transitiva). Infine da aRb segue, per il teorema precedente, l’eguaglianza [a]=[b], contraddizione.
3) L’unione di tutte le classi di equivalenza è uguale all’insieme A: ciò è ovvio, perché preso un generico elemento aA, tale elemento appartiene ad almeno una classe di equivalenza (per esempio alla classe [a], sempre per la proprietà riflessiva).
Esempio: nell’esempio precedente si sono ottenute 2 sole classi distinte {naturali pari} e {naturali dispari}, e in effetti esse costituiscono una partizione di N, come affermato dal Teorema.
Costruiremo ora delle particolari relazioni di equivalenza nell’insieme Z dei numeri interi relativi.
Congruenze
Estendiamo i concetti di divisore e di multiplo dall’insieme N dei numeri naturali all’insieme Z dei numeri interi relativi: se a,bZ diremo che a è divisore di b (o che b è multiplo di a) e scriveremo ab , se esiste un cZ tale che ac=b.
Per esempio (-3)15 perché esiste –5Z tale che (-3)(-5)=15.
Ovviamente per ogni aZ si ha a0 perché a0=0.
Fissiamo un intero relativo mZ (detto modulo) e definiamo una relazione nell’insieme Z mediante il predicato P(x,y)=”m(x-y)” (dove x,y variano in Z). Dunque un numero intero relativo x è associato in tale relazione ad un numero intero relativo y quando m è divisore della differenza (x-y), o equivalentemente quando La differenza (x-y) è un multiplo di m.
Tale relazione è detta congruenza modulo m, e se un intero relativo x è associato in tale relazione ad un intero relativo y, diremo che x è congruo y modulo m e scriveremo:
x≡y (mod m)
Per esempio: 12≡2 (mod 5) perché 5 è divisore della differenza (12-2)=10; 16≡(-5) (mod 7) perché 7 è divisore della differenza 16-(-5)=21.
Teorema. La relazione di congruenza modulo m è una relazione di equivalenza.
Dimostrazione:
Proprietà riflessiva: per ogni aZ si ha a≡a (mod m) perché a-a=0=0m è multiplo di m.
Proprietà simmetrica: per ogni a,bZ se a≡b (mod m) allora si ha b≡a (mod m) perché se a-b=mk con k intero relativo, allora b-a=-(a-b)=m(-k) con (-k) intero relativo.
Proprietà transitiva: per ogni a,b,cZ se a≡b (mod m) e se b≡c (mod m) allora si ha a≡c (mod m) perché se a-b=mk, b-c=mh con k,h interi relativi, allora a-c=(b+mk)-(b-mh)=m(h+k) con (h+k) intero relativo.
Notiamo che se x≡y (mod m) allora esiste cZ tale che (x-y)=mc, da cui (x-y)=(-m)(-c) quindi si ha anche x≡y (mod -m); viceversa se x≡y (mod -m) allora si ha in egual modo che x≡y (mod m).
Dunque la congruenza modulo m coincide con la congruenza modulo –m, da cui si deduce che possiamo limitarci a studiare le congruenze con modulo non negativo. Quindi supporremo d’ora in poi che il modulo m sia 0 .
Studiamo alcuni casi con moduli particolari.
a) m=0: si ha x≡y (mod 0) se (x-y) è multiplo di 0, quindi se esiste cZ tale che x-y=0c=0 ossia se x=y. Dunque la congruenza modulo 0 coincide con la relazione di eguaglianza. Ogni classe di equivalenza contiene un solo elemento (il rappresentante della classe) e si ottengono infinite classi.
b) m=1: si ha x≡y (mod 1) se (x-y) è multiplo di 1, ma ciò è sempre vero. Dunque nella congruenza modulo 1 tutti gli interi relativi sono congrui fra loro. Vi è un’unica classe di equivalenza, coincidente con l’intero insieme Z.
Avendo studiato in dettaglio tali casi particolari, supporremo d’ora in poi che il modulo m sia >1.
Ci proponiamo ora di studiare le classi di equivalenza della congruenza modulo m, dette classi di congruenza modulo m. Se scegliamo ad arbitrio un rappresentante aZ, la classe di congruenza [a] rappresentata da a è definita come segue:
[a] = { xZ / x≡a (mod m) } = { xZ / x-a è multiplo di m } = { xZ / x-a=mk con kZ }=
= { xZ / x=a+mk con kZ }.
Dunque gli elementi di [a] sono della forma x=a+mk con k che varia in Z: al variare del parametro k, si ottengono tutti gli elementi della classe [a] (che sono infiniti numeri interi relativi).
Possiamo calcolare qualche elemento di [a] facendo assumere al coefficiente k alcuni valori interi relativi (k=0,1,-1,2,-2,…..): [a] = {a , a+m , a-m , a+2m , a-2m ,….}
Per esempio nella congruenza modulo m=7, la classe [3] rappresentata da a=3 contiene i numeri della forma x=3+7k, con k che varia in Z: [3] = { 3, 10, -4, 17, -11, ….}.
Dunque ogni classe di congruenza modulo m contiene infiniti numeri interi relativi. Ma quante sono in tutto le distinte classi di congruenza modulo m ?
Esempio. Studiamo le classi di congruenza modulo m=4.
Costruiamo una di tali classi, fissando per esempio il rappresentante a=6:
[6] = { xZ / x≡6 (mod 4) } = { xZ / x=6+4k con kZ } = {6, 10, 2, 14, -2, …}
Se vogliamo costruire una classe di congruenza diversa, dobbiamo scegliere un rappresentante a che non sia congruo 6 modulo 4 (perché sappiamo da un Teorema precedente che se aRb allora [a]=[b]). Possiamo per esempio scegliere a=11 (la differenza 11-6=5 non è multiplo di m=4):
[11] = { xZ / x≡11 (mod 4) } = { xZ / x=11+4k con kZ } = {11, 15, 7, 19, 3, …}
Se vogliamo costruire una classe di equivalenza diversa dalle 2 già costruite, dobbiamo scegliere un rappresentante a che non sia congruo 6 modulo 4 e che non sia congruo 11 modulo 4. Possiamo per esempio scegliere a=5 (le differenze 6-5=1, 11-5=6 non sono multipli di m=4):
[5] = { xZ / x≡5 (mod 4) } = { xZ / x=5+4k con kZ } = {5, 9, 1, 13, -3, …}
Se vogliamo costruire una classe di equivalenza diversa dalle 3 già costruite, dobbiamo scegliere un rappresentante a che non sia congruo 6 modulo 4, che non sia congruo 11 modulo 4, e che non sia congruo 5 modulo 4. Possiamo per esempio scegliere a=8:
[8] = { xZ / x≡8 (mod 4) } = { xZ / x=8+4k con kZ } = {8, 12, 4, 16, 0, …}
A questo punto non riusciamo a costruire una classe di equivalenza diversa dalle 4 già costruite, perché non riusciamo, per quanti tentativi facciamo, a trovare un rappresentante a che non sia congruo 6 modulo 4, che non sia congruo 11 modulo 4, che non sia congruo 5 modulo 4, e che non sia congruo 8 modulo 4.
Possiamo concludere che le classi di congruenza distinte modulo 4 sono in numero di 4, cioè in numero uguale al modulo.
I prossimi risultati dimostreranno che ciò non è casuale.
