Matematica Discreta Lezione del giorno 20 aprile 2009 Simbologia additiva e moltiplicativa per un’operazione in un insieme

Matematica Discreta

Lezione del giorno 20 aprile 2009

Simbologia additiva e moltiplicativa per un’operazione in un insieme

Talvolta per indicare un’operazione in un generico insieme A useremo, al posto della notazione astratta xy, la simbologia moltiplicativa.

In tale simbologia il risultato dell’operazione sugli operandi x,y (invece che con x*y) sarà indicato con il simbolo xy; l’eventuale elemento neutro di A (detto unità di A) sarà indicato con 1A; il simmetrico di un elemento simmetrizzabile xA sarà detto inverso di x e sarà indicato con x^-1. Analogamente potremo usare la simbologia additiva: x+y indicherà il risultato, il neutro (detto zero di A) sarà indicato con 0A, il simmetrico di un elemento simmetrizzabile x (detto opposto di x) sarà indicato con –x.

Operazioni fra classi di equivalenza

Consideriamo un insieme Ain cui sia anche 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.

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 [x]=[x1]  xRx1 .

Indicheremo con il simbolo A/R l’insieme delle classi di equivalenza della relazione R in A.

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 * 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 e poi si considera la classe rappresentata da tale risultato).

Ciò solleva però un problema: il concetto di operazione implica l’unicità del risultato (fissati i 2 operandi). 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].

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 si definisce 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 coincide 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]

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

[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)

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

Per quanto osservato in precedenza l’insieme delle classi di congruenza modulo m viene allora dotato di un’operazione di somma di classi e di un’operazione di prodotto di classi definite da:

[x]+[y] = [x+y] [x][y] = [xy].

Esempi: se consideriamo le seguenti classi di congruenza modulo 7 [5], [6]

possiamo calcolare la loro somma e il loro prodotto:

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

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

(fare riferimento sempre all’algoritmo precedente).