0
$\begingroup$

The theorem as stated in my mathematical logic textbook says:

Godel's First Incompleteness Theorem. Let $\Phi$ be consistent and $R$-decidable and suppose $\Phi$ allows representations. Then there is an $S_ {ar}$-sentence $\phi$ such that neither $\Phi\vdash\phi$ nor $\Phi\vdash\neg\phi$.

Is it correct to use the Completeness theorem for first order logic to change the end to:

Then there is an $S_ {ar}$-sentence such that neither $\Phi\vdash\phi$, nor $\Phi\vdash\neg\phi$, and neither $\Phi\vDash\phi$ nor $\Phi\vDash\neg\phi$.


Moreover, I have been thinking about how to understand the first incompleteness theorem more intuitively. I've reached, using informal proof, a conclusion that seems like it must be wrong (since otherwise, I would have heard of it before).

What is wrong with my argument? (or is it correct?)

Firstly, it seems that this follows from the theorem:

Corollary. For every structure $\mathfrak{A}$, there is no consistent and decidable set of first-order formulas $\Phi$ that has as its consequence its first-order theory $Th(\mathfrak{A})$. That is, there is no such $\Phi$ such that $\Phi\vDash Th(\mathfrak{A})$.

Which seems to be equivalent to:

Corollary. There is no structure that has an axiomatizable theory in first-order logic.

my informal argument is: If there were such a structure, then according to the completeness of first order logic, we would be able to derive either $\phi$ or $\neg\phi$ from its axioms, which is a contradiction to the first incompleteness theorem.

Does this make sense?

$\endgroup$
  • $\begingroup$ Second point : NO. G's Incompleteness Th, applies to theories with "a certain amount of expressive capabilities". $\endgroup$ – Mauro ALLEGRANZA Sep 15 '16 at 11:15
  • $\begingroup$ If we change it to "no consistent and decidable set of first-order formulas Φ that allows representations", in the second corollary. Does that make it correct? $\endgroup$ – user56834 Sep 15 '16 at 12:30
  • $\begingroup$ Your corollaries do not follow from the theorem. Why do you think they do? $\endgroup$ – Rob Arthan Sep 15 '16 at 22:05
  • $\begingroup$ I put an argument there didn't I... I accept that it has to be incorrect, but I don't know why. $\endgroup$ – user56834 Sep 16 '16 at 6:23
  • $\begingroup$ @Programmer2134 See my edit. I addressed your argument implicitly in the last sentence, but now I've made that a bit more explicit. $\endgroup$ – Noah Schweber Sep 16 '16 at 14:29
3
$\begingroup$

Your "strengthened" conclusion to Goedel's Theorem is true, but already follows from the usual conclusion together with the completeness theorem (also proved by Goedel; despite the names, they don't contradict each other). Meanwhile, as Mauro points out, your second point is false. Some explicit examples of computable theories which are complete and consistent are:

  • Dense linear orders without endpoints.

  • Algebraically closed fields of fixed characteristic.

  • Arithmetic with only "$+$" (Presberger arithmetic).

  • Arithmetic with only "$\times$" (Skolem arithmetic).

  • The theory of the field $(\mathbb{R}; +, \times)$ (even though it contains the natural numbers, it is logically less complicated!).

  • And many others.

All of these theories share the property that they cannot represent arbitrary computable functions; in particular, they cannot define provability predicates for themselves.


EDIT: To address your most recent comment, the flaw in your argument at the end is the sentence

. . . which is a contradiction to the first incompleteness theorem.

The first incompleteness theorem only applies to certain theories - specifically, those which are (a) consistent computably axiomatizable and (b) "allow representations." In your argument, you are implicitly assuming that (b) holds for every theory, which is simply not true. All the theories I've mentioned above do not let you represent arbitrary computable functions (as I wrote above), and hence the incompleteness theorem does not apply to them.

$\endgroup$

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.