Teorie complete - LOGICA
Buongiorno, ho un dubbio sulla logica del primo ordine, in particolare vorrei capire perché $Th(\mathbb{N},0,S,+,\cdot )$ non è completa. Con la notazione $Th(...)$ intendo "tutte le formule CHIUSE vere sulla struttura in argomento"
In particolare $Th(\mathbb{N},0,S,+,\cdot )$ è l'insieme di tutti i teoremi veri su $\mathbb{N}$ dotato della somma, prodotto e successore (la funzione $S(n)=n+1$).
Ricordo inoltre che una teoria completa è un insieme di formule $T$ tale che per ogni formula $\phi$ si ha che
$T\vdash\phi$ oppure $T\vdash\not\phi$.
Ora che abbiamo chiarito un po' di notazione, che non sempre può essere comune, approfondisco la domanda: come è possibile che $Th(M$, struttura a caso$)$ possa non essere completa? Una formula CHIUSA è VERA o FALSA su UNA struttura, quindi presa una formula $\phi$ si avrà che $M\models\phi$ oppure $M\cancel\models\phi$. Nel primo caso $\phi\in Th(M)$ e quindi $Th(M)\vdash\phi$, nel secondo caso invece $M\models\not\phi$ e similmente a prima si avrà $Th(M)\vdash\not\phi$.
In particolare $Th(\mathbb{N},0,S,+,\cdot )$ è l'insieme di tutti i teoremi veri su $\mathbb{N}$ dotato della somma, prodotto e successore (la funzione $S(n)=n+1$).
Ricordo inoltre che una teoria completa è un insieme di formule $T$ tale che per ogni formula $\phi$ si ha che
$T\vdash\phi$ oppure $T\vdash\not\phi$.
Ora che abbiamo chiarito un po' di notazione, che non sempre può essere comune, approfondisco la domanda: come è possibile che $Th(M$, struttura a caso$)$ possa non essere completa? Una formula CHIUSA è VERA o FALSA su UNA struttura, quindi presa una formula $\phi$ si avrà che $M\models\phi$ oppure $M\cancel\models\phi$. Nel primo caso $\phi\in Th(M)$ e quindi $Th(M)\vdash\phi$, nel secondo caso invece $M\models\not\phi$ e similmente a prima si avrà $Th(M)\vdash\not\phi$.
Risposte
Non sono un esperto, quindi prendi con le pinze quello che dico.
Secondo me fai confusione con due concetti differenti di completezza.
Completezza sintattica:
Una teoria \(T\) è sintatticamente completa se per ogni formula si ha \( T \vdash \varphi \) oppure \( T \vdash \neg \varphi \).
Completezza semantica:
Data una teoria \(T\), è detta semanticamente completa se dato un modello \(M\) e una formula \( \varphi \) tale che \(M \models \varphi \) allora \( T \vdash \varphi \).
Chiarezza sui simboli:
- \( M \models \varphi \) significa che la formula è valida (vera) nel modello \(M\), ovvero interpretando i simboli nel modello \(M\).
- \( T \models \varphi \) significa che per ogni modello \(M\) di \(T\) si ha \( M \models \varphi \), in tal caso la formula \( \varphi \) si dice universalmente valida.
- \(T \vdash \varphi \) vuol dire che esiste una procedura finita per dedurre sintatticamente \( \varphi \) da \(T\).
Il teorema di incompletezza di Godel afferma che ogni teoria consistente \(T\) che contiene l'aritmetica è incompleta (sintattticamente), i.e. non è possibile affermare se \( T \vdash \varphi \) e neppure se \( T \vdash \neg \varphi \).
Il teorema di completezza (semantico) di Godel afferma che se una formula è universalmente valida, i.e. \( T \models \varphi \) allora \( T \vdash \varphi \), il viceversa è sempre vero.
Dunque l'aritmetica di Peano essendo incompleto sintatticamente vuol dire che possiede almeno una formula espressa su questo linguaggio tale per cui non si ha \( T \vdash \varphi \) e neppure se \( T \vdash \neg \varphi \), questa formula \( \varphi \) non può essere universalmente valida, quindi esistono due modelli \(M\) ed \(N\) tale per cui \(M \models \varphi \) e \( N \not \models \varphi \) e dunque non puoi applicare il teorema di completezza di Godel per \( \varphi \) e non puoi dunque affermare \( T \vdash \varphi \).
Secondo me fai confusione con due concetti differenti di completezza.
Completezza sintattica:
Una teoria \(T\) è sintatticamente completa se per ogni formula si ha \( T \vdash \varphi \) oppure \( T \vdash \neg \varphi \).
Completezza semantica:
Data una teoria \(T\), è detta semanticamente completa se dato un modello \(M\) e una formula \( \varphi \) tale che \(M \models \varphi \) allora \( T \vdash \varphi \).
Chiarezza sui simboli:
- \( M \models \varphi \) significa che la formula è valida (vera) nel modello \(M\), ovvero interpretando i simboli nel modello \(M\).
- \( T \models \varphi \) significa che per ogni modello \(M\) di \(T\) si ha \( M \models \varphi \), in tal caso la formula \( \varphi \) si dice universalmente valida.
- \(T \vdash \varphi \) vuol dire che esiste una procedura finita per dedurre sintatticamente \( \varphi \) da \(T\).
Il teorema di incompletezza di Godel afferma che ogni teoria consistente \(T\) che contiene l'aritmetica è incompleta (sintattticamente), i.e. non è possibile affermare se \( T \vdash \varphi \) e neppure se \( T \vdash \neg \varphi \).
Il teorema di completezza (semantico) di Godel afferma che se una formula è universalmente valida, i.e. \( T \models \varphi \) allora \( T \vdash \varphi \), il viceversa è sempre vero.
Dunque l'aritmetica di Peano essendo incompleto sintatticamente vuol dire che possiede almeno una formula espressa su questo linguaggio tale per cui non si ha \( T \vdash \varphi \) e neppure se \( T \vdash \neg \varphi \), questa formula \( \varphi \) non può essere universalmente valida, quindi esistono due modelli \(M\) ed \(N\) tale per cui \(M \models \varphi \) e \( N \not \models \varphi \) e dunque non puoi applicare il teorema di completezza di Godel per \( \varphi \) e non puoi dunque affermare \( T \vdash \varphi \).
Ciao, per prima cosa ti ringrazio per il tempo che mi hai dedicato nel rispondermi!
Per... "completezza" risponderò da solo alla mia domanda, infatti dopo un paio di settimane in cui mi arrovellavo il cervello ho finalmente trovato la soluzione:
Per prima cosa bisogna sapere che pensavo che $Th(\mathbb{N},0,+,\cdot,S)$ non fosse completa perché così avevo sentito a lezione (e la lezione era stata registrata, per cui l'ho ascoltata diverse volte). In realtà questa si è rivelata essere una piccola svista del professore, dunque, in effetti $Th(\mathbb{N})$ è completa, e non solo, per il ragionamento che ho fatto nel testo della domanda $Th($qualcosa$)$ è completo.
Rispondendo a te: è vero che ci sono due concetti diversi indicati dalla parola "completezza", ma nel mio caso non li ho confusi. Il mio problema era che pensavo che la teoria $Th(\mathbb{N})$, per come è definita, dovesse essere completa, MA in una lezione veniva chiaramente detto che non lo era.
Per concludere voglio specificare che il teorema di incompletezza non si applica in questo caso, infatti esso afferma che ogni sistema di assiomi RICORSIVAMENTE ENUMERABILE che contiene gli assiomi di Peano (ma basta anche meno) è incompleto! Il punto è che $Th(\mathbb{N},0,+,\cdot,S)$ NON è ricorsivamente enumerabile e quindi può essere (e nella fattispecie è) completo.
Ringrazio ancora chi ha risposto o anche solo letto e pensato al problema e scusate la confusione che ho fatto
Per... "completezza" risponderò da solo alla mia domanda, infatti dopo un paio di settimane in cui mi arrovellavo il cervello ho finalmente trovato la soluzione:
Per prima cosa bisogna sapere che pensavo che $Th(\mathbb{N},0,+,\cdot,S)$ non fosse completa perché così avevo sentito a lezione (e la lezione era stata registrata, per cui l'ho ascoltata diverse volte). In realtà questa si è rivelata essere una piccola svista del professore, dunque, in effetti $Th(\mathbb{N})$ è completa, e non solo, per il ragionamento che ho fatto nel testo della domanda $Th($qualcosa$)$ è completo.
Rispondendo a te: è vero che ci sono due concetti diversi indicati dalla parola "completezza", ma nel mio caso non li ho confusi. Il mio problema era che pensavo che la teoria $Th(\mathbb{N})$, per come è definita, dovesse essere completa, MA in una lezione veniva chiaramente detto che non lo era.
Per concludere voglio specificare che il teorema di incompletezza non si applica in questo caso, infatti esso afferma che ogni sistema di assiomi RICORSIVAMENTE ENUMERABILE che contiene gli assiomi di Peano (ma basta anche meno) è incompleto! Il punto è che $Th(\mathbb{N},0,+,\cdot,S)$ NON è ricorsivamente enumerabile e quindi può essere (e nella fattispecie è) completo.
Ringrazio ancora chi ha risposto o anche solo letto e pensato al problema e scusate la confusione che ho fatto
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo