Teorema di Cantor-Bernstein-Schröder

Da Wikipedia, l'enciclopedia libera.

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

Presupposti e conseguenze del teorema[modifica | modifica sorgente]

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[modifica | modifica sorgente]

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 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[modifica | modifica sorgente]

Collegamenti esterni[modifica | modifica sorgente]

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