Matematica Discreta Lezione del giorno 21 aprile 2010

(1)

Matematica Discreta

Lezione del giorno 21 aprile 2010

Abbiamo 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 fg: A  A , ottenuta applicando di seguito g ed f:

per ogni xA (fg)(x) = f(g(x))

E’ facile verificare che l’operazione di composizione è associativa: date le funzioni f,g,h : A A

si ha f(gh) = (fg)h.

Infatti preso un elemento qualunque xA si hanno i seguenti risultati uguali:

[f(gh)](x)=f((gh)(x))=f(g(h(x)) [(fg)h)](x)=(fg)(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 xA).

Sappiamo infatti dall’insiemistica che per ogni funzione f : A  A si ha fi

X

= f i

X

f = 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

ⁿ

. Se A è infinito, ovviamente il monoide F (A) sarà infinito.

Tale monoide F (A) è commutativo ?.

(2)

Se A contiene un solo elemento, il monoide F (A) contiene solo la funzione identica i

A

ed è 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 fg  gf nel modo seguente.

Definiamo le seguenti funzioni :

f : A  A definita da f(x)=a per tutti gli elementi xA

g : A  A definita da g(a)=b, g(b)=a (e definita in modo arbitrario per tutti gli xa,b) Notiamo appunto che fg  gf (perché (fg)(a)=f(g(a))=f(b)=a, mentre (gf)(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

ⁿ

) si può descrivere in modo esplicito mediante la tavola operazionale, che sarà una matrice con n

ⁿ

righe ed n

ⁿ

colonne.

Esempi:

1) Nel caso A abbia cardinalità 2:

A = {a,b}

il monoide F (A) contiene 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

2

f

3

otteniamo:

(f

2

f

3

)(a) = f

2

(f

3

(a)) = f

2

(a) = b (f

2

f

3

)(b) = f

2

(f

3

(b)) = f

3

(a) = b Dunque f

2

f

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

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

³

=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

A

ed f

2

: sono le uniche funzioni da A in A che siano biunivoche.

Ciò non è casuale:

(3)

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 ff

^-1

= i

A

f

^-1

f = i

A

dunque f ha simmetrico f

^-1

(essendo i

A

l’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 ff ‘ = i

A

f ‘f = i

A

e dimostriamo che f è allora biunivoca.

Iniettività di f: se per assurdo esistessero a,bA, ab 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 bA si deve trovare un elemento aA tale che f(a)=b.

Ma osservando che f(f ‘(b))= (ff ‘)(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

2

definita 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

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

2

definita da f

2

(a)=b, f

2

(b)=c, f

2

(c)=a f

3

definita da f

3

(a)=c, f

3

(b)=a, f

3

(c)=b f

4

definita da f

4

(a)=a, f

4

(b)=c, f

4

(c)=b

f

5

definita da f

5

(a)=c, f

5

(b)=b, f

5

(c)=a f

6

definita 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

f f f f f f

(4)

Notiamo che tale tavola operazionale non è simmetrica rispetto alla diagonale principale quindi (nel caso in cui A ha cardinalità 3) il gruppo F (A)* non è commutativo,come anche il monoide F (A) (che lo contiene).

Questo avviene in tutti i casi in cui A abbia almeno 3 elementi:

**Se A ha cardinalità >2 (quindi anche se A è infinito) il gruppo F (A)* non è commutativo.**

Se infatti A contiene almeno tre elementi a,b,c:

A={a,b,c,…..}

possiamo costruire 2 elementi f,g nel gruppo F (A)* tali che fg  gf nel modo seguente.

Definiamo le seguenti funzioni :

f : A  A definita da f(a)=b, f(b)=c, f(x)=x per tutti gli elementi xA diversi da a,b g : A  A definita da g(a)=c, g(c)=a, f(x)=x per tutti gli elementi xA diversi da a,c Tal funzioni sono biunivoche (come si verifica facilmente) quindi sono elementi di F (A)*.

Matematica Discreta Lezione del giorno 21 aprile 2010

Matematica Discreta

Lezione del giorno 21 aprile 2010

Abbiamo 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 fg: A  A , ottenuta applicando di seguito g ed f:

per ogni xA (fg)(x) = f(g(x))

E’ facile verificare che l’operazione di composizione è associativa: date le funzioni f,g,h : A A

si ha f(gh) = (fg)h.

Infatti preso un elemento qualunque xA si hanno i seguenti risultati uguali:

[f(gh)](x)=f((gh)(x))=f(g(h(x)) [(fg)h)](x)=(fg)(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 (definita da i

(A)=A per ogni xA).

Sappiamo infatti dall’insiemistica che per ogni funzione f : A  A si ha fi

= f i

f = 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

. 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

ed è 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 fg  gf nel modo seguente.

Definiamo le seguenti funzioni :

f : A  A definita da f(x)=a per tutti gli elementi xA

g : A  A definita da g(a)=b, g(b)=a (e definita in modo arbitrario per tutti gli xa,b) Notiamo appunto che fg  gf (perché (fg)(a)=f(g(a))=f(b)=a, mentre (gf)(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

) si può descrivere in modo esplicito mediante la tavola operazionale, che sarà una matrice con n

righe ed n

colonne.

Esempi:

1) Nel caso A abbia cardinalità 2:

A = {a,b}

il monoide F (A) contiene 2

=4 funzioni, e precisamente le seguenti:

f

: A  A definita da f

(a)=a, f

(b)=b (quindi f

è la funzione identica i

) f

: A  A definita da f

(a)=b, f

(b)=a

f

: A  A definita da f

(a)=a, f

(b)=a f

: A  A definita da f

(a)=b, f

(b)=b

Se per esempio proviamo a calcolare la composizione f

f

otteniamo:

(f

f

)(a) = f

(f

(a)) = f

(a) = b (f

f

)(b) = f

(f

(b)) = f

(a) = b Dunque f

f

Abbiamo 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).

**Z* = {1,-1}.**

**Q* = Q-{0} R* = R-{0}**