Matematica Discreta Lezione del giorno 22 aprile 2010

Matematica Discreta

Lezione del giorno 22 aprile 2010 Operazioni fra classi di equivalenza

Consideriamo un insieme A in cui sia definita una relazione di equivalenza R: ricordiamo che se l’elemento xA è associato nella relazione R all’elemento yA scriviamo il simbolo xRy.

Inoltre per ipotesi R soddisfa le proprietà riflessiva, simmetrica e transitiva.

Sappiamo che, fissato xA, si può costruire la classe di equivalenza rappresentata da x, contenente tutti gli elementi di A che sono associati ad x nella relazione R:

[x] = { yA / xRy }

Ricordiamo inoltre che le distinte classi di equivalenza formano una partizione di A (cioè 2 classi diverse hanno intersezione vuota, e l’unione di tutte le classi è l’insieme A).

Si ha inoltre, per un risultato già dimostrato:

[x]=[y]  xRy .

Indicheremo con il simbolo A/R l’insieme delle classi di equivalenza della relazione R in A (è detto anche insieme quoziente dell’insieme A rispetto alla relazione di equivalenza R).

Supponiamo anche che nell’insieme A sia definita (oltre alla relazione di equivalenza R) anche un’operazione *.

Potremmo allora provare a definire nell’insieme A/R delle classi di equivalenza un’operazione fra classi (che indichiamo sempre con il simbolo *) servendoci dell’operazione * (che è definita nell’insieme A) nel modo seguente:

[a]*[b] = [a*b]

(quindi per calcolare il risultato dell’operazione sulle classi [a],[b] prima si calcola il risultato dell’operazione * sui rappresentanti a,b, ottenendo un elemento a*b in A, e poi si considera la classe rappresentata da tale elemento come risultato dell’operazioni fra le 2 classi).

Ciò solleva però un problema: il concetto di operazione implica l’unicità del risultato (perché l’operazione è una funzione che associa ad ogni coppia di operandi uno e un solo risultato). Quindi per essere certi che la nostra operazione fra classi abbia risultato unico (fissate le 2 classi su cui si opera) dobbiamo essere sicuri che se [a]=[c] e se [b]=[d] (abbiamo lasciato invariate le 2 classi ma cambiato il rappresentante) allora necessariamente [a*b]=[c*d] (il risultato deve essere invariato).

Tale proprietà si può esprimere in modo equivalente nel modo seguente:

se aRc, e se bRd allora necessariamente (a*b)R(c*d)

(è detta compatibilità della relazione di equivalenza R con l’operazione *).

Riassumendo dunque: se in un insieme A sono definite sia una relazione di equivalenza R che un’operazione *, e se R è compatibile con * (cioè se da aRc, bRd segue sempre (a*b)R(c*d)) allora nell’insieme A/R delle classi di equivalenza si può definire un’operazione * fra classi (con risultato unico) ponendo [a]*[b] = [a*b].

Tale operazioni fra classi di equivalenza è detta operazione indotta dall’operazione * definita in A.

Operazioni fra classi congruenza.

Ricordiamo che, fissato un intero m>1 (modulo), si definisce nell’insieme Z degli interi relativi una relazione di equivalenza, detta congruenza modulo m: dati gli interi x,yZ, x associato con y quando (x-y) è multiplo di m (cioè se esiste kZ tale che x-y=mk).

Se x è associato con y si scrive xy (mod m) invece di xRy (e si legge x congruo y modulo m).

Si possono costruire dunque le classi di equivalenza di tale relazione, che sono dette classi di congruenza modulo m.

Ricordiamo anche che le classi di congruenza (distinte) modulo m sono le seguenti:

[0], [1], ……, [m-1]

e quindi sono in numero di m (cioè in numero uguale al modulo).

Abbiamo a suo tempo dimostrato che, dato un qualunque intero relativo x, per trovare quale delle classi dell’elenco suddetto coincida con la classe [x] si deve usare il seguente algoritmo:

- se x>0 , dividendo x per m si ha x=mq+r, ed in questo caso [x]=[r]

- se x<0 allora dividendo -x per m si ha -x=mq+r, ed in questo caso:

- se r=0 allora [x]=[0]

- se r>0 allora [x]=[m-r]

L’insieme quoziente di Z rispetto alla relazione di congruenza modulo m (cioè l’insieme delle classi di congruenza modulo m) sarà indicato con il simbolo Z

:

Z

= { [0], [1], ……, [m-1] }

Esempi: le classi di congruenza distinte modulo 7 sono le 7 classi seguenti:

Z

= { [0], [1], [2], [3], [4], [5], [6] }

Si ha per esempio (facendo riferimento all’algoritmo precedente):

[18] = [4] (perché 18>0 e r=4 è il resto della divisione di 18 per 7) [-28] = [4] (perché -28<0 e r=0 è il resto della divisione di 28 per 7) [-30] = [5] (perché -30<0 e r=2 è il resto della divisione di 30 per 7)

Dimostreremo in seguito che sia l’operazione di somma che quella di prodotto esistenti in Z sono compatibili con la relazione di congruenza modulo m.

Da ciò seguirà che sarà possibile definire, nell’insieme Z

delle classi di congruenza modulo m, le operazioni di somma e prodotto fra classi indotte dalle operazioni di somma e prodotto fra numeri interi:

[a]+[b] = [a+b] [a][b] = [ab]

Esempio.

Consideriamo l’insieme Z

delle 7 classi di congruenza modulo 7:

Z

= { [0],[1],[2],[3],[4],[5],[6] } e le seguenti classi di congruenza modulo 7 [5], [6]Z

Possiamo allora calcolare la somma e il prodotto di queste 2 classi:

[5]+[6] = [5+6] = [11] = [4]

[5][6] = [56] = [30] = [2]

(fare riferimento sempre all’algoritmo precedente per ottenere [11]=[4], [30]=[2]).