patternMinor
Propositional logic --- syntactical completeness
Viewed 0 times
completenesslogicpropositionalsyntactical
Problem
Lets consider propositional logic. We say a proof system for propositional logic is syntactically (negation) complete if for every $\alpha$, either $\alpha$ or $\neg \alpha$ are provable within the system, i.e., $\Sigma \vdash \alpha$ or $\Sigma \vdash \neg \alpha$. (I assume standard definitions for $\Sigma$ and $\vdash$).
It seems to be me that no sound proof system for propositional logic could prove $p$ or $\neg p$ from empty set of sentences, where $p$ is a propositional atom. So, propositional logic is not syntactically complete.
Now, it is to my understanding that this is kind of completeness Godel was considering in his Incompleteness Theorem for FOL. Since FOL (with abuse of terminology) subsumes propositional logic, it trivially holds that FOL is not syntactically complete either. This seems to simple, so I am wondering what am I doing wrong? Or his proof focused on Peano arithmetic specifically?
Related: link
It seems to be me that no sound proof system for propositional logic could prove $p$ or $\neg p$ from empty set of sentences, where $p$ is a propositional atom. So, propositional logic is not syntactically complete.
Now, it is to my understanding that this is kind of completeness Godel was considering in his Incompleteness Theorem for FOL. Since FOL (with abuse of terminology) subsumes propositional logic, it trivially holds that FOL is not syntactically complete either. This seems to simple, so I am wondering what am I doing wrong? Or his proof focused on Peano arithmetic specifically?
Related: link
Solution
You are not doing anything "wrong", you just missed the point of the incompleteness theorem, a bit.
What you claim (correctly) is that a proof system with no axioms is incomplete. You also say that this is not very impressive...
What Godel showed is something much stronger: consider the theory of Peano arithmetic, then there does not exist a complete axiomatization for it.
How does this relate to your post? Well, in your suggestion, even when you consider an empty set of axioms, there are still some true sentences (the tautologies), and there are axiom systems that capture exactly those sentences.
What you claim (correctly) is that a proof system with no axioms is incomplete. You also say that this is not very impressive...
What Godel showed is something much stronger: consider the theory of Peano arithmetic, then there does not exist a complete axiomatization for it.
How does this relate to your post? Well, in your suggestion, even when you consider an empty set of axioms, there are still some true sentences (the tautologies), and there are axiom systems that capture exactly those sentences.
Context
StackExchange Computer Science Q#29336, answer score: 5
Revisions (0)
No revisions yet.