Operazioni

Definizione ed esempi[modifica | modifica wikitesto]

Definizione 1.16

Sia un insieme, un'operazione è una funzione .

 


Esempio 1.16

La somma è un'operazione. La differenza sugli interi non è un'operazione, e non lo è nemmeno la divisione sugli interi o sui reali. L'unione, l'intersezione e la differenza simmetrica su sono operazioni.

 


Definizione 1.17

L'operazione si dice associativa se per ogni ,

mentre si dice commutativa se

 


Esempio 1.17

Non tutte le operazioni sono associative, ad esempio tale che non è commutativa, infatti per , si ha

 


Definizione 1.18

Un elemento si dice un elemento neutro di se,

 


Esempio 1.18

Sia , allora l'intersezione ha elemento neutro e l'unione ha elemento neutro . Per l'operazione differenza simmetrica, se e è l'elemento neutro, si deve avere

allora l'elemento neutro è l'insieme vuoto.

 


Esempio 1.19

Sia tale che . Allora cerco se esiste tale che

ma non è sempre verificata, quindi non esiste elemento neutro.

 

Composizione di funzioni[modifica | modifica wikitesto]

Definizione 1.19

Siano e funzioni. Allora si può costruire la funzione tale che

 


Esempio 1.20

Data e , si ha

 


Esercizio 1.5

Dimostrare che

  1. date due funzioni iniettive, allora è iniettiva.
  2. suriettive implica suriettiva.
  3. biettive implica biettiva.

Soluzione:

  1. è iniettiva se e solo se, dati , segue che
    se e solo se .Siccome è iniettiva, se e solo se , ma siccome anche è iniettiva, se e solo se , quindi si ottiene che se e solo se , cioè la composizione di funzioni iniettive è iniettiva.
  2. è suriettiva se e solo se per ogni esiste tale che . Siccome è suriettiva, per ogni esiste tale che . Ma siccome anche è suriettiva, per ogni esiste tale che , quindi sostituendo con ottengo che , e quindi è suriettiva.
  3. Il fatto che la composizione di funzioni biunivoche è biunivoca segue dai punti precedenti.

cvd

 

Insiemi di funzioni[modifica | modifica wikitesto]

Definizione 1.20

Sia un insieme, con si denota l'insieme di tutte le funzioni . Se , ho un'unica funzione. Se , ha 4 elementi:

Se ha tre elementi, ha elementi.

 


Esempio 1.21

Non è una funzione la legge che a un elemento associa un elemento tale che .

 


Definizione 1.21

La composizione di funzioni è un'operazione tale che .

Sia

non si può definire un'operazione che prese associa la composizione con e , perché un'operazione dev'essere definita da ad .

Date una funzione e , allora è definita se .
 


Proposizione 1.2

La funzione identità è l'elemento neutro per la composizione.

 
Dimostrazione 1.1

Sia , , allora . Analogamente

quindi . cvd

 


Esercizio 1.6

Dimostrare che è l'unico elemento neutro per la composizione. Soluzione: Supponiamo che esistano due elementi neutri, e , allora siccome è un elemento neutro, per ogni si ha , allora per si deve avere . Tuttavia anche è un elemento neutro, quindi per ogni , quindi per si deve avere . Allora ho ottenuto:

allora e l'elemento neutro è unico. cvd

 


Proposizione 1.3

La composizione di funzioni è associativa.

 
Dimostrazione 1.2

Considero , e confronto

Sia , allora

allora vale la proprietà associativa.


cvd

 


Proposizione 1.4

Se ha almeno 2 elementi, allora non è commutativa.

 
Dimostrazione 1.3

Basta trovare due funzioni tali che . Siano due punti distinti. Sia tale che , e . Allora

quindi la composizione non è commutativa. (in questo caso si ha anche e )
cvd

 

Gruppo simmetrico[modifica | modifica wikitesto]

Considero funzioni in . Denotiamo con l'insieme delle funzioni tali che sia biettiva. Si nota che tale che è un'operazione (ricordare che la composizione di funzioni biettive è biettiva).

Quest'operazione ha come elemento neutro sempre l'identità che è un elemento di .


Esercizio 1.7

Dimostrare che l'operazione non è commutativa se ha almeno tre elementi. Soluzione: Sia e considero tale che:

Allora ad esempio si ha

allora . cvd

 

Somma NIM[modifica | modifica wikitesto]

Dimostrazione 1.4

La somma NIM di due numeri si denota con . Per fare la somma NIM tra due numeri, devo scrivere ognuno dei due numeri come somma di potenze di 2. Poi, per fare la somma, scrivo solo le potenze di 2 che compaiono nei due numeri e non sono comuni a entrambi.

 


Esempio 1.22

Eseguo l'operazione . Per scrivere un numero come somma di potenze di 2, cerco prima la massima potenza di che è contenuta nel numero, poi la sottraggo al numero e ripeto la stessa operazione sulla differenza ottenuta:

Ora eseguo la somma e riscrivo le potenze di 2 che compaiono nei due numeri e che non sono comuni a entrambi

(in questo caso non riscrivo )

 


Esempio 1.23

Eseguire la somma:

(non riscrivo ).

 

La somma NIM di un numero con se stesso è sempre nulla.

La somma NIM è commutativa, associativa, ha elemento neutro.

Alcuni esempi[modifica | modifica wikitesto]

Esempio 1.24

Considero l'insieme dei punti del piano, e definisco la relazione tale che due punti sono equivalenti se hanno la stessa ordinata. Questa relazione è di equivalenza. Le classi di equivalenza di questa relazione sono le rette orizzontali, e l'insieme quoziente è l'insieme di tutte le rette orizzontali.

 


Esempio 1.25

Sia

Mostro che :

  1. : considero un elemento con intero. Verifico che l'elemento sta in : sono coordinate intere, e soddisfano l'equazione , infatti:
    e l'uguaglianza è verificata, quindi ogni elemento di sta in .
  2. : prendo , allora
    e siccome il membro di sinistra è pari e intero, anche dev'essere intero e pari, allora dev'essere dispari, quindi con intero (è 1 a cui sommo un numero pari).Sostituendo nell'equazione al posto di ottengo
    e isolando :
    Quindi .
 

Elementi neutri e opposti[modifica | modifica wikitesto]

Proposizione 1.5

Sia un insieme e un'operazione. Siano due elementi neutri di . Allora .

 


Dimostrazione 1.5

Affinché sia un elemento neutro, si deve avere

ma siccome anche è un elemento neutro:

Considerando , si ha che per il fatto che è un elemento neutro, , ma siccome anche è un elemento neutro, , quindi . cvd

 


Definizione 1.22

Sia l'elemento neutro di , e sia . Il reciproco / opposto / inverso di , se esiste, è un elemento di con .

 


L'elemento neutro ha come inverso se stesso.


Esempio 1.26

Data l'operazione di unione su , l'elemento neutro è l'insieme vuoto, allora, l'opposto di , se esiste, dev'essere tale che . Allora un elemento con questa proprietà può esistere solo se .


Considerando invece l'operazione di intersezione, il suo elemento neutro è l'insieme . Allora l'opposto di esiste solo se e quindi anche in questo caso l'unico elemento che ammette opposto è l'elemento neutro.

 


Esempio 1.27

Nella somma NIM definita sui naturali, con elemento neutro 0, ogni elemento ha come inverso se stesso.

 

Gerarchia di strutture algebriche[modifica | modifica wikitesto]

Definizione 1.23

La coppia si dice struttura algebrica.

  1. la coppia è un semigruppo se è associativa.
  2. è un monoide se è un semigruppo, e ha elemento neutro.
  3. è un gruppo se è un monoide e ogni elemento ha inverso.Ad esempio, i numeri interi con l'operazione di somma sono un gruppo. I razionali con l'operazione di prodotto non sono un gruppo perché lo zero non ha inverso. Invece con l'operazione di prodotto è un gruppo. I naturali con la somma NIM sono un gruppo.
 

L'inverso è unico?[modifica | modifica wikitesto]

Proposizione 1.6

Se è associativa, l'inverso, se esiste, è unico.

 
Dimostrazione 1.6

Sia , e siano inversi di . Mostriamo che .


Osservo che

con elemento neutro. Moltiplicando a sinistra entrambi i membri per :

ma , e riscrivo il primo membro usando l'associatività:

ma , quindi ottengo cioè . cvd

 

Tavole di moltiplicazione[modifica | modifica wikitesto]

Sia , e considero la tabella chiamata tavola di moltiplicazione che ha righe (chiamate ) e colonne con i nomi degli elementi di nello stesso ordine delle righe. In ciascuna casella della griglia scrivo l'elemento .

Dalla tavola si possono dedurre alcune proprietà dell'operazione secondo le seguenti regole:

  1. se l'operazione è commutativa la tabella è una matrice simmetrica.
  2. se l'operazione ha un elemento neutro , allora ogni elemento della riga corrispondente è ilnome della colonna j-esima, e ogni elemento della colonna corrispondente sarà il nome della j-esima riga.
  3. Un elemento è invertibile se sulla riga che ha il nome di quell'elemento compare una e lo stesso vale per la colonna.
  4. l'associatività non si deduce facilmente dalla tabella. Però, in generale, se è una struttura algebrica e se è una relazione di equivalenza compatibile con , se è associativa, anche è associativa. Quindi, se riconosco che una certa operazione è uguale a un'operazione sul quoziente, allora l'operazione è associativa.


Esempio 1.28

Supponiamo che

e considero la tabella di moltiplicazione:

Quest'operazione ha un elemento neutro , e ogni elemento è invertibile, gli elementi e hanno addirittura due inversi. Questo significa che l'operazione non è associativa, e lo si dimostra facilmente:

e si ottengono valori diversi.

 

Anello[modifica | modifica wikitesto]

Definizione 1.24

Sia un insieme con operazioni e . Allora è un anello se:

  1. è un gruppo commutativo con elemento neutro 0.
  2. è un semigruppo
  3. valgono le proprietà distributive:
 

Un esempio è l'insieme dei razionali con operazioni di somma e prodotto.

Definizione 1.25

L'insieme è un campo se è un anello e se l'operazione ha elemento neutro 1 e se è un gruppo commutativo.

 


Ad esempio: è un campo.

Relazioni compatibili con un'operazione[modifica | modifica wikitesto]

Definizione 1.26

Sia una struttura algebrica, una relazione su si dice compatibile con se dati , se e , allora

 


Esempio 1.29

Sia , l'operazione di somma e tale che se è divisibile per 2. è compatibile con la somma.

 
Dimostrazione 1.7

Considero interi. Per ipotesi e , vogliamo dedurre che è in relazione con .


significa che è divisibile per 2, implica che è divisibile per 2. Ci chiediamo se è divisibile per 2. Questo è vero perché è somma di numeri pari e .

 


Assumiamo che sia relazione di equivalenza. L'operazione definita su determina senza ambiguità un'operazione nell'insieme quoziente , definita in questo modo: tale che . L'operazione non è definita in modo ambiguo perché prendendo due qualsiasi elementi nelle classi di equivalenza e il risultato è sempre lo stesso.

Esempio 1.30

Con come prima ( se è pari), consiste delle due classi di equivalenza: (i numeri pari) e (numeri dispari). Per eseguire la somma si ha . Scegliendo altri due elementi nella classe di , ad esempio , si ha

Scrivendo la tavola della somma di questo insieme quoziente si ha:

 
 PrecedenteSuccessivo