Operazioni

Definizione ed esempi

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

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

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

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

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

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

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

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?

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

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

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

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