Il metodo della diagonale di Cantor
Benvenuta/o nella nostra guida sul metodo della diagonale di Cantor.
Questa procedura ha permesso di scoprire che l’insieme dei numeri reali non è numerabile, cioè che i reali sono “più numerosi” dei numeri naturali, portando alla conclusione sorprendente che esistono diverse tipologie di “infinito”.
Questo articolo è una “passeggiata in diagonale”, una guida essenziale e chiara che esplora le seguenti domande:
- Come si confrontano gli insiemi infiniti?
- Gli insiemi numerici più comuni hanno diverse “cardinalità”?
- Esistono insiemi infiniti sempre “più grandi”?
- Quali proprietà degli insiemi finiti si trasferiscono agli insiemi infiniti?
A queste domande si può rispondere con la semplice ma geniale procedura diagonale ideata da Cantor, oltre che con la nozione di equipotenza e col teorema di Cantor-Bernstein.
Se a questo punto sei curioso di scoprire di cosa si tratta, non ti resta che cominciare la lettura!
Oltre all’esaustiva lista di materiale reperibile alla fine della pagina, consigliamo la lettura dei seguenti articoli:
- Insiemi Numerici ;
- L’insieme dei numeri reali: costruzione e applicazioni;
- Il principio di induzione;
- Costruzioni alternative di .
Autori e revisori
Mostra autori e revisori.
Introduzione
Leggi...
Fu Georg Cantor (1845-1918) a riconoscere che, in realtà, questa concezione era sbagliata e che nella matematica erano presenti insiemi infiniti essenzialmente diversi.
Per confrontare la cardinalità di insiemi, concetto che corrisponde al numero di elementi che vi appartengono, Cantor propose un metodo valido anche anche quando, come nel caso degli insiemi infiniti, non è possibile contarli per stabilire quale sia il maggiore tra i due.
Il sistema proposto da Cantor è semplice quanto geniale: dati due insiemi e , diciamo che essi hanno la stessa cardinalità se i loro elementi possono essere messi in una corrispondenza uno a uno; in termini matematici, ciò corrisponde a richiedere che esista una funzione biunivoca. Se ciò avviene, si può dire che e sono equipotenti.
Se e sono finiti, questo è equivalente a dire che e hanno lo stesso numero di elementi; ma il particolare che rende questa idea geniale risiede nel fatto che questa caratterizzazione funziona benissimo anche nel caso in cui e siano infiniti.
Utilizzando questa idea, Cantor confrontò gli insiemi infiniti allora noti e dimostrò che l’insieme dei numeri razionali è equipotente all’insieme dei numeri naturali , evidenziando la caratteristica controintuitiva degli insiemi infiniti di essere equipotenti a un suo sottoinsieme proprio.
Tutto ciò divenne ancor più interessante quando egli non riuscì a mettere in corrispondenza biunivoca i numeri naturali con i numeri reali e anzi, si rese conto che questo era impossibile: dimostrò cioè che non esiste alcuna funzione biunivoca , dimostrando cioè che l’infinito di è “essenzialmente più grande” di quello di . Per ottenere questo risultato, Cantor ideò quello che oggi viene chiamato in suo onore processo diagonale di Cantor; con tale metodo è possibile inoltre mostrare che, dato un qualsiasi insieme , il suo insieme delle parti ha sempre cardinalità maggiore di . Questo risultato viene oggi chiamato proprio teorema di Cantor, in quanto generalizza la dimostrazione della non numerabilità dei numeri reali.
Iterando questo risultato si vede facilmente che esistono infinite cardinalità infinite, oltre a quella dei numeri naturali e dei reali. Si possono costruire, cioè, insiemi infiniti arbitrariamente più grandi.
È interessante notare che la scoperta di Cantor dell’esistenza di diverse cardinalità infinite fu inizialmente osteggiata e quasi derisa dall’ambiente matematico dell’epoca.
Nonostante ciò, il processo diagonale ha trovato applicazione in molti campi della Matematica del ‘900: esso compare, ad esempio, anche nella dimostrazione di Gödel dei suoi celebri teoremi di incompletezza [1] e nella dimostrazione di Turing che il problema della fermata non può essere risolto [1]
Notazioni
Leggi...
Insieme dei numeri interi:
Insieme dei numeri razionali
Insieme dei numeri reali
Insieme delle parti dell’insieme
Funzione da in
Insieme delle funzioni da in
Se : immersione di in
Se è una funzione e : immagine tramite di
Se è una funzione e : controimmagine tramite di ;
e sono equipotenti (definizione 1)
e non sono equipotenti (definizione 1)
Cardinalità di minore o uguale alla cardinalità di ;
Insiemi infiniti
Leggi...
(1)
Il lettore può trovare maggiori dettagli in [3]. Poiché i numeri naturali servono proprio a contare gli oggetti, ciò li forza in qualche modo a essere infiniti; infatti, si può sempre costruire un insieme più grande aggiungendo qualche elemento.
non è chiaramente l’unico insieme infinito; ad esempio, l’insieme dei numeri naturali pari
(2)
è infinito. Più in generale, ogni sottoinsieme che non è limitato superiormente (cioè a cui appartengono numeri arbitrariamente grandi) è infinito. Tutti questi insiemi sono appunto contenuti in . Esistono anche insiemi infiniti che contengono ; come esempio citiamo l’insieme dei numeri interi:
(3)
Vi è poi l’insieme dei numeri razionali, cioè delle frazioni di numeri interi:
(4)
Scegliendo nella frazione , si vede che contiene (e quindi ). Vi è poi l’insieme dei numeri reali ; senza entrare nei dettagli di una costruzione formale di , un numero reale può essere pensato come una stringa infinita di cifre in base 10 che non termini in una sequenza infinitamente ripetuta di cifre 9:
(5)
Nella scrittura (5), le cifre rappresentano la parte intera del numero reale, mentre la stringa (infinita) ne rappresenta la parte decimale. Occorre escludere le scritture terminanti in una serie infinita di cifre 9 in quanto esse rappresentano lo stesso numero reale di una stringa terminante in una serie infinita di cifre 0:
(6)
Poiché ogni numero razionale ha una scrittura decimale (e si può vedere che essa rappresenta un numero razionale se e solo se è periodica 1 ), si ha . L’inclusione è in realtà stretta, in quanto appunto, considerando scritture decimali non periodiche, si ottengono i cosiddetti numeri reali irrazionali. Quindi .
Riassumiamo la serie di insiemi numerici presentati osservando anche i relativi rapporti di inclusione:
(7)
Viene spontaneo chiedersi se si possano confrontare tra di loro questi insiemi in termini di cardinalità, nonostante i loro rapporti di inclusione ci dicano intuitivamente che, sicuramente, quelli a destra sono “almeno grandi quanto” quelli a sinistra.
- Per scrittura periodica intendiamo anche scritture terminanti con una sequenza infinita di cifre 0, come ad esempio quella in (6) ↩
Equipotenza e insiemi numerabili
Leggi...
Osservazione 2. La definizione 1 è un’estensione del concetto di “avere lo stesso numero di elementi” valida per insiemi finiti. Infatti, se e hanno elementi, ciò vuol dire che esistono due funzioni e biunivoche. Pertanto, la funzione è biunivoca. Ovviamente, se e sono infiniti, non ha senso chiedersi quanti elementi abbiano, però l’esistenza di una funzione biunivoca tra e ci permette di dire che i loro elementi possono essere comunque messi in una corrispondenza “uno a uno”; il concetto di equipotenza, quindi, è un’estensione di “avere lo stesso numero di elementi” a insiemi possibilmente infiniti.
Per tale ragione, l’equipotenza possiede molte delle proprietà della relazione di “avere la stessa cardinalità”. Ne elenchiamo alcune nella seguente proposizione.
- ;
- se e solo se ;
- e , allora .
Osservazione 4. In altre parole, la proposizione 3 afferma che la relazione tra insiemi è una relazione di equivalenza.
Dimostrazione della proposizione 3. La dimostrazione è molto semplice e sfrutta semplicemente la definizione 1.
- La funzione (si veda [2, Definizione 2.18]) è biunivoca;
- Se è biunivoca, allora è di nuovo biunivoca.
- Se è biunivoca e se è biunivoca, allora è biunivoca.
A volte, oltre che stabilire se le cardinalità di due insiemi anche infiniti sono uguali, può essere conveniente capire se uno dei due ha una cardinalità minore o uguale a quella dell’altro. Lo strumento che permette di effettuare questo confronto è costituito dalle funzioni iniettive.
Osservazione 6. La definizione 5 è un’estensione del concetto “ possiede al più tanti elementi quanti ne ha ” valido nel caso di insiemi finiti. Infatti, l’esistenza di una funzione iniettiva tra e significa che si possono mettere in corrispondenza biunivoca gli elementi di con il sottoinsieme (non necessariamente proprio) di .
Osservazione 7. In generale, se esiste una funzione iniettiva ma non biunivoca, ciò non vuol dire che . Infatti, come vedremo in seguito, l’insieme dei numeri pari è equipotente a , pur esistendo una funzione iniettiva ma non suriettiva da in , ossia l’immersione definita4 da
(8)
Come abbiamo osservato, in qualche senso il prototipo di insieme infinito è costituito dall’insieme dei numeri naturali. È quindi naturale stabilire una terminologia per indicare gli insiemi infiniti equipotenti a .
- si dice numerabile se è equipotente all’insieme dei numeri naturali.
- si dice al più numerabile se .
- si dice invece più che numerabile se non è numerabile ed esiste una funzione iniettiva.
Un insieme numerabile quindi ha la stessa cardinalità di , un insieme al più numerabile ha cardinalità al più pari a quella di , mentre un insieme più che numerabile ha cardinalità strettamente maggiore di quella di .
Nella prossima sezione faremo alcuni esempi di insiemi numerabili, mentre nella sezione “L’insieme dei numeri reali è più che numerabile”, mostreremo che l’intervallo e l’insieme dei numeri reali sono più che numerabili.
Esempi di insiemi numerabili
Leggi...
Dimostrazione. Consideriamo la funzione definita da
(9)
La funzione è chiaramente biunivoca: è iniettiva in quanto se e solo se , ed è suriettiva poiché ogni numero pari si ottiene appunto come doppio di un numero naturale. Pertanto .
Vale la seguente generalizzazione della proposizione 9.
Dimostrazione. Si costruirà una funzione biunivoca.
- Costruzione di .
Definiamo per induzione: poniamo e, supponendo definito per ogni , poniamo
(10)
Poiché non è superiormente limitato mentre è finito, l’insieme non è vuoto, quindi è ben definito per ogni .
- è strettamente crescente; in particolare, è iniettiva.
Infatti, per (10) si ha
(11)
(12)
- per ogni .
Poiché , si ha . Supponiamo ora che ; per la stretta monotonia di provata al punto precedente otteniamo . Per induzione si ha quindi
(13)
- è suriettiva.
Supponiamo per assurdo che non sia suriettiva; allora l’insieme sarebbe non vuoto, e quindi esisterebbe
(14)
Si proverà per induzione che per ogni numero naturale , chiaramente una contraddizione.
Poiché , si ha .
Supponiamo ora che per qualche . Poiché , si ha
(15)
Per induzione si è provato quindi che per ogni e, per (13), si ottiene
(16)
che contraddice il fatto che . Tale contraddizione mostra che l’insieme è vuoto, cioè che è suriettiva.
Da queste considerazioni segue che è biunivoca, cioè .
Mostriamo ora che esistono insiemi numerabili che contengono l’insieme dei numeri naturali: l’insieme dei numeri interi, pur contenendo intuitivamente “il doppio” degli elementi di , è in realtà equipotente a , come mostra la prossima proposizione.
Dimostrazione. Consideriamo la funzione definita da
(17)
In altre parole, alterna un valore positivo a uno negativo partendo da e allontanandosi nella direzione dei numeri positivi per pari, e in quella dei numeri negativi per dispari.
Dalla definizione è chiaro che è iniettiva, mentre il fatto che è suriettiva segue dal fatto che ogni numero positivo si ottiene come per qualche numero naturale pari, mentre ogni numero negativo si ottiene come per qualche numero naturale dispari. Poiché è biunivoca, si ha .
Anche l’insieme dei numeri razionali è numerabile, come mostra la seguente proposizione.
Dimostrazione. L’idea della dimostrazione consiste nel costruire una funzione iniettiva; in tal modo si avrà che . Si userà poi la proposizione 10 per provare che .
- Costruzione di iniettiva. Osserviamo che ogni numero razionale si può esprimere in modo unico nella forma
(18)
Pertanto, risulta ben definita la funzione data da
(19)
dove sono definiti in (18).
Se sono tali che , dal teorema fondamentale dell’Aritmetica segue che , quindi è iniettiva. Essa non è però suriettiva, in quanto ad esempio .
-
Poiché è iniettiva, la funzione definita da
(20)
rimane iniettiva ed è anche ovviamente suriettiva, pertanto è biettiva. Quindi
(21)
Poiché è infinito, anche lo è, ed è quindi superiormente illimitato. Dalla proposizione 10, segue che .
Poiché ogni numero razionale è sostanzialmente identificato da una coppia di numeri interi, la dimostrazione della proposizione 12 può essere facilmente modificata (il lettore può farlo per esercizio) per provare il prossimo risultato.
Poiché i numeri razionali sembrano infinitamente più numerosi dei numeri naturali, l’enunciato della proposizione 12 può apparire a prima vista controintuitivo. Una volta però che ci si è convinti della sua verità, si potrebbe essere portati a pensare che ogni insieme infinito sia numerabile. Ciò è falso: come mostrato nella prossima sezione, l’insieme dei numeri reali non è numerabile.
L’insieme dei numeri reali è più che numerabile
Leggi...
Occorre quindi trovare una strategia che mostri che nessuna funzione possa essere biunivoca. Ciò è proprio quanto ottenne Cantor utilizzando il suo metodo della diagonale .
Dimostrazione.
- .
Si consideri la funzione definita da
(22)
Per come è definita, chiaramente la funzione è iniettiva, quindi per la definizione 2.
- , con 5
Sia l’insieme delle successioni a valori in che non terminino con una sequenza infinita di cifre . Formalmente è l’insieme delle funzioni tali che
(23)
dove abbiamo indicato con l’elemento -esimo della successione , ossia .
Osserviamo che ogni successione determina il numero reale il cui sviluppo decimale coincide con gli elementi della successione :
(24)
Tale corrispondenza è suriettiva, in quanto ogni numero possiede uno sviluppo decimale le cui cifre costituiscono una successione in ; inoltre la corrispondenza è iniettiva in quanto si sono escluse le successioni definitivamente pari a 9, che determinerebbero gli stessi numeri reali di successioni definitivamente pari a 0. Pertanto .
- .
Fissiamo una qualunque funzione e dimostriamo che non è suriettiva.
La funzione associa a ogni numero naturale una successione non terminate con una serie infinita di 9, i cui elementi sono al variare di ; possiamo rappresentare questa situazione in una tabella:
Ad esempio si potrebbe avere
Cioè rappresenterebbe il numero , rappresenterebbe , …
Costruiamo ora una funzione definita da
(25)
In altre parole, è la successione costruita cambiando tutti gli elementi della diagonale evidenziati nella tabella. Poiché assume solo valori 4 e 5, sicuramente .
Inoltre, poiché per ogni , si ha
(26)
Ciò mostra che non appartiene all’immagine di , e quindi non è suriettiva. Per cui (e quindi anche ) non è numerabile.
Una conseguenza del teorema 14 è che, come si può intuire, anche è più che numerabile. Si dedurrà questo fatto dalla seguente proposizione di carattere più generale.
Dimostrazione. Poiché è più che numerabile, esiste una funzione iniettiva. Allora anche la funzione è iniettiva, dove è l’immersione6 di in definita da
(27)
Pertanto, per mostrare che è più che numerabile, basta dimostrare che ogni funzione iniettiva non è suriettiva.
Sia quindi una qualsiasi funzione iniettiva e mostriamo che non è suriettiva.
Consideriamo l’insieme dei numeri naturali la cui immagine tramite appartiene ad , ossia, in termini formali, la controimmagine dell’insieme tramite :
(28)
Poiché è iniettiva, la funzione definita da
(29)
è iniettiva; essa non può però essere suriettiva, altrimenti sarebbe una biezione e sarebbe equipotente al sottoinsieme di , che per la proposizione 10 è finito o numerabile, mentre è più che numerabile.
Pertanto non è suriettiva e per la definizione di , ciò implica che esistono elementi di che non sono immagine di alcun numero naturale tramite , cioè neanche è suriettiva.
Per l’arbitrarietà di , si ha che non è numerabile e dalle considerazioni iniziali segue quindi che esso è più che numerabile.
Dimostrazione. La tesi è una conseguenza immediata del teorema 14 e della proposizione 15 applicata al caso e .
In realtà, vale la tesi, più forte della precedente, che e sono equipotenti. La dimostreremo in appendice A, come conseguenza del notevole teorema 18.
Insiemi infiniti di cardinalità diversa
Leggi...
(30)
Dimostrazione.
- .
Si consideri la funzione definita da
(31)
In altre parole, la funzione associa all’elemento di il sottoinsieme di . Per come è definita, chiaramente la funzione è iniettiva, quindi per la definizione 5.
- .
Osserviamo che ogni funzione determina il sottoinsieme cui appartengono tutti e soli gli elementi di su cui vale :
(32)
La corrispondenza è chiaramente biunivoca. Pertanto .
- . Fissiamo una qualunque funzione e dimostriamo che non è suriettiva.
La funzione associa a ogni elemento una funzione , le cui immagini sono al variare di ; possiamo rappresentare questa situazione in una tabella:
Costruiamo ora una funzione definita da
(33)
In altre parole, è la funzione costruita cambiando tutti gli elementi della diagonale evidenziati nella tabella.
Poiché per ogni si ha
(34)
Ciò mostra che non appartiene all’immagine di , e quindi non è suriettiva. Per cui (e quindi ) non è equipotente ad .
Osservazione 16. Considerando che ogni funzione determina un sottoinsieme di , la funzione determina l’insieme definito da
(35)
L’insieme ricorda quello del famoso paradosso di Russell . Il lettore può provare per esercizio a costruire l’insieme protagonista del paradosso effettuando tale costruzione col metodo della diagonale di Cantor.
Considerando che ogni funzione determina un sottoinsieme di , la funzione determina l’insieme definito da
(36)
L’insieme ricorda quello del famoso paradosso di Russell. Il lettore può provare per esercizio a costruire l’insieme protagonista del paradosso effettuando tale costruzione col metodo della diagonale di Cantor. Partendo da un qualunque insieme infinito e applicando iterativamente il teorema 15, si ottiene che la successione di insiemi
(37)
è costituita da insiemi con cardinalità via via maggiori; ciò prova che, se esiste un insieme infinito, allora esistono infinite cardinalità infinite diverse.
Il teorema di Cantor-Bernstein
Leggi...
Dimostrazione. Definiamo per ricorrenza gli insiemi e ; poniamo e . Supponiamo ora definiti e e poniamo
(38)
Definiamo poi
(39)
Dalla costruzione si ha che
(40)
(41)
dove nella terza uguaglianza si è usato che e che per .
Definiamo ora la funzione ottenuta ponendo (si veda la figura 1).
(42)
dove con si è indicato l’unico elemento tale che . Poiché , risulta ben definita.
Figura 1: costruzione della funzione h nella dimostrazione del teorema 18
.
Osserviamo che, per l’iniettività di e e per la definizione degli e , è una biezione tra e per ogni , mentre è una biezione tra e per ogni . Inoltre, sempre per l’iniettività di e per (41), è una biezione tra e . Per questi motivi, è biettiva.
Usando il teorema 18 si ottiene che e sono equipotenti.
Dimostrazione. Consideriamo le funzioni e definite da
(43)
Esse sono entrambe iniettive. Per il teorema 18, si ha .
Riferimenti bibliografici
[1] Hofstadter, D. R., Gödel, Escher, Bach: un’Eterna Ghirlanda Brillante; Adelphi (1984)
[2] Qui Si Risolve, Funzioni elementari – Volume 1 .
[3] Qui Si Risolve, Insiemi numerici .