• Non ci sono risultati.

Matematica Discreta Lezione dei giorni 21,25 e 28 marzo 2011 Proprietà commutativa.

N/A
N/A
Protected

Academic year: 2021

Condividi "Matematica Discreta Lezione dei giorni 21,25 e 28 marzo 2011 Proprietà commutativa."

Copied!
1
0
0

Testo completo

(1)

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 xy= yx (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:

23=2

3

32=3

2

.

Nell’insieme A = {a, b, c} l’operazione definita in precedenza non è commutativa perché per esempio: ab=cba=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,zA, si ha:

(xy)z = x(yz) 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), (xy)z=x(yz), comunque dati i numeri naturali x,y,z.

Invece l’operazione di elevamento a potenza xy=x

y

non è associativa perché, dati i numeri naturali x,y,z, non è sempre vero che i seguenti risultati sono uguali:

(xy)z= (x

y

)z=(x

y

)

z

=x

yz

x(yz)= x(y

z

) = x (y

z

)

L’operazione (esaminata come esempio in precedenza) definita in modo implicito nell’insieme dei numeri naturali da:

xy = x+y+xy

è associativa, perché i seguenti 2 risultati:

(xy)z= (x+y+xy)z=(x+y+xy)+z+(x+y+xy)z=x+y+xy+z+xz+yz+xyz x(yz)= x(y+z+yz)= x+(y+z+yz)+x(y+z+yz)= x+y+z+yz+xy+xz+xyz

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 (ab)c=cc=a è diverso da a(bc)=aa=b.

(2)

Elemento neutro.

In un insieme A in cui è definita un’operazione , si dice che l’elemento eA è un elemento neutro se per ogni xA si ha xe=ex=x.

Ovviamente se l’operazione * è commutativa, basta verificare (per ogni xA) solo una delle 2 eguaglianze:

xe=x ex=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 ee’=e’ (perché e è neutro), ee’=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 ab=a

b

non esiste elemento neutro (il numero 1 funziona da neutro solo come secondo operando, perché x1=x

1

=x, ma non come primo operando perché 1x=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 eZ tale che:

per ogni xZ si ha xe=x.

Si ottiene:

xe=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) è:

(3)

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 eA.

Fissato un elemento xA, si dice che l’elemento x’A è un simmetrico di x se:

xx’=x’x=e.

Ovviamente se l’operazione * è commutativa, basta verificare (per ogni xA) solo una delle 2 eguaglianze:

xx’=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 bc=cb=a, ma anche bd=db=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 eA. Supponiamo inoltre che l’operazione sia associativa.

Allora il simmetrico di un elemento xA (se esiste) è unico.

Dimostrazione Se x’, x’’ sono entrambi simmetrici di x, si ha, sfruttando la proprietà associativa:

x’ = x’e = x’(xx’’) = (x’x)x’’= ex’’= 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

(4)

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 xZ 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 eA è simmetrizzabile, ed è uguale al suo simmetrico (perché ee=e)

2) Se l’elemento xA è simmetrizzabile con simmetrico x’A, allora anche x’ è simmetrizzabile con simmetrico x (perché xx’=x’x=e). In pratica il simmetrico del simmetrico di x è x stesso:

(x’)’ = x

3) Se gli elementi x,yA sono simmetrizzabili con simmetrici rispettivamente x’,y’A, anche xy è simmetrizzabile con simmetrico y’x’. Infatti, applicando la proprietà associativa, si ha:

(xy)(y’x’)=[(xy) y’] x’=[x(yy’)] x’=[xe] x’=xx’=e

(e analogamente (y’x’)(xy)=e).

(5)

In pratica il simmetrico di xy si ottiene operando con l’operazione * sul simmetrico di y (come primo operando) e sul simmetrico di x (come secondo operando):

(xy)’ = (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 xA* 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 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

(6)

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

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

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

n

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

n

righe ed n

n

colonne.

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

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

f f f f

f f f f

f

f

f

f

(7)

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

A

ed 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 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

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:

(8)

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

f f f f f f

f f f f f f

f f f f f f

f f f f f f

f f f f f f

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

Inoltre fg  gf (perché (fg)(a)=f(g(a))=f(c)=c, mentre (gf)(a)=g(f(a))=g(b)=b).

Proprietà che si trasmettono da un’operazione all’operazione indotta.

Torniamo al caso generale di un insieme A in cui sono definite sia una relazione di equivalenza R che un’operazione * compatibile con R, in modo che nell’insieme quoziente A/R delle classi di equivalenza sia definita un’operazione indotta * fra le classi.

Notiamo che in tale caso molte proprietà dell’operazione * dell’insieme A si trasmettono all’analoga operazione * dell’insieme delle classi A/R:

1) se l’operazione * in A é associativa, l’operazione indotta * in A/R é anch’essa associativa. Infatti, date 3 classi [a],[b],[c] si ha (sfruttando la proprietà associativa valida in A):

[a]*([b]*[c]) = [a]*[b*c] = [a*(b*c)] = [(a*b)*c] = [a*b]*[c] = ([a]*[b])*[c]

2) se l’operazione * in A é commutativa, l’operazione indotta * in A/R é anch’essa commutativa.

Infatti, date 3 classi [a],[b],[c] si ha (sfruttando la proprietà commutativa valida in A):

[a]*[b] = [a*b] = [b*a] = [b]*[a]

3) se esiste l’elemento neutro eA rispetto all’operazione *, allora esiste anche l’elemento neutro nell’insieme delle classi A/R rispetto all’operazione indotta * ; inoltre tale elemento neutro é la classe [e]. Infatti per ogni classe [a] si ha:

[a]*[e] = [a*e] = [a] ; [e]*[a] = [e*a] = [a]

4) se un elemento aA é simmetrizzabile rispetto all’operazione * con simmetrico a’A, allora la

classe [a] é simmetrizzabile nell’insieme delle classi A/R rispetto all’operazione indotta * ed il suo

simmetrico é la classe [a’]. Infatti si ha :

(9)

[a]*[a’] = [a*a’] = [e] = elemento neutro di A/R; [a’]*[a] = [a’*a] = [e] = elemento neutro di A/R In particolare:

- se A é monoide rispetto all’operazione *, anche A/R é monoide rispetto all’operazione indotta * - se A é gruppo rispetto all’operazione *, anche A/R é gruppo rispetto all’operazione indotta * Inoltre se A è monoide (rispettivamente gruppo) commutativo anche A/R lo é.

Applichiamo le considerazioni precedenti all’insieme Z

m

delle classi di congruenza modulo m, in cui abbiamo definito le operazioni di somma e prodotto di classi, indotte dalle operazioni di somma e prodotto fra interi.

Vediamo quali proprietà hanno tali operazioni.

Essendo Z un gruppo commutativo rispetto all’operazione di somma (con elemento neutro 0 e con simmetrico di un elemento a uguale all’opposto –a) per le osservazioni precedenti si ottiene che l’insieme Z

m

delle classi di congruenza modulo m é un gruppo commutativo rispetto all’operazione di somma fra classi (l’elemento neutro sarà [0] e il simmetrico di una classe [a]

sarà la classe [-a]).

Invece essendo Z solo un monoide commutativo rispetto all’operazione di prodotto (con elemento neutro 1) per le osservazioni precedenti si ottiene che l’insieme Z

m

delle classi di congruenza modulo m é un monoide commutativo rispetto all’operazione di prodotto fra classi (l’elemento neutro sarà [1]).

Per quanto riguarda l’operazione di somma fra classi in Z

m

, possiamo notare che per calcolare il simmetrico (sempre rispetto alla somma) di una classe [a] scelta fra le classi {[0], [1],..., [m-1]}, vi é una regola pratica molto semplice:

- se [a] = [0], il suo simmetrico é [0] (l’elemento neutro ha come simmetrico sé stesso)

- se [a]  [0] (quindi se a=1,2...,m-1) allora il simmetrico di [a] é la classe [m-a] (infatti sommando [a] con [m-a] si ottiene [a]+[m-a] = [a+m-a] = [m] = [0] = elemento neutro, perché r=0 é il resto della divisione di m per m).

Per esempio in Z

100

il simmetrico di [48] é [100-48] = [52].

Abbiamo detto che rispetto all’operazione di prodotto di classi, l’insieme Z

m

é un monoide commutativo (con elemento neutro [1]), perché tale è Z rispetto al prodotto.

Tale monoide Z

m

non è un gruppo: possiamo infatti notare che [0] non é certamente simmetrizzabile rispetto al prodotto fra classi, in quanto non può esistere il simmetrico di [0], perché il prodotto di [0] per qualunque classe dà come risultato sempre [0] (quindi non si ottiene mai [1] che é l’elemento neutro).

Se esaminiamo per esempio la tavola operazionale del prodotto in Z

4

(vista in precedenza) si verifica che gli unici elementi simmetrizzabili sono [1] e [3].

Resta da risolvere un problema generale: nel monoide Z

m

(rispetto all’operazione di prodotto fra classi) quali sono gli elementi simmetrizzabili e come si calcola il loro simmetrico (cioé il loro inverso) ?

Ricordiamo anche che l’insieme degli elementi simmetrizzabili del monoide Z

m

é un gruppo (indicato con Z

m

*) rispetto alla stessa operazione di prodotto fra classi (ed é ovviamente commutativo anch’esso).

Abbiamo già notato che [0] non é certamente simmetrizzabile rispetto al prodotto fra classi, dunque gli elementi simmetrizzabili nel monoide Z

m

sono da cercare fra le classi diverse da [0], cioé fra le classi [1],..., [m-1].

Il prossimo risultato che dimostreremo caratterizza fra queste classi quali sono simmetrizzabili.

(10)

Richiamiamo dapprima alcune nozioni relative all’algoritmo Euclideo delle divisioni successive, che serve per calcolare il mcd(a,b), dove a,b sono numeri naturali.

Lo schema delle divisioni effettuate nell’algoritmo è il seguente:

divisione 1 a=bq

1

+r

1

con q

1

,r

1

interi 0, r

1

<b (se r

1

>0) divisione 2 b=r

1

q

2

+r

2

con q

2

,r

2

interi 0, r

2

<r

1

(se r

2

>0) divisione 3 r

1

=r

2

q

3

+r

3

con q

3

,r

3

interi 0, r

3

<r

2

(se r

3

>0) divisione 4 r

2

=r

3

q

4

+r

4

con q

4

,r

4

interi 0, r

4

<r

3

. . . .

(se r

n-2

>0) divisione (n-1) r

n-3

=r

n-2

q

n-1

+r

n-1

con q

n-1

,r

n-1

interi 0, r

n-1

<r

n-2

(se r

n-1

>0) divisione n r

n-2

=r

n-1

q

n

+r

n

con q

n

,r

n

interi 0, r

n

=0

Quando il resto r

n

è =0 (quindi se l’algoritmo ha termine con la divisione numero n) si ottiene che r

n- 1

=mcd(a,b).

Abbiamo già dimostrato che questo algoritmo (con una opportuna “estensione”) serve anche per calcolare i coefficienti interi relativi x,y che permettono di rappresentare il mcd(a,b) nella forma mcd(a,b)=ax+by.

Ripercorreremo ora il procedimento per calcolare i coefficienti x,y con qualche nuova considerazione.

Osserviamo che se riusciamo per ognuna delle divisioni successive ad esprimere il resto della divisione r

i

come combinazione lineare di a e b, allora anche r

n-1

= mcd (a,b) lo potremo scrivere in questo modo.

Supponiamo di conoscere una scrittura di questo tipo per i resti r

i-1

e r

i-2

, cioè:

r

i-1

= a x

i-1

+ by

i-1

r

i-2

= a x

i-2

+ b y

i-2

allora dalla divisione che ha per resto r

i ,

cioè r

i-2

= r

i-1

q

i

+ r

i

si ha : r

i

= r

i-2

- r

i-1

q

i

e sostituendo in questa espressione r

i-1

e r

i-2

otteniamo:

r

i

= ( a x

i-2

+ by

i-2

) - q

i

(a x

i-1

+ by

i-1

) = a( x

i-2

- q

i

x

i-1

)

+

b( y

i-2

- q

i

y

i-1

).

Abbiamo quindi espresso r

i

come combinazione lineare di a e b:

r

i

= a x

i

+ by

i

= a( x

i-2

- q

i

x

i-1

)

+

b( y

i-2

- q

i

y

i-1

)

e per calcolare i coefficienti x

i

e y

i

della combinazione lineare serve conoscere soltanto il quoto q

i

della divisione che ha come resto r

i

e i coefficienti delle combinazioni lineari che esprimono r

i-1

e r

i- 2

in funzione di a e b.

Per questo motivo per fare partire la procedura di calcolo si possono considerare due coppie di coefficienti

(x

–1

= 1 , y

-1

= 0) e (x

0

= 0 , y

0

= 1) scelti in modo tale che da essi si possono ottenere i coefficienti delle combinazioni lineari di r

1

e r

2

con le formule trovate prima,infatti si ha:

r

1

= a – bq

1

= a ( x

-1

– q

1

x

0

) + b(y

-1

– q

1

y

0

),

r

2

= b – r

1

q

2

= b – ( a-bq

1

)q

2

= a (-q

2

) + b(1+ q

1

q

2

) = a( x

0

– q

2

x

1

) + b(y

0

– q

2

y

1

).

Esempio : riprendiamo l’esempio già illustrato in una lezione precedente:

mcd(371,98) = 7

Le divisioni effettuate erano in tutto 5:

(11)

371=983+77 q

1

=3, r

1

=77 98=771+21 q

2

=1, r

2

=21 77=213+14 q

3

=3, r

3

=14 21=141+7 q

4

=1, r

4

=7 14=72+0 q

5

=2, r

5

=0

I coefficienti x

i

e y

i

calcolati con la regola precedente sono:

x

-1

= 1, x

0=

0, x

1

= 1, x

2

= -1, x

3

=4, x

4

= -5 y

-1

= 0, y

0=

1, y

1

= -3, y

2

= 4, y

3

= -15, y

4

= 19 e si ottengono alla fine i valori di x, y : x = x

4

= -5 y = y

4

= 19

tali che mcd(371,98) = 7 = 371x+98y .

Riferimenti

Documenti correlati

• i numeri irrazionali algebrici alcuni numeri molto particolari, che non sono contenuti negli insiemi precedenti perché non sono esprimibili con una frazione, Sono numeri

Due numeri relativi con lo stesso segno sono detti concordi. Due numeri relativi con segno diverso sono detti discordi. Due numeri relativi con segno diverso e valore assoluto

La somma di due numeri relativi positivi ……… un numero positivo 2.. La somma di due numeri relativi negativi ……… un numero

Il numero di bit necessari per rappresentare un certo numero nel sistema binario è minore o al più eguale del numero di bit necessari per rappresentare lo stesso numero in

La somma di due numeri relativi discordi è un numero che ha il segno dell’addendo di valore assoluto maggiore e valore assoluto uguale alla differenza dei loro valori assoluti. Si

Nel 12 d.C., alla morte di Ottaviano Augusto, gli succedette come imperatore. Quanti anni passarono tra i due eventi

Nelle attività introduttive abbiamo incontrato alcune situazioni nelle quali i numeri naturali non sono più sufficienti. Essi formano l’insieme dei numeri interi relativi

Le tre seguenti successioni di numeri interi sono state scritte seguendo un preciso procedimento