Alcuni dubbi di logica, dal Diavolo in cattedra di Odifreddi

[Lorenzo Pantieri]

Ciao a tutti!

Ho appena terminato di leggere (forse sarebbe meglio dire "studiare") il libro Il diavolo in cattedra di Piergiorgio Odifreddi. La materia è davvero appassionante ed importante -anche se non poco ostica-, l'autore brillante e competente. Purtroppo, nonostante sia laureato in matematica, non ho seguito nessun corso di logica, e si vede! Nello studio del lesto, ho accumulato diversi dubbi. Ve li espongo, con la speranza che qualcuno di voi sappia darmi qualche chiarimento: ve ne sarei davvero grato! Nell'esposizione, le pagine che sono riferite sono relative all'edizione Einaudi, 2003. Vi ringazio fin d'ora della vostra attenzione.

"Odifreddi":Un sistema si dice (p.221):
semanticamente corretto, se dimostra solo verità;
semanticamente completo, se dimostra tutte le verità;
sintatticamente corretto (o consistente), se non dimostra una formula e la sua negazione;
sintatticamente completo, se dimostra una formula o la sua negazione.

La logica proposizionale è semanticamente corretta e completa. Inoltre è sintatticamente corretta ma non completa (p.98).

La logica predicativa è semanticamente corretta e completa. Inoltre è sintaticamente corretta ma non completa (p.184).

Teorema di Rosser di incompletezza per i sistemi consistenti: sotto certe ipotesi, un sistema consistente è incompleto, sintatticamente e dunque anche semanticamente (p.224).

Che legame c'è fra completezza semantica e completezza sintattica? Dal "dunque" del teorema di Rosser sembrerebbe che la completezza semantica implichi quella sintattica, ma i teoremi di incompletezza semantica ma non sintattica per le logiche proposizionale e predicativa sembrano smentire questa implicazione. A me pare una contraddizione, ma certamente mi sfugge qualcosa!

Quando si parla di "incompletezza" (senza ulteriori specificazioni), si intende incompletezza semantica o sintattica?

Si può dire: "Un sistema è sintatticamente completo se non esiste nel sistema una formula indecidibile (cioè né dimostrabile né refutabile)"?

"Odifreddi":Il primo teorema di Goedel afferma sostanzialmente che nei sistemi formali consistenti e sufficientemente espressivi esistono verità indimostrabili (incompletezza semantica) e formule indecidibili (incompletezza sintattica) (p.219).

In generale, esempi di affermazioni indecidibili sono:
1. l'ipotesi del continuo nella teoria ZF degli insiemi con l'assioma di scelta;
2. l'assioma di scelta nella teoria ZF;
3. il quinto postulato nella geometria assoluta (geometria assoluta = sistema assiomatico dei primi quattro postulati di Euclide);

1. Un esempio di verità indimostrabile è, per esempio, il teorema di Goodstein nell'aritmetica di Peano;
2. Anche la frase che dice di sé stessa di non essere dimostrabile è una verità indimostrabile (primo teorema di Goedel).

Giusto?

Sapete darmi qualche altro esempio di "verità indimostrabile"?

A me pare che ci sia una bella differenza tra "affermazione indecidibile" e "verità indimostrabile". Infatti un'affermazione indecidibile può essere "elevata a ruolo di postulato", dando origine ad un "nuovo" sistema formale, oppure si può elevare a ruolo di postulato la sua negazione, ottenendo un sistema formale ancora diverso. Ad esempio si può affiancare ai primi quattro postulati di Euclide il quinto (ottenendo la geometria euclidea) o la sua negazione (ottenendo le geometrie non euclidee). Naturalmente, non si può elevare a ruolo di postulato la negazione di una verità indimostrabile. Giusto?

Vorrei sapere se è giusta la seguente affermazione: "Una proposizione è indecidibile in un sistema assiomatico quando è indipendente dagli assiomi. Per dimostrare che una proposizione è indecidibile in un sistema formale si deve dimostrare il fatto che tale proposizione sia vera o falsa non è in contraddizione con alcun assioma del sistema".

"Odifreddi":La logica predicativa monadica è decidibile, esattamente come quella proposizionale. La logica predicativa a più argomenti è indecidibile (p.248).

Un sistema consistente e completo è decidibile (p.249).

"Un sistema formale è detto decidibile se non esiste alcun algoritmo in grado di determinare se una formula è un teorema oppure no". Giusto? L'algoritmo deve essere unico per tutte le formule, o basta che ne esista uno per ogni formula?

Visto che la logica predicativa a più argomenti è semanticamente completa ma indecidibile, immagino che nell'implicazione "completezza implica decidibilità", la "completezza" sia quella sintattica e non semantica. Giusto?

"In altre parole: se un sistema non contiene affermazioni indecidibili, allora è decidibile". Il viceversa non vale (controesempio: la logica proposizionale). Giusto?

"Odifreddi":La teoria dei numeri reali è completa. Ne segue che, come ogni sistema formale completo, è decidibile (p.264).

La geometria è completa e decidibile (p.264).

La completezza di cui si parla in questi due casi è sintattica, semantica o sia sintattica sia semantica?

"Odifreddi":Una teoria è categorica quando descrive sostanzialmente un'unica realtà: tutti i modelli sono isomorfi tra loro. Una teoria categorica è completa. Il viceversa non vale. Ad esempio, la teoria dei numeri reali non è categorica, benché sia completa (p.268).

La completezza di cui si parla nell'implicazione "categorico implica completo" è sintattica, semantica o entrambe le cose?

"Odifreddi":Un sistema è (citazione tratta da Divertimento geometrico, p.31):
consistente, quando esiste un modello;
completo, quando ogni modello soddisfa le stesse proprietà;
categorico, quando c'è un solo modello di un data cardinalità (a meno di isomorfismi).

Giusto? La "completezza" qui è sintattica, semantica o entrambe?

Vorrei sapere se è giusto questo ragionamento: "Se la congettura di Goldbach fosse indecidibile, sarebbe vera! Infatti una qualunque formula aritmetica è vera o falsa per i numeri interi. Se si provasse che la congettura di Goldbach è indecidibile, non potrebbe essere falsa, perché allora si potrebbe esibire un controesempio, e questo sarebbe una refutazione della congettura".

Vi chiedo scusa per la lunghezza dell'intervento.

Grazie mille!
Lorenzo

[Malcolm1]

"Lorenzo Pantieri":Mi ricordo di averlo leggiucchiato durante il primo anno d'università, ma non ne sono rimasto fulminato. Il ricordo che mi è rimasto è di un lavoro un tantino prolisso e verboso... Anche se è un ricordo di tanti anni fa, non mi è più venuta la voglia di riprenderlo in mano... neppure dopo aver letto Odifreddi!
Ciao,
L.

A me invece aveva spaventato, la prima volta. Me lo fece vedere mio zio, quando avevo quindici anni circa, ma lo bollò come un libro "molto difficile" o qualcosa del genere. Qualche mese dopo lo vidi in libreria e decisi di comprarlo, con l'iniziale intento di ingrassare la mensola dei libri non letti.
Non mi ricordo perchè, ma un giorno, spinto da una specie di raptus, iniziai a leggerlo. Beh, ci ho messo un mese (la prima volta), ma posso dire con certezza che è stato uno dei due libri che mi hanno cambiato la vita.
Se hai un po' di tempo, prendilo in mano. Non avrà l'effetto dirompente che ha avuto sul me sedicenne, ma è una lettura molto affascinante.

[Lorenzo Pantieri]

"Malcolm":
Questo, oltre che il mio libro preferito (cosa che non interessa a nessuno), è l'opera di un genio (cosa che dovrebbe interessare a qualcuno).
Non è che è consigliabile leggerlo, è OBBLIGATORIO!

Mi ricordo di averlo leggiucchiato durante il primo anno d'università, ma non ne sono rimasto fulminato. Il ricordo che mi è rimasto è di un lavoro un tantino prolisso e verboso... Anche se è un ricordo di tanti anni fa, non mi è più venuta la voglia di riprenderlo in mano... neppure dopo aver letto Odifreddi!

Ciao,
L.

[Malcolm1]

"motorhead":Questo è un famoso libro divulgativo che trattava anche di logica che lessi quando ero alle superiori.
Lo stile era molto simpatico (fantastici i dialoghi tra Achille e la tartaruga) ed i concetti erano chiari

http://www.amazon.com/Godel-Escher-Bach ... 0465026567

Questo, oltre che il mio libro preferito (cosa che non interessa a nessuno), è l'opera di un genio (cosa che dovrebbe interessare a qualcuno).
Non è che è consigliabile leggerlo, è OBBLIGATORIO!

[fields1]

"motorhead":Questo è un famoso libro divulgativo che trattava anche di logica che lessi quando ero alle superiori.
Lo stile era molto simpatico (fantastici i dialoghi tra Achille e la tartaruga) ed i concetti erano chiari

http://www.amazon.com/Godel-Escher-Bach ... 0465026567

Sì, è decisamente un classico e c'è anche in italiano... Anch'io l'ho letto alle superiori, molto carino.

[motorhead]

Questo è un famoso libro divulgativo che trattava anche di logica che lessi quando ero alle superiori.
Lo stile era molto simpatico (fantastici i dialoghi tra Achille e la tartaruga) ed i concetti erano chiari

http://www.amazon.com/Godel-Escher-Bach ... 0465026567

[fields1]

"Lorenzo Pantieri":Grazie ancora per le tue preziosissime risposte: se avrò ancora dei dubbi, saprò a chi rivolgermi!

Ti ringrazio per... i ringraziamenti

Questa è una delle ragioni per cui ho sempre trovato la filosofia un "sapere amatoriale"...

Basta pensare alla straordinaria trasformazione e agli eccezionali risultati ottenuti dalla logica a partire da quando è passata dall'indagine dei filosofi a quella dei matematici...

[Lorenzo Pantieri]

"fields":
Del resto anch'io iniziai con i libri divulgativi, che mi fecero abbastanza confusione. Poi all'università, con il rigore della matematica, e del primo eccezionale professore che ho avuto, mi si è tutto chiarito. Comunque il libro di Odifreddi è molto più che divulgativo, anche se non è al livello della logica che si studia all'università.

Grazie ancora per le tue preziosissime risposte: se avrò ancora dei dubbi, saprò a chi rivolgermi!

In generale, sono d'accordo sul fatto che solo con il rigore della matematica è possibile impostare e risolvere correttamente ed esaurientemente un problema... Questa è una delle ragioni per cui ho sempre trovato la filosofia un "sapere amatoriale"...

Ciao e ancora grazie,
Lorenzo

[Lorenzo Pantieri]

"Charlie Epps":Vorrei sapere se questo libro è adatto a essere letto per studenti delle superiori?

Ti consiglio di inziare dalle "Menzogne di Ulisse", che è più divulgativo (anche se copre sostanzialmente gli stessi argomenti). Se fai le superiori e ti piace la materia, è un must!

Ciao,
L.

[fields1]

Valide vuol dire "vere in ogni modello"?

Sì, lo dice anche Odifreddi, quando parla della logica proposizionale. In tal caso la validità di una formula consiste nell'essere sempre vera (i.e. tutte le possibili tabelle di verità per la formula danno valore vero)(nel caso della logica proposizionale i modelli sono semplicemente tavole di verità).

Comunque già la materia è incasinata, se poi si indicano con lo stesso nome due cose diverse, si introduce un'inevitabile confusione. Come vengono chiamati da altri autori la "completezza-semantica-nel-senso-che-tutte-le-formule-valide-vengono-dimostrate" e la "completezza-semantica-nel-senso-che-tutte-le-formule-vere-vengono-dimostrate"?

Sì, infatti, in questo Odifreddi ha fatto un po' di confusione. Nei testi universitari di logica tale confusione non c'è, naturalmente.
La "completezza-semantica-nel-senso-che-tutte-le-formule-valide-vengono-dimostrate" viene chiamata semplicemente teorema di completezza. Tale teorema è un teorema che riguarda la logica, e non i particolari sistemi assiomatici che la logica produce. Ovvero: la logica proposizionale ha il suo teorema di completezza, la logica predicativa il proprio, la logica intuizionistica il proprio, la varie logiche modali hanno a loro volta il proprio e così via.. Il teorema di completezza dice che la logica in questione ha l'importantissima proprietà di collegare perfettamente il concetto di consequenzialità logica con quello di dimostrabilità: se un'affermazione segue da certi assiomi, allora la puoi dimostrare. Questo senza dubbio è uno dei più grandi risultati del pensiero logico (e non solo) umano.
La "completezza-semantica-nel-senso-che-tutte-le-formule-vere-vengono-dimostrate" non ricorre molto, perché si dà più importanza alla completezza sintattica. In ogni caso è sempre chiaro dal contesto a quale completezza ci si riferisce: si parlerà di completezza semantica di un sistema di assiomi, mentre invece si parlerà del teorema di completezza della logica XY.

Quanto al resto, le tue risposte sono tutte positive. Ne inferisco che, pur essendo autodidatta, qualcosa di buono ci ho tirato fuori!

Certo! Del resto anch'io iniziai con i libri divulgativi, che mi fecero abbastanza confusione. Poi all'università, con il rigore della matematica, e del primo eccezionale professore che ho avuto, mi si è tutto chiarito. Comunque il libro di Odifreddi è molto più che divulgativo, anche se non è al livello della logica che si studia all'università.

Cioè? Qual'è la definizione di completezza adottata qui da Odifreddi? Potresti dirmi qualcosa di più?

Qui tratta la completezza utilizzando la teoria dei modelli. In poche parole definisce un sistema di assiomi S completo se- per ogni coppia M e N di modelli di S- succede che M e N rendono vere le stesse formule, ovviamente fra quelle scritte nel linguaggio di S. Conseguenza di ciò e del già citato teorema di completezza, è che S è sintatticamente completo. Ed è vera anche l'implicazione inversa.

Vorrei sapere se questo libro è adatto a essere letto per studenti delle superiori?

E' impegnativo, ma tranquillamente leggibile da uno studente sveglio. Non tutto però potrà essere capito da chi non conosca già la logica. Comunque è scritto in modo da non richiedere nessuna preparazione matematica per essere letto, dunque adatto anche ai bravi studenti delle scuole superiori.

[Charlie Epps]

Vorrei sapere se questo libro è adatto a essere letto per studenti delle superiori?

[Lorenzo Pantieri]

"fields":I tuoi dubbi sono perfettamente comprensibili, Lorenzo, li avrei avuti anch'io se prima di leggere Odifreddi non avessi già studiato la logica.

Innanzitutto, grazie mille per le risposte!!

"fields":I termini completezza semantica e sintattica vengono usati da Odifreddi in modi diversi. Nel caso della logica proposizionale, con completezza semantica intende dire che tutte le formule valide vengono dimostrate. Nel caso dei sistemi formali come l'aritmetica di Peano con completezza semantica intende dire che tutte le formule vere vengono dimostrate (e per vere intende quelle che dicono verità sui numeri naturali). I concetti di validità e verità sono diversi. Dunque nel secondo caso effettivamente la completezza semantica implica quella sintattica, nel primo caso no.

Valide vuol dire "vere in ogni modello"?

Comunque già la materia è incasinata, se poi si indicano con lo stesso nome due cose diverse, si introduce un'inevitabile confusione. Come vengono chiamati da altri autori la "completezza-semantica-nel-senso-che-tutte-le-formule-valide-vengono-dimostrate" e la "completezza-semantica-nel-senso-che-tutte-le-formule-vere-vengono-dimostrate"?

Quanto al resto, le tue risposte sono tutte positive. Ne inferisco che, pur essendo autodidatta, qualcosa di buono ci ho tirato fuori!

"fields":Un sistema è:
consistente, quando esiste un modello;
completo, quando ogni modello soddisfa le stesse proprietà;
categorico, quando c'è un solo modello di un data cardinalità (a meno di isomorfismi).

La completezza qui descritta non si riferisce alle definizioni del "diavolo in cattedra". E' tuttavia equivalente alla completezza sintattica, ma tale equivalenza non è niente affatto banale.

Cioè? Qual'è la definizione di completezza adottata qui da Odifreddi? Potresti dirmi qualcosa di più?

Ancora grazie, grazie e grazie!

Ciao,
Lorenzo

[fields1]

I tuoi dubbi sono perfettamente comprensibili, Lorenzo, li avrei avuti anch'io se prima di leggere Odifreddi non avessi già studiato la logica.

Che legame c'è fra completezza semantica e completezza sintattica? Dal "dunque" del teorema di Rosser sembrerebbe che la completezza semantica implichi quella sintattica, ma i teoremi di incompletezza semantica ma non sintattica per le logiche proposizionale e predicativa sembrano smentire questa implicazione. A me pare una contraddizione, ma certamente mi sfugge qualcosa!

L'incongruenza deriva dal fatto che i termini completezza semantica e sintattica vengono usati da Odifreddi in modi diversi. Nel caso della logica proposizionale, con completezza semantica intende dire che tutte le formule valide vengono dimostrate. Nel caso dei sistemi formali come l'aritmetica di Peano con completezza semantica intende dire che tutte le formule vere vengono dimostrate (e per vere intende quelle che dicono verità sui numeri naturali). I concetti di validità e verità sono diversi. Dunque nel secondo caso effettivamente la completezza semantica implica quella sintattica, nel primo caso no.

Quando si parla di "incompletezza" (senza ulteriori specificazioni), si intende incompletezza semantica o sintattica?

Di solito s'intende incompletezza sintattica.

Si può dire: "Un sistema è sintatticamente completo se non esiste nel sistema una formula indecidibile (cioè né dimostrabile né refutabile)"?

Sì.

A me pare che ci sia una bella differenza tra "affermazione indecidibile" e "verità indimostrabile". Infatti un'affermazione indecidibile può essere "elevata a ruolo di postulato", dando origine ad un "nuovo" sistema formale, oppure si può elevare a ruolo di postulato la sua negazione, ottenendo un sistema formale ancora diverso. Ad esempio si può affiancare ai primi quattro postulati di Euclide il quinto (ottenendo la geometria euclidea) o la sua negazione (ottenendo le geometrie non euclidee). Naturalmente, non si può elevare a ruolo di postulato la negazione di una verità indimostrabile. Giusto?

Quello che dici sulla "affermazione indecidibile" è ok.

Naturalmente, non si può elevare a ruolo di postulato la negazione di una verità indimostrabile. Giusto?

Se il sistema è semanticamente corretto, si può elevare a ruolo di postulato la negazione di una verità indimostrabile A. Infatti, siccome non A è falsa, il sistema non dimostra non A. Dunque A è indecidibile, e da quanto tu stesso hai detto sopra, non A può diventare postulato. Naturalmente il sistema non sarà più semanticamente corretto. Tuttavia il sistema sarà sintatticamente corretto. Infatti il sistema senza non A fra gli assiomi è consistente, altrimenti non sarebbe semanticamente corretto. Ma allora il sistema con non A fra gli assiomi non può essere inconsistente, perché è noto che in tale caso il sistema dimostrerebbe A.

"Per dimostrare che una proposizione è indecidibile in un sistema formale si deve dimostrare il fatto che tale proposizione sia vera o falsa non è in contraddizione con alcun assioma del sistema".

Ok, anche se questa affermazione non è molto rigorosa.

Un sistema formale è detto decidibile se non esiste alcun algoritmo in grado di determinare se una formula è un teorema oppure no". Giusto? L'algoritmo deve essere unico per tutte le formule, o basta che ne esista uno per ogni formula?

Giusto. L'algoritmo deve valere per tutte le formule, altrimenti sarebbe facile costruire un algoritmo "ad hoc" per ciascuna formula che, nel caso particolare, azzecca la risposta giusta, tirando a indovinare (scriveremmo un algoritmo che dice sì, la formula è un teorema, e un altro che dice no, la formula non è un teorema, e uno dei due indovina).

Visto che la logica predicativa a più argomenti è semanticamente completa ma indecidibile, immagino che nell'implicazione "completezza implica decidibilità", la "completezza" sia quella sintattica e non semantica. Giusto?

Yes.

"In altre parole: se un sistema non contiene affermazioni indecidibili, allora è decidibile".

Esatto. L'idea è che, data una formula A, cerchi di dimostrare A e nel frattempo, separatamente, cerchi di dimostrare non A. Una delle due sarà dimostrabile e dunque in un tempo finito arriverai a dimostrare A o non A. Naturalmente il successo di questa operazione segue dal fatto che, se una formula è dimostrabile, in un tempo finito ne puoi trovare la dimostrazione con un algoritmo.

La teoria dei numeri reali è completa. Ne segue che, come ogni sistema formale completo, è decidibile (p.264).

La geometria è completa e decidibile (p.264).

La completezza di cui si parla in questi due casi è sintattica, semantica o sia sintattica sia semantica?

Sintattica.

Una teoria è categorica quando descrive sostanzialmente un'unica realtà: tutti i modelli sono isomorfi tra loro. Una teoria categorica è completa. Il viceversa non vale. Ad esempio, la teoria dei numeri reali non è categorica, benché sia completa (p.268).

La completezza dell'implicazione "categorica implica completa" è sintattica, semantica o entrambe le cose?

Si parla di completezza sintattica.

Un sistema è (citazione tratta da Divertimento geometrico, p.31):
consistente, quando esiste un modello;
completo, quando ogni modello soddisfa le stesse proprietà;
categorico, quando c'è un solo modello di un data cardinalità (a meno di isomorfismi).

Giusto? La "completezza" è sintattica, semantica o entrambe?

La completezza qui descritta non si riferisce alle definizioni del "diavolo in cattedra". E' tuttavia equivalente alla completezza sintattica, ma tale equivalenza non è niente affatto banale.

"Se la congettura di Goldbach fosse indecidibile, sarebbe vera! Infatti una qualunque formula aritmetica è vera o falsa per i numeri interi. Se la congettura fosse falsa, si potrebbe esibire un controesempio, e questo sarebbe una refutazione della congettura".

E' giusto questo ragionamento?

Sì.