Due insiemi E e F hanno la stessa cardinalità, fatto che si indica con Card(E) = Card(F), se esiste una biezione ff da E a F. Si tratta di una relazione di equivalenza sulla classe degli insiemi. Si parla qui di «classe» perché non si può parlare dell’insieme di tutti gli insiemi. Questa relazione è effettivamente riflessiva, simmetrica e transitiva, poiché l’identità è una biezione, l’inversa di una biezione è anch’essa una biezione e lo è anche la composta di due biezioni.
-
L’insieme di tutti gli insiemi --------------------------------
Perché l’insieme di tutti gli insiemi non esiste? L’insieme di tutti gli insiemi sarebbe l’insieme i cui elementi sarebbero tutti gli insiemi. Bertrand Russell dimostra che un oggetto simile non può esistere. Immaginiamo infatti che esista. Per definizione, questo insieme ipotetico appartiene allora a sé stesso. L’affermazione sembra strana, ma perché no? A priori, nessuna logica ci vieta di pensarlo. Per assurdo, consideriamo allora gli insiemi che non appartengono a sé stessi, poi l’insieme di tali insiemi. Dov’è? Se appartiene a sé stesso, non appartiene a sé stesso; e se non appartiene a sé stesso, vi appartiene. Una storia da pazzi, non è vero? Senza precauzioni, è possibile fabbricare chimere di questo genere. Quanto all’insieme di tutti gli insiemi, non insistiamo: va escluso.
Torniamo alle cardinalità. Analogamente, si scrive Card(E) ≤ Card(F) se E ha la stessa cardinalità di un sottoinsieme di F. In questo caso esistono un sottoinsieme E' di F e una biezione ff da E a E'; ff è allora un’iniezione da E in F. Estendendo l’inversa f−1f^{-1} di ff e associando un qualunque elemento di E agli elementi del complementare di E' in F, si ottiene una suriezione da F a E. Si dimostra facilmente che Card(E) ≤ Card(F) equivale all’esistenza di un’iniezione da E in F e a quella di una suriezione da F a E. Queste equivalenze permettono di mostrare facilmente che la relazione di disuguaglianza delle cardinalità sulla classe degli insiemi è riflessiva e transitiva. Il paragrafo seguente dimostra inoltre che è antisimmetrica: è il teorema di Cantor–Bernstein. Se E e F sono due insiemi tali che esistano un’iniezione da E in F e un’iniezione da F in E, allora esiste una biezione da E a F. Si tratta dunque di una relazione d’ordine sulla classe degli insiemi.