3
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\begingroup$ I think you're mixing up propositional and first-order logic. The incompleteness theorem applies to first-order logic, not propositional logic. $\endgroup$
    – templatetypedef
    Aug 23, 2014 at 18:13
  • $\begingroup$ I have stated that his theorem applies to FOL. My confusion stemmed from the wrong assumption of what constitutes a FOL theory, in particular the language part of it. $\endgroup$
    – bellpeace
    Aug 23, 2014 at 18:30

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Simple follow-up question. Does one usually prove (in)completeness w.r.t. a subset of the language also? As far as I know, PA axioms do not tell anything about propositional atoms, so incompleteness would then trivially hold by my argument. $\endgroup$
    – bellpeace
    Aug 23, 2014 at 14:37
  • $\begingroup$ I don't really understand the question. Please elaborate, preferably as a new post. $\endgroup$
    – Shaull
    Aug 23, 2014 at 15:50
  • $\begingroup$ I'll try to do it here, as it is probably just my simple misunderstanding. Consider the theory of PA, and consider any propositional atom $p$. Then, again you cannot prove $p$ nor $\neg p$, hence incompleteness. We don't consider propositional atoms in PA? Basically, are we just focusing on a subset of FOL language in this case? $\endgroup$
    – bellpeace
    Aug 23, 2014 at 16:18
  • 1
    $\begingroup$ Well, PA is a first-order theory. There, propositional atoms are captured by 0-ary relations. In PA, there are no 0-ary relations, so you can't even say $p$. This makes this problem nonexistent. $\endgroup$
    – Shaull
    Aug 23, 2014 at 16:24
  • $\begingroup$ Ok, this is what I had in mind when saying a subset of the FOL language. Thanks! $\endgroup$
    – bellpeace
    Aug 23, 2014 at 18:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.