matematicamente indimostrabile
Claudio Bernardi
Sapienza - Dipartimento di Matematica
che cosa fa un matematico?
calcoli, per esempio, 95247  3518,
(a+b)
a mano sono complicati, ma “so farli”
esecuzione meccanica, senza sorprese
(e se poi ho una calcolatrice ...)
molto più interessante: problemi
numeri primi, come 2, 3, 5, 7, 11, 13, ...
9
quanti sono i numeri primi?
Euclide: «esistono infiniti numeri primi»
con un controllo diretto, non posso né verificare,
né confutare
2  3  5  7  11  13 + 1 = 30 031
30 031 non è divisibile per 2, 3, 5, 7, 11, 13
ha un “nuovo” fattore primo: 30 031 = 59 × 509
calcoli e problemi
situazioni analoghe per uno studente:
“calcola il valore di …”,
“dimostra che …”
come si dimostrano le proprietà nell’insieme N
dei numeri naturali 0, 1, 2, … (con le consuete
operazioni)?
riportiamo la proprietà che stiamo esaminando a
fatti noti
teoria assiomatica
accettiamo proprietà di base, assiomi o postulati
e, a partire dagli assiomi, dimostriamo i teoremi
fra le teorie assiomatiche per i numeri naturali,
la più nota è l'aritmetica di Peano (PA)
x (0 ≠ x’)
x y [x ≠ y  x’ ≠ y’]
x (x + 0 = x)
x y [x + y’ = (x + y)’]
x (x0 = 0)
x y (xy’ = xy + x)
H(0)  x (H(x)  H(x’))  x H(x)
gli assiomi, e di conseguenza anche i teoremi,
esprimono fatti veri in N
domanda cruciale: gli assiomi permettono di
dimostrare tutto quello che è vero?
congettura di Goldbach: ogni numero pari
maggiore di 2 è somma di due numeri primi
(4 = 2+2
12 = 5+7
22 = 3+19)
se è vera, riuscirò a dimostrarla?
primo Teorema di Gödel (1931)
Esiste almeno una formula G tale la mia teoria
(es.: PA) non dimostra G, ma nemmeno ¬G.
formula G indecidibile - teoria incompleta
due possibilità:
- la formula G è vera in N e ¬G è falsa
- la formula G è falsa in N e ¬G è vera
in ogni caso, esiste una formula che è vera in N
ma non è un teorema
la teoria non dimostra tutto quello che vorrei;
forse, la congettura di Goldbach è vera ma non
dimostrabile
il primo teorema di Gödel si dimostra costruendo
una formula G tale che
G  ¬ Theor (G)
G è una formula che, in un certo senso, dice
«non esiste una dimostrazione di G»
attenzione: il I teorema di Gödel vale solo se la
teoria è coerente (o non contraddittoria)
se dagli assiomi della teoria si potesse dedurre
una contraddizione, allora ogni formula sarebbe
un teorema
gli assiomi di PA sono contraddittori??
la teoria è non contraddittoria se non c’è una
dimostrazione di 2+2 = 5
¬Theor (2+2 = 5)
questa formula esprime
la coerenza (non contraddittorietà) della teoria
secondo Teorema di Gödel
nella teoria (in PA) la formula ¬ Theor (2+2 = 5)
non si può dimostrare
diamo “un’occhiata” a parte della dimostrazione
|– Theor (G)  Theor (Theor (G))
|– Theor (G)  Theor (¬ G)
per le proprietà di G
|– Theor (G)  Theor (¬ G)  Theor (G)
|– Theor (G)  Theor (2+2 = 5) perché ¬ G  G equivale a 2+2 = 5
|– ¬ Theor (2+2 = 5)  ¬ Theor (G)
contronominale
|– ¬ Theor (2+2 = 5)  G
per le proprietà di G
una conseguenza importante
non c’è (non ci può essere)
un procedimento generale di decisione
per i problemi matematici
(differenza fra calcoli e problemi)
nessuno potrà mai realizzare un software
che risponda a ogni domanda del tipo
«è vera la congettura di Goldbach?»
abbiamo una “ragionevole fiducia” che la
teoria PA sia non contraddittoria
ci sono dimostrazioni, che non si possono
tradurre nella teoria stessa
dopo i Teoremi di Gödel,
morte della logica?
perdita della certezza matematica?
NO, anzi