Prezzi Registrazione Login
Qui si risolve LOGO
a

Menu

M

Chiudi

Il metodo della diagonale di Cantor

Insiemi, Insiemi numerici N, Z, Q, R

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| \le |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: inclusione di A in B

Se f \colon A \to B e X \subseteq A: immagine di X tramite f

Se f \colon A \to B e Y \subseteq B: controimmagine di Y tramite f

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 1 ), 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.    

\[\,\]

  1. Per scrittura periodica intendiamo anche scritture terminanti con una sequenza infinita di cifre 0, come ad esempio quella in (6) ↩

\[\,\]

\[\,\]

\[\,\]

Equipotenza e insiemi numerabili

Questa parte è riservata agli abbonati

per continuare a leggere, attiva un abbonamento.

• Mensile: 7,99€ / mese • Trimestrale: 19,99€ / 3 mesi • Annuale: 79,99€ / anno

Attiva abbonamento

Già abbonato? Accedi