I'm trying to reconstruct the proof of Godel's first theorem (Rosser's strong version) from the uncomputability of the Halting function. If we just started with the language $\mathcal{L}=\{0, S, +, \cdot\}$ and we took Robinson arithmetic $Q$, we could show $Q$ is incomplete in the following way: Let $U$ be a Turing Machine that takes as input a pair $\langle M,x\rangle$ where $M$ is a TM. With some work we can show that $U$ can write down an $\mathcal{L}$-formula $\phi_{M,x}(t)$, such that if we took the standard model $\mathbb{N}$ of $Q$ and $n\in\mathbb{N}$, $\mathbb{N}\models\phi_{M,x}(n)$ if and only if $M$ halts in at most $n$ steps on input $x$. This works because each computation step, which at most flips one bit, can be treated as an arithmetic operation on the string. From there it's easy to show $Q$ must be incomplete, otherwise we could ask $U$ to enumerate all strings until it encountered a proof or disproof of $\exists t\phi_{M,x}(t)$.

More generally, this construction should hold in any consistent recursively axiomatizable theory $T$ over any language $\mathcal{L}$ (where $\mathcal{L}$ is finite since the TM only takes finite alphabets), as long as we can get the Turing Machine $U$ to write down an $\mathcal{L}$-formula $\phi_{M,x}(t)$, such that there is some model $\mathcal{M}$ of $T$ where, for $m\in\mathcal{M}$, $\mathcal{M}\models\phi_{M,x}(m)$ if and only $m$ is a natural number and $M$ halts on input $x$ in at most $m$ steps. So the theory $T$ should be such that there is enough arithmetic that there is a model $\mathcal{M}$ of $T$ which has $\mathbb{N}$ as a definable substructure (so that $T$ knows what a “natural number” is) and such that the interpretation the formula $\phi_{M,x}(t)$ in $\mathcal{M}$ is "$t\in\mathbb{N}$ and $M$ halts on $x$ in at most $t$ steps". But what does this mean in a general case where we have some language which may not contain arithmetic symbols?

For example, if you just took the language $\mathcal{L}=\{\in\}$, you could write down the sentence “There is a minimal inductive set $\mathbb{N}$ and there are subsets $+,\cdot\subseteq\mathbb{N}^3$ satisfying Robinson arithmetic", and then in some model of ZFC the sentence “There is a minimal inductive set $\mathbb{N}$ and there are subsets $+,\cdot\subseteq\mathbb{N}^3$ satisfying Robinson arithmetic and there exists an $n\in\mathbb{N}$ such that $\phi_{M,x}(n)$” would be true if and only if $M$ halted on input $x$, which is what we want. But in general, what is the formal, general way to state the condition that $T$ is a r.a $\mathcal{L}$-theory that has “enough arithmetic” that we can interpret the formula $\phi_{M,x}(t)$ in the correct way in some model of $T$?

  • $\begingroup$ When you write write down the sentence “There is, where does that sentence finish? $\endgroup$ – David Roberts Apr 1 '14 at 6:53
  • $\begingroup$ I forgot a right quotation mark. Good catch. Fixed now. $\endgroup$ – JAN Apr 1 '14 at 7:13
  • 1
    $\begingroup$ You can see Raymond Smullyan, Godel's incompleteness theorems (Oxford - 1992). $\endgroup$ – Mauro ALLEGRANZA Apr 1 '14 at 12:24

The usual answer to this question is indeed, that you can interpret addition and multiplication which satisfy the axioms of Robinson Arithmetic.

Almost all those axioms are used if you want to show the "Rosser form" of the theorem: in particular you need to be able to show: \begin{equation} x\leq \overline{n}\ \leftrightarrow x=0\vee\ldots\vee x = \overline{n}\qquad (1)\end{equation} Or the "trick" doesn't work. Obviously, only having addition isn't enough: Presburger Arithmetic is decidable.

Now it's natural to ask whether some other "structure" than the natural numbers is sufficient to get the first incompleteness theorem.

There are many such structures, but note that given an encoding of Turing machines, you can express closed numerals $\overline{n}$ and $+,\times,\leq$ in a straightforward way. Then the question of whether you can prove the equation $(1)$ becomes important: if you can apply the "Rosser trick", i.e. prove that you can enumerate a finite number of proofs, then you can prove the equation (1). This essentially means that elementary arithmetic is "necessary and sufficient" to get the strong variant of Gödel's Theorem.

The 2nd theorem is another matter altogether.

  • $\begingroup$ Thanks. I was mostly just making sure that I got the formal conditions correct, although I probably didn't need to be so long winded. What I have written down as the full statement of what I am trying to prove is: Let L be a finite language and let T be a consistent r.a L-theory such that there is a model M of T satisfying the following: \\M has a definable subset N, such that there is an element 0\in N and L-definable functions S:N->N and +,*:N^2->N such that <N,0,S,+,*> is the standard model of Q.\\ Then T is incomplete. $\endgroup$ – JAN Apr 1 '14 at 21:49

Note that S. Świerczkowski has written very detailed proofs of both theorems using hereditarily finite set theory. HF set theory and Peano arithmetic can each be straightforwardly embedded in the other. But superficially they look quite different.


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.