Logica, discorso e conoscenza

Logica, discorso e conoscenza

Primo modulo:

Logica e verit` a (matematica) ovvero Logica, deduzione, verit` a

Lezioni 4, 5 e 6

Simone Martini

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

martini@cs.unibo.it

Collegio Superiore

Ottobre–novembre, 2006

Outline

1

Quarta lezione: dimostrazioni Sistemi formali per la derivabilit` a

2

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

3

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

4

Temi d’esame

Dimostrazioni come oggetti formali

Un linguaggio L

Un insieme di formule su L, gli assiomi Un insieme di regole di inferenza

Un insieme di (meta-)regole (sintattiche, combinatorie, effettive) che spiegano come le regole di inferenza permettono di “dedurre” nuove formule a partire da formula gi` a dedotte Un teorema ` e una formula dedotta dagli assiomi con una serie (finita) di applicazioni delle regole di inferenza

Nessun riferimento ad una specifica semantica o modello

inteso

Sistemi formali

Pluralit` a di “tipi” di sistemi formali:

alla Hilbert (assiomi e regole)

il pi` u antico; comodo per parlare dei modelli di una teoria deduzione naturale (Gentzen, 1934)

studio delle dimostrazioni come oggetti formali sequenti (Gentzen, 1934)

studio delle dimostrazioni, dimostrazioni di consistenza tableaux (Beth, 1955)

ricerca di dimostrazioni risoluzione (Robinson, 1963) ricerca di dimostrazioni

reti di dimostrazione (Girard, 1987)

dimostrazioni in logica lineare

ecc.

Esempio: logica positiva dell’implicazione alla Hilbert

(Schemi di) assioma

1

A → (B → A) assioma K

2

(A → (B → C)) → ((A → B) → (A → C)) assioma S Regola di inferenza

P → Q P

Q modus ponens

Meta-regole

1

Ogni istanza di un assioma ` e un assioma

2

Una derivazione ` e una sequenza di formule P

, P

, . . . , P

dove ogni P

` e:

F

un assioma, oppure

F

` e ottenuta mediante modus ponens da P

e P

, con j , k < i

Una derivazione

Vogliamo dimostrare A → A

(1) (A → ((A → A) → A)) → ((A → (A → A)) → (A → A)) assioma S (2) A → ((A → A) → A)

assioma K (3) (A → (A → A)) → (A → A) MP, da (1) e (2) (4) A → (A → A)

assioma K

(5) A → A MP, da (3) e (4)

Logica classica proposizionale, alla Hilbert

1

A → (B → A)

2

(A → (B → C)) → ((A → B) → (A → C))

3

B ∧ C → B

4

B ∧ C → C

5

B → (C → B ∧ C)

6

B → B ∨ C

7

C → B ∨ C

8

(B → D) → ((C → D) → (B ∨ C → D))

9

(B → C) → ((B → ¬C) → ¬B)

10

¬B → (B → C)

11

A ∨ ¬A

12

Regola: modus ponens

Logica classica dei predicati, alla Hilbert

1

Gli assiomi proposizionali

2

( 8xP(x)) → P(t)

3

P(t) → 9xP(x)

4

8x(Q → P(x)) → (Q → 8xP(x))

5

8x(P(x) → Q) → (9xP(x) → Q)

6

Regole di inferenza

I

modus ponens

I

P(x )

8xP(x) generalizzazione

Condizione aggiuntiva: In 4 e 5, Q non deve contenere x (libera)

Altri sistemi logici

Diverso ruolo reciproco di assiomi e regole

Diversa nozione di dimostrazione (e.g., no successione di formule, ma oggetto grafico bidimensionale)

Un certo sistema formale S d` a luogo ad una propria nozione di derivazione `

Equivalenza

Tutti i sistemi formali per la logica del prim’ordine sono equivalenti rispetto ai teoremi

cio` e, dati due sistemi formali S e S

, si ha

Γ `

A sse Γ `

A

La deduzione naturale:

calcolo minimale per ∧ e →

Assiomi: nessuno Regole:

A B

A ∧ B ∧I A ∧ B

A ∧E

A ∧ B

B ∧E

[A] .. ..

B

A → B → I A → B A

B → E

Deduzione naturale:

un esempio di dimostrazione

` A ∧ B → B ∧ A [A ∧ B]

A

[A ∧ B]

B

A ∧ B → B ∧ A

Dimostrazioni

`

A

la formula A ` e un teorema all’interno del sistema formale S Possiamo usare anche assiomi propri

Sia Γ un’insieme di formule (assiomi propri)

Una dimostrazione “da Γ ” (o “in Γ ”) ` e una dimostrazione in cui possono comparire (oltre ad assiomi o a formule

precedentemente derivate) anche (istanze del-) le formule di Γ Γ `

A

la formula A ` e un teorema all’interno del sistema formale S , con

assiomi propri Γ

Teoremi in specifiche teorie

I sistemi formali con assiomi propri permettono di indagare classi di strutture matematiche (di modelli)

Grp ` P

Ord ` P

PA ` P

Consistenza

Un certo sistema logico S ` e consistente se 6`

A ∧ ¬A In virt` u dell’equivalenza dei sistemi logici rispetto ai teoremi, possiamo considerare la consistenza come una propriet` a delle formule (e non dei sistemi formali)

Un insieme di formule Γ ` e consistente sse

Γ 6` A ∧ ¬A Se Γ inconsistente, Γ dimostra qualsiasi cosa:

per ogni B si ha Γ ` B

Consistenza, 2

Nozione sintattica molto importante

Sistemi formali quali il calcolo dei sequenti sono stati introdotti per dare dimostrazioni di consistenza I sistemi formali che abbiamo visto sono tutti, per se, consistenti

Importante: Consistenza di assiomi propri,

quali Ord, Grp, PA ?

Sintassi e semantica: correttezza

Teorema di correttezza (o validit` a, soundness):

Γ ` A =⇒ Γ |= A

In particolare, se ` A, allora A `e una legge logica

Consistenza, 3

L’esistenza di un modello per Γ implica, per correttezza, la consistenza di Γ

(la semantica ` e platonicamente consistente)

Ma la costruzione di un modello coinvolge strumenti semanticamente complessi (p.e., infinito)

Come dare dimostrazioni di consistenza sintattiche e

“semplici”?

Questo problema per l’aritmetica PA (quale fondamento

dell’intera matematica) ` e il cuore del progetto hilbertiano

In effetti, Gentzen con i sequenti dimostra la consistenza di

PA, ma in modo non soddisfacente secondo Hilbert (` e

necessariamente cos`ı, d’apr` es G¨ odel)

La nozione di dimostrazione ` e decidibile

Nella definizione di sistema formale dicemmo

E presente un insieme di (meta-)regole (sintattiche, combinatorie, ` effettive) che spiegano come le regole di inferenza permettono di

“dedurre” nuove formule a partire da formula gi` a dedotte Deve essere sempre possibile, ispezionando una sequenza di formule, decidere se si tratta di una dimostrazione nel senso tecnico di questa parola

Cio` e, la nozione di “essere una dimostrazione nel sistema S ” ` e decidibile

Propriet` a intrinseca di un sistema formale: se non vale, non

abbiamo un sistema formale

La nozione di teorema ` e decidibile?

Una formula A ` e un teorema sse esiste una dimostrazione per A

A differenza della nozione di dimostrazione, nella definizione di sistema formale nulla impone che i teoremi siano decidibili La nozione di sistema formale ci dice per` o che, se gli assiomi sono enumerabili, allora anche i teoremi sono enumerabili meccanicamente:

parti dagli assiomi ed applica le regole in tutti i modi possibili E ` semidecidibile se una formula ` e un teorema di una teoria con assiomi enumerabili

Lo Entscheidungsproblem alla radice della logica (e

dell’informatica) moderna

Sintassi e semantica: completezza

Teorema di completezza:

Γ |= A =⇒ Γ ` A

In particolare, se A ` e una legge logica, allora ` A.

Lo Entscheidungsproblem proposizionale ` e decidibile

Esiste un mezzo automatico per decidere se una formula proposizionale ` e una legge logica (tautologia):

le tabelle di verit` a

In virt` u del teorema di completezza, questo ` e un procedimento di decisione anche per la nozione di “teorema proposizionale”

Nel caso predicativo (puro) tale metodo non si pu` o applicare

Intermezzo: Una questione di cardinalit` a

Sia L

un linguaggio del prim’ordine e A un’interpretazione per L

, con dominio D

Una formula P(x ) su L

con una sola variabile libera x viene interpretata come [[P(x )]]

2 {V , F }

Ovvero (solo x ` e libera):

[[P(x )]]

: D → {V , F }

Quante sono le possibili funzioni D → {V , F }?

E quante sono le possibili formule P(x ) su L

?

Quante sono le formule?

L’alfabeto di L

` e numerabile (cio` e della cardinalit` a di N) Le formule sono certo non di pi` u di tutte le stringhe su tale alfabeto

. . .

Le formule sono al pi` u di cardinalit` a numerabile anch’esse

Quante sono le funzioni?

L’argomento “diagonale” di Cantor

Un ragionamento per assurdo mostra che le funzioni D → {V , F } non possono essere numerabili

Essendo certo di cardinalit` a infinita, esse sono di cardinalit` a strettamente maggiore di N

Ci sono (molte) pi` u funzioni che formule!

Ci sono (molte) pi` u propriet` a semantiche di quelle descrivibili

dal nostro linguaggio!

L’argomento diagonale di Cantor

Supponiamo D numerabile e anzi che D = N

Supponiamo che le funzioni N → {V , F } siano numerabili:

{f

}

Ogni funzione ` e una sequenza infinita (dove f

(n) 2 {V , F }) f

: f

(0), f

(1), f

(2), f

(3),


, f

(n),

Disponiamo i loro valori in una tabella infinita f

f

(0) f

(1) f

(2) . . . f

(i ) . . . f

f

(0) f

(1) f

(2) . . . f

(i ) . . . f

f

(0) f

(1) f

(2) . . . f

(i ) . . . .. .

f

f

(0) f

(1) f

(2) . . . f

(i ) . . .

.. .

L’argomento diagonale di Cantor, 2

Disponiamo i loro valori in una tabella infinita f

f

(0) f

(1) f

(2) . . . f

(i ) . . . f

f

(0) f

(1) f

(2) . . . f

(i ) . . . f

f

(0) f

(1) f

(2) . . . f

(i ) . . . .. .

f

f

(0) f

(1) f

(2) . . . f

(i ) . . . .. .

Definiamo la funzione g (n) = ¬f

(n)

Pu` o la funzione g

: N → {V , F } comparire tra le {f

}

?

No! Differisce da ciascuna di essa “sulla diagonale”

Questioni di cardinalit` a

There are more things in heaven and earth, Horatio, Than are dreamt of in your philosophy.

[W. Shakespeare, Hamlet, Act 1, Scene 5]

Ci son dunque (molte) pi` u propriet` a vere su N di quante la nostra logica potr` a mai nominare

Restringiamo la nostra attenzione alle propriet` a che possiamo descrivere col linguaggio (le sole alla nostra portata)

Siamo in grado di dimostrare tutte le formule vere in N?

Occorre in primo luogo un’assiomatizzazione (delle propriet` a

salienti) di N

Il teorema di L¨ owenheim-Skolem

Sia L

un linguaggio del prim’ordine Sia Γ un insieme di formule su L

Se Γ ha un modello di cardinalit` a infinita, Γ ha un modello di ogni cardinalit` a infinita.

Corollario: Ogni teoria con modelli infiniti ha un modello numerabile

Esempio: La teoria formale dei numeri reali

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

Gli assiomi di Peano

Da Arithmetices principia, con piccole modifiche notazionali. In rosso le modifiche all’assiomatica

1 2 N

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

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

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)

Commenti

Gli assiomi

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

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!

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

Il teorema di compattezza

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

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

Conseguenze del teorema di correttezza

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

Qualche cenno alla struttura di un modello non standard

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

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

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

Overspill

Se una propriet` a vale per infiniti standard, allora vale anche per qualche non standard

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

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)

L’aritmetica del second’ordine

La teoria formale del secondo ordine PA

sostituisce lo schema 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)]

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

Definiamo su M 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

Esercizio

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

?

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.

Incompletezza

Una teoria T ` e incompleta se esiste una formula G tale che n´ e T ` G, n´e T ` ¬G

Se T ` e incompleta ` e consistente Dunque ha modelli

Fissato uno di tali modelli, la formula “indipendente” G ` e vera o falsa, in quel modello

Per completezza, vi saranno modelli in cui G ` e vera ed altri in

cui G ` e falsa

Vari risultati di incompletezza

Sia T una teoria con assiomi decidibili, che includa abbastanza aritmetica.

Se T ` e vera (cio` e N `e un modello), `e incompleta Se T ` e consistente, ` e incompleta

E possibile ` costruire una formula G nel linguaggio L

, tale che, se T ` e vera, G testimonia l’incompletezza di T . E possibile ` costruire una formula G nel linguaggio L

, tale che, se T ` e (ω-)consistente, G testimonia l’incompletezza di T .

L’ultimo enunciato ` e propriamente il primo teorema di G¨ odel

Una prima idea (molto rozza)

Sostituire il paradosso del mentitore

I

“Questa frase ` e falsa”

(che non ` e un paradosso in PA, perch´ e non formalizzabile) con una formula della forma

I

“Questa formula non ` e dimostrabile”

Se la formula fosse dimostrabile, PA non sarebbe corretta Se non ` e dimostrabile non c’` e paradosso, ma. . .

Se ` e vera in N, `e una formula vera e non dimostrabile

Aritmetizzazione, 1

Aritemetizzazione = far corrispondere numeri e relazioni

aritmetiche ai concetti sintattici (linguaggio e derivazioni di PA).

Per il momento: tali relazioni sono semantiche (in N).

Esempi:

Ad ogni termine t un numero ptq Ad ogni formula A un numero pAq

Ad ogni successione di formule A

, . . . , A

un numero pA

, . . . , A

q

Informalmente:

p q : Sintassi −→ N

Funzioni effettive

I dettagli di p q non sono rilevanti Importante:

I

p q deve essere “davvero calcolabile” in termini di + e  Scopo:

I

trasformare la p q semantica in termini e formule di L

. Col senno di poi:

I

p q `e una funzione effettiva

Ovvero: (primitiva) ricorsiva, calcolabile secondo Turing, calcolabile da un programma di calcolatore ecc.

G¨ odel non aveva tale concetto e lo introduce!

Aritmetizzazione, 2

Un predicato effettivo Term(n) con valore 1 (vero) sse n ` e la codifica di un termine

I

Term( psucc(0)q) = 1

I

Term( p0 = 0q) = 0

Un predicato effettivo Fbf (n) con valore 1 (vero) sse n ` e la codifica di una formula

I

Fbf ( psucc(0)q) = 0

I

Fbf ( p0 = 0q) = 1

Un predicato effettivo Dimo(n) con valore 1 (vero) sse n ` e la codifica di una successione di formule

Un predicato effettivo Dim(n, m) sse n codifica una

dimostrazione della formula (il cui codice ` e) m

Predicati decidibili

Tutti i predicati visti sin’ora ammettono un procedimento (semantico) di decisione

Cio` e un programma che in tempo finito risponde SI o NO

Mappa del teorema, 1

Codificare le operazioni sintattiche come relazioni

(semantiche) aritmetiche X

“Riflettere” tali operazioni semantiche nella sintassi. . .

Lemma di rappresentazione

Se P(n, m) ` e un predicato decidibile, esiste una formula Π

(x , y ) che rappresenta (in modo forte) P. Cio` e:

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

(n, m)

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

(n, m)

Espressione (semantica) vs rappresentazione (sintattica)

Sul lemma di rappresentazione

Propriet` a sintattiche corrispondono a dimostrabilit` a di opportune formule

Il lemma vale per teorie molto pi` u deboli di PA. P.e., Aritmetica di Robinson (Q):

I

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

I

8a [succ(a) 6= 0]

I

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

I

8a [a + 0 = a]

I

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

I

8a [a  0 = 0]

I

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

Mappa del teorema, 2

Codificare le operazioni sintattiche come relazioni

(semantiche) aritmetiche X

“Riflettere” (rappresentare) tali operazioni semantiche nella

sintassi X

Autoriferimento. . .

Lemma di diagonalizzazione

Sia Π(x ) una formula con la sola x libera. Allora ` e possibile costruire una formula Ψ (senza variabili) tale che

PA ` Ψ ↔ Π(pΨq) Insomma:

Ψ ` e (nel sistema formale) la stessa cosa della formula Π(x )

applicata a (il numero di G¨ odel di) se stessa

Sul lemma di diagonalizzazione

La dimostrazione usa prima le tecniche di aritmetizzazione, poi il lemma di rappresentazione

Dunque la diagonalizzazione vale laddove vale la

rappresentazione

Mappa del teorema, 3

Codificare le operazioni sintattiche come relazioni

(semantiche) aritmetiche X

“Riflettere” (rappresentare) tali operazioni semantiche nella

sintassi X

Autoriferimento X

La formula g¨ odeliana. . .

Definiamo la formula Teor (x )  9y[Π

(y , x )]

Per diagonalizzazione costruiamo

G ↔ ¬Teor(pGq)

Primo teorema di G¨ odel versione semantica

Se PA ha assiomi veri (ovvero: se N `e un modello di PA), allora

PA 6` G e anche PA 6` ¬G.

G ` e vera

Segue “subito” che:

Se PA ha assiomi veri (ovvero: se N `e un modello di PA), allora N |= G .

Teor (x ) ↔ 9y[Π

(y , x )]

G ↔ ¬Teor(pGq) Sappiamo che PA 6` G

Dunque, per ogni n, Dim(n, pG q) `e falso

Per il lemma di rappresentazione, PA ` ¬Π

(n, pG q)

Per correttezza, N |= ¬Π

(n, pG q), per ogni n

Che ` e lo stesso che N |= ¬9xΠ

(x , pG q)

Ovvero N |= ¬Teor (pG q)

Sulla versione semantica

Abbiamo una formula G

Che ` e vera nel modello standard N Ma n´ e PA ` G, n´e PA ` ¬G

Il teorema ` e sufficiente se siamo convinti della consistenza di PA

Ma ` e inutile se vogliamo indagare la consistenza

Osserva: il teorema vale anche per Q!

Incompletezza e Incompletabilit` a

Sia PA

= PA + G Ora PA

` G

Ma l’esistenza di G dipende dal solo lemma di rappresentazione

Possiamo rifare tutto, in riferimento a PA

Otterremo G

indipendente in PA

E cos`ı via. . .

Incompletabilit` a di PA (a dire il vero: di Q)

Primo teorema di G¨ odel versione semantica

Sia T un’estensione di Q i cui assiomi siano decidibili e veri in N.

E possibile costruire una formula G `

(nel linguaggio L

) per cui

T 6` G

e anche T 6` ¬G

.

Incompletabilit` a

Se vogliamo teorie con assiomi decidibili

e corrette (cio` e i cui assiomi sono veri in N)

non possiamo avere teorie complete

Primo teorema di G¨ odel (-Rosser) versione sintattica

Sia T un’estensione consistente di Q con assiomi decidibili.

E possibile costruire una formula G `

(nel linguaggio L

) per cui

T 6` G

e anche T 6` ¬G

.

Anche PA 2 . . .

Teorema (G¨ odel-Rosser)

Sia T un’estensione consistente di Q con assiomi decidibili.

E possibile costruire una formula G `

(nel linguaggio L

) per cui T 6` G

e anche T 6` ¬G

.

PA

` e un’estensione di Q con assiomi decidibili.

Se PA

` e consistente, ` e incompleta (e incompletabile) Certo, PA

dimostra cose che PA non dimostra:

I

PA

` G

PA

6` G

PA 2 non gode del thm di completezza

PA

6` G

PA

|= G

per gli stessi motivi per cui N |= G

Dunque:

PA

|= P 6=⇒ PA

` P

Al prim’ordine:

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

Al second’ordine:

{P | PA

` P}  {P | PA

|= P} = Th(N)

Verso gli altri teoremi limitativi

Gli ingredienti fondamentali del teorema di G¨ odel:

Lemma di rappresentazione

Tutte le funzioni effettivamente calcolabili sono rappresentabili in modo forte in Q

Lemma di diagonalizzazione

Segue da rappresentazione, se la sintassi ` e effettivamente calcolabile

permettono di stabilire anche:

1

Teorema di Church

2

Teorema di Tarski

Il teorema di Church

Sia T un’estensione consistente di Q con assiomi decidibili.

La nozione di essere un teorema di T non ` e decidibile.

Il teorema segue da questo lemma

Sia T un’estensione consistente di Q con assiomi decidibili.

La nozione di essere un teorema di T (cio` e il predicato Teor (n)) non ` e rappresentabile in modo forte in T .

che mostra le relazioni con le altre nozioni viste sino a qui.

Conseguenze per il calcolo puro

La nozione di essere un teorema del calcolo dei predicati puro (cio` e senza assiomi) non ` e decidibile.

Dim.: Il teorema di Church si applica all’aritmetica di Robinson Q.

Q ha un numero finito di assiomi (a differenza di PA).

Allora Q ` P sse ` ∧Q → P.

Che fine ha fatto “il mentitore”?

G¨ odel riposa sulla riflessione del metalinguaggio nel linguaggio Allora forse “questa frase ` e falsa” ` e una proposizione

Certo il lemma di diagonalizzazione permette di dire

“questa frase...”

E possibile riflettere in ` L

la metateoria semantica (cio` e la

nozione di vero/falso)?

Un predicato di verit` a

Definiamo il predicato True(n) vero sse

n ` e il numero di G¨ odel di una formula (in L

) vera in N Esiste una formula T (x ) (in L

) che definisca True?

Cio` e per la quale valga:

True(n) vero in N sse T (n) vera in N

Il teorema di Tarski

Non esiste nel linguaggio L

alcuna formula che definisca True.

Livelli di descrizione

Sia P(n) una qualche propriet` a su N.

P ` e definibile, se esiste una formula Π

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

(n) vero

P ` e rappresentabile, 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)

Livelli di descrizione, 2

Esistono propriet` a non definibili: True(n)

Esistono propriet` a definibili, ma non rappresentabili: ¬Teor(n) Teor (n) ↔ 9xΠ

(x , y )

Esistono propriet` a rappresentabili: ogni propriet` a decidibile

Livelli di descrizione, 3

Lemma (rappresentazione):

Decidibile = Rappresentabile (in modo forte)

Verso il secondo teorema di G¨ odel

(Mezzo) enunciato del primo teorema Se PA ` e consistente, allora PA 6` G Pu` o essere espresso nel linguaggio di PA Sia Con ↔ ¬Teor(pA ∧ ¬Aq)

E scriviamo

Con → ¬Teor(pGq)

Il secondo teorema di G¨ odel

Non solo l’enunciato del primo teorema ` e esprimibile. ` E addirittura dimostrabile all’interno di PA:

Teorema

PA ` Con → ¬Teor(pGq) Ma allora:

Teorema (II teorema di G¨ odel)

Se PA ` e consistente, allora PA 6` Con.

perch´ e altrimenti avremmo PA ` ¬Teor(pGq), ovvero (per

costruzione di G ), PA ` G, che contraddice il primo teorema.

Vale per teorie pi` u semplici?

Il secondo teorema non vale per Q Qualche forma di induzione ` e necessaria

Occorre l’assioma d’induzione almeno per formule della forma

9xA , con A senza quantificatori. (Σ

-formule)

PA ` e incompleta solo in casi patologici?

Le formule G e Con sono un caso patologico

Forse PA “decide” tutti i casi di genuino interesse matematico No!

I

una variante del teorema di Ramsey finito, Paris & Harrington, 1977

I

teorema di Goodstein Kirby & Paris, 1980

I

molti altri. . .

Verso il teorema di Goodstein, 1

1

Rappresentazione pura di n in base k

I

Rappresenta n come somma di potenze di k Esempio: 266 = 2

+ 2

+ 2

266 = 3

+ 3

+ 3

+ 3

+ 3

+ 3

I

Riscrivi gli esponenti di k come somma di potenze di k 266 = 2

+ 2

+ 2

I

E cos`ı via 266 = 2

0+20 )

+ 2

+ 2

266 = 3

+ 3

+ 3

+ 3

+ 3

Verso il teorema di Goodstein, 2

2

Bump: B

(n)

Prendi la rappresentazione pura di n in base k e cambia k in k + 1; sottrai 1

B

(266) = 3

0+30)

+ 3

+ 3

− 1  3.990838  10

B

(19) = 7625597484990

3

Sequenza di Goodstein:

G (n) = n, B

(n), B

(B

(n)), B

(B

(B

(n))), . . . Esempi:

G (3) = 3, 3, 3, 2, 1, 0

G (4) = 4, 26, 41, 60, 83, 109, 139, 173, 211, 253, 299, 348, . . .

G (6) = 6, 29, 257, 3125, 46655, 98039, 187243, . . .

Il teorema di Goodstein

Teorema (Goodstein)

Per ogni n, G (n) termina su zero.

Teorema (Kirby & Paris, 1982)

L’enunciato del teorema di Goodstein ` e formalizzabile in PA, ma non ` e dimostrabile in PA.

Siccome PA ` e corretta, neppure la negazione del teorema ` e

dimostrabile in PA.

Vero e non dimostrabile

La validit` a del teorema di Goodstein non ` e un atto di fede Abbiamo dimostrazioni perfette, ma. . .

esse utilizzano strumenti/concetti non esprimibili in PA Thm di Goodstein: ordinali

Variante del Thm di Ramsey finito: lemma di K¨ onig

Lemma di K¨ onig

Un albero infinito che ad ogni nodo interno ha un numero finito di figli, ha un cammino infinito.

Questo riferimento all’infinito non pu` o essere formalizzato in PA.

Principio di buon ordinamento

Un insieme non vuoto di numeri naturali possiede un elemento pi` u piccolo di tutti gli altri.

Questo riferimento alla struttura ordinata (“geometrica”) non pu` o essere formalizzato in PA.

Invero: tale principio implica l’induzione al secondo ordine.

Le dimostrazioni in PA sono

“aritmetiche”?

[Una formula ` e dimostrabile in PA se] its truth or falsity [is]

perceived directly on the basis of [...] the fundamental nature and structure of the natural numbers.

[D. Isaacson, Some consideration on arithmetical truth and the ω-rule]

` E una posizione difendibile/ragionevole?

Commenti

Scarto tra “principi di costruzione” e “principi di dimostrazione” [Bailly&Longo]

Principi di costruzione

I

Intuizione spazio-temporale della successione naturale Principi di dimostrazione

I

Induzione formale al I ordine

Gli enunciati “indipendenti” (e.g., Goodman) usano propriet` a (e.g., buon ordinamento) evidenti all’intuizione

spazio-temporale, ma non colti dall’induzione.

Il formalismo ` e una visione limitata dell’accesso alla verit` a

(aritmetica)

Commenti, 2

Il formalismo ha dato vita alla (e sopravvive nella) informatica

Ma la bont` a del prodotto (le macchine calcolatrici) non

giustifica il formalismo come filosofia della matematica. . .

Temi d’esame

1

Il paradosso del mentitore: soluzioni moderne (non semplice) (Etchemendy)

2

Il programma di Hilbert per la fondazione della matematica

3

I teoremi di completezza e compattezza per la logica dei predicati

4

Un sistema formale per la logica dei predicati: deduzione naturale

5

Un sistema formale per la logica dei predicati: calcolo dei sequenti

6

Un sistema formale per la logica dei predicati: risoluzione

7

Un sistema formale per la logica dei predicati: tableaux

8

La nozione di decidibilit` a (ovvero: rudimenti di calcolabilit` a)

9

Il teorema di Goodstein (richiede nozioni elementari di aritmetica ordinale)

10

Il lemma di diagonalizzazione (richiede rudimenti di calcolabilit` a)

11

Il lemma di rappresentazione (ovvero: aritmetizzazione della sintassi; per chi ama le codifiche combinatorie)

12

La discussione “filosofica” sul teorema di G¨ odel (p.e. Minds, machines and G¨ odel di Lukas ecc.)

13

Il teorema di G¨ odel nella versione originale (ω-completezza).