6
$\begingroup$

There is a theorem that states that arithmetic is undecidable: i.e. $Th(\mathcal N)$, the set of all sentences in the standard arithmetic structure $\mathcal N=(\mathbb N,+,\cdot , 0,1)$ where the symbols are interpreted in the standard way, is undecidable.

Godel's first incompleteness theorem states that there does not exist a set of axioms from which we can prove all true arithmetic statements: There does not exist a set of first order formula's $\Phi$ that is consistent and decidable, such that for any first order $(+,\cdot,0,1)$ sentence $\phi$, we have $\Phi\vdash\phi$ or $\Phi \vdash \neg \phi$. By the completeness theorem we could have instead written "$\Phi\models\phi$ or $\Phi \models\neg \phi$"

But since we can construct a first order proof system that is complete, in the sense that all valid sentences can be proven, doesn't this boil down to the same thing?

Isn't godel's incompleteness theorem simply an implication of the undecidability of arithmetic?

$\endgroup$
  • $\begingroup$ Closely related" cs.stackexchange.com/q/419/98 Duplicate? $\endgroup$ – Raphael Mar 30 '18 at 10:57
  • $\begingroup$ @Raphael, I cannot find "undecidability of arithmetic" there. I already checked that post. $\endgroup$ – user56834 Mar 30 '18 at 11:26
  • $\begingroup$ What do you mean by "undecidability of arithmetic"? $\endgroup$ – Yuval Filmus Mar 30 '18 at 21:21
  • $\begingroup$ @YuvalFilmus. Sorry. I mean that the set of first order sentences that are true in arithmetic (the natural numbers with the successor function, 0, 1, addition and multiplication) are undecidable $\endgroup$ – user56834 Mar 31 '18 at 6:06
  • $\begingroup$ What do you mean by "true"? The completeness theorem talks about statements valid in all models, but another option is to consider statements true in a specific model ("true arithmetic") which consists of the "honest" natural numbers. $\endgroup$ – Yuval Filmus Mar 31 '18 at 6:57
1
$\begingroup$

Yes, if we know that $Th(\mathcal{N})$ is undecidable then we know that it is not computably axiomatizable, and in particular we know that no computably axiomatizable theory consisting only of true sentences of arithmetic is complete.

Here I'm adopting a Platonist view with regards to $\mathcal{N}$: I assume that "the" set of natural numbers exists, and "true" means "true in that structure.

However, there are a couple points here:

  • How do we know that $Th(\mathcal{N})$ is undecidable?

  • What about strengthenings of Godel's theorem, like "No consistent computably axiomatizable theory of arithmetic extending PA (or even Q) is complete"? (This is an extension due to Rosser of the theorem as originally proved by Godel, but is basically just one clever idea on top of the usual proof.)

Ultimately, (1) really already uses the key idea/argument of Godel's theorem, while (2) points out the limitations of measuring the complexity of a single structure.

So this shouldn't be construed as trivializing Godel's theorem in any way; in particular, I object to the word "simply" in the last line.

$\endgroup$
  • 2
    $\begingroup$ A Platonist view seems to be unecessary here. All you need is a reasonable theory of truth, but that may be based in any number of philosophical views. No? For example, if I take on the idea of a multiverse of mathematics, I will simply observe that all of tehm satisfy the theorems in question and so it doesn't matter which one I am in. $\endgroup$ – Andrej Bauer Jul 7 '18 at 19:00

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.