Matematica Discreta Lezione del giorno 29 marzo 2012 Operazioni in un insieme.

Matematica Discreta

Lezione del giorno 29 marzo 2012 Operazioni in un insieme.

In aritmetica é ben noto il concetto di “operazione” fra numeri: un esempio sono le operazioni di somma e prodotto fra numeri naturali.

Ma cos’è formalmente un’operazione ?

Se esaminiamo la somma fra numeri naturali, essa non è altro che una regola che associa ad ogni coppia (x,y) di numeri naturali (detti “addendi”) un unico numero naturale x+y (detto “somma”).

Nel linguaggio insiemistico dunque la somma fra numeri naturali è una funzione f. NxNN.

Da queste osservazioni si perviene facilmente alla seguente definizione più generale:

Un’operazione definita nell’insieme (non vuoto) A è una funzione f : AxA → A

(dove AxA = {(x,y) / x,yA } è il prodotto cartesiano contenente le coppie ordinate di elementi di A) che associa ad ogni coppia ordinata (x,y) di elementi di A uno e un solo elemento f(x,y)A.

Gli elementi x,y sono detti operandi (l’elemento x è il primo operando, l’elemento y è il secondo operando), mentre l’elemento f(x,y) è detto risultato dell’operazione sugli operandi x,y.

Useremo spesso il simbolo xy per indicare il risultato f(x,y) dell’operazione sugli operandi x,y.

Esempio.

Nell’insieme N dei numeri naturali sono esempi di operazioni quelle definite ponendo:

xy = x+y (somma) xy = x∙y (prodotto)

xy = x^y (elevamento a potenza)

Poiché un’operazione non è altro che una funzione, un’operazione in un insieme A può essere definita:

- in modo implicito: dati 2 operandi variabili x,y in A si definisce un’operazione ponendo xy = ………

dove dopo il segno di eguaglianza vi è una “formula” nelle variabili x, y che permette di calcolare il risultato, dati gli operandi x,y.

Gli esempi precedenti di operazioni di somma, prodotto, elevamento a potenza in N sono definiti in modo implicito. Ovviamente nello stesso insieme N potremmo definire in modo implicito altre operazioni, ovviamente meno “utili” di quelle precedenti (che sono legate al procedimento di

“contare”).

Per esempio potremmo definire in modo implicito un’operazione in N ponendo:

xy = x + y + xy

Se volessimo allora calcolare in particolare in questa operazione il risultato 32 dovremmo calcolare:

32 = 3 + 2 + 32 = 11

- in modo esplicito (tale modalità è praticabile solo nel caso in cui l’insieme A sia finito): per ognuna delle possibili coppie di operandi x,y in A si indica esplicitamente il risultato xy (che deve essere un unico elemento di A).

Per esempio nell’insieme A = {a, b, c} delle prime 3 lettere dell’alfabeto, possiamo definire un’operazione indicando, per ognuna delle 9 coppie possibili di operandi in A, il risultato nel modo seguente:

aa=b, bb=b, cc=a, ab=c, ba=a, ac=b, ca=c, bc=a, cb=a

Si può rendere la definizione esplicita di una operazione (definita in un insieme finito A di cardinalità n) utilizzando una tavola operazionale: è una matrice quadrata di n² caselle disposte in n righe e n colonne, in cui si fanno corrispondere alle righe e alle colonne ordinatamente gli elementi di A (in un ordine prefissato), e inserendo in ogni casella il risultato xy, dove x è l’operando corrispondente alla riga della casella, y è l’operando corrispondente alla colonna della casella.

Nell’ esempio precedente, l’operazione definita nell’insieme A = {a, b, c} di cardinalità 3 avrebbe la seguente tavola operazionale 3x3 (rispetto all’ordine prefissato a,b,c):

a b c a

b c

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2=3² .

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^(yz)

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

b c b

a b a

c a a

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.

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¹=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 = {a1, a2,……, an}

é definita un’operazione  in modo esplicito mediante una tavola operazionale (rispetto all’ordinamento a1, a2,……, an), un elemento è elemento neutro se la riga e la colonna corrispondenti a quell’elemento contengono ordinatamente gli elementi a1, a2,……, an.

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 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’’ .

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

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

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

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.