Matematica Discreta II Lezione del giorno 11 ottobre 2007

(1)

Matematica Discreta II

Lezione del giorno 11 ottobre 2007

Le principali proprietà degli elementi simmetrizzabile di un monoide (A, ) sono:

1) L’elemento neutro eA è simmetrizzabile, ed è uguale al suo simmetrico (segue da ee=e) 2) Se l’elemento xA è simmetrizzabile con simmetrico x’A, allora anche x’ è simmetrizzabile con simmetrico x (segue da xx’=x’x=e)

3) Se gli elementi x,yA sono simmetrizzabili con simmetrici rispettivamente x’,y’A, anche xy è simmetrizzabile con simmetrico y’x’. Infatti, applicando la proprietà associativa, si ha:

(xy)(y’x’)=[(xy) y’] x’=[x(yy’)] x’=[xe] x’=xx’=e (e analogamente (y’x’)(xy)=e).

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

In tale notazione il risultato dell’operazione sugli operandi x,y sarà indicato con xy (o semplicemente con xy); l’eventuale elemento neutro di A (detto unità di A) sarà indicato con 1

A

; un elemento simmetrizzabile xA sarà detto invertibile e il suo simmetrico (detto inverso di x) sarà indicato con x

^-1

. Le proprietà 2), 3) precedenti si tradurranno dunque nel modo seguente:

(x

^-1

)

^-1

=x, (xy)

^-1

=y

^-1

x

^-1

.

Analogamente potremo usare la notazione additiva: x+y indicherà il risultato, il neutro (detto zero di A) sarà indicato con 0

A

, il simmetrico di un elemento simmetrizzabile x (detto opposto di x) sarà indicato con –x. In tale caso le proprietà 2), 3) precedenti si tradurranno nel modo seguente:

-(-x)=x, -(x+y)=(-y)+(-x) .

Un insieme (A, ) è detto gruppo se è un monoide e se tutti i suoi elementi sono simmetrizzabili.

Un gruppo è commutativo (o abeliano) se la sua operazione soddisfa la proprietà commutativa.

Esempi:

I monoidi Z, Q, R rispetto alla somma sono esempi di gruppi (commutativi).

I monoidi di matrici M

n

(Z), M

n

(Q), M

n

(R) rispetto alla somma di matrici sono esempi di gruppi (commutativi).

Se (A, ) è un monoide, indicheremo con A* il sottoinsieme degli elementi simmetrizzabili di A. La proprietà 3) precedente implica che A* è chiuso rispetto all’operazione di A, quindi si può considerare l’insieme (A*,) dotato della stessa operazione di A.

Tale insieme (A,) è in effetti un gruppo: infatti in esso vale la proprietà associativa (perché vale in A); esiste in esso l’elemento neutro (che coincide con l’elemento neutro e di A, il quale appartiene ad A per la proprietà 1)); ogni elemento xA* ha simmetrico x’A, ma (per la proprietà 2)) si ha x’A, dunque ogni elemento di A è simmetrizzabile in A*.

Esempi:

Considerando l’insieme degli elementi simmetrizzabili dei monoidi esaminati in precedenza, otteniamo nuovi esempi di gruppi.

L’insieme {1, -1} è un gruppo (commutativo) rispetto al prodotto aritmetico.

Gli insiemi Q-{0}, R-{0} (rispettivamente dei razionali non nulli e dei reali non nulli) sono esempi di gruppi (commutativi) rispetto al prodotto aritmetico.

Il sottoinsieme di M

n

(Z) contenente le matrici con elementi tutti =1 è esempio di gruppo

(commutativo) rispetto al prodotto di matrici (elemento per elemento).

(2)

I sottoinsiemi di M

n

(Q), M

n

(R) contenenti le matrici con elementi tutti 0 sono esempi di gruppi (commutativi) rispetto al prodotto di matrici (elemento per elemento).

Il sottoinsieme di M

n

(Z) contenente le matrici con determinante =1 è esempio di gruppo (non commutativo) rispetto al prodotto righe per colonne.

I sottoinsiemi di M

n

(Q), M

n

(R) contenenti le matrici con determinante 0 sono esempi di gruppi (non commutativi) rispetto al prodotto righe per colonne.

Il sottoinsieme di F(X) contenente le funzioni biunivoche f : X → X è esempio di gruppo (non commutativo se la cardinalità di X è >2) rispetto alla composizione di funzioni.

Consideriamo un insieme (A, ) dotato di operazione , e in cui sia anche definita una relazione di equivalenza R: se l’elemento xA è associato nella relazione R all’elemento yA scriveremo xRy.

Ricordiamo che, fissato xA, si può costruire la classe di equivalenza rappresentata da x:

[x] = { yA / xRy }

e che le distinte classi di equivalenza formano una partizione di A.

Si ha inoltre [x]=[x

1

]  xRx

1

.

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

Diremo che l’operazione  e la relazione R sono compatibili se, comunque dati x,y,z,tA, se xRz e se yRt allora si ha (xy)R(zt).

In tale caso nell’insieme A/R delle classi di equivalenza si può definire un’operazione fra classi (che indicheremo con lo stesso simbolo ) ponendo:

[x][y] = [xy] per ogni coppia di classi [x],[y]A/R.

La compatibilità dell’operazione e della relazione R ci garantisce l’unicità del risultato, indipendentemente dalla scelta dei rappresentanti x,y delle classi su cui operiamo: infatti se [x]=[z], e se [y]=[t], allora si ha xRz e yRt, da cui (xy)R(zt), [xy]=[x][y]=[zt]=[z][t].

Riassumendo: se un insieme (A, ) é dotato di operazione , e se in A é anche definita una relazione di equivalenza R compatibile con l’operazione , allora l’insieme A/R delle classi di equivalenza è anch’esso dotato di operazione  “indotta” da quella di A e definita come sopra.

Notiamo che in tale caso molte proprietà di (A, ) si trasmettono all’insieme (A/R, ), come si verifica facilmente: se in (A, ) vale la proprietà associativa o la commutativa, lo stesso vale in (A/R, ); se in (A, ) esiste l’elemento neutro eA, anche in (A/R, ) esiste l’elemento neutro, coincidente con [e]; se un elemento xA è simmetrizzabile con simmetrico x’A, anche [x] è simmetrizzabile in A/R con simmetrico coincidente con [x’].

In particolare possiamo applicare le ultime considerazioni al caso della congruenza aritmetica.

Ricordiamo che, fissato un intero m>1 (modulo), si definisce nell’insieme Z degli interi relativi una relazione di equivalenza, detta congruenza modulo m, ponendo:

per ogni x,yZ xRy se e solo se (x-y) è multiplo di m (cioè se esiste kZ tale che x-y=mk).

Si scrive xy (mod m) invece di xRy (e si legge x congruo y modulo m).

E’ facile verificare che sia l’operazione di somma aritmetica che quella di prodotto aritmetico esistenti in Z sono compatibili con tale relazione di congruenza modulo m. Infatti se xz (mod m), e se yt (mod m) allora x-z=mk, y-t=mh, da cui (x+y)-(z+t)=m(h+k), ossia (x+y)(z+t) (mod m);

inoltre xy-zt=x(y-t)+(x-z)t=m(xh+tk), ossia (xy)(zt) (mod m).

Per quanto osservato in precedenza, l’insieme Z

m

Matematica Discreta II Lezione del giorno 11 ottobre 2007

Matematica Discreta II

Lezione del giorno 11 ottobre 2007

Le principali proprietà degli elementi simmetrizzabile di un monoide (A, ) sono:

1) L’elemento neutro eA è simmetrizzabile, ed è uguale al suo simmetrico (segue da ee=e) 2) Se l’elemento xA è simmetrizzabile con simmetrico x’A, allora anche x’ è simmetrizzabile con simmetrico x (segue da xx’=x’x=e)

3) Se gli elementi x,yA sono simmetrizzabili con simmetrici rispettivamente x’,y’A, anche xy è simmetrizzabile con simmetrico y’x’. Infatti, applicando la proprietà associativa, si ha:

(xy)(y’x’)=[(xy) y’] x’=[x(yy’)] x’=[xe] x’=xx’=e (e analogamente (y’x’)(xy)=e).

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

In tale notazione il risultato dell’operazione sugli operandi x,y sarà indicato con xy (o semplicemente con xy); l’eventuale elemento neutro di A (detto unità di A) sarà indicato con 1

; un elemento simmetrizzabile xA sarà detto invertibile e il suo simmetrico (detto inverso di x) sarà indicato con x

. Le proprietà 2), 3) precedenti si tradurranno dunque nel modo seguente:

(x

)

=x, (xy)

=y

x

.

Analogamente potremo usare la notazione additiva: x+y indicherà il risultato, il neutro (detto zero di A) sarà indicato con 0

, il simmetrico di un elemento simmetrizzabile x (detto opposto di x) sarà indicato con –x. In tale caso le proprietà 2), 3) precedenti si tradurranno nel modo seguente:

-(-x)=x, -(x+y)=(-y)+(-x) .

Un insieme (A, ) è detto gruppo se è un monoide e se tutti i suoi elementi sono simmetrizzabili.

Un gruppo è commutativo (o abeliano) se la sua operazione soddisfa la proprietà commutativa.

Esempi:

I monoidi Z, Q, R rispetto alla somma sono esempi di gruppi (commutativi).

I monoidi di matrici M

(Z), M

(Q), M

(R) rispetto alla somma di matrici sono esempi di gruppi (commutativi).

Se (A, ) è un monoide, indicheremo con A* il sottoinsieme degli elementi simmetrizzabili di A. La proprietà 3) precedente implica che A* è chiuso rispetto all’operazione di A, quindi si può considerare l’insieme (A*,) dotato della stessa operazione di A.

Esempi:

Considerando l’insieme degli elementi simmetrizzabili dei monoidi esaminati in precedenza, otteniamo nuovi esempi di gruppi.

L’insieme {1, -1} è un gruppo (commutativo) rispetto al prodotto aritmetico.

Gli insiemi Q-{0}, R-{0} (rispettivamente dei razionali non nulli e dei reali non nulli) sono esempi di gruppi (commutativi) rispetto al prodotto aritmetico.

Il sottoinsieme di M

(Z) contenente le matrici con elementi tutti =1 è esempio di gruppo

(commutativo) rispetto al prodotto di matrici (elemento per elemento).

I sottoinsiemi di M

(Q), M

(R) contenenti le matrici con elementi tutti 0 sono esempi di gruppi (commutativi) rispetto al prodotto di matrici (elemento per elemento).

Il sottoinsieme di M

(Z) contenente le matrici con determinante =1 è esempio di gruppo (non commutativo) rispetto al prodotto righe per colonne.

I sottoinsiemi di M

(Q), M

(R) contenenti le matrici con determinante 0 sono esempi di gruppi (non commutativi) rispetto al prodotto righe per colonne.

Il sottoinsieme di F(X) contenente le funzioni biunivoche f : X → X è esempio di gruppo (non commutativo se la cardinalità di X è >2) rispetto alla composizione di funzioni.

Consideriamo un insieme (A, ) dotato di operazione , e in cui sia anche definita una relazione di equivalenza R: se l’elemento xA è associato nella relazione R all’elemento yA scriveremo xRy.

Ricordiamo che, fissato xA, si può costruire la classe di equivalenza rappresentata da x:

[x] = { yA / xRy }

e che le distinte classi di equivalenza formano una partizione di A.

Si ha inoltre [x]=[x

]  xRx

.

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

Diremo che l’operazione  e la relazione R sono compatibili se, comunque dati x,y,z,tA, se xRz e se yRt allora si ha (xy)R(zt).

In tale caso nell’insieme A/R delle classi di equivalenza si può definire un’operazione fra classi (che indicheremo con lo stesso simbolo ) ponendo:

[x][y] = [xy] per ogni coppia di classi [x],[y]A/R.

In particolare possiamo applicare le ultime considerazioni al caso della congruenza aritmetica.

Ricordiamo che, fissato un intero m>1 (modulo), si definisce nell’insieme Z degli interi relativi una relazione di equivalenza, detta congruenza modulo m, ponendo:

per ogni x,yZ xRy se e solo se (x-y) è multiplo di m (cioè se esiste kZ tale che x-y=mk).

Si scrive xy (mod m) invece di xRy (e si legge x congruo y modulo m).

E’ facile verificare che sia l’operazione di somma aritmetica che quella di prodotto aritmetico esistenti in Z sono compatibili con tale relazione di congruenza modulo m. Infatti se xz (mod m), e se yt (mod m) allora x-z=mk, y-t=mh, da cui (x+y)-(z+t)=m(h+k), ossia (x+y)(z+t) (mod m);

inoltre xy-zt=x(y-t)+(x-z)t=m(xh+tk), ossia (xy)(zt) (mod m).

Per quanto osservato in precedenza, l’insieme Z

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]

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

Z

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

e quindi sono in numero di m.