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 teorema
[modifica | modifica wikitesto]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.
Dimostrazione
[modifica | modifica wikitesto]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.
![](http://178.128.105.246/host-http-upload.wikimedia.org/wikipedia/commons/thumb/b/b7/Cantor-bernstein.svg/310px-Cantor-bernstein.svg.png)
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 correlate
[modifica | modifica wikitesto]Altri progetti
[modifica | modifica wikitesto]Wikimedia Commons contiene immagini o altri file su teorema di Cantor-Bernstein-Schröder
Collegamenti esterni
[modifica | modifica wikitesto]- Cantor-Schroder-Bernstein, teorema di, in Enciclopedia della Matematica, Istituto dell'Enciclopedia Italiana, 2013.
- (EN) Eric W. Weisstein, Teorema di Cantor-Bernstein-Schröder, su MathWorld, Wolfram Research.
- (EN) Cantor-Bernstein-Schroeder theorem da Cut The Knot