From lecture notes by Lou van den Dries: http://www.math.uiuc.edu/~vddries/main.pdf

Proposition 5.5.7. - Every complete and computably axiomatizable L-theory is decidable.

Theorem 5.6.1 (Church)- No consistent L-theory extending $\underline{N}$ is decidable.

Corollary 5.6.2 (Weak form of Gödel's Incompleteness Theorem)- Each computably axiomatizable L-theory extending $\underline{N}$ is incomplete.

Proof 5.6.2 - Immediate from 5.5.7 and Church's Theorem.

Could someone explain me why/whether 5.6.2 is true? Presuming an theory is complete for a contradiction, we've found an L-theory extending $\underline{N}$ that is decidable. If it were inconsistent, we would get an contradiction with 5.6.1, but we're not presuming it's inconsistent, so I'm not sure how it would follow.

It also seems to me, like the following is a counter-example to 5.6.2:

Choose $T$ set of all L-sentences - $T$ itself is computable, so it is computably axiomatizable. It's also complete.


See the definition on page 22 - a complete theory is consistent:

We say that $\Sigma$ is complete if $\Sigma$ is consistent, and for each $p$ either $\Sigma\vdash p$ or $\Sigma\vdash\neg p$.

So the corollary is true. However, you are right that if we drop the assumption of consistency, then the corollary is false.

| cite | improve this answer | |
  • $\begingroup$ Thank you, somehow I forgot that it already contains consistency, and though that "Complete" only means "For each $p$, either $\Sigma\vdash p$ or $\Sigma\vdash \neg p$". $\endgroup$ – John P Dec 27 '16 at 9:38
  • 1
    $\begingroup$ @JohnP: Note that some (other) authors do not require completeness to require consistency. So also with some answers on Math SE. $\endgroup$ – user21820 Dec 27 '16 at 11:06

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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