Matematica Discreta
Lezione dei giorni 21,25 e 28 marzo 2011 Proprietà commutativa.
Un’operazione definita nell’insieme A è detta commutativa, se, comunque dati gli operandi x,y, si ha xy= yx (ossia se il risultato non cambia quando si cambia l’ordine degli operandi).
Esempio.
Nell’insieme N dei numeri naturali le operazioni di somma e prodotto sono commutative (perché è ben noto che, comunque dati i numeri naturali x,y si ha x+y=x+y , x∙y=y∙x).
Invece l’operazione di elevamento a potenza non è commutativa, perché per esempio:
23=2
332=3
2.
Nell’insieme A = {a, b, c} l’operazione definita in precedenza non è commutativa perché per esempio: ab=cba=a .
Nel caso di un insieme finito, la proprietà commutativa si riflette in proprietà della tavola operazionale: la proprietà commutativa equivale alla proprietà che la tavola operazionale sia simmetrica rispetto alla diagonale principale \ (sinistra alto – destra basso), nel senso che caselle simmetriche rispetto a tale diagonale hanno eguale contenuto.
Proprietà associativa.
Un’operazione definita nell’insieme A è associativa se, comunque presi gli elementi x,y,zA, si ha:
(xy)z = x(yz) Esempio.
E’ ben noto che le operazioni di somma e prodotto nell’insieme dei numeri naturali sono associative, in quanto (x+y)+z=x+(y+z), (xy)z=x(yz), comunque dati i numeri naturali x,y,z.
Invece l’operazione di elevamento a potenza xy=x
ynon è associativa perché, dati i numeri naturali x,y,z, non è sempre vero che i seguenti risultati sono uguali:
(xy)z= (x
y)z=(x
y)
z=x
yzx(yz)= x(y
z) = x (yz)
L’operazione (esaminata come esempio in precedenza) definita in modo implicito nell’insieme dei numeri naturali da:
xy = x+y+xy
è associativa, perché i seguenti 2 risultati:
(xy)z= (x+y+xy)z=(x+y+xy)+z+(x+y+xy)z=x+y+xy+z+xz+yz+xyz x(yz)= x(y+z+yz)= x+(y+z+yz)+x(y+z+yz)= x+y+z+yz+xy+xz+xyz
sono uguali (notare che in tale ragionamento si sono utilizzate proprietà della somma e del prodotto di numeri naturali, come la proprietà distributiva).
L’operazione definita in precedenza in modo esplicito nell’insieme A={a,b,c} non è associativa
perché per esempio (ab)c=cc=a è diverso da a(bc)=aa=b.
Elemento neutro.
In un insieme A in cui è definita un’operazione , si dice che l’elemento eA è un elemento neutro se per ogni xA si ha xe=ex=x.
Ovviamente se l’operazione * è commutativa, basta verificare (per ogni xA) solo una delle 2 eguaglianze:
xe=x ex=x
perché l’altra sarà automaticamente verificata.
E’ facile dimostrare 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’ (per l’unicità del risultato di una operazione).
Esempi.
1) Nell’insieme N dei numeri naturali:
- rispetto all’operazione di prodotto esiste l’elemento neutro ed è il numero 1
- rispetto all’operazione di somma non esiste l’elemento neutro (perché il numero 0 non appartiene ad N)
- rispetto all’operazione di elevamento a potenza ab=a
bnon esiste elemento neutro (il numero 1 funziona da neutro solo come secondo operando, perché x1=x
1=x, ma non come primo operando perché 1x=1
x=1 per ogni x).
2) Nell’insieme Z dei numeri interi relativi
- rispetto all’operazione di prodotto esiste l’elemento neutro ed è il numero 1 - rispetto all’operazione di somma esiste l’elemento neutro ed è il numero 0
Proprietà simili valgono per le operazioni di prodotto e somma definite nell’insieme Q dei numeri razionali relativi e nell’insieme R dei numeri reali relativi (gli elementi neutri sono rispettivamente il numero 1 e il numero 0, considerati come numeri razionali e reali).
3) Definiamo nell’insieme Z dei numeri interi relativi la seguente operazione:
x*y = x+y+5
Esiste l’elemento neutro in Z rispetto a tale operazione ? Cerchiamo (se esiste) un numero intero relativo eZ tale che:
per ogni xZ si ha xe=x.
Si ottiene:
xe=x+e+5=x
ricavando il valore e= -5, dunque il numero intero relativo e= -5 è l’elemento neutro rispetto a tale operazione.
Se nell’insieme finito di cardinalità n:
A = {a
1, a
2,……, a
n}
é definita un’operazione in modo esplicito mediante una tavola operazionale (rispetto all’ordinamento a
1, a
2,……, a
n), un elemento è elemento neutro se la riga e la colonna corrispondenti a quell’elemento contengono ordinatamente gli elementi a
1, a
2,……, a
n.
Per esempio, se A ={a,b,c} e se la tavola operazionale dell’operazione (rispetto all’ordinamento
a,b,c) è:
a b c a
b c
allora esiste l’elemento neutro ed esso coincide con l’elemento c (perché la terza riga e la terza colonna contengono ordinatamente gli elementi a,b,c).
Simmetrico.
Sia dato un insieme A in cui è definita l’operazione *; supponiamo inoltre che esista l’ elemento neutro eA.
Fissato un elemento xA, si dice che l’elemento x’A è un simmetrico di x se:
xx’=x’x=e.
Ovviamente se l’operazione * è commutativa, basta verificare (per ogni xA) solo una delle 2 eguaglianze:
xx’=e x’x=e
perché l’altra sarà automaticamente verificata.
Un elemento x può non avere simmetrico, o anche averne più di uno.
Per esempio, se A ={a,b,c,d} e se la tavola operazionale (rispetto all’ordinamento a,b,c,d) è:
a b c d a
b c d
si può notare che l’elemento a è neutro (perché la prima riga e la prima colonna contengono ordinatamente gli elementi a,b,c,d); inoltre l’elemento b ha 2 simmetrici c,d (in quanto bc=cb=a, ma anche bd=db=a).
L’unicità del simmetrico di un elemento (se esso esiste) è però garantita nel caso in cui l’operazione sia associativa:
Teorema. Sia dato un insieme A in cui è definita l’operazione *, e supponiamo che esista l’elemento neutro eA. Supponiamo inoltre che l’operazione sia associativa.
Allora il simmetrico di un elemento xA (se esiste) è unico.
Dimostrazione Se x’, x’’ sono entrambi simmetrici di x, si ha, sfruttando la proprietà associativa:
x’ = x’e = x’(xx’’) = (x’x)x’’= ex’’= x’’
e si conclude che x’= x’’ .
Un insieme A in cui è definita un’operazione * è detto un semigruppo se l’operazione è associativa, mentre è detto monoide se l’operazione è associativa ed esiste l’elemento neutro (si parla di semigruppo commutativo o di monoide commutativo se l’operazione è commutativa).
Un elemento x di un monoide A è detto simmetrizzabile se esiste in A il simmetrico x’ di x (che per quanto dimostrato sopra è unico).
b c a
a b b
a b c
a b c d
b b a a
c a c d
d a b c
Esempi:
1) Gli insiemi Z, Q, R (rispettivamente dei numeri interi relativi, dei numeri razionali relativi e dei numeri reali relativi) sono monoidi (commutativi) rispetto all’operazione di somma: in tutti e 3 i casi l’elemento neutro è il numero 0, e il concetto di simmetrico coincide con quello di opposto, quindi tutti gli elementi sono simmetrizzabili.
Gli stessi 3 insiemi sono monoidi (commutativi) anche rispetto all’operazione di prodotto: in tutti e 3 i casi l’elemento neutro è il numero 1, e il concetto di simmetrico coincide con quello di inverso.
Nel monoide Z gli unici elementi simmetrizzabili rispetto al prodotto sono i numeri 1, -1 (gli unici che hanno inverso in Z). Invece nei monoidi Q, R tutti gli elementi sono simmetrizzabili tranne il numero 0 (di tutti i razionali o reali non nulli esiste l’inverso razionale o reale).
2) Definiamo nell’insieme Z dei numeri interi relativi la seguente operazione (già esaminata in un esempio precedente):
x*y = x+y+5
Abbiamo già dimostrato che esiste un elemento neutro e= -5.
Inoltre l’operazione é associativa in quanto, comunque dati x,y,z in Z i seguenti risultati sono uguali:
x*(y*z)=x*(y+z+5)=x+(y+z+5)+5=x+y+z+10 (x*y)*z=(x+y+5)*z=(x+y+5)+z+5=x+y+z+10
L’operazione è anche commutativa in quanto comunque dati x,y in Z i seguenti risultati sono uguali:
x*y=x+y+5 y*x=y+x+5
Infine verifichiamo se per ogni xZ esiste il simmetrico x’Z tale che si abbia:
x*x’=e=-5 (essendo l’operazione commutativa è superfluo imporre che x’*x=e).
Ciò equivale a:
x+x’+5= -5 e si trova il valore x’= -10-a.
(per esempio il simmetrico di x=7 è il numero x’= -10-7= -17; il simmetrico di x= -2 è il numero x’= -10-(-2)= -8 etc…).
Dunque Z rispetto a tale operazione * è un monoide commutativo in cui ogni elemento è simmetrizzabile.
Un insieme A in cui è definita un’operazione * è detto gruppo se è un monoide e se tutti i suoi elementi sono simmetrizzabili (si parla di gruppo commutativo se l’operazione è commutativa).
Esempi:
I monoidi Z, Q, R rispetto all’operazione di somma sono esempi di gruppi (commutativi).
L’insieme Z rispetto all’operazione x*y=x+y+5 è un gruppo (commutativo), come visto sopra.
Se l’insieme A è un monoide rispetto all’operazione *, indicheremo con A* il sottoinsieme di A formato da tutti gli elementi simmetrizzabili di A (ovviamente se A è gruppo si ha A=A*).
Le principali proprietà degli elementi simmetrizzabili del monoide A sono:
1) L’elemento neutro eA è simmetrizzabile, ed è uguale al suo simmetrico (perché ee=e)
2) Se l’elemento xA è simmetrizzabile con simmetrico x’A, allora anche x’ è simmetrizzabile con simmetrico x (perché xx’=x’x=e). In pratica il simmetrico del simmetrico di x è x stesso:
(x’)’ = x
3) Se gli elementi x,yA sono simmetrizzabili con simmetrici rispettivamente x’,y’A, anche xy è simmetrizzabile con simmetrico y’x’. Infatti, applicando la proprietà associativa, si ha:
(xy)(y’x’)=[(xy) y’] x’=[x(yy’)] x’=[xe] x’=xx’=e
(e analogamente (y’x’)(xy)=e).
In pratica il simmetrico di xy si ottiene operando con l’operazione * sul simmetrico di y (come primo operando) e sul simmetrico di x (come secondo operando):
(xy)’ = (y’x’)
Teorema. Dato un monoide A rispetto all’operazione *, il sottoinsieme A* formato da tutti gli elementi simmetrizzabile di A è un gruppo, rispetto alla stessa operazione *.
Dimostrazione.
Sfrutteremo le proprietà 1),2)3) di A* dimostrate sopra.
Per la proprietà 3) l’operazione * definita in A diventa anche un’operazione nel sottoinsieme A*
(perché applicata a 2 operandi in A* fornisce un risultato che appartiene ancora ad A*). Rispetto a tale operazione *, per la proprietà 1), esiste in A* l’elemento neutro (è lo stesso elemento neutro di A); inoltre vale in A* la proprietà associativa (perché vale in A, dunque a maggior ragione in un sottoinsieme A* di A); infine ogni elemento xA* ha (per come è definito A*) il simmetrico x’A, ma (per la proprietà 2)) anche x’ è simmetrizzabile, dunque x’A*, e si deduce che ogni elemento di A* è simmetrizzabile in A*.
In sostanza il Teorema precedente afferma che, se abbiamo un monoide A rispetto all’operazione * che non sia un gruppo, possiamo ottenere un gruppo A* rispetto alla stessa operazione considerando solo gli elementi simmetrizzabili di A (quindi eliminando tutti gli elementi che non hanno il simmetrico).
Abbiamo dunque dimostrato che, dato un monoide A rispetto all’operazione *, considerando il sottoinsieme A* di A (contenente tutti gli elementi simmetrizzabili di A) si ottiene un gruppo, rispetto alla stessa operazione * (ovviamente tale gruppo A* è commutativo se il monoide A è commutativo).
Esempi:
Gli insiemi Z, Q, R rispetto all’operazione di prodotto sono esempi di monoidi (commutativi): in tali monoidi il concetto di simmetrico coincide con quello di inverso.
Nel caso di Z gli elementi simmetrizzabili (cioè gli interi relativi che hanno inverso intero relativo) sono solo 1,-1, dunque il gruppo degli elementi simmetrizzabili di Z rispetto al prodotto è:
Z* = {1,-1}.
Invece nei casi di Q, R gli elementi simmetrizzabili sono tutti i numeri (razionali o reali) non nulli (tutti tranne 0 hanno inverso), dunque i gruppi degli elementi simmetrizzabili rispetto al prodotto sono rispettivamente :
Q* = Q-{0} R* = R-{0}
I gruppi ottenuti in questi esempi sono tutti commutativi perché provengono da monoidi commutativi.
Vedremo ora esempi di monoidi e gruppi non commutativi,
Il monoide delle funzioni rispetto all’operazione di composizione.
Fissiamo un insieme non vuoto A e consideriamo l’insieme F (A) di tutte le funzioni f : A A.
In tale insieme F (A) si può definire l’operazione di composizione di funzioni.
Date le funzioni f,g: A A (quindi f,g F (A) il risultato f*g è la funzione composta fg: A A , ottenuta applicando di seguito g ed f:
per ogni xA (fg)(x) = f(g(x))
E’ facile verificare che l’operazione di composizione è associativa: date le funzioni
f,g,h : A A si ha f(gh) = (fg)h.
Infatti preso un elemento qualunque xA si hanno i seguenti risultati uguali:
[f(gh)](x)=f((gh)(x))=f(g(h(x)) [(fg)h)](x)=(fg)(h(x))=f(g(h(x))
Inoltre esiste in F (A) l’elemento neutro rispetto all’operazione di composizione ed è la funzione identica i
A: A A (definita da i
X(A)=A per ogni xA).
Sappiamo infatti dall’insiemistica che per ogni funzione f : A A si ha fi
X= f i
Xf = f
In conclusione: dato un qualunque insieme non vuoto A, l’insieme F (A) di tutte le funzioni da A in A rispetto all’operazione di composizione è un monoide.
Se A è finito di cardinalità n, il monoide F (A) sarà finito di cardinalità n
n. Se A è infinito, ovviamente il monoide F (A) sarà infinito.
Tale monoide F (A) è commutativo ?.
Se A contiene un solo elemento, il monoide F (A) contiene solo la funzione identica i
Aed è ovviamente commutativo.
Se A ha cardinalità >1 (quindi anche se A è infinito) il monoide F (A) non è commutativo.
Se infatti A contiene almeno due elementi a,b:
A={a,b,…..}
possiamo costruire 2 elementi f,g nel monoide F (A) tali che fg gf nel modo seguente.
Definiamo le seguenti funzioni :
f : A A definita da f(x)=a per tutti gli elementi xA
g : A A definita da g(a)=b, g(b)=a (e definita in modo arbitrario per tutti gli xa,b) Notiamo appunto che fg gf (perché (fg)(a)=f(g(a))=f(b)=a, mentre (gf)(a)=g(f(a))=g(a)=b).
Se A è un insieme finito di cardinalità n, l’operazione di composizione nel monoide F (A) (di cardinalità n
n) si può descrivere in modo esplicito mediante la tavola operazionale, che sarà una matrice con n
nrighe ed n
ncolonne.
Esempi:
1) Nel caso A abbia cardinalità 2:
A = {a,b}
il monoide F (A) contiene 2
2=4 funzioni, e precisamente le seguenti:
f
1: A A definita da f
1(a)=a, f
1(b)=b (quindi f
1è la funzione identica i
A) f
2: A A definita da f
2(a)=b, f
2(b)=a
f
3: A A definita da f
3(a)=a, f
3(b)=a f
4: A A definita da f
4(a)=b, f
4(b)=b
Se per esempio proviamo a calcolare la composizione f
2f
3otteniamo:
(f
2f
3)(a) = f
2(f
3(a)) = f
2(a) = b (f
2f
3)(b) = f
2(f
3(b)) = f
3(a) = b Dunque f
2f
3= f
4.
Così procedendo si possono ottenere tutti i valori da inserire nella tavola operazionale, che è la seguente matrice 4x4 (rispetto all’ordine f
1,.f
2,f
3,f
4):
4 4 4 4
3 3 3 3
3 4 1 2
4 3 2 1
f f f f
f f f f
f f f f
f
f
f
f
Notiamo che (come previsto) il monoide F (A) non è commutativo (A contiene almeno 2 elementi) e la tavola operazionale non è simmetrica rispetto alla diagonale principale.
2) Nel caso A abbia cardinalità 3:
A = {a,b,c}
il monoide F (A) contiene 3
3=27 funzioni (che si possono elencare con un po’ di pazienza), e la tavola operazionale è una matrice 27x27 (anche questa non simmetrica rispetto alla diagonale principale).
Poniamoci il seguente problema: dato l’insieme A e il monoide F (A), quali sono gli elementi simmetrizzabili di F (A) (e quindi quali elementi contiene il gruppo F (A)*) ?
Esaminando la tavola operazionale nel caso particolare in cui A={a,b} abbia cardinalità 2, si vede che gli unici elementi che hanno simmetrico sono f
1=i
Aed f
2: sono le uniche funzioni da A in A che siano biunivoche.
Ciò non è casuale:
Teorema. Dato un insieme non vuoto A, gli elementi simmetrizzabili del monoide F (A) rispetto all’operazione di composizione sono tutte e sole le funzioni biunivoche f: A A.
Dimostrazione.
Se f: A A è biunivoca, sappiamo dall’insiemistica che esiste la funzione inversa f
-1: A A, e che inoltre ff
-1= i
Af
-1f = i
Adunque f ha simmetrico f
-1(essendo i
Al’elemento neutro).
Viceversa se la funzione f: A A è simmetrizzabile, esiste il suo simmetrico nel monoide F (A), cioè una funzione f ’: A A tale che ff ‘ = i
Af ‘f = i
Ae dimostriamo che f è allora biunivoca.
Iniettività di f: se per assurdo esistessero a,bA, ab tali che f(a)=f(b), applicando la funzione f ‘ ad ambo i membri si avrebbe:
f ‘(f(a)) = f ‘(f(b) (f ‘f)(a) = (f ‘f)(b) i
A(a) = i
A(b)
a = b (contraddizione).
Surgettività di f: dato un qualunque elemento bA si deve trovare un elemento aA tale che f(a)=b.
Ma osservando che f(f ‘(b))= (ff ‘)(b)= i
A(b)=b si conclude che l’elemento cercato è a=f ‘(b).
Dunque, comunque dato un insieme non vuoto A, il gruppo F (A)* degli elementi simmetrizzabili del monoide F (A) (rispetto all’operazione di composizione) coincide con l’insieme delle funzioni biunivoche da A in A.
Se A è finito di cardinalità n, tale gruppo F (A)* è finito di cardinalità n!.
Esempi:
1) Nel caso A abbia cardinalità 2:
A = {a,b}
con le stesse notazioni dell’esempio precedente il gruppo F (A)* contiene 2!=2 funzioni biunivoche:
f
1(funzione identica) ed f
2definita da f
2(a)=b, f
2(b)=a
In questo caso la tavola operazionale del gruppo F (A)* è la seguente matrice 2x2:
1 2
2 1
f f
f f
Notiamo che tale tavola operazionale è simmetrica rispetto alla diagonale principale quindi (nel caso in cui A ha cardinalità 2) il gruppo F (A)* è commutativo nonostante che, come visto in precedenza, il monoide F (A) (che lo contiene) non sia commutativo.
2) Nel caso A abbia cardinalità 3:
A = {a,b,c}
il gruppo F (A)* contiene 3!=2 funzioni biunivoche, ed esattamente:
f
1(funzione identica) f
2definita da f
2(a)=b, f
2(b)=c, f
2(c)=a f
3definita da f
3(a)=c, f
3(b)=a, f
3(c)=b f
4definita da f
4(a)=a, f
4(b)=c, f
4(c)=b
f
5definita da f
5(a)=c, f
5(b)=b, f
5(c)=a f
6definita da f
6(a)=b, f
6(b)=a, f
6(c)=c In questo caso la tavola operazionale del gruppo F (A)* è la seguente matrice 6x6:
1 3 2 5 4 6
2 1 3 4 6 5
3 2 1 6 5 4
4 6 5 2 1 3
5 4 6 1 3 2
6 5 4 3 2 1