Matematica Discreta II
Lezione del giorno 10 ottobre 2007
In un insieme A in cui è definita un’operazione , si dice che l’operazione soddisfa la proprietà commutativa, se, comunque dati x,yA, si ha xy=yx.
Esaminiamo quali delle operazioni definite negli esempi 1),….,5) soddisfano la proprietà commutativa.
Nell’esempio 1) è ben noto che le prime due operazioni (somma e prodotto) soddisfano la proprietà commutativa, mentre l’operazione di elevamento a potenza xy = xy non la soddisfa in quanto in generale xyyx .
Nell’esempio 2) è ben noto che le prime due operazioni (somma e prodotto) soddisfano la proprietà commutativa, mentre l’ operazione di sottrazione xy = x-y non la soddisfa in quanto in generale si ha x-yy-x .
Nell’esempio 3) le prime 2 operazioni fra matrici (somma e prodotto) soddisfano la proprietà commutativa, come si può facilmente verificare (sfruttando la proprietà commutativa della somma e prodotto fra numeri).
L’operazione di prodotto righe per colonne non soddisfa la proprietà commutativa. Per esempio:
0 0
0
1
0 0
1
0 =
0 0
1
0 ;
0 0
1
0
0 0
0
1 =
0 0
0 0
Nell’esempio 4) la composizione di funzioni in F(X) non soddisfa la proprietà commutativa, se X ha cardinalità >2: per esempio se a,b,c sono 3 elementi distinti di X, e se le funzioni f,g sono definite ponendo f(a)=b, f(b)=a, f(c)=c, f(x)=x per ogni xa,b,c; g(a)=a, g(b)=c, g(c)=c, g(x)=x per ogni xa,b,c, si ha (fg)(a)=f(g(a))=b, (gf)(a)=g(f(a))=c, quindi fggf .
Nell’esempio 5) l’operazione definita in A non soddisfa la proprietà commutativa: per esempio si ha abba.
In generale, se, dato un insieme finito di cardinalità n:
A = {a1, a2,……, an}
in cui sia definita un’operazione , si costruisce una tavola operazionale di n righe ed n colonne, tale che la casella all’incrocio fra riga i e colonna j contenga il risultato aiaj , l’operazione soddisfa la proprietà commutativa se e solo se per ogni i,j la casella di riga i e colonna j e la casella di riga j e colonna i contengono lo stesso elemento ossia se solo se la tavola è simmetrica rispetto alla diagonale principale (che va da alto-sinistra a basso-destra).
In un insieme A in cui è definita un’operazione , si dice che l’elemento eA è neutro se per ogni xA si ha xe=ex=x.
Notiamo che se esiste un elemento neutro, esso è unico: infatti se e, e’ sono elementi neutri, allora ee’=e’ (perché e è neutro), ee’=e (perché e’ è neutro) quindi e=e’.
Esempi:
Esaminiamo per quali delle operazioni definite negli esempi 1),….,5) esiste il neutro.
Nell’esempio 1) per l’operazione di somma non esiste il neutro, per quella di prodotto esiste il neutro e=1. Per l’operazione di elevamento a potenza non esiste il neutro (l’elemento 1 funziona solo “a destra” perché per ogni naturale x si ha x1=x1=x, ma non “a sinistra” in quanto 1x=1x=1) . Nell’esempio 2) per l’operazione di somma esiste il neutro e=0, per quella di prodotto esiste il neutro e=1. Per l’operazione di sottrazione non esiste il neutro (l’elemento 0 funziona solo “a destra” perché per ogni naturale x si ha x0=x-0=x, ma non “a sinistra” in quanto 0x=0-x=-x) .
Nell’esempio 3) per l’operazione di somma fra matrici esiste il neutro che coincide con la matrice con tutti gli elementi =0, e per l’operazione di prodotto fra matrici esiste il neutro che coincide con la matrice con tutti gli elementi =1. Per l’operazione di prodotto righe per colonne esiste il neutro che coincide con la matrice con tutti gli elementi della diagonale principale =1 e con tutti gli altri=0, cioè la matrice (cij)i,j=1,…,n dove cij=1 per i=j, e cij=0 per ij .
Nell’esempio 4) l’elemento neutro coincide con la funzione identica iX : X → X, definita da iX(x)=x per ogni x, poiché per ogni funzione fF(X) si ha fiX=iXf=f .
Nell’esempio 5) per l’operazione definita in A non esiste elemento neutro: in generale, se, dato un insieme finito di cardinalità n:
A = {a1, a2,……, an}
in cui sia definita un’operazione , si costruisce (come sopra) una tavola operazionale, un elemento ai è elemento neutro se e solo se la riga i e la colonna i contengono ordinatamente gli elementi a1, a2,
……, an (nell’esempio di A={a, b, c} non esiste nessuna riga né colonna che contenga ordinatamente gli elementi a,b,c) .
Un insieme A dotato di operazione sarà indicato con (A, ).
Si dice che (A, ) è un semigruppo se vale in A la proprietà associativa.
Si dice che (A, ) è un monoide se è un semigruppo e se esiste in A un elemento neutro.
Esempi:
L’insieme (N, +) è un semigruppo ma non un monoide.
Sono esempi di monoidi: (N, ∙); gli insiemi numerici Z, Q, R sia rispetto alla somma che al prodotto usuali; gli insiemi di matrici (ad elementi in Z, Q, R) rispetto alla somma, al prodotto e al prodotto righe per colonne; l’insieme F(X) rispetto all’operazione di composizione.
Sia dato un monoide (A, ) con elemento neutro eA.
Un elemento xA è detto simmetrizzabile se esiste un elemento x’A (detto simmetrico di x) tale che xx’=x’x=e.
Poiché ee=e, l’elemento neutro è in ogni caso simmetrizzabile, con simmetrico coincidente con sé stesso.
Notiamo che se x è simmetrizzabile, il suo simmetrico è unico: infatti se x’, x’’ sono simmetrici di x, allora si ha:
x’(xx’’)=x’e=x’ (x’x)x’’=ex’’=x’’
da cui, per la proprietà associativa, si ricava x’=x’’ . Esempi.
Nei monoidi Z, Q, R rispetto alla somma, il simmetrico di x coincide con l’opposto –x, dunque tutti gli elementi di questi monoidi sono simmetrizzabili.
Nei monoidi N, Z, Q, R rispetto al prodotto, il simmetrico di x coincide con l’inverso 1/x, dunque in N l’unico elemento simmetrizzabile è il neutro 1, in Z gli unici elementi simmetrizzabili sono 1, -1 (ognuno simmetrico di sé stesso), mentre in Q, R sono simmetrizzabili tutti e soli gli elementi diversi da 0.
Nei monoidi delle matrici Mn(Z), Mn(Q), Mn(R) rispetto all’operazione di somma, ogni matrice (cij)i,j=1,…,n è simmetrizzabile con simmetrico uguale alla matrice (-cij)i,j=1,…,n ; rispetto all’operazione di prodotto, una matrice (cij)i,j=1,…,n è simmetrizzabile se e solo se ogni elemento cij ha inverso (in Z, Q, R rispettivamente), dunque nel caso di Mn(Z) una matrice (cij)i,j=1,…,n è simmetrizzabile se e solo se ogni elemento cij=1, mentre nel caso di Mn(Q) o Mn(R) una matrice (cij)i,j=1,…,n è simmetrizzabile se e solo se ogni elemento cij0.
Nel caso del prodotto righe per colonne, se una matrice (cij)i,j=1,…,n è simmetrizzabile allora esiste una una matrice (xij)i,j=1,…,n tale che il prodotto righe per colonne (cij) (xij)coincida con la matrice elemento neutro (yij)i,j=1,…,n dove yij=1 per i=j, e yij=0 per ij ; calcolando il determinante di ambo i membri, si ha det((cij) (xij))=det(cij)det(xij)=det((yij)=1, e si conclude che il det(cij) deve avere inverso (in Z, Q, R rispettivamente). Ma viceversa se esiste l’inverso di det(cij), allora, con la teoria dei sistemi lineari, si possono trovare dei valori xij tali che (cij) (xij)=(yij), dunque la matrice (cij)i,j=1,
…,n è simmetrizzabile.
Riassumendo si ha che nel monoide delle matrici Mn(Z) rispetto all’operazione di prodotto righe per colonne le matrici simmetrizzabili sono tutte e sole quelle con determinante =1, mentre nei monoidi Mn(Q) e Mn(R) le matrici simmetrizzabili sono tutte e sole quelle con determinante 0 . Nel monoide F(X) rispetto all’operazione di composizione, se fF(X) è simmetrizzabile allora esiste un simmetrico gF(X) tale che fg=gf=iX e da ciò segue che f è biunivoca: per l’iniettività basta notare che se f(x)=f(y), allora g(f(x))=g(f(y)), da cui iX(x)=iX(y), ossia x=y; per la surgettività, scelto un qualunque yX, dall’eguaglianza f(g(y))=y si ricava l’elemento g(y)X la cui immagine mediante f è y. Ma viceversa se f è biunivoca allora esiste la funzione inversa f-1: X → X ed è facile verificare che ff-1=f-1f=iX dunque f è simmetrizzabile con simmetrico coincidente con f-1.
Riassumendo: nel monoide F(X) rispetto all’operazione di composizione, gli elementi simmetrizzabili sono tutte e sole le funzioni biunivoche.
