1.11 cardinalità

Definizione 1.134 (cardinalità). Diremo che due insiemi e hanno la stessa cardinalitàcardinalità (oppure sono equipotenti) se esiste una funzione bigettiva . Scriveremo in tal caso: Se esiste una funzione iniettiva significa che ha la stessa cardinalità di un sottoinsieme di (in quanto risulta essere bigettiva). Scriveremo in tal caso:

Intuitivamente se due insiemi hanno la stessa cardinalità significa che hanno lo stesso numero di elementi. Ma la precedente definizione riesce a catturare tale concetto senza dover ricorrere al concetto di numero. Questo ha il vantaggio di rendere questa definizione applicabile a qualunque insieme, anche con infiniti elementi.

Si osservi che non abbiamo dato una definizione di e quindi non stiamo definendo cos’è la cardinalità di un insieme ma stiamo soltanto definendo una relazione tra insiemi che denotiamo, impropriamente, utilizzando una uguaglianza: .

E’ ovvio che in quanto l’identità è bigettiva. E’ anche chiaro che se e allora in quanto componendo tra loro due funzioni bigettive si ottiene ancora una funzione bigettiva. Infine se allora (in quanto le funzioni bigettive sono iniettive) ed è chiaro che se e allora (in quanto composizione di funzioni iniettive è iniettiva).

Possiamo definire il simbolo inverso come . Ovviamente se si ha . Se il seguente teorema ci dice che è equivalente a dire che esiste surgettiva.

Teorema 1.135. Sia . Esiste surgettiva se e solo se esiste iniettiva.

Dimostrazione. Da un lato se esiste iniettiva, allora è una bigezione tra e . La funzione inversa Questa funzione si chiama inversa sinistra di in quanto si ha per ogni può essere estesa a tutto fissando un valore qualunque (questo si può fare se non è vuoto) nei punti di ottenendo quindi una funzione surgettiva da in . D’altro lato se esiste una funzione surgettiva, per ogni l’insieme non è mai vuoto e quindi è chiaro che debba esistere una funzione tale che è un qualunque elemento di tale insieme Questa funzione si chiama inversa destra di in quanto per ogni (qui si utilizza l’assioma 1.136 discusso più sotto). Chiaramente è iniettiva. □

Nella dimostrazione del teorema precedente abbiamo utilizzato il seguente assioma della teoria degli insiemi che, sorprendentemente, non è conseguenza degli assiomi che abbiamo già introdotto finora.

Assioma 1.136 (della scelta). Sia una funzione tale che per ogni . Allora esiste una funzione tale che per ogni .

L’assioma della scelta (denotato spesso con , axiom of choice) è un assioma per certi versi controverso e alcuni matematici preferiscono non utilizzarlo nelle loro dimostrazioni. Il sistema formale che definisce la teoria degli insiemi senza introdurre l’assioma della scelta si chiama (Zermelo-Fraenkel) mentre se si aggiunge l’assioma della scelta (choice) la teoria si chiama .

Grazie all’assioma della scelta è anche possibile dimostrare che dati due insiemi e le loro cardinalità si possono confrontare: oppure . La dimostrazione però diventa complicata e va oltre i nostri scopi.

Teorema 1.137. Se e sono insiemi qualunque si ha oppure .

Il seguente teorema dimostra invece la proprietà antisimmetrica della relazione tra cardinalità.

Teorema 1.138. Se e allora .

Dimostrazione. Non è altro che il teorema 1.30 di Cantor-Bernstein. □

Ricordiamo il teorema 1.70 che ci dice che è un insieme finito se e solo se esiste tale che dove abbiamo posto . Ora possiamo osservare che è una abbreviazione di .

La cardinalità di viene a volte indicata con il simbolo dunque potremo scrivere per significare rispettivamente Il simbolo è la prima lettera dell’alfabeto ebraico e si legge aleph.
Ricordiamo (teorema 1.65) che gli insiemi che soddisfano gli assiomi di Peano sono tutti tra loro isomorfi e quindi, in particolare, hanno tutti la stessa cardinalità. Abbiamo già osservato (teorema 1.48) che se è un insieme infinito esiste che soddisfa gli assiomi di Peano. L’inclusione è iniettiva e quindi per qualunque infinito. In questo senso è il più piccolo insieme infinito dunque è la più piccola cardinalità infinita.
Si potrebbe anche dimostrare che deve esistere una cardinalità che è la più piccola cardinalità maggiore di . Sappiamo che ma curiosamente non è possibile dimostrare che (questa si chiama ipotesi del continuo in quanto vedremo nel teorema 1.142 che e l’insieme viene chiamato continuo là dove viene chiamato discreto). Dunque l’ipotesi del continuo è un ulteriore assioma che potrebbe essere aggiunto agli assiomi della teoria degli insiemi: non esistono insiemi con cardinalità strettamente compresa tra le cardinalità di e di .

Abbiamo già osservato che è un insieme infinito e dunque anche , e sono infiniti. Per gli insiemi finiti se ma risulta in quanto . Dobbiamo però osservare che lo stesso non vale per gli insiemi infiniti. In effetti la funzione definita da risulta essere una bigezione tra e . Dunque nonostante la differenza tra i due insiemi abbia cardinalità . Anche l’insieme dei numeri pari o l’insieme dei quadrati perfetti (come aveva notato già Galileo) hanno la stessa cardinalità di in quanto le funzioni e la funzione sono iniettive.

Non è difficile trovare una funzione iniettiva da in (lo lasciamo per esercizio): questo dimostra che anche .

Cantor dimostra addirittura che : per farlo utilizza il seguente.

Teorema 1.139 (primo metodo diagonale di Cantor). L’insieme ha la stessa cardinalità di . Di conseguenza

Idea di dimostrazione. Numerare le caselle di una scacchiera infinita come in Figura 1.10.

Visto che è piuttosto facile trovare una funzione iniettiva da in si deduce facilmente che . □

3 9
2 5 8 12
1 2 4 7 11
0 0 1 3 6 10
0 1 2 3 4
Figura 1.10: La numerazione diagonale delle caselle di una scacchiera infinita. Si potrebbe verificare che il numero presente nella casella di coordinate si scrive come ed è una funzione bigettiva .

A questo punto si potrebbe pensare che tutti gli insiemi infiniti siano numerabili. Invece preso un qualunque insieme (anche infinito) esiste sempre un insieme con cardinalità maggiore, come dimostrato nel seguente teorema che è un piccolo gioiello della logica. In effetti il metodo utilizzato è assimilabile al paradosso del mentitore ed è la stessa idea usata nel paradosso di Russell (teorema 1.11). L’insieme è l’insieme delle parti, definito a pag. 40

Teorema 1.140 (Cantor). Se è un qualunque insieme allora .

Dimostrazione. E’ chiaro che in quanto la funzione definita da è ovviamente iniettiva.

Supponiamo allora per assurdo che esista bigettiva e consideriamo l’insieme Se fosse surgettiva dovrebbe esistere tale che . Possiamo allora chiederci se e scoprire che, per definizione di la proposizione è equivalente a . Dunque , che è assurdo. □

Corollario 1.141 (non esiste l’insieme di tutti gli insiemi). Se esistesse un insieme (universo) tale che , allora si avrebbe contraddicendo il teorema precedente.

Per quanto riguarda l’insieme si scopre in effetti che (sempre grazie a Cantor, teorema 1.142 qui sotto) e si potrebbe dimostrare che effettivamente .

Teorema 1.142 (secondo metodo diagonale di Cantor). L’insieme di Cantor ha cardinalità In particolare .

Dimostrazione. Consideriamo la funzione definita nel capitolo 3.3 che associa ad una sequenza di cifre binarie il corrispondente numero reale. Vogliamo verificare che è iniettiva. Abbiamo già visto in generale che solamente se la prima cifra diversa in e differisce di una unità. Ma siccome tutte le cifre di e per ipotesi sono oppure , non differiscono di una unità e quindi è iniettiva. Dunque . D’altra parte in quanto ogni può essere messo in corrispondenza biunivoca con l’insieme degli indici per cui .

Dal teorema 1.140 deduciamo che e visto che a maggior ragione .

D’altra parte possiamo mostrare che in quanto possiamo costruire una funzione in questo modo: Per la densità di in sappiamo che se esiste con e dunque da cui . Dunque è iniettiva, che significa Ma dunque e la dimostrazione è conclusa. □

L’insieme definito nella precedente dimostrazione con è lo stesso insieme di Cantorinsieme di Cantor considerato nell’esempio 6.86. Infatti si potrebbe mostrare facilmente che .