Matematica Discreta Lezione del giorno 17 aprile 2009 Leggi di cancellazione in un gruppo

Matematica Discreta

Lezione del giorno 17 aprile 2009 Leggi di cancellazione in un gruppo Sia A un gruppo rispetto all’operazione *.

Se sono dati 3 elementi a,b,cA tali che a*c=b*c allora si ha a=b (è la cosiddetta legge di cancellazione a destra, perché il secondo operando c viene “cancellato” in ambo i membri dell’eguaglianza). Dimostriamo tale legge di cancellazione: se eA è l’elemento neutro di A, e se c’A è il simmetrico di c in A, si ha (utilizzando la proprietà associativa):

a=a*e=a*(c*c’)=(a*c)*c’=(b*c)*c’=b*(c*c’)=b*e=b dunque a=b (tesi).

Con ragionamento analogo si ottiene la cosiddetta legge di cancellazione a sinistra valida in ogni gruppo A: se sono dati 3 elementi a,b,cA tali che c*a=c*b allora si ha a=b.

Notare che se A non è gruppo, tali leggi possono anche non valere (come vedremo in un prossimo esempio).

Se A é un gruppo finito di cardinalità n, la tavola dell’operazione di A forma un quadrato latino di ordine n: infatti sappiamo che se gli n elementi distinti di A ordinati come segue

A = {a

1

,a

2

,...,a

n

}

allora la tavola dell’operazione di A é una matrice nxn in cui nella generica casella all’incrocio fra riga i e colonna j vi é il risultato a

i

*a

j

. Se per assurdo non si ottenesse in tal modo un quadrato latino, vi sarebbero 2 elementi uguali nella stessa riga o nella stessa colonna. Ma se per esempio vi fossero 2 elementi uguali nella stessa riga i (nelle colonne j,k) allora si avrebbe la seguente eguaglianza:

a

i

*a

j =

a

i

*a

k

e per la legge di cancellazione a sinistra si concluderebbe che a

j

=a

k

(contraddizione perché gli elementi a

1

,a

2

,...,a

n

sono distinti. Con ragionamento analogo, se vi fossero invece 2 elementi uguali nella stessa colonna, si otterrebbe una contraddizione (utilizzando stavolta la legge di cancellazione a destra).

Dunque un modo per ottenere un quadrato latino di ordine n é per esempio quello di costruire la tavola dell’operazione di un gruppo di cardinalità n.

Il monoide delle funzioni da un insieme in sé stesso

Sia T un insieme non vuoto qualunque, e consideriamo l’insieme F(T) i cui elementi sono tutte le possibili funzioni f: T  T. Per esempio, se T è finito di cardinalità n, l’insieme F(T) ha cardinalità n

ⁿ

, come è ben noto dal calcolo combinatorio. Se T è infinito ovviamente anche F(T) è infinito.

Sappiamo che nell’insieme F(T) é definita l’operazione di composizione di funzioni: prese due funzioni f,g : T  T, la loro composizione è la funzione fg : T  T definita applicando di seguito prima la funzione g e poi la funzione f (formalmente per ogni elemento xT si ha (fg)(x)=f(g(x))).

Nell’insieme F(T) l’operazione di composizione è associativa: se infatti sono date 3 funzioni f,g,h : T  T

calcolando il corrispondente di un elemento generico xT mediante le funzioni f(gh), (fg)h si ottiene lo stesso risultato:

[f(gh)](x)=f((gh)(x))=f(g(h(x)))

[(fg)h](x)=(fg)(h(x))=f(g(h(x)))

dunque é vero che f(gh)=(fg)h.

Inoltre esiste in F(T) l’elemento neutro rispetto all’operazione di composizione ed esso coincide con la funzione identica i

T

: T  T definita da i

T

(x)=x per ogni xT. Si verifica infatti facilmente che per ogni fF(T) si ha:

fi

T

=f i

T

f=f

Dunque l’insieme F(T) di tutte le funzioni da T in T rispetto all’operazione di composizione è un monoide.

Esempio: Se T={a,b} ha cardinalità 2, allora F(T) contiene 2

²

=4 funzioni f

1

,f

2

,f

3

,f

4

: T  T definite rispettivamente da:

f

1

(a)=a, f

1

(b)=b f

2

(a)=a, f

2

(b)=a f

3

(a)=b, f

3

(b)=a f

4

(a)=b, f

4

(b)=b

Calcoliamo per esempio la composizione f

2

f

3

.

Si ha: (f

2

f

3

)(a)=f

2

(f

3

(a))=f

2

(b)=a, (f

2

f

3

)(b)=f

2

(f

3

(b))=f

2

(a)=a Dunque:

(f

2

f

3

)(a)=a, (f

2

f

3

)(b)=a

Si osserva dunque che la composizione f

2

f

3

coincide con la funzione f

2

: f

2

f

3

=f

2

.

Calcoliamo invece la composizione f

3

f

2

.

Si ha: (f

3

f

2

)(a)=f

3

(f

2

(a))=f

3

(a)=b, (f

3

f

2

)(b)=f

3

(f

2

(b))=f

3

(a)=b Dunque:

(f

3

f

2

)(a)=b, (f

3

f

2

)(b)=b

Si osserva dunque che la composizione f

3

f

2

coincide con la funzione f

4

: f

3

f

2

=f

4

.

(notare che l’operazione di composizione non è in questo caso commutativa)

Se calcoliamo tutti i risultati possibili per le diverse coppie di elementi di F(T)={f

1

,f

2

,f

3

.f

4

} otteniamo in questo caso la seguente tavola dell’operazione di composizione in F(T) :

f

1

f

2

f

3

f

4

f

1

f

2

f

3

f

4

In questo caso F(T) non è un gruppo: gli elementi f

2

,f

4

non hanno simmetrico, come si vede esaminando la tavola.

Notiamo anche che non vale la legge di cancellazione a sinistra: per esempio f

2

f

3

=f

2

f

4

ma non è vero che f

3

=f

4

. Non vale neanche quella a destra: per esempio f

1

f

4

=f

4

f

4

ma non è vero che f

1

=f

4

. Non si ottiene dunque un quadrato latino, in questo caso,

Ricordiamo che, dato un monoide A rispetto all’operazione *, il sottoinsieme A* di tutti gli elementi simmetrizzabile di A è un gruppo rispetto alla stessa operazione di A.

Studiamo allora il gruppo degli elementi simmetrizzabili del monoide F(T).

Se una funzione fF(T) é biunivoca, sappiamo che esiste la funzione inversa f

^-1

: T  T (dunque anche f

^-1

F(T)); si ha inoltre ff

^-1

=i

T

, e che f

^-1

f=i

T

.

Dunque: se una funzione fF(T) é biunivoca, essa é simmetrizzabile nel monoide F(T) ed il suo simmetrico é la funzione inversa f

^-1

.

f

1

f

2

f

3

f

4

f

2

f

2

f

2

f

2

f

3

f

4

f

1

f

2

f

4

f

4

f

4

f

4

Ma viceversa supponiamo che una funzione fF(T) sia simmetrizzabile e che f ‘F(T) sia il suo simmetrico, cioè f ‘ : T  T é una funzione tale che ff ‘=i

T

, e che f ‘f=i

T

. Da ciò segue allora che f é iniettiva (perché se f(a)=f(b) allora applicando f ‘ ad ambo i membri si ha f ‘(f(a))=f ‘(f(b)), da cui (f ‘f)(a)= (f ‘f)(b), cioé i

T

(a)=i

T

(b), ed infine a=b) ed inoltre f é surgettiva (comunque dato b T, posto a=f ‘(b)T, si ha f(a)= f(f ‘(b))=(ff ‘)(b)=i

T

(b)=b, dunque per ogni bT esiste qualche aT tale che f(a)=b).

Dunque: se una funzione fF(T) é simmetrizzabile nel monoide F(T), essa é biunivoca.

Abbiamo in pratica dimostrato che il gruppo F(T)* degli elementi simmetrizzabili del monoide F(T) é formato da tutte e sole le funzioni biunivoche da T in T.

Se per esempio T è un insieme finito di cardinalità n, allora il gruppo F(T)* contiene n! funzioni biunivoche.

Esempio: Se T={a,b,c} ha cardinalità 3, allora F(T) contiene 3

³

=27 funzioni da T in T (é troppo lungo costruirle tutte, e la tavola dell’operazione sarebbe una matrice 27x27). Il gruppo F(T)* degli elementi simmetrizzabili ha cardinalità 3!=6 ed é formato dalle 6 funzioni biunivoche da T in T che sono le seguenti f

1

,f

2

,f

3

,f

4

,f

5,

f

6

definite da:

f

1

(a)=a, f

1

(b)=b, f

1

(c)=c (quindi f

1

=i

T

applicazione identica di T) f

2

(a)=a, f

2

(b)=c, f

2

(c)=b

f

3

(a)=c, f

3

(b)=b, f

3

(c)=a f

4

(a)=b, f

4

(b)=a, f

4

(c)=c f

5

(a)=b, f

5

(b)=c, f

5

(c)=a f

6

(a)=c, f

6

(b)=a, f

6

(c)=b

La tavola dell’operazione del gruppo F(T)* é in questo caso (rispetto all’ordine f

1

,f

2

,f

3

,f

4

,f

5,

f

6

) la seguente matrice 6x6:

f

1

f

2

f

3

f

4

f

5

f

6

f

1

f

2

f

3

f

4

f

5

f

6

Si può notare che, come previsto, la tavola é un quadrato latino di ordine 6, essendo F(T)* un gruppo.

Inoltre la tavola non é simmetrica rispetto alla diagonale principale, quindi l’operazione del gruppo F(T)* in questo caso non é commutativa (per esempio f

3

f

2

f

2

f

3

).

Quest’ultima osservazione non é un caso: se T é un insieme con almeno 3 elementi, l’operazione di composizione nel gruppo F(T)* non é mai commutativa. Infatti se T={a,b,c,...} basta definire le 2 funzioni f,g : T  T ponendo

f(a)=a, f(b)=c, f(c)=b (sugli altri elementi f agisce come l’applicazione identica) g(a)=c, g(b)=b, g(c)=a (sugli altri elementi g agisce come l’applicazione identica)

e si osserva facilmente che f,g sono biunivoche, dunque f,gF(T)*, ma le 2 composizioni fg, gf sono diverse (perché per esempio (fg)(a)=f(g(a))=f(c)=b, mentre (gf)(a)=g(f(a))=g(a)=c).

Notiamo invece che nel caso di un insieme T={a,b} di cardinalità 2, il gruppo F(T)* contiene solo 2 funzioni biunivoche (oltre la funzione identica i

T

, vi è la funzione f definita da f(a)=b, f(b)=a) e in questo caso l’operazione è commutativa con tavola:

i

T

f i

T

f

f

1

f

2

f

3

f

4

f

5

f

6

f

2

f

1

f

5

f

6

f

3

f

4

f

3

f

6

f

1

f

5

f

4

f

2

f

4

f

5

f

6

f

1

f

2

f

3

f

5

f

4

f

2

f

3

f

6

f

1

f

6

f

3

f

4

f

2

f

1

f

5

i

T

f

f i

T