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 $A$ e $B$, se esistono due funzioni iniettive $f\colon A\rightarrow B$ e $g\colon B\rightarrow A$, allora esiste una funzione biiettiva $h\colon A\rightarrow B$.

Presupposti e conseguenze del teorema

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 $|A|\leq |B|$ ("la cardinalità di $A$ è minore o uguale della cardinalità di $B$"), dove $A,B$ sono due insiemi qualunque, è:

Esiste una funzione iniettiva da $A$ in $B$.

Mentre la definizione di $|A|=|B|$ ("$A$ e $B$ sono equipotenti") è:

Esiste una funzione biiettiva da $A$ in $B$.

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

Se $|A|\leq |B|$ e $|B|\leq |A|$, allora $|A|=|B|$

Questo è proprio uno dei requisiti fondamentali che deve avere $\leq$ 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

Innanzitutto osserviamo che $f$ è l'unica funzione che sappiamo definire su $A-g(B-f(A))$; allo stesso modo, l'unica funzione che abbiamo su $B-f(A-g(B))$ è $g$, che corrisponde a $g^{-1}$ sull'immagine ${g(B-f(A-g(B)))=g(B)-g(f(A-g(B)))}$. La funzione $h$ viene costruita proprio in questo modo, dividendo l'insieme $A$ in sottoinsiemi $A-g(B)$, $g(B)-g(f(A))$, $g(f(A))-g(f(g(B)))$, eccetera, sui quali $h$ dev'essere pari a $f$ o $g^{-1}$ in modo alterno.

Alcune aree delimitate dalle iterazioni di f e g. Si riconoscono $A_{1}=A-g(B)$ e $A_{2}=g(B)-g(f(A))$.

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 $x$ di $A$ ha un precedente $y$ in $B$ se $x=g(y)$
• un punto $y$ di $B$ ha un precedente $z$ in $A$ se $y=f(z)$

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 $A$ in una partizione come:

• $A_{A}$ è l'insieme dei punti di $A$ che hanno un primo precedente in $A$;
• $A_{B}$ è l'insieme dei punti di $A$ che hanno un primo precedente in $B$;
• $A_{C}$ è l'insieme dei punti di $A$ che non hanno un primo precedente, cioè per i quali la catena dei precedenti non termina.

Questa suddivisione permette di definire una bigezione tra $A$ e $B$
$h(x)={\begin{cases}f(x)&{\text{se }}x\in A_{A}\\g^{-1}(x)&{\text{se }}x\in A_{B}\\f(x)&{\text{se }}x\in A_{C}\end{cases}}$
(Si può indifferentemente scegliere di definire $h$ pari a $g^{-1}$ su $A_{C}$.)

Voci correlate

• Teorema di Hartogs (teoria degli insiemi)

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file su teorema di Cantor-Bernstein-Schröder

Collegamenti esterni

• 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