Relationship between Church's theorem and weak form of Gödel's incompleteness theorem

87 Views Asked by At

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.

1

There are 1 best solutions below

2
On BEST ANSWER

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.