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

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

Esiste una funzione iniettiva da ${\displaystyle A}$ in ${\displaystyle B}$.

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

Esiste una funzione biiettiva da ${\displaystyle A}$ in ${\displaystyle B}$.

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

Se ${\displaystyle |A|\leq |B|}$ e ${\displaystyle |B|\leq |A|}$, allora ${\displaystyle |A|=|B|}$

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

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

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 ${\displaystyle x}$ di ${\displaystyle A}$ ha un precedente ${\displaystyle y}$ in ${\displaystyle B}$ se ${\displaystyle x=g(y)}$
• un punto ${\displaystyle y}$ di ${\displaystyle B}$ ha un precedente ${\displaystyle z}$ in ${\displaystyle A}$ se ${\displaystyle 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 ${\displaystyle A}$ in una partizione come:

• ${\displaystyle A_{A}}$ è l'insieme dei punti di ${\displaystyle A}$ che hanno un primo precedente in ${\displaystyle A}$;
• ${\displaystyle A_{B}}$ è l'insieme dei punti di ${\displaystyle A}$ che hanno un primo precedente in ${\displaystyle B}$;
• ${\displaystyle A_{C}}$ è l'insieme dei punti di ${\displaystyle 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 ${\displaystyle A}$ e ${\displaystyle B}$
${\displaystyle 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 ${\displaystyle h}$ pari a ${\displaystyle g^{-1}}$ su ${\displaystyle A_{C}}$.)

• Teorema di Hartogs (teoria degli insiemi)

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

• 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

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