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(φ)

Annunci

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.