Non numerabilità dei reali

I numeri reali li conosciamo tutti, sono quei numeri tipo Pi greco (π = 3,141592…).
La cosa interessante di questi numeri è che non sono numerabili. Ora, se indichiamo l’insieme dei numeri reali con la lettera ℜ, allora diciamo che ℜ è numerabile se e solo se ogni elemento appartenente ad esso può essere messo in corrispondenza biunivoca con i numeri naturali (1, 2, 3, …). Che cos’è la corrispondenza biunivoca? Niente di difficile, significa solo che: se ci immaginiamo i numeri disposti in ordine crescente su una retta, allora ad ogni numero reale corrisponde uno ed un solo numero naturale e viceversa. Possiamo immaginare la situazione così:

1, 456830 ↔ 1
1, 485003 ↔ 2
2, 068428 ↔ 3
2, 858003 ↔ 4
3, 264593 ↔ 5

E così via ad infinitum. Il punto è: instaurare una corrispondenza biunivoca fra questi due insiemi (quello dei numeri naturali e quello dei numeri reali) è possibile?
Secondo Georg Cantor (1845-1918) la risposta è: no, non è possibile. I numeri reali non sono numerabili. Detto altrimenti: nell’insieme dei numeri naturali diciamo che la serie dei numeri è discreta, ossia a 1 segue un 2, a 2 segue subito 3, a 3 segue subito 4 e così via. Nell’insieme dei reali, invece, la serie dei numeri è continua: fra 1 e 2 ci sono infiniti numeri! Cioè: 1, 00000 < 1, 00001 < 1, 00002 < … < 2.
Ma come si fa a dimostrare che i numeri reali, quindi, non sono numerabili? Eh la dimostrazione è anch’essa piuttosto semplice e fa uso del metodo diagonale (o diagonalizzazione) inventato dallo stesso Cantor.
Dimostrazione: per assurdo
Supponiamo che l’insieme dei reali sia numerabile e scriviamo:
(1) Num(ℜ)
Se questo insieme è numerabile, allora lo sarà anche l’intervallo fra 0 e 1 appartenente ai numeri reali, cioè la serie: 0, 00000 < 0, 000001  <  … <  1. Scriviamo quindi:
(2) Num([0, 1])
Se questo intervallo è numerabile, allora possiamo indicare tutti i numeri decimali all’interno di questo intervallo disponendoli in una matrice (tabella). Chiamiamo questi numeri compresi fra 0 e 1 con la lettera greca α, allora:
(3) < α1, α2, α3, α4 > ∈ ℜ
α1 = 0, 8 2 1
α2 = 0, 3 3 2
α3 = 0, 4 3 8
α4 = 0, 4 5 8 1
Per semplicità fermiamoci al quarto numero compreso fra 0 e 1, supponendo di averli enumerati tutti. Adesso, però, possiamo usare il metodo della diagonale di Cantor e prendere le cifre che ho evidenziato in grassetto per costruire un nuovo numero che chiamiamo β, che avrà la forma:
(4) β = 0, 3 8 4 1
Questo numero, appartiene ancora all’insieme dei numeri compresi fra 0 e 1 e sarà uno dei numeri che, presumibilmente, viene dopo α4. Tuttavia possiamo definire adesso un nuovo tipo di numero, β*, tale che questo β* differisca per costruzione da ogni altro numero appartenente all’intervallo fra 0 e 1. Come? Così:
(5) β* = ∀∈ β → n +1.
Ossia, possiamo costruire questo numero β* non compreso nella precedente tabella aggiungendo un +1 ad ogni numero decimale di β.
(6) β* = 0, 4 9 5 2
Questo nuovo numero, per come lo abbiamo costruito, differisce al più per una cifra da ogni altro numero che esiste nella tabella. Questo numero appartiene all’intervallo [0, 1]. Eh ma noi avevamo supposto che quell’intervallo fosse già stato enumerato completamente! Ergo: siamo caduti in un assurdo: pur supponendo di aver un intervallo completamente enumerato, esiste un numero non elencato nell’enumerazione di quell’intervallo. Quindi: l’intervallo fra 0 e 1 non è numerabile!
(7) ¬Num([0, 1])
E a maggior ragione se una sua parte non è numerabile, allora non sarà numerabile neanche l’intero insieme dei numeri reali. Quindi:
(8) ¬Num(ℜ).

QED

La dimostrazione è conclusa e, in modo ingegnoso ma semplice, siamo riusciti a dimostrare il teorema della non numerabilità dei numeri reali.


∃x(φ)

Teorema di Robinson

Il Teorema di Robinson (1956), anche detto teorema della somma di teorie, ci dice in che modo due teorie possano unirsi. Stabilisce, cioè, le condizioni affinché due teorie differenti (ma che abbiano almeno qualcosa in comune) possano unirsi per formare un’unica teoria unificata. Perché è importante questo teorema? Beh, se si pensa che la fisica quantistica (o, più specificatamente: la teoria della relatività e la meccanica quantistica) non è altro che un insieme di teorie matematiche fra loro non necessariamente non contraddittorie, allora il teorema di Robinson ci indica la strada da percorrere affinché si possa giungere ad una teoria del tutto (o teoria fisica unificata).
Veniamo ora nel vivo del teorema:

Enunciato: T e T* sono consistenti se e solo se sono compatibili. Dove compatibili significa che: (I) T è consistente; (II) T* è consistente; (III) non esiste una formula C tale che il linguaggio in cui è formulata C è incluso o uguale all’intersezione del linguaggio di T con il linguaggio di T* e: T dimostra C e T* dimostra ¬C.

[Ho usato il segno ¬ per indicare la negazione di C, quindi ¬C equivale a non-C].
Spieghiamo meglio cosa significa l’enunciato. Due teorie differenti, che chiamiamo T e T*, sono non contraddittorie (ossia, consistenti fra loro) soltanto quando esse sono compatibili. Ovviamente se le due teorie sono inconsistenti (ossia si contraddicono a vicenda), allora non sono compatibili: se una teoria dimostra A ed una dimostra non-A, allora A sarà sia vera sia falsa nella loro somma. Ma questo violerebbe il principio di non contraddizione, quindi è assurdo che si verifichi una tale evenienza. Per essere, invece, compatibili le due teorie devono essere entrambe, se considerate singolarmente, non contraddittorie (ossia non si dà il caso che T dimostri B e non-B,  e lo stesso vale per T*). In più, per essere sommate, bisogna che esse abbiano almeno qualcosa in comune nel loro linguaggio (ossia nel loro apparato concettuale diremmo in termini meno formali). Questo è un requisito necessario, altrimenti potremmo sommare una teoria che parla di atomi ed una che parla di Dio. Ma così confonderemmo una teoria scientifica con una teologica! Noi invece vogliamo restare in un campo ristretto, sicché si possano sommare teorie fra loro correlate.
Si noti, poi, che le due teorie sono consistenti fra loro se e solo se i loro assiomi di partenza sono consistenti.
Possiamo riscrivere (III) così:

  • (III)*   Esiste una C tale che L(C) ⊆ [L(T) ∩ L(T*)].

Bene, bell’enunciato sicuramente. Ma è vero o falso? Per scoprirlo è necessaria una dimostrazione dell’enunciato. La dimostrazione si conduce sciogliendo il “se e solo se” nei due versi, ossia mostrando che il primo termine implica il secondo e, viceversa, che anche il secondo implica il primo.

Dimostrazione:
Dim 1: Se T e T* sono consistenti, allora sono compatibili. Questo verso della doppia implicazione è banale: se T e T* sono entrambe consistenti allora le condizioni (I) e (II) valgono. Quindi T non dimostra contraddizioni e neanche T* ne dimostra. Supponiamo ora che per assurdo le due teorie non siano compatibili, allora ciò significa che T+T* dimostra una contraddizione. Ma questo vuol dire che una fra T e T* è inconsistente! Ma non avevamo supposto fossero entrambe consistenti? L’ipotesi che due teorie sono consistenti ma incompatibili ci conduce dunque all’assurdo, quindi è falsa. Sarà allora vero che se due teorie sono consistenti allora esse sono compatibili.
Dim 2: Se T e T* sono compatibili, allora T e T* sono consistenti. Si procede con una dimostrazione per assurdo, cioè assumiamo che le due teorie siano compatibili ma che non siano consistenti.
(Userò il segno ⇒ per indicare che le due teorie dimostrano una certa proposizione. Userò poi il segno ⊥ per indicare una contraddizione e simbolizza l’assunzione “le due teorie, messe insieme, sono contraddittorie”; in altre parole equivale al fatto che si sta dimostrando l’enunciato per assurdo. Userò il segno ≡ per indicare che due forme sono equivalenti).
(o) T e T* sono compatibili.
(1) T + T* ⇒ ⊥
(2) Siano A gli assiomi di T e B gli assiomi di T*.
(3) A, B ⇒ ⊥
(4) ⇒ A→[B→(⊥)]   [(3) e (4) sono equivalenti; ho solo riscritto (3)]
(5) ⇒ A→ ¬B            [Se B implica l’assurdo, allora è vera non-B]
(5.1) A→¬B è vera anche se è falso A, cioè ¬A è vero, ed è vero ¬B.
(6) Dato (5.1), si danno i tre seguenti casi:
(6.1)  ⇒¬A ma per (2)   T ⇒ A & ¬A.
(6.2)  ⇒ ¬B ma per (2)  T* ⇒ B & ¬B.
(6.3)  Esiste una C tale che L(C) ⊆ [L(T) ∩ L(T*)] e dunque:
          (6.3.1) [⇒A → C] ≡ [T ⇒ C].
          (6.3.2) [⇒ C → ¬B] ≡ [⇒ B → ¬C] ≡ [T* ⇒ ¬C]

QED

Poiché i sottocasi di (6) hanno condotto all’assurdo — i primi due perché sono in contraddizione con gli assiomi e l’ultimo, coi rispettivi altri due suoi sottocasi, perché dice che le due teorie T e T* dimostrano rispettivamente C e non-C — allora la negazione del teorema è falsa perché contraddittoria. Quindi l’enunciato del teorema è necessariamente vero.

                              

Che cos’è un numero naturale?

Non è facile definire un numero naturale. Certo qualcuno, pragmaticamente, potrebbe dire: “Un numero naturale è uno dei numeri che iniziano per 0, 1, 2, …”. Bella risposta, almeno intuitivamente. Ma la domanda non era “quanti e quali sono i numeri naturali?”, bensì quale fosse la definizione di un numero naturale. In altre parole: non vogliamo un elenco di numeri naturali, vogliamo prima sapere quali siano le proprietà che li caratterizzano. Ossia la loro natura. A fornirci la risposta è stato il matematico italiano Giuseppe Peano (1858-1932) che ha definito l’assiomatizzazione standard di tali numeri nel suo lavoro: “Arithmetices principia, nova methodo exposita”, pubblicato nel 1889 .
Che cos’è, dunque, un numero naturale? Sappiamo che ogni genere di numeri fa parte di un insieme ed è in un insieme contenuto. L’insieme (o il dominio) dei numeri naturali viene per convenzione chiamato “Insieme N“. Diremo che un numero x è naturale se e solo se x ∈ N. Se x appartiene all’insieme, o è un elemento dell’insieme, N, allora x è un numero naturale. Cioè si deve verificare la seguente condizione:

= {x}

La rappresentazione è intuitiva. Abbiamo definito come un insieme con un unico elemento. “= {1}” è un insieme formato da soli numeri naturali per esempio. Potremmo anche scrivere così:

  1. = {x, y, z, …, n}
  2. = {1, 2, 3, …, 1938}

1. e 2. sono perfettamente equivalenti, possiamo dire che 2. è un’istanza di 1, cioè 2. è l’esempio pratico dell’esempio formale 1. Fatto vedere ciò, però, ancora non siamo giunti ad individuare le proprietà che fanno sì che questi numeri siano naturali. Abbiamo, infatti, semplicemente mostrato un elenco di numeri, ora vogliamo sapere quali siano i criteri per i quali far rientrare un numero x sotto l’insieme dei numeri naturali.
Supponiamo che ci siano dei numeri naturali x, y, z, allora le condizioni (o proprietà) di base che essi devono soddisfare sono:

(1)   0 è un numero naturale.
(2)   Per ogni numero naturale, x = x.
(3)   Per ogni numero naturale, (x = y) ⇒ (y = x).
(4)   Per ogni numero naturale, [(x = y) & (y = z)] ⇒ (x = z)
(5)   Per ogni x e y, se y è un numero naturale e (x = y), allora anche x è un naturale.

(1) è un’assunzione ed indica che 0 è una costante. (2)-(5) indicano le proprietà equazionali dei numeri naturali, rispettivamente essi sono: riflessivi, simmetrici, transitivi e chiusi rispetto all’equazione (cioè se due numeri sono uguali fra loro e di uno dei due sappiamo che è un naturale, allora possiamo dedurre che anche l’altro sia un naturale). Aggiungiamo ora le ultime condizioni che specificano invece le proprietà aritmetiche.

(6)   Per ogni numero naturale x, S(x) è un numero naturale.
(7)   Per ogni naturale x e y, (x = y) se e solo se [S(x) = S(y)].
(8)   Per ogni numero naturale, S(x) = 0 è falso.

Le condizioni (6)-(8) sono ciò che davvero individua i numeri in quanto naturali. La condizione (6) ci dice che il successore di un numero naturale è ancora un numero naturale. Per cui:

  1. (1 ∈ N) ⇒ S(1) ∈ N
  2.    S(1) ∈⇒ S(S(1)) ∈ N

In 1. ci viene detto sostanzialmente che il successore di 1, ossia 2, fa ancora parte dei numeri naturali, così il successore del successore di 1, ossia 3, fa ancora parte dei numeri naturali.
La condizione (7) a tal punto è banale: due numeri naturali sono uguali se e solo se anche le loro successioni lo sono. Ossia:

(1 = 1) ⇔ (2 = 2)
(1 = 3) ⇔ (2 = 4)

Infine la condizione (8) è forse la più intuitiva: nessun numero ha come successore 0. Ossia: 0 è il primo dei numeri naturali e dunque non è il successore di nessun numero, perché non ci sono altri numeri naturali prima di esso!
Ecco fatto, siamo riusciti ad individuare tutti i numeri naturali per mezzo delle condizioni (1)-(8).


COROLLARIO: Come si generano i numeri naturali?

La generazione dei numeri naturali si dà semplicemente aggiungendo una condizione, che chiamiamo, in continuità con le precedenti condizioni, (9):

(9) Se è un insieme tale che:

  • 0 è un elemento di N,
  • Per ogni numero n in N, si ha che S(n) è anch’esso in N,

Allora contiene ogni numero naturale.

La condizione (9) è anche detta “assioma dell’induzione”. A partire cioè da soli due elementi (lo zero ed il successore di un numero, che potrebbe appunto essere anche il successore di zero) e dalle loro proprietà possiamo derivare l’esistenza e la costruzione dell’intero insieme dei numeri naturali.



∃x(φ)