3
$\begingroup$

I read online a statement to the effect that (I'm paraphrasing):

Goedel's incompleteness theorem shows that we cannot even have a complete and consistent theory for the natural numbers.

I am under the (qualitative) impression that this statement is true within the axioms of natural numbers themselves, so that

  • if one expanded the of axioms one could prove all of the true statements that can be expressed solely in terms of natural numbers.

Note that this larger system itself is not complete and consistent.

Does Godel's incompleteness theorem have the feature that it shows that these larger systems are somehow representable with the axioms of the natural numbers?

$\endgroup$
10
$\begingroup$

For any recursively axiomatized (consistent) theory $T$ that extends first-order Peano arithmetic, there is a sentence in the language of Peano arithmetic that is neither provable nor refutable in $T$. Note that the theory $T$ can be over a language that extends the usual language of Peano arithmetic.

This states a version of the First Incompleteness Theorem. One can strengthen this, and at the same time make it more informal, by replacing the condition "$T$ is recursively axiomatized" by "there is an algorithm for enumerating the axioms of $T$."

Remark: One can weaken the result, by omitting reference to Peano Arithmetic. Let $L_0$ be a language whose non-logical symbols are $0$, $S$ (for successor), $+$, and $\times$, and let $L$ be an extension of $L_0$. Then there is no (consistent) recursively axiomatized theory $T$ over $L$ such that all sentences of $L_0$ that are (under the usual interpretation of the non-logical symbols) true in $\mathbb{N}$ are theorems of $T$.

$\endgroup$
5
  • $\begingroup$ I didn't know it was such a softball. $\endgroup$ – Dave Aug 14 '12 at 0:34
  • $\begingroup$ @Dave:The Second Incompleteness Theorem is much harder to state semi-formally without distortion. $\endgroup$ – André Nicolas Aug 14 '12 at 0:42
  • $\begingroup$ You mean "extension of $L_0$" right? $\endgroup$ – user21820 Aug 16 '16 at 16:57
  • $\begingroup$ @user21820: Many thanks for pointing out the missing subscript. $\endgroup$ – André Nicolas Aug 16 '16 at 17:23
  • $\begingroup$ You're welcome! Also, for the first incompleteness theorem even Robinson's Q suffices (as I'm sure you know), which is interesting mainly because it is finitely axiomatized, does not even prove basic theorems of PA such as commutativity of addition, because it has no induction, and is in some sense a minimal incompletable theory. A direct consequence is that the stronger theory PA$^-$ (the theory of discrete ordered semi-rings) is also incompletable, and so there are models with initial segment isomorphic to $\mathbb{N}$ that do not satisfy Con(PA). $\endgroup$ – user21820 Aug 17 '16 at 11:21

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.