Insiemi

Definizione ((naïve) insieme)

Un insieme è una famiglia (o collezione) ben definita di elementi. "Ben definita" significa che è possibile affermare con certezza se un certo elemento è contenuto nell'insieme.

 


Questa definizione però porta a paradossi come, per esempio, l'antinomia di Russell:

Sia :

  • se (assurdo)
  • se (assurdo)

Quindi o non possono essere considerati insiemi. Esistono delle teorie più formali degli insiemi[1], ma non è opportuno né necessario approfondire questo discorso in questo contesto.

Relazioni[modifica | modifica wikitesto]

Definizione (relazione)

Sia un insieme. Un sottoinsieme del prodotto cartesiano si dice relazione su . Equivalentemente, chiamiamo relazione su una funzione .

 


Osservazione

Le due definizioni sono equivalenti per questo motivo: se vediamo la relazione come insieme , possiamo definire la funzione in modo tale che . Allo stesso modo, se vediamo la relazione come funzione , possiamo definire l'insieme come , ossia come la controimmagine di mediante .

 


Definizione

Due elementi si dicono in relazione se . In questo caso scriveremo .

 


Relazioni d'ordine[modifica | modifica wikitesto]

Definizione (relazione d'ordine)

Dato un insieme e una relazione su , diciamo che R è una relazione d'ordine (parziale) se vale che:

  1. (proprietà riflessiva);
  2. (proprietà antisimmetrica);
  3. (proprietà transitiva).
 


Definizione (POSET)

La coppia (in cui è una relazione d'ordine e è un insieme) si dice POSET (Partially Ordered SET).

 


Esempio

Un esempio di POSET è , con che indica insieme delle parti di .

 


Definizione (insieme totalmente ordinato)

Sia un POSET. è un insieme totalmente ordinato se vale che:

  • .

In tal caso, si dice relazione d'ordine totale.

 


Esempio

Un esempio di insieme totalmente ordinato è .

 


Relazioni d'equivalenza[modifica | modifica wikitesto]

Definizione (relazione d'equivalenza)

Siano un insieme e una relazione su . si dice relazione d'equivalenza se:

  1. (proprietà riflessiva);
  2. (proprietà simmetrica);
  3. (proprietà transitiva).
 

Notazione: se è una relazione d'equivalenza si usa il simbolo (e.g ).

[2]

Esempio

. L'uguaglianza è un relazione d'equivalenza, infatti:

  • Riflessività: ;
  • Simmetria: ;
  • Transitività:
 


Esempio

Sia una funzione. Definisco . Questa è una relazione d'equivalenza, infatti:

  • Riflessività: ;
  • Simmetria: Siano ;
  • Transitività: Siano .
 


Classi di Equivalenza[modifica | modifica wikitesto]

Definizione (classe di equivalenza)

Sia un insieme e sia una relazione d'equivalenza su . Per si definisce . si dice classe d'equivalenza di .

 


Proposizione

Siano . Allora vale una e una sola delle seguenti:

Inoltre .

 
Dimostrazione

Bisogna mostrare che Ovviamente, .

Sia .

Dato che , si ha che In maniera analoga si dimostra che , quindi .

Ora bisogna dimostrare .

  • : se , allora ;
  • : se , allora
 


Definizione (insieme delle classi di equivalenza)

Siano un insieme, l'insieme delle parti di e una relazione d'equivalenza su . si dice insieme delle classi d'equivalenza (o insieme quoziente) di .

 


Definizione (proiezione sul quoziente)

Sia un insieme, sia una relazione d'equivalenza su . Allora data da è una funzione e si chiama proiezione (canonica) sul quoziente.

 
Osservazione

 

.

Definizione

Sia un insieme e sia relazione d'equivalenza su . Un sistema di rappresentanti per in è un sottoinsieme .

 


Lemma

Sia funzione suriettiva. Allora

 
Proposizione

Sia un insieme e sia una relazione d'equivalenza su . Allora esiste un sistema di rappresentanti per .

 
Dimostrazione

Sia la proiezione sul quoziente. è suriettiva (ovvero ), quindi (per il Lemma precedente) .

Sia .

.

Siano e siano . Allora .

Pertanto è un sistema di rappresentanti per .

 


Esempio

Sia . Sia la relazione data da . Si dimostra facilmente che questa relazione così definita è d'equivalenza.

Sia e sia . Sia .

.

Sia un sistema di rappresentanti.

( è la parte intera di ).

Sia .

Sia tale che .

 


Esiste una funzione ? Sì, secondo il Lemma della forbice (non si chiama veramente così, ma si usa questo nome perchè rende l'idea di una forbice; inoltre è un lemma molto utilizzato in vari teoremi molto importanti in Algebra, quindi è meglio dare un nome a questo lemma).

Lemma (della forbice)

Siano un insieme, una relazione d'equivalenza su e una funzione che passa al quoziente (ossia t.c ). Allora esiste una mappa tale che .

 


Schema lemma forbici-Algebra1.svg


Dimostrazione

Sia .

Definiamo .

Sia ; .

L'ultima uguaglianza vale poichè e passa al quoziente, pertanto si ha che .

Quindi

 
  1. https://it.wikipedia.org/wiki/Teorie_formali_degli_insiemi
  2. Trucchetto per ricordarsi: una relazione è d'equivalenza se è R-S-T (Riflessiva Simmetrica Transitiva)
Successivo