Verso l'infinito, ma con calma - la cardinalità dell'insieme delle parti

Ora andiamo sul difficile, vogliamo dimostrare che se la cardinalità di un insieme A è uguale a α, allora la cardinalità del suo insieme delle parti P(A) è uguale a 2^α.

La dimostrazione segue questa strada: si vuole far vedere che l'insieme delle funzioni che vanno da A nell'insieme {0,1} è in corrispondenza biunivoca con P(A).

“Insieme di funzioni? Ma le funzioni sono particolari relazioni, cioè a loro volta sono insiemi. Mi sa che stiamo astraendo troppo”.

“L'avevo detto che era difficile. Proviamo a ragionare con un esempio: immagina di avere davanti a te tutti gli oggetti che fanno parte di A”.

“Va bene. Finiti o infiniti?”.

“Per adesso non importa. Per comodità, pensa che siano finiti, ma non è indispensabile”.

“Ok. Ora che faccio?”.

“Ora immagina che a ogni oggetto sia associata una lampadina, che tu puoi accendere o spegnere a tuo piacimento”.

“Bene, fin qua è facile”.

“Ora pensa di accendere qualche lampadina, quelle che vuoi tu, come vuoi tu”.

“Fatto”.

“Perfetto. Hai associato a ogni elemento di A una lampadina, accesa o spenta”.

“Vero”.

“Se la lampadina accesa rappresenta un 1, e la lampadina spenta rappresenta uno 0, hai associato a ogni elemento di A uno 0 oppure un 1”.

“Ho capito! Ho costruito una funzione che va da A all'insieme {0,1}”.

“Bene. Ora ascolta: in quanti modi puoi creare una sequenza di lampadine accese o spente associate agli elementi di A? Supponiamo per ora che A sia finito”.

“Questa è difficile”.

“No, ragiona in questo modo: per quanto riguarda la prima lampadina, quante possibilità hai?”.

“Beh, 2, o è accesa o spenta”.

“Per quanto riguarda la seconda?”.

“Ancora 2”.

“Quindi, se metti insieme la prima e la seconda lampadina, hai 2 possibilità per la prima, e per ognuna di queste 2 possibilità ne hai altre 2 per la seconda”.

“Totale 4?”.

“Certo. Se vuoi te le elenco: 00, 01, 10, 11”.

“Mh, mi ricorda la numerazione binaria. Se aggiungo una terza lampadina, allora, potrei avere uno 0 da associare a queste quattro possibilità, oppure un 1. Otterrei 000, 001, 010, 011 e poi 100, 101, 110, 111. Totale 8. Ogni volta che aggiungo una lampadina moltiplico per 2!”.

“Bene, quindi se in A ci sono α elementi, hai 2^α modi di accendere le lampadine. E cioè, hai 2^α funzioni che vanno da A a {0,1}”.

“Ok, ho capito, detto così non è difficile”.

“La matematica non è mai difficile quando la capisci”.

“Permettimi di non commentare e andiamo avanti”.

“Ora vogliamo dimostrare che questo insieme di funzioni è in corrispondenza biunivoca con P(A)”.

“E come facciamo?”.

“Facciamo così: ad ogni successione di lampadine (cioè ad ogni funzione) associamo l'insieme che contiene solo gli elementi per le quali le lampadine sono accese”.

“Credo di aver capito, ma se ci fosse un esempio sarebbe meglio”.

“Va bene. Prendiamo un insieme facile: {a,b}. Ora costruisci tu tutte le funzioni che vanno da questo insieme a {0,1}”.

“Allora, posso associare a a 0 e b a 0. Oppure a a 0 e b a 1. Forse è meglio se faccio uno schema. Eccolo qua, ho numerato le quattro funzioni”.

f1  f2  f3  f4
a-0 a-0 a-1 a-1
b-0 b-1 b-0 b-1

“Perfetto. Ora scegline una”.

“La numero 2. Era il voto preferito del mio prof di matematica”.

“Va bene. La funzione f₂ accende solo una lampadina, quella di b. Quindi ad essa associamo l'insieme {b}”.

“Mh. Forse ho capito. La funzione f₁ è associata all'insieme vuoto, perché non accende lampadine?”.

“Giusto. Provi a fare uno schema anche per questa corrispondenza tra funzioni e insiemi?”.

“Ok, ecco qua:”.

f1 - {}
f2 - {b}
f3 - {a}
f4 - {a,b}

“Molto bene. Hai notato che hai elencato tutti i sottoinsiemi dell'insieme da cui siamo partiti, cioé {a,b}?”.

“Vedo. Ma siamo sicuri che non sia un caso?”.

“No, è vero in generale: se prendi due modi diversi di accendere le lampadine, troverai certamente due insiemi diversi. Viceversa, se prendi due insiemi diversi, essi ti daranno modi diversi di accendere le lampadine. Insomma, le lampadine accese corrispondono agli elementi: stesse lampadine, stessi elementi; stessi elementi, stesse lampadine”.

“Va bene”.

“E tieni presente che questa dimostrazione vale anche per il caso infinito. Cioè, puoi mettere in corrispondenza biunivoca i due insiemi delle funzioni da A in {0,1} e P(A) anche se A è infinito. Chiaramente non potrai calcolare 2^α in questo caso. Però si può dimostrare che il cardinale transfinito α è minore del cardinale transfinito 2^α”.

“Non me lo lasci come esercizio, vero?”.

“No, questo è difficile. Lo vediamo la prossima volta”.