T1: Logica, discorso e conoscenza

ovvero

Deduzione formale vs verit` a:

un’introduzione ai teoremi limitativi

Simone Martini

Dipartimento di Scienze dell’Informazione Alma mater studiorum – Universit`a di Bologna

martini@cs.unibo.it

Collegio Superiore ottobre–novembre, 2011

1 / 233

Outline

1

Prima lezione: la logica dall’informale al formale Pillole di storia (e problemi) della logica

2

Seconda lezione: Linguaggi del prim’ordine Logica proposizionale; linguaggi predicativi

3

Terza lezione: verit` a e validit` a

Formule vere dovunque e vere in classi di modelli

4

Quarta lezione: dimostrazioni Sistemi formali per la derivabilit` a

1

Quinta lezione: l’aritmetica di Peano Un sistema di assiomi; propriet` a

6

Sesta lezione: i teoremi limitativi I teoremi di G¨ odel e Church

6 / 233

Logica proposizionale; linguaggi predicativi

3

Terza lezione: verit` a e validit` a

Formule vere dovunque e vere in classi di modelli

4

Quarta lezione: dimostrazioni Sistemi formali per la derivabilit` a

1

Quinta lezione: l’aritmetica di Peano Un sistema di assiomi; propriet` a

6

Sesta lezione: i teoremi limitativi I teoremi di G¨ odel e Church

149 / 233

Aritmetica formale

Una teoria che formalizzi e descriva le propriet` a vere in N In un certo senso, che “caratterizzi N”. Che vuol dire?

I

Che ha N come unico modello?

I

Che prova tutte e sole le propriet` a vere in N?

I

Che sia in grado di distinguere N da altri eventuali modelli?

Hermann Grassmann, 1861. Lehrbuch der Arithmetik

Richard Dedekind, 1888. Was sind und was sollen die Zahlen?

Giuseppe Peano, 1889. Arithmetices principia, nova methodo exposita

150 / 233

a 2 N → succ(a) 2 N

a, b 2 N ∧ [a = b ↔ succ(a) = succ(b)]

a 2 N → succ(a) 6= 1

a, b 2 N → a + succ(b) = succ(a + b) a 2 N → a + 1 = succ(a)

a, b 2 N → a  succ(b) = a  b + a a 2 N → a  1 = a

se k ` e una classe

[1 2 k ∧ (x 2 k → succ(x) 2 k)] → N  k

151 / 233

Il ruolo dell’induzione

se k ` e una classe

[1 2 k ∧ (x 2 k → succ(x) 2 k)] → N  k

L’assioma di induzione ` e la vera “potenza” dell’aritmetica Senza di esso si potrebbero dimostrare solo enunciati puntuali, come

(3 + 5) + 1 = 3 + (5 + 1)

senza poter dimostrare il caso generale (certo vero in N):

8a8b8c [(a + b) + c = a + (b + c)]

E una ` propriet` a di chiusura:

Dice che (l’interpretazione di) N ` e il pi` u piccolo insieme che contiene 1 ed ` e “chiuso” rispetto al successore succ

152 / 233

a, b 2 N ∧ [a = b ↔ succ(a) = succ(b)]

a 2 N → succ(a) 6= 1

a, b 2 N → a + succ(b) = succ(a + b) a 2 N → a + 1 = succ(a)

a, b 2 N → a  succ(b) = a  b + a a 2 N → a  1 = a

se k ` e una classe

[1 2 k ∧ (x 2 k → succ(x) 2 k)] → N  k

153 / 233

Gli assiomi al prim’ordine: PA

L

: costanti: 0 a 2 N → succ(a) 2 N

a, b 2 N ∧ [a = b ↔ succ(a) = succ(b)]

a 2 N → succ(a) 6= 1

a, b 2 N → a + succ(b) = succ(a + b) a 2 N → a + 1 = succ(a)

a, b 2 N → a  succ(b) = a  b + a a 2 N → a  1 = a

se k ` e una classe

[1 2 k ∧ (x 2 k → succ(x) 2 k)] → N  k

154 / 233

L

a, b 2 N ∧ [a = b ↔ succ(a) = succ(b)]

a 2 N → succ(a) 6= 1

a, b 2 N → a + succ(b) = succ(a + b) a 2 N → a + 1 = succ(a)

a, b 2 N → a  succ(b) = a  b + a a 2 N → a  1 = a

se k ` e una classe

[1 2 k ∧ (x 2 k → succ(x) 2 k)] → N  k

155 / 233

Gli assiomi al prim’ordine: PA

L

: costanti: 0 L

: funzioni: succ

8a8b [succ(a) = succ(b) → a = b]

a 2 N → succ(a) 6= 1

a, b 2 N → a + succ(b) = succ(a + b) a 2 N → a + 1 = succ(a)

a, b 2 N → a  succ(b) = a  b + a a 2 N → a  1 = a

se k ` e una classe

[1 2 k ∧ (x 2 k → succ(x) 2 k)] → N  k

156 / 233

L

8a8b [succ(a) = succ(b) → a = b]

8a [succ(a) 6= 0]

a, b 2 N → a + succ(b) = succ(a + b) a 2 N → a + 1 = succ(a)

a, b 2 N → a  succ(b) = a  b + a a 2 N → a  1 = a

se k ` e una classe

[1 2 k ∧ (x 2 k → succ(x) 2 k)] → N  k

157 / 233

Gli assiomi al prim’ordine: PA

L

: costanti: 0 L

: funzioni: succ

8a8b [succ(a) = succ(b) → a = b]

8a [succ(a) 6= 0]

8a8b [a + succ(b) = succ(a + b)]

a 2 N → a + 1 = succ(a)

a, b 2 N → a  succ(b) = a  b + a a 2 N → a  1 = a

se k ` e una classe

[1 2 k ∧ (x 2 k → succ(x) 2 k)] → N  k

158 / 233

L

8a8b [succ(a) = succ(b) → a = b]

8a [succ(a) 6= 0]

8a8b [a + succ(b) = succ(a + b)]

8a [a + 0 = a]

a, b 2 N → a  succ(b) = a  b + a a 2 N → a  1 = a

se k ` e una classe

[1 2 k ∧ (x 2 k → succ(x) 2 k)] → N  k

159 / 233

Gli assiomi al prim’ordine: PA

L

: costanti: 0 L

: funzioni: succ

8a8b [succ(a) = succ(b) → a = b]

8a [succ(a) 6= 0]

8a8b [a + succ(b) = succ(a + b)]

8a [a + 0 = a]

8a8b [a  succ(b) = a  b + a]

a 2 N → a  1 = a se k ` e una classe

[1 2 k ∧ (x 2 k → succ(x) 2 k)] → N  k

160 / 233

L

8a8b [succ(a) = succ(b) → a = b]

8a [succ(a) 6= 0]

8a8b [a + succ(b) = succ(a + b)]

8a [a + 0 = a]

8a8b [a  succ(b) = a  b + a]

8a [a  0 = 0]

se k ` e una classe

[1 2 k ∧ (x 2 k → succ(x) 2 k)] → N  k

161 / 233

Gli assiomi al prim’ordine: PA

L

: costanti: 0 L

: funzioni: succ

8a8b [succ(a) = succ(b) → a = b]

8a [succ(a) 6= 0]

8a8b [a + succ(b) = succ(a + b)]

8a [a + 0 = a]

8a8b [a  succ(b) = a  b + a]

8a [a  0 = 0]

Sia P una formula con la sola x libera P(0) ∧ 8x [P(x) → P(succ(x))] → 8x P(x)

162 / 233

assicurano che il dominio (di ogni modello) ` e infinito

La definizione ricorsiva di somma e prodotto non d` a problemi Lo schema di induzione

P(0) ∧ 8x [P(x) → P(succ(x))] → 8x P(x) sostituisce alla quantificazione sulle classi

se k ` e una classe [1 2 k ∧ (x 2 k → succ(x) 2 k)] → N  k (cio` e sulla semantica dei predicati) la variabilit` a sulle formule Differenza di cardinalit` a sostanziale!

163 / 233

Modelli di PA

Non ` e difficile vedere che N |= PA

Ma: la costruzione di N `e “pi`u complessa” della teoria PA Invero: N |= PA implica la consistenza di PA

Per L¨ owenheim-Skolem esistono modelli in tutte le cardinalit` a infinite

Dunque PA ` e ben lungi dal “caratterizzare” (almeno in termini di modelli) N

164 / 233

Modelli numerabili diversi da N?

Si ottengono da un importante teorema della logica del primo ordine

Teorema di compattezza

Se tutti i sottoinsiemi finiti di un insieme di formule hanno un modello, allora anche l’intero insieme ha un modello

165 / 233

Modelli non standard

Se tutti i sottoinsiemi finiti di un insieme di formule hanno un modello, allora anche l’intero insieme ha un modello

Aggiungiamo a L

una nuova costante c , ottenendo L

. Su questo linguaggio, consideriamo le (infinite) formule

P

 c 6= n PA

= PA [ {P

}

Ogni sottoinsieme finito di PA

ha un ovvio modello (Esercizio: quale?)

Dunque PA

ha un modello; e un modello numerabile per LS Chiamiamo modello non standard di PA ogni modello numerabile di PA

166 / 233

Correttezza: PA ` Q =⇒ PA |= Q

Dunque, tutti i teoremi di PA son veri anche nei modelli non standard

Il che impone una struttura complessa in tali modelli

167 / 233

Qualche cenno alla struttura di un modello non standard

0 1 · · · n · · ·

Abbiamo ovviamente i naturali “standard”

168 / 233

Esiste un elemento d , diverso da tutti gli “standard” n PA ` 8n[0 < n]

PA ` 8n ¬9m[n < m ∧ m < succ(n)]

Dunque d deve stare dopo tutti gli altri

169 / 233

Qualche cenno alla struttura di un modello non standard

0 1 · · · n · · · d d + 1 · · ·

succ deve agire su d e PA ` succ(d) > d d ha dunque un successore: d + 1 E d + 1 ha un successore, e cos`ı via. . .

170 / 233

PA ` 8a [a 6= 0 → 9b succ(b) = a]

d ha dunque un predecessore: d-1 E d − 1 ha un predecessore, e cos`ı via. . .

171 / 233

Qualche cenno alla struttura di un modello non standard

0 1 · · · n · · · · · · d − 1 d d + 1 · · · · · · 2d − 1 2d 2d + 1 · · ·

Dove si situa d + d ?

PA ` 8a8b8c [a + b = a + c → b = c]

Ma allora, per ogni standard n, d + d 6= d + n d + d sta in un altro blocco rispetto a d

2d ha un successore e un predecessore, e cos`ı via

172 / 233

PA ` 8a  2 9b [a < b ∧ b < 2  a]

Esiste un (non standard) compreso tra d e 2d e vive in un blocco diverso da quello di d e 2d

173 / 233

Qualche cenno alla struttura di un modello non standard

0 1 · · · n · · · · · · d − 1 d d + 1 · · · · · · 2d − 1 2d 2d + 1 · · ·

· · · · · · · · · · · ·

PA ` 8a 6= 0 9b < a (2b = a ∨ 2b + 1 = a)

Per ogni non standard, esiste un non standard pi` u piccolo di lui e sta in un altro blocco

(Non esiste un non standard pi` u piccolo di tutti gli altri non standard)

174 / 233

PA ` 8a 6= 0(a + a > a)

Dunque per ogni non standard ne esiste uno pi` u grande di lui (e sta in un altro blocco)

175 / 233

Livelli di descrizione

Fissiamo un linguaggio, un sistema formale e un modello.

Esempi canonici: L

, PA, N oppure N

non standard.

Sia P(n) una propriet` a sul modello (P : N → {V , F }).

P ` e definibile, se esiste una formula Π

(n) tale che P(n) vero sse Π

(n) vero

P ` e rappresentabile (in modo forte), se esiste una formula Π

(n) tale che

I

per ogni n, se P(n) ` e vero, allora PA ` Π

(n)

I

per ogni n, se P(n) ` e falso, allora PA ` ¬Π

(n)

Per cardinalit` a, esistono infinite propriet` a non rappresentabili.

Non ci preoccuperanno molto (ma vedremo esempi per N

e N).

176 / 233

Corollario

Per un qualsiasi N

, non esiste alcuna formula S (x ) (nel linguaggio L

) tale che

S (n) vera sse n ` e standard

Non possiamo definire (separare) la parte standard di un modello per mezzo del linguaggio L

177 / 233

Alcuni personaggi in commedia

Le formule (esprimibili in L

) vere in N

I

costituiscono la teoria di N : Th( N)

Le formule (esprimibili in L

) vere in tutti i modelli

I

{P | PA |= P}

Le formule (esprimibili in L

) dimostrabili nella teoria formale

I

{P | PA ` P}

{P | PA ` P} = {P | PA |= P}  Th(N) (al prim’ordine)

178 / 233

d’induzione

P(0) ∧ 8x [P(x) → P(succ(x))] → 8x P(x) con l’assioma di induzione

8P [P(0) ∧ 8x [P(x) → P(succ(x))] → 8x P(x)]

179 / 233

PA 2 ` e categorica

PA

ha un solo modello (che ` e ovviamente N) Sia M |= PA

E facile vedere che ` M deve contenere “una copia” di N.

Sia essa St  M

Su M, sia P la propriet`a P(n) = V sse n 2 St Certo 0 2 St, dunque vale P(0)

Supposto n 2 St, sia ha anche n + 1 2 St, ovvero 8n[P(n) → P(succ(n))]

Ma allora, per l’induzione al secondo ordine, per ogni n 2 M, vale P(n), cio` e n 2 St

Dunque M = St

180 / 233

Perch´ e lo stesso ragionamento non si pu` o condurre per l’aritmetica del prim’ordine PA ?

Suggerimento: su quale propriet` a deve essere applicata l’induzione ?

E qual ` e la differenza sostanziale tra l’induzione in PA e quella in PA

?

181 / 233

Al second’ordine dunque. . .

Primo ordine:

{P | PA ` P} = {P | PA |= P}  Th(N)

Secondo ordine:

{P | PA

` P}  {P | PA

|= P} = Th

(N)

G¨ odel: entrambe le inclusioni sono proprie.

182 / 233