Matematica Discreta Lezione del giorno 28 aprile 2010

Matematica Discreta

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

Affermiamo che:

dati comunque gli elementi a,b,cA tali che a*c=b*c allora si ha necessariamente a=b

(è la cosiddetta legge di cancellazione a destra, perché il secondo operando c viene “cancellato a destra” 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 insieme con l’ipotesi a*c=b*c ):

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:

dati comunque gli elementi a,b,cA tali che c*a=c*b allora si ha necessariamente a=b.

Notare che se A non è gruppo, tali leggi di cancellazione possono anche non valere.

Per esempio nel monoide Z

delle classi di congruenza modulo 4 rispetto al prodotto di classi si ha:

[2][3]=[6]=[2]=[2][1]

eppure non è vero che [3]=[1] (quindi non si può “cancellare” l’operando [2]

nei due membri dell’eguaglianza).

Una conseguenza delle leggi di cancellazione è la seguente: 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 sono ordinati come segue A = {a

,a

,...,a

}

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

*a

. 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 per assudo vi fossero 2 elementi uguali nella stessa riga i (in due diverse colonne j,k) allora si avrebbe la seguente eguaglianza:

a

*a

a

*a

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

=a

(contraddizione perché gli elementi a

,a

,...,a

sono distinti). Con

ragionamento analogo, se vi fossero invece per assurdo 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 qualunque gruppo di cardinalità n.

Notiamo anche che per ogni numero naturale n abbiamo a disposizione gruppi di cardinalità n: per esempio il gruppo Z

delle classi di congruenza modulo n rispetto all’operazione di somma di classi.

Potenza di un elemento di un gruppo ad esponente intero non negativo.

Siano A un gruppo rispetto all’operazione * ed aA un elemento fissato.

Vogliamo definire il concetto di potenza di base a ed esponente intero non negativo, in modo analogo a quanto si fa per le ordinarie potenze numeriche.

Per ogni numero naturale kN definiamo la potenza a

di a con esponente k nel modo seguente:

a

= a*a*….*a (dove il numero degli operandi coincide con l’esponente k)

Dunque:

a

=a, a

=a*a, a

=a*a*a etc…

(notare che la validità della proprietà associativa ci permette di non specificare come si associano gli operandi: per esempio a

=(a*a)*a = a*(a*a)).

Estendiamo poi convenzionalmente la definizione di potenza anche al caso di un esponente nullo, definendo: a

= e (elemento neutro di A).

Esempio:

Consideriamo il gruppo delle classi di congruenza modulo 20 rispetto all’operazione di somma di classi:

Z

= { [0],[1],[2],[3],….,[19] } e fissiamo a=[3].

Allora per esempio:

[3]

=[3]+[3]+[3]=[3+3+3]=[9]

[3]

=[3]+[3]+[3]+[3]+[3]+[3]+[3]+[3]=[3+3+3+3+3+3+3+3]=[24]=[4]

(perché 4 è il resto della divisione di 24 per 20) [3]

=[0] (perché [0] è l’elemento neutro).

Consideriamo invece il gruppo delle classi di congruenza modulo 20 che sono simmetrizzabili rispetto all’operazione di prodotto di classi (sappiamo che sono le classi [a] con a=1,2,…..,19 e tali che mcd(a,20)=1):

Z

* = {[1],[3],[7],[9],[11],[13],[17],[19]}

e fissiamo di nuovo a=[3].

Allora per esempio:

[3]

=[3][3][3]=[333]=[27]=[7]

(perché 7 è il resto della divisione di 27 per 20).

[3]

=[1] (perché [1] è l’elemento neutro).

Esempio:

Consideriamo il gruppo F(X)* delle funzioni biunivoche da un insieme X in sé

stesso, dove X={a,b,c} ha cardinalità 3, rispetto all’operazione di

composizione di funzioni.

Fissiamo la funzione biunivoca f: X  X definita da f(a)=b, f(b)=c, f(c)=a:

dunque f è elemento del gruppo F(X)*.

Si ha allora, per esempio:

f

=i

=funzione identica di X (perché è l’elemento neutro rispetto alla composizione di funzioni)

f

=ff dove ff: X  X è la funzione biunivoca definita da:

(ff)(a)=f(f(a))=f(b)=c, (ff)(b)=f(f(b))=f(c)=a, (ff)(c)=f(f(c))=f(a)=b

Per le potenze di un elemento a di un gruppo A valgono le analoghe proprietà delle potenze numeriche.

Comunque presi gli interi non negativi h,k si ha:

1) (a

)*(a

)=a

2) (a

)

=a

Dimostriamo per esempio la 1), distinguendo 3 casi e in ognuno di essi dimostrando la tesi:

caso 1: h=0; allora (indicato con eA il neutro di A) (a

)*(a

)=(a

)*(a

)=e*(a

)=a

=a

=a

;

caso 2: k=0 (dimostrazione simile)

caso 3: h,k>0; allora (a

)*(a

)=(a*a*…*a)*(a*a*…*a) (dove nella prima parentesi vi sono h operandi, nella seconda k operandi), dunque (a

)*(a

)=a*a*…*a (con un totale di h+k operandi) e si conclude che (a

)*(a

)=a

anche in questo caso.

La dimostrazione della 2) segue uno schema simile.

Teorema. Se A è un gruppo finito di cardinalità n con elemento neutro eA, fissato un elemento aA esiste sempre qualche intero k>0, kn tale che a

= e.

Dimostrazione:

Consideriamo le seguenti potenze di a:

a

, a

, ……….., a

Tali elementi di A non sono tutti distinti (se così fosse sarebbero n+1 elementi distinti di A, in contraddizione con l’ipotesi che n è la cardinalità di A), dunque esistono almeno 2 interi t,s tali che ts, 0t,sn, a

= a

. Supponiamo per esempio t>s (se t<s si ragiona in modo analogo).

Se s=0 si ha la tesi, perché allora a

= a

= e, con t>0, tn, e il valore di k cercato è k=t.

Supponiamo dunque s>0.

Allora da a

= a

segue a

= e*a

, e poiché a

= a*a*……*a (con t operandi), a

= a*a*……*a (con s operandi), applicando s volte la legge di cancellazione a destra (valida nel gruppo A):

a

= e con t-s>0, t-stn

Si ottiene anche in questo caso la tesi, scegliendo k=t-s.

Se A è un gruppo finito di cardinalità n con elemento neutro eA, e se fissiamo un elemento aA, per il Teorema precedente esistono esponenti positivi kn tali che a

=e, dunque (per l’Assioma del minimo) possiamo considerare il più piccolo intero positivo kn tale che a

= e, detto periodo dell’elemento a.

Notiamo anche che ovviamente il periodo dell’elemento neutro è sempre k=1

perché e

= e.

Esempio. Consideriamo il gruppo delle classi di congruenza modulo 18 che sono simmetrizzabili rispetto all’operazione di prodotto di classi ([a] con a=1,2,

…..,17 e tali che mcd(a,18)=1):

Z

* = {[1],[5],[7],[11],[13],[17]}

e calcoliamo per esempio il periodo dell’elemento a=[7], cioè il minimo intero positivo k tale che [7]

= [1] (perché [1] è in questo caso l’elemento neutro del gruppo).

Si ha:

[7]

= [7];

[7]

= [7][7] = [77] = [49] = [13] (perché 13 è il resto della divisione di 49 per 18); [7]

= [7]

[7]

= [13][7] = [137] = [91] = [1] (perché 1 è il resto della divisione di 91 per 18)

Dunque k=3 è il periodo dell’elemento a=[7] nel gruppo Z

*.

Facendo i calcoli per tutti gli elementi di Z

* si ottengono i seguenti risultati:

[1] ha periodo 1;

[17] ha periodo 2;

[7], [13] hanno periodo 3;

[5], [11] hanno periodo 6.

Si può notare in questo esempio che non solo il periodo di ogni elemento è 

della cardinalità 6 del gruppo, ma è anche divisore della cardinalità 6 del

gruppo (dimostreremo in seguito che ciò non è casuale).