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?

Improve this question
$\endgroup$
14
  • $\begingroup$ Closely related" cs.stackexchange.com/q/419/98 Duplicate? $\endgroup$
    – Raphael
    Commented Mar 30, 2018 at 10:57
  • $\begingroup$ @Raphael, I cannot find "undecidability of arithmetic" there. I already checked that post. $\endgroup$
    – user56834
    Commented Mar 30, 2018 at 11:26
  • $\begingroup$ What do you mean by "undecidability of arithmetic"? $\endgroup$
    – Yuval Filmus
    Commented Mar 30, 2018 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
    Commented Mar 31, 2018 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
    Commented Mar 31, 2018 at 6:57

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$
1
  • 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
    Commented Jul 7, 2018 at 19:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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