Il metodo della diagonale di Cantor

Home » 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:

Autori e revisori

Mostra autori e revisori.

Autori: Luigi De Masi, Daniele Fakhoury.

Revisori: Valerio Brunetti, Chiara Bellotti, Matteo Talluri, Sergio Fiorucci, Davide La Manna.

$\,$

Introduzione

Leggi...

Il concetto di infinito è sicuramente tra i più affascinanti e al tempo stesso controversi della matematica. Il fatto che l’infinito sia fuori dalla portata delle azioni umane aveva portato i pensatori e i matematici alla convinzione che non vi fosse possibilità di esistenza di diversi tipi di infinito.

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 $A$ e $B$ , 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 $f \colon A \to B$ biunivoca. Se ciò avviene, si può dire che $A$ e $B$ sono equipotenti.

Se $A$ e $B$ sono finiti, questo è equivalente a dire che $A$ e $B$ 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 $A$ e $B$ siano infiniti.

Utilizzando questa idea, Cantor confrontò gli insiemi infiniti allora noti e dimostrò che l’insieme dei numeri razionali $\mathbb{Q}$ è equipotente all’insieme dei numeri naturali $\mathbb{N}$ , 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 $f \colon \mathbb{N} \to \mathbb{R}$ , dimostrando cioè che l’infinito di $\mathbb{R}$ è “essenzialmente più grande” di quello di $\mathbb{N}$ . 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 $A$ , il suo insieme delle parti $\mathcal{P}(A)$ ha sempre cardinalità maggiore di $A$ . 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...

$\mathbb{N}$

$\mathbb{Z}$

$\mathbb{Q}$

$\mathbb{R}$

$\mathcal{P}(A)$

$f \colon A \to B$

$B^A$

$\iota \colon A\to B$

$f(X)$

$f^{-1}(Y)$

$A \cong B$

$A \ncong B$

$|A|\leq |B|$

Insieme dei numeri naturali: $\{0,1,2,3,4,\dots\}$

Insieme dei numeri interi: $\{\dots,-2,-1,0,1,2,\dots\}$

Insieme dei numeri razionali

Insieme dei numeri reali

Insieme delle parti dell’insieme $A$

Funzione da $A$ in $B$

Insieme delle funzioni da $A$ in $B$

Se $A \subseteq B$ : immersione di $A$ in $B$

Se $f \colon A \to B$ è una funzione e $X \subseteq A$ : immagine tramite $f$ di $X$

Se $f \colon A \to B$ è una funzione e $Y \subseteq B$ : controimmagine tramite $f$ di $Y$ ;

$A$ e $B$ sono equipotenti (definizione 1)

$A$ e $B$ non sono equipotenti (definizione 1)

Cardinalità di $A$ minore o uguale alla cardinalità di $B$ ;

$\,$

$\quad$

$\,$

Insiemi infiniti

Leggi...

L’insieme infinito più famoso, tanto da far parte della cultura comune, è quello dei numeri naturali:

(1) $\begin{equation*} \mathbb{N}=\{0,1,2,3,4,\dots\}. \end{equation*}$

$\,$

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.

$\mathbb{N}$ non è chiaramente l’unico insieme infinito; ad esempio, l’insieme dei numeri naturali pari

(2) $\begin{equation*} 2\mathbb{N}=\{0,2,4,6,\dots\} \end{equation*}$

è infinito. Più in generale, ogni sottoinsieme $A \subseteq \mathbb{N}$ che non è limitato superiormente (cioè a cui appartengono numeri arbitrariamente grandi) è infinito. Tutti questi insiemi sono appunto contenuti in $\mathbb{N}$ . Esistono anche insiemi infiniti che contengono $\mathbb{N}$ ; come esempio citiamo l’insieme $\mathbb{Z}$ dei numeri interi:

(3) $\begin{equation*} \mathbb{Z}=\{\dots,-2,-1,0,1,2,\dots\}. \end{equation*}$

$\,$

Vi è poi l’insieme $\mathbb{Q}$ dei numeri razionali, cioè delle frazioni di numeri interi:

(4) $\begin{equation*} \mathbb{Q}=\Big\{ \frac{m}{n} \colon m \in \mathbb{Z},\,\, n \in \mathbb{N}\setminus \{ 0\} \Big\}. \end{equation*}$

$\,$

Scegliendo $n=1$ nella frazione $\frac{m}{n}$ , si vede che $\mathbb{Q}$ contiene $\mathbb{Z}$ (e quindi $\mathbb{N}$ ). Vi è poi l’insieme dei numeri reali $\mathbb{R}$ ; senza entrare nei dettagli di una costruzione formale di $\mathbb{R}$ , un numero reale $x$ può essere pensato come una stringa infinita di cifre in base 10 che non termini in una sequenza infinitamente ripetuta di cifre 9:

(5) $\begin{equation*} \mathbb{R}=\big\{ b_n b_{n-1}\dots b_1 b_0,a_1 a_2 \dots \colon n \in \mathbb{N},\,\, b_i,a_j \in \{0,1,\dots,9\},\, a_j \text{ non definitivamente pari a 9} \big\}. \end{equation*}$

$\,$

Nella scrittura (5), le cifre $b_n,\dots,b_0$ rappresentano la parte intera del numero reale, mentre la stringa (infinita) $a_1 \, a_2\dots$ 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) $\begin{equation*} \text{45,30000000}\dots {} = \text{45,29999999}\dots. \end{equation*}$

$\,$

Poiché ogni numero razionale ha una scrittura decimale (e si può vedere che essa rappresenta un numero razionale se e solo se è periodica ¹ ), si ha $\mathbb{Q}\subseteq \mathbb{R}$ . L’inclusione è in realtà stretta, in quanto appunto, considerando scritture decimali non periodiche, si ottengono i cosiddetti numeri reali irrazionali. Quindi $\mathbb{Q} \subsetneq \mathbb{R}$ .

Riassumiamo la serie di insiemi numerici presentati osservando anche i relativi rapporti di inclusione:

(7) $\begin{equation*} 2\mathbb{N} \subset \mathbb{N} \subset \mathbb{Z} \subset \mathbb{Q} \subset \mathbb{R}. \end{equation*}$

$\,$

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...

Presentiamo l’idea fondamentale di Cantor affinché due insiemi siano equivalenti dal punto di vista della cardinalità, ossia la nozione di equipotenza.

Definizione 1. Due insiemi non vuoti $A,B$

si dicono equipotenti se esiste una funzione $f \colon A \to B$

biunivoca ² . In tal caso si scrive $A \cong B$

oppure $|A|=|B|$

. Se $A$

e $B$

non sono equipotenti, scriviamo $A \ncong B$

oppure $|A| \neq |B|$

Osservazione 2. La definizione 1 è un’estensione del concetto di “avere lo stesso numero di elementi” valida per insiemi finiti. Infatti, se $A$ e $B$ hanno $n$ elementi, ciò vuol dire che esistono due funzioni $f_A \colon A \to \{1,\dots,n\}$ e $f_B \colon B \to \{1,\dots,n\}$ biunivoche. Pertanto, la funzione $(f_B)^{-1}\circ f_A \colon A \to B$ è biunivoca. Ovviamente, se $A$ e $B$ sono infiniti, non ha senso chiedersi quanti elementi abbiano, però l’esistenza di una funzione biunivoca tra $A$ e $B$ 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.

Proposizione 3. Siano $A,B,C$

insiemi non vuoti. Allora:

$A \cong A$ ;
$A \cong B$ se e solo se $B \cong A$ ;
$A \cong B$ e $B \cong C$ , allora $A \cong C$ .

Osservazione 4. In altre parole, la proposizione 3 afferma che la relazione $\cong$ tra insiemi è una relazione di equivalenza.

$\,$

Dimostrazione della proposizione 3. La dimostrazione è molto semplice e sfrutta semplicemente la definizione 1.

$\,$

La funzione $\id_A \colon A \to A$ (si veda [2, Definizione 2.18]) è biunivoca;
Se $f \colon A \to B$ è biunivoca, allora $f^{-1} \colon B \to A$ è di nuovo biunivoca.
Se $f \colon A \to B$ è biunivoca e se $g \colon B \to C$ è biunivoca, allora $g \circ f \colon A \to C$ è 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.

$\,$

Definizione 5. Siano $A,B$

due insiemi non vuoti. Diciamo che la cardinalità di $A$

è minore o uguale alla cardinalità di $B$

se esiste una funzione $f \colon A \to B$

iniettiva ³ . In tal caso scriviamo $|A| \leq |B|$

$\,$

Osservazione 6. La definizione 5 è un’estensione del concetto “ $A$ possiede al più tanti elementi quanti ne ha $B$ ” valido nel caso di insiemi finiti. Infatti, l’esistenza di una funzione iniettiva tra $A$ e $B$ significa che si possono mettere in corrispondenza biunivoca gli elementi di $A$ con il sottoinsieme (non necessariamente proprio) $f(A)$ di $B$ .

$\,$

Osservazione 7. In generale, se esiste una funzione $f \colon A \to B$ iniettiva ma non biunivoca, ciò non vuol dire che $A \ncong B$ . Infatti, come vedremo in seguito, l’insieme dei numeri pari $2\mathbb{N}$ è equipotente a $\mathbb{N}$ , pur esistendo una funzione iniettiva ma non suriettiva da $2\mathbb{N}$ in $\mathbb{N}$ , ossia l’immersione $\iota \colon 2\mathbb{N}\to \mathbb{N}$ definita⁴ da

(8) $\begin{equation*} \iota (n) = n \qquad \forall n \in \mathbb{N}. \end{equation*}$

$\,$

Come abbiamo osservato, in qualche senso il prototipo di insieme infinito è costituito dall’insieme $\mathbb{N}$ dei numeri naturali. È quindi naturale stabilire una terminologia per indicare gli insiemi infiniti equipotenti a $\mathbb{N}$ .

$\,$

Definizione 8. Sia $A$

un insieme;

$\,$

$A$ si dice numerabile se è equipotente all’insieme $\mathbb{N}$ dei numeri naturali.
$A$ si dice al più numerabile se $|A| \leq |\mathbb{N}|$ .
$A$ si dice invece più che numerabile se non è numerabile ed esiste una funzione $f \colon \mathbb{N} \to A$ iniettiva.

$\,$

Un insieme numerabile quindi ha la stessa cardinalità di $\mathbb{N}$ , un insieme al più numerabile ha cardinalità al più pari a quella di $\mathbb{N}$ , mentre un insieme più che numerabile ha cardinalità strettamente maggiore di quella di $\mathbb{N}$ .

Nella prossima sezione faremo alcuni esempi di insiemi numerabili, mentre nella sezione “L’insieme dei numeri reali è più che numerabile”, mostreremo che l’intervallo $[0,1)$ e l’insieme dei numeri reali $\mathbb{R}$ sono più che numerabili.

$\,$

Il lettore può riferirsi a [2, Definizioni 1.1 e 2.1] per la definizione di funzione e di funzione biunivoca ↩

Il lettore può riferirsi a [2, Definizione 2.1] per la definizione di funzione iniettiva. ↩

Si veda [2, Definizione 2.20] ↩

Scarica la teoria

Ottieni il documento sintetico contenente la teoria sul metodo della diagonale di Cantor.

Esempi di insiemi numerabili

Leggi...

In questa sezione proveremo che alcuni insiemi infiniti presentati nella sezione 1 sono numerabili. Cominciamo col mostrare che l’insieme $2\mathbb{N}$

dei numeri naturali pari, pur essendo un sottoinsieme proprio di $\mathbb{N}$

, è numerabile. Come abbiamo già osservato, $| 2\mathbb{N}|\leq |\mathbb{N}|$

, ossia $2\mathbb{N}$

è al più numerabile.

Proposizione 9. L’insieme $2\mathbb{N}$

dei numeri naturali pari è numerabile.

$\,$

Dimostrazione. Consideriamo la funzione $f \colon \mathbb{N} \to 2\mathbb{N}$ definita da

(9) $\begin{equation*} f(n) = 2n \qquad \forall n \in \mathbb{N}. \end{equation*}$

$\,$

La funzione $f$ è chiaramente biunivoca: è iniettiva in quanto $2n=2m$ se e solo se $n=m$ , ed è suriettiva poiché ogni numero pari si ottiene appunto come doppio di un numero naturale. Pertanto $2\mathbb{N} \cong \mathbb{N}$ .

Vale la seguente generalizzazione della proposizione 9.

Proposizione 10. Sia $A \subseteq \mathbb{N}$

un insieme non vuoto e non superiormente limitato. Allora $A$

è numerabile. In particolare, ogni sottoinsieme di $\mathbb{N}$

e ogni insieme al più numerabile è finito oppure numerabile.

$\,$

Dimostrazione. Si costruirà una funzione $\psi \colon \mathbb{N} \to A$ biunivoca.

Costruzione di $\psi$ .
Definiamo $\psi$ per induzione: poniamo $\psi(0)=\min A$ e, supponendo definito $\psi(k)$ per ogni $k <n$ , poniamo

(10) $\begin{equation*} \psi(n) = \min \big( A \setminus \{\psi(k) \colon k < n\} \big). \end{equation*}$

$\,$

Poiché $A$ non è superiormente limitato mentre $\{\psi(k) \colon k < n\}$ è finito, l’insieme $A \setminus \{\psi(k) \colon k < n\}$ non è vuoto, quindi $\psi(n)$ è ben definito per ogni $n \in \mathbb{N}$ .
$\psi$ è strettamente crescente; in particolare, $\psi$ è iniettiva.
Infatti, per (10) si ha

(11) $\begin{equation*} \psi(n+1) \neq \psi(n) \qquad \forall n \in \mathbb{N}. \end{equation*}$

$\,$

Inoltre, dato che $\{\psi(k) \colon k < n\} \subset \{\psi(k) \colon k < n+1\}$ , si ha

(12) $\begin{equation*} \psi(n+1) = \min \big( A \setminus \{\psi(k) \colon k < n+1\} \big) %\{\psi(k) \colon k < n+1\} \geq \min \big( A \setminus \{\psi(k) \colon k < n\} \big) = \psi(n) \qquad \forall n \in \mathbb{N}. \end{equation*}$

$\,$

Da (11) e (12), segue che $\psi$ è strettamente crescente.

$\,$

$\psi(n) \geq n$ per ogni $n \in \mathbb{N}$ .
Poiché $A \subseteq \mathbb{N}$ , si ha $\psi(0)= \min A \geq 0$ . Supponiamo ora che $\psi(n) \geq n$ ; per la stretta monotonia di $\psi$ provata al punto precedente otteniamo $\psi(n+1) \geq \psi(n)+1 > \psi(n)$ . Per induzione si ha quindi

(13) $\begin{equation*} \psi(n) \geq n \qquad \forall n \in \mathbb{N}. \end{equation*}$

$\,$

$\psi$ è suriettiva.
Supponiamo per assurdo che $\psi$ non sia suriettiva; allora l’insieme $A \setminus \psi(\mathbb{N})$ sarebbe non vuoto, e quindi esisterebbe

(14) $\begin{equation*} m = \min \big( A \setminus \psi(\mathbb{N}) \big). \end{equation*}$

$\,$

Si proverà per induzione che $m \geq n$ per ogni numero naturale $n$ , chiaramente una contraddizione.

Poiché $m \in A$ , si ha $m \geq \min A = \psi(0)$ .

Supponiamo ora che $m \geq \psi(n)$ per qualche $n \in \mathbb{N}$ . Poiché $A \setminus \psi(\mathbb{N}) \subset A \setminus \{\psi(k) \colon k \leq n\}$ , si ha

(15) $\begin{equation*} m = \min \big( A \setminus \psi(\mathbb{N}) \big) \geq \min \big( A \setminus \{\psi(k) \colon k \leq n\} = \psi(n+1). \end{equation*}$

$\,$

Per induzione si è provato quindi che $m \geq \psi(n)$ per ogni $n \in \mathbb{N}$ e, per (13), si ottiene

(16) $\begin{equation*} m \geq n \qquad \forall n \in \mathbb{N}, \end{equation*}$

che contraddice il fatto che $m \in \mathbb{N}$ . Tale contraddizione mostra che l’insieme $A \setminus \psi(\mathbb{N})$ è vuoto, cioè che $\psi$ è suriettiva.

Da queste considerazioni segue che $\psi$ è biunivoca, cioè $A \cong \mathbb{N}$ .

$\,$

Mostriamo ora che esistono insiemi numerabili che contengono l’insieme dei numeri naturali: l’insieme $\mathbb{Z}$ dei numeri interi, pur contenendo intuitivamente “il doppio” degli elementi di $\mathbb{N}$ , è in realtà equipotente a $\mathbb{N}$ , come mostra la prossima proposizione.

$\,$

Proposizione 11. L’insieme $\mathbb{Z}$

dei numeri interi è numerabile.

$\,$

Dimostrazione. Consideriamo la funzione $f \colon \mathbb{N} \to \mathbb{Z}$ definita da

(17) $\begin{equation*} f(n) = \begin{cases} \dfrac{n}{2} & \text{se $n$ è pari}\\[7pt] -\dfrac{n+1}{2} & \text{se $n$ è dispari}. \end{cases} \end{equation*}$

$\,$

In altre parole, $f(n)$ alterna un valore positivo a uno negativo partendo da $0$ e allontanandosi nella direzione dei numeri positivi per $n$ pari, e in quella dei numeri negativi per $n$ dispari.

Dalla definizione è chiaro che $f$ è iniettiva, mentre il fatto che è suriettiva segue dal fatto che ogni numero positivo si ottiene come $\frac{n}{2}$ per qualche numero naturale $n$ pari, mentre ogni numero negativo si ottiene come $-\frac{n+1}{2}$ per qualche numero naturale $n$ dispari. Poiché $f$ è biunivoca, si ha $\mathbb{Z} \cong \mathbb{N}$ .

Anche l’insieme $\mathbb{Q}$ dei numeri razionali è numerabile, come mostra la seguente proposizione.

Proposizione 12. L’insieme $\mathbb{Q}$

dei numeri razionali è numerabile.

$\,$

Dimostrazione. L’idea della dimostrazione consiste nel costruire una funzione $g \colon \mathbb{Q} \to \mathbb{N}$ iniettiva; in tal modo si avrà che $\mathbb{Q} \cong g(\mathbb{Q}) \subset \mathbb{N}$ . Si userà poi la proposizione 10 per provare che $g(\mathbb{Q}) \cong \mathbb{N}$ .

$\,$

Costruzione di $g \colon \mathbb{Q} \to \mathbb{N}$ iniettiva. Osserviamo che ogni numero razionale $q \in \mathbb{Q} \setminus \{0\}$ si può esprimere in modo unico nella forma

(18) $\begin{equation*} q=(-1)^s \frac{m}{n} \qquad \text{con } s \in \{0,1\} \text{ e } (m,n) \in \mathbb{N} \times \mathbb{N} \setminus \{0\} \text{ coprimi}. \end{equation*}$

$\,$

Pertanto, risulta ben definita la funzione $g \colon \mathbb{Q} \to \mathbb{N}$ data da

(19) $\begin{equation*} g(q) = \begin{cases} 2^s \cdot 3^m \cdot 5^n & \text{se } q \neq 0\ 0 & \text{se } q = 0, \end{cases} \end{equation*}$

dove $m,n,s$ sono definiti in (18).

Se $q,r \in \mathbb{Q}$ sono tali che $g(q)=g(r)$ , dal teorema fondamentale dell’Aritmetica segue che $q=r$ , quindi $g$ è iniettiva. Essa non è però suriettiva, in quanto ad esempio $7 \notin g(\mathbb{Q})$ .
$\mathbb{Q} \cong \mathbb{N}$ Poiché $g$ è iniettiva, la funzione $\tilde{g} \colon \mathbb{Q} \to g(\mathbb{Q})$ definita da

(20) $\begin{equation*} \tilde{g}(q)= g(q) \qquad \forall q \in \mathbb{Q}, \end{equation*}$

rimane iniettiva ed è anche ovviamente suriettiva, pertanto è biettiva. Quindi

(21) $\begin{equation*} \mathbb{Q} \cong g(\mathbb{Q}) \subset \mathbb{N}. \end{equation*}$

$\,$

Poiché $\mathbb{Q}$ è infinito, anche $g(\mathbb{Q})$ lo è, ed è quindi superiormente illimitato. Dalla proposizione 10, segue che $g(\mathbb{Q}) \cong \mathbb{N}$ .

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.

$\,$

Proposizione 13. Sia $A$

un insieme numerabile, allora anche $A \times A$

è numerabile.

$\,$

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 $\R$ dei numeri reali non è numerabile.

$\,$

L’insieme dei numeri reali è più che numerabile

Leggi...

Come il lettore può immaginare, mentre per dimostrare che un insieme $A$

sia numerabile basta trovare una particolare funzione biunivoca $f \colon \mathbb{N} \to A$

, per mostrare invece che $A$

non è numerabile occorre provare che non può esistere alcuna funzione biunivoca siffatta, il che può essere molto arduo, considerata l’infinità delle funzioni $f \colon \mathbb{N} \to A$

Occorre quindi trovare una strategia che mostri che nessuna funzione $f \colon \mathbb{N} \to A$ possa essere biunivoca. Ciò è proprio quanto ottenne Cantor utilizzando il suo metodo della diagonale .

Teorema 14 (Cantor). Sia $f \colon \mathbb{N} \to [0,1)$

una funzione, allora $f$

non è suriettiva. In particolare, l’intervallo $I = [0,1) \subset \mathbb{R}$

è più che numerabile.

$\,$

Dimostrazione.

$|\mathbb{N}|\leq [0,1)$ . Si consideri la funzione $h \colon \mathbb{N} \to [0,1)$ definita da

(22) $\begin{equation*} h(n) = 10^{-n-1} \qquad \forall n \in \mathbb{N}. \end{equation*}$

$\,$

Per come è definita, chiaramente la funzione $h$ è iniettiva, quindi $|\mathbb{N}|\leq |[0,1)|$ per la definizione 2.
$[0,1) \cong S$ , con $S\subset \{0,1,\dots,9\}^\mathbb{N}$ ⁵ Sia $S \subset \{0,1,\dots,9\}^\mathbb{N}$ l’insieme delle successioni a valori in $\{0,1,\dots,9\}$ che non terminino con una sequenza infinita di cifre $9$ . Formalmente $S$ è l’insieme delle funzioni $a \colon \mathbb{N} \to \{0,1,\dots,9\}$ tali che

(23) $\begin{equation*} \forall n \in \mathbb{N} \,\, \exists m \geq n \colon a_m \neq 9, \end{equation*}$

dove abbiamo indicato con $a_m$ l’elemento $m$ -esimo della successione $a$ , ossia $a(m)$ .

Osserviamo che ogni successione $a \in S$ determina il numero reale $x\in [0,1)$ il cui sviluppo decimale coincide con gli elementi della successione $a$ :

(24) $\begin{equation*} x=0,a_0 \,a_1\, a_2\, a_3 \dots \end{equation*}$

$\,$

Tale corrispondenza è suriettiva, in quanto ogni numero $x \in [0,1)$ possiede uno sviluppo decimale le cui cifre costituiscono una successione in $S$ ; 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 $[0,1) \cong S$ .
$\mathbb{N} \ncong S$ . Fissiamo una qualunque funzione $f \colon \mathbb{N} \to S$ e dimostriamo che $f$ non è suriettiva.

La funzione $f$ associa a ogni numero naturale $n$ una successione $f_n \colon \mathbb{N} \to \{0,1,\dots\}$ non terminate con una serie infinita di 9, i cui elementi sono $f_n(m)$ al variare di $m \in \mathbb{N}$ ; possiamo rappresentare questa situazione in una tabella:

$\,$

Ad esempio si potrebbe avere

$\,$

Cioè $f_0$ rappresenterebbe il numero $\text{0,2653}\dots$ , $f_1$ rappresenterebbe $\text{0,3436}\dots$ , …

Costruiamo ora una funzione $g \in S$ definita da

(25) $\begin{equation*} g(n) = \begin{cases} 5 & \text{se } f_n(n)=4\\ 4 & \text{se } f_n(n) \neq 4 \end{cases} \qquad \forall n \in \mathbb{N}. \end{equation*}$

$\,$

In altre parole, $g \colon \mathbb{N} \to \{0,1,\dots,9\}$ è la successione costruita cambiando tutti gli elementi della diagonale evidenziati nella tabella. Poiché $g$ assume solo valori 4 e 5, sicuramente $g \in S$ .

Inoltre, poiché $g(n) \neq f_n(n)$ per ogni $n \in \mathbb{N}$ , si ha

(26) $\begin{equation*} g \neq f_n \qquad \forall n \in \mathbb{N}. \end{equation*}$

$\,$

Ciò mostra che $g$ non appartiene all’immagine di $f$ , e quindi $f$ non è suriettiva. Per cui $S$ (e quindi anche $[0,1)$ ) non è numerabile.

$\,$

Una conseguenza del teorema 14 è che, come si può intuire, anche $\mathbb{R}$ è più che numerabile. Si dedurrà questo fatto dalla seguente proposizione di carattere più generale.

$\,$

Proposizione 15. Siano $A,B$

insiemi tali che $A$

sia più che numerabile e $A \subseteq B$

. Allora $B$

è più che numerabile.

$\,$

Dimostrazione. Poiché $A$ è più che numerabile, esiste una funzione $g \colon \mathbb{N} \to A$ iniettiva. Allora anche la funzione $\iota \circ g \colon \mathbb{N} \to B$ è iniettiva, dove $\iota \colon A \to B$ è l’immersione⁶ di $A$ in $B$ definita da

(27) $\begin{equation*} \iota(x) = x \qquad \forall x \in A. \end{equation*}$

$\,$

Pertanto, per mostrare che $B$ è più che numerabile, basta dimostrare che ogni funzione $g \colon \mathbb{N} \to B$ iniettiva non è suriettiva.

Sia quindi $g \colon \mathbb{N} \to B$ una qualsiasi funzione iniettiva e mostriamo che non è suriettiva.

Consideriamo l’insieme $X$ dei numeri naturali la cui immagine tramite $g$ appartiene ad $A$ , ossia, in termini formali, la controimmagine $g^{-1}(A)$ dell’insieme $A$ tramite $g$ :

(28) $\begin{equation*} X = g^{-1}(A) = \{n \in \mathbb{N} \colon g(n) \in A \}. \end{equation*}$

$\,$

Poiché $g$ è iniettiva, la funzione $f \colon X \to A$ definita da

(29) $\begin{equation*} f(n) = g(n) \qquad \forall n \in X \end{equation*}$

è iniettiva; essa non può però essere suriettiva, altrimenti $f$ sarebbe una biezione e $A$ sarebbe equipotente al sottoinsieme $X$ di $\mathbb{N}$ , che per la proposizione 10 è finito o numerabile, mentre $A$ è più che numerabile.

Pertanto $f$ non è suriettiva e per la definizione di $f$ , ciò implica che esistono elementi di $A\subseteq B$ che non sono immagine di alcun numero naturale tramite $g$ , cioè neanche $g$ è suriettiva.

Per l’arbitrarietà di $g$ , si ha che $B$ non è numerabile e dalle considerazioni iniziali segue quindi che esso è più che numerabile.

$\,$

Corollario 16. L’insieme $\mathbb{R}$

dei numeri reali è più che numerabile.

$\,$

Dimostrazione. La tesi è una conseguenza immediata del teorema 14 e della proposizione 15 applicata al caso $A=[0,1)$ e $B=\mathbb{R}$ .

In realtà, vale la tesi, più forte della precedente, che $[0,1)$ e $\mathbb{R}$ sono equipotenti. La dimostreremo in appendice A, come conseguenza del notevole teorema 18.

$\,$

Se $A,B$ sono insiemi non vuoti, il simbolo $B^A$ denota l’insieme delle funzioni aventi dominio $A$ e codominio $B$ . Pertanto, $\{0,1,\dots,9\}^\N$ è l’insieme delle funzioni da $\N$ a valori in $\{0,1,\dots,9\}$ , ossia l’insieme delle successioni di cifre appartenenti all’insieme $\{0,1,\dots,9\}$ . ↩

Si veda [2, Definizione 2.20.] ↩

$\,$

Insiemi infiniti di cardinalità diversa

Leggi...

L’argomento della diagonale di Cantor presentato nella dimostrazione del teorema 14 può essere utilizzato per provare che, dato un insieme $A$

, il suo insieme delle parti $\mathcal{P}(A)$

non è equipotente ad $A$

, e precisamente ha cardinalità strettamente maggiore di $A$

Teorema 17 (Cantor). Sia $A$

un insieme. Allora $A$

non è equipotente all’insieme delle parti $\mathcal{P}(A)$

di $A$

. Precisamente, vale

(30) $\begin{equation*} |A| \leq |\mathcal{P}(A)| \qquad \text{e} \qquad A \ncong\mathcal{P}(A). \end{equation*}$

$\,$

Dimostrazione.

$|A| \leq |\mathcal{P}(A)|$ . Si consideri la funzione $h \colon A \to \mathcal{P}(A)$ definita da

(31) $\begin{equation*} h(x) = \{x\} \in \mathcal{P}(A) \qquad \forall x \in A. \end{equation*}$

$\,$

In altre parole, la funzione $h$ associa all’elemento $x$ di $A$ il sottoinsieme $\{x\}$ di $A$ . Per come è definita, chiaramente la funzione $h$ è iniettiva, quindi $|A| \leq |\mathcal{P}(A)|$ per la definizione 5.
$\mathcal{P}(A) \cong \{0,1\}^A$ . Osserviamo che ogni funzione $\alpha \colon A \to \{0,1\}$ determina il sottoinsieme $X_\alpha \in \mathcal{P}(A)$ cui appartengono tutti e soli gli elementi di $A$ su cui $\alpha$ vale $1$ :

(32) $\begin{equation*} X_\alpha= \{a \in A \colon \alpha(a)=1\} \in \mathcal{P}(A). \end{equation*}$

$\,$

La corrispondenza $\alpha \in \{0,1\}^A \mapsto X_\alpha \in \mathcal{P}(A)$ è chiaramente biunivoca. Pertanto $\mathcal{P}(A) \cong \{0,1\}^A$ .

$\,$

$A \ncong \{0,1\}^A$ . Fissiamo una qualunque funzione $f \colon A \to \{0,1\}^A$ e dimostriamo che $f$ non è suriettiva.
La funzione $f$ associa a ogni elemento $a \in A$ una funzione $f_a \colon A \to \{0,1\}$ , le cui immagini sono $f_a(t)$ al variare di $t \in A$ ; possiamo rappresentare questa situazione in una tabella:

$\,$

Costruiamo ora una funzione $g \in \{0,1\}^A$ definita da

(33) $\begin{equation*} g(a) = \begin{cases} 1 & \text{se } f_a(a)=0\\ 0 & \text{se } f_a(a)=1 \end{cases} \qquad \forall a \in A. \end{equation*}$

$\,$

In altre parole, $g \colon A \to \{0,1\}$ è la funzione costruita cambiando tutti gli elementi della diagonale evidenziati nella tabella.

Poiché $g(a) \neq f_a(a)$ per ogni $a \in A$ si ha

(34) $\begin{equation*} g \neq f_a \qquad \forall a \in A. \end{equation*}$

$\,$

Ciò mostra che $g$ non appartiene all’immagine di $f$ , e quindi $f$ non è suriettiva. Per cui $\{0,1\}^A$ (e quindi $\mathcal{P}(A)$ ) non è equipotente ad $A$ .

$\,$

$\,$

Osservazione 16. Considerando che ogni funzione $f_a \colon A \to \{0,1\}$ determina un sottoinsieme $X_{f_a}$ di $A$ , la funzione $g \colon A \to \{0,1\}$ determina l’insieme $G \in \mathcal{P}(A)$ definito da

(35) $\begin{equation*} G = \{a \in A \colon a \notin X_{f_a}\} \end{equation*}$

L’insieme $G$ 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 $f_a \colon A \to \{0,1\}$ determina un sottoinsieme $X_{f_a}$ di $A$ , la funzione $g \colon A \to \{0,1\}$ determina l’insieme $G \in \mathcal{P}(A)$ definito da

(36) $\begin{equation*} G = \{a \in A \colon a \notin X_{f_a}\} \end{equation*}$

$\,$

L’insieme $G$ 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 $A$ e applicando iterativamente il teorema 15, si ottiene che la successione di insiemi

(37) $\begin{equation*} A,\,\, \mathcal{P}(A),\,\, \mathcal{P}(\mathcal{P}(A)),\,\, \mathcal{P}(\mathcal{P}(\mathcal{P}(A))), \dots \end{equation*}$

è 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...

Riportiamo in questa appendice l’importante risultato dovuto, tra gli altri, a Cantor e Bernstein (1878-1956): esso afferma che, se $|A| \leq |B|$

e $|B| \leq |A|$

, allora $|A| = |B|$

. Intuitivamente, ciò significa che la relazione di “avere cardinalità minore o uguale a” è una relazione d’ordine.

Teorema 18 (Cantor-Bernstein). Siano $A$

e $B$

due insiemi non vuoti e siano $f \colon A \to B$

e $g \colon B \to A$

due funzioni iniettive. Allora $A$

e $B$

sono equipotenti.

$\,$

Dimostrazione. Definiamo per ricorrenza gli insiemi $A_n \subset A$ e $B_n \subset B$ ; poniamo $A_0=A \setminus g(B)$ e $B_0=B \setminus f(A)$ . Supponiamo ora definiti $A_n$ e $B_n$ e poniamo

(38) $\begin{equation*} A_{n+1} = g(B_n), \qquad B_{n+1} = f(A_n). \end{equation*}$

$\,$

Definiamo poi

(39) $\begin{equation*} A_\infty= A \setminus \bigcup_{n=0}^{+\infty} A_n, \qquad B_\infty= B \setminus \bigcup_{n=0}^{+\infty} B_n. \end{equation*}$

$\,$

Dalla costruzione si ha che

(40) $\begin{equation*} A= \left( \bigcup_{n=0}^{+\infty} A_n \right) \cup A_\infty, \qquad B= \left( \bigcup_{n=0}^{+\infty} B_n \right) \cup B_\infty. \end{equation*}$

$\,$

Osserviamo che

(41) $\begin{equation*} f^{-1}(B_\infty) = f^{-1}\left( B \setminus \bigcup_{n=0}^{+\infty} B_n \right) = f^{-1}(B) \setminus f^{-1} \left( \bigcup_{n=0}^{+\infty} B_n \right) = A \setminus \left( \bigcup_{n=0}^{+\infty} A_n \right) = A_\infty, \end{equation*}$

dove nella terza uguaglianza si è usato che $f^{-1}(B_0)=\emptyset$ e che $f^{-1}(B_{n+1})=A_n$ per $n \in \mathbb{N}$ .

Definiamo ora la funzione $h \colon A \to B$ ottenuta ponendo (si veda la figura 1).

(42) $\begin{equation*} h(a) = \begin{cases} f(a) & \textbf{se } a \in A_\infty \cup \left( \bigcup_{n=0}^{+\infty} A_{2n} \right)\\ g^{-1}(a) & \textbf{se } a \in \bigcup_{n=0}^{+\infty} A_{2n+1}. \end{cases}, \end{equation*}$

dove con $g^{-1}(a)$ si è indicato l’unico elemento $b \in B$ tale che $g(b)=a$ . Poiché $\bigcup_{n=0}^{+\infty} A_{2n+1} \subset g(B)$ , $h$ risulta ben definita.

$\,$

Figura 1: costruzione della funzione h nella dimostrazione del teorema 18

$\,$

Osserviamo che, per l’iniettività di $f$ e $g$ e per la definizione degli $A_n$ e $B_n$ , $f$ è una biezione tra $A_{2n}$ e $B_{2n+1}$ per ogni $n \in \mathbb{N}$ , mentre $g$ è una biezione tra $B_{2n}$ e $A_{2n+1}$ per ogni $n \in \mathbb{N}$ . Inoltre, sempre per l’iniettività di $f$ e per (41), $f$ è una biezione tra $A_\infty$ e $B_\infty$ . Per questi motivi, $f$ è biettiva.

$\,$

Usando il teorema 18 si ottiene che $[0,1)$ e $\mathbb{R}$ sono equipotenti.

$\,$

Proposizione 19. L’intervallo $[0,1)$

e l’insieme $\mathbb{R}$

dei numeri reali sono equipotenti.

$\,$

Dimostrazione. Consideriamo le funzioni $f \colon [0,1) \to \mathbb{R}$ e $g \colon \mathbb{R} \to [0,1)$ definite da

(43) $\begin{equation*} f(x) = x \quad \forall x \in [0,1), \qquad g(y)=\frac{2}{\pi} \arctan y \quad \forall y \in \mathbb{R}. \end{equation*}$

$\,$

Esse sono entrambe iniettive. Per il teorema 18, si ha $[0,1) \cong \mathbb{R}$ .

$\,$

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 .

Document

Tutta la teoria di analisi matematica

Leggi...

Tutte le cartelle di Analisi Matematica

Leggi...

Tutti gli esercizi di geometria

In questa sezione vengono raccolti molti altri esercizi che coprono tutti gli argomenti di geometria proposti all’interno del sito con lo scopo di offrire al lettore la possibilità di approfondire e rinforzare le proprie competenze inerenti a tali argomenti.

Strutture algebriche.

Algebra lineare.

Geometria analitica.

Geometria differenziale.

Risorse didattiche aggiuntive per approfondire la matematica

Leggi...

Math Stack Exchange – Parte della rete Stack Exchange, questo sito è un forum di domande e risposte specificamente dedicato alla matematica. È una delle piattaforme più popolari per discutere e risolvere problemi matematici di vario livello, dall’elementare all’avanzato.
Art of Problem Solving (AoPS) – Questo sito è molto noto tra gli studenti di matematica di livello avanzato e i partecipanti a competizioni matematiche. Offre forum, corsi online, e risorse educative su una vasta gamma di argomenti.
MathOverflow – Questo sito è destinato a matematici professionisti e ricercatori. È una piattaforma per domande di ricerca avanzata in matematica. È strettamente legato a Math Stack Exchange ma è orientato a un pubblico con una formazione più avanzata.
PlanetMath – Una comunità collaborativa di matematici che crea e cura articoli enciclopedici e altre risorse di matematica. È simile a Wikipedia, ma focalizzata esclusivamente sulla matematica.
Wolfram MathWorld – Una delle risorse online più complete per la matematica. Contiene migliaia di articoli su argomenti di matematica, creati e curati da esperti. Sebbene non sia un forum, è una risorsa eccellente per la teoria matematica.
The Math Forum – Un sito storico che offre un’ampia gamma di risorse, inclusi forum di discussione, articoli e risorse educative. Sebbene alcune parti del sito siano state integrate con altri servizi, come NCTM, rimane una risorsa preziosa per la comunità educativa.
Stack Overflow (sezione matematica) – Sebbene Stack Overflow sia principalmente noto per la programmazione, ci sono anche discussioni rilevanti di matematica applicata, specialmente nel contesto della scienza dei dati, statistica, e algoritmi.
Reddit (r/Math) – Un subreddit popolare dove si possono trovare discussioni su una vasta gamma di argomenti matematici. È meno formale rispetto ai siti di domande e risposte come Math Stack Exchange, ma ha una comunità attiva e molte discussioni interessanti.
Brilliant.org – Offre corsi interattivi e problemi di matematica e scienza. È particolarmente utile per chi vuole allenare le proprie capacità di problem solving in matematica.
Khan Academy – Una risorsa educativa globale con lezioni video, esercizi interattivi e articoli su una vasta gamma di argomenti di matematica, dalla scuola elementare all’università.

Document

Menu

Chiudi

Il metodo della diagonale di Cantor

Autori e revisori

Mostra autori e revisori.

Introduzione

Leggi...

Notazioni

Leggi...

Insiemi infiniti

Leggi...

Equipotenza e insiemi numerabili

Leggi...

Scarica la teoria

Esempi di insiemi numerabili

Leggi...

L’insieme dei numeri reali è più che numerabile

Leggi...

Insiemi infiniti di cardinalità diversa

Leggi...

Il teorema di Cantor-Bernstein

Leggi...

Riferimenti bibliografici

Tutta la teoria di analisi matematica

Leggi...

Tutte le cartelle di Analisi Matematica

Leggi...

Tutti gli esercizi di geometria

Strutture algebriche.

Algebra lineare.

Geometria analitica.

Geometria differenziale.

Risorse didattiche aggiuntive per approfondire la matematica

Leggi...

Suggerimenti, refusi ed errori

Cosa dicono di noi