Question

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

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top