are these correct formulations of Godel's first incompleteness theorem?

Question

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?

Answer 1

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.