Teorema di Cantor-Bernstein-Schröder

In matematica, il teorema di Cantor-Bernstein-Schröder, a cui spesso si fa riferimento semplicemente come teorema di Cantor-Bernstein, afferma che, dati due insiemi e , se esistono due funzioni iniettive e , allora esiste una funzione biiettiva .

Presupposti e conseguenze del teoremaModifica

Questo teorema è nato, ed ha una grande importanza, nell'ambito della teoria degli insiemi e in particolare nello studio delle cardinalità.

Infatti la definizione classica di   ("la cardinalità di   è minore o uguale della cardinalità di  "), dove   sono due insiemi qualunque, è:

Esiste una funzione iniettiva da   in  .

Mentre la definizione di   ("  e   sono equipotenti") è:

Esiste una funzione biiettiva da   in  .

Ciò detto, il teorema di Cantor-Bernstein-Schröder può essere riformulato come segue:

Se   e  , allora  

Questo è proprio uno dei requisiti fondamentali che deve avere   per essere una relazione d'ordine parziale. Il teorema è quindi fondamentale per poter ordinare gli insiemi in base alla loro cardinalità. È da notare che per stabilire che una tale relazione d'ordine è totale è necessario supporre l'assioma della scelta.

DimostrazioneModifica

Innanzitutto osserviamo che   è l'unica funzione che sappiamo definire su  ; allo stesso modo, l'unica funzione che abbiamo su   è  , che corrisponde a   sull'immagine  . La funzione   viene costruita proprio in questo modo, dividendo l'insieme   in sottoinsiemi  ,  ,  , eccetera, sui quali   dev'essere pari a   o   in modo alterno.

 
Alcune aree delimitate dalle iterazioni di f e g. Si riconoscono   e  .

Per una definizione più precisa e semplice, si considerano i concetti di precedente e di primo tra i precedenti (introducendo un particolare ordinamento parziale):

  • un punto   di   ha un precedente   in   se  
  • un punto   di   ha un precedente   in   se  

Per l'iniettività delle due funzioni, se esiste, ogni precedente è unico; si può quindi cercare di risalire la catena dei precedenti (x,y,z,...) per trovarne il primo. È ora possibile suddividere   in una partizione come:

  •   è l'insieme dei punti di   che hanno un primo precedente in  ;
  •   è l'insieme dei punti di   che hanno un primo precedente in  ;
  •   è l'insieme dei punti di   che non hanno un primo precedente, cioè per i quali la catena dei precedenti non termina.

Questa suddivisione permette di definire una bigezione tra   e  
 
(Si può indifferentemente scegliere di definire   pari a   su  .)

Voci correlateModifica

Collegamenti esterniModifica

  Portale Matematica: accedi alle voci di Wikipedia che trattano di matematica