Undecidability of Arithmetic

To show that in a suitable sense arithmetic is undecidable, we reduce the halting problem to arithemetic.

We will produce for each register machine P a sentence %$\phi_{\text{P}}$% in the language of arithmetic such that the sentence is true if and only if P halts. To do that we produce a sentence %$\chi_{\text{P}}$% such that %\[\mathcal{N}\models \chi_{\text{P}}[l_{0},\dots ,l_{n},L,m_{0},\dots ,m_{n}]\]% if and only if P beginning with the left-hand configuration eventually reaches the right-hand configuration.

The sentence %$\chi_{\text{P}}$% will say "there is a number %$s$% and a sequence %$C_{0},\dots ,C_{s}$% of %$n+2$%-tuples such that %$C_{i}$% is the %$i$%th configuration of the machine.

Instead of using a sequence of %$s$% %$n+2$%-tuples, we'll actually just use a single sequence of length %$s\cdot (n+2)$%. The conditions on the relations between the configuration tuples are easy, if a bit long, to write out—they are a lot like what we already did to reduce the halting problem to logical truth. The hard part is finding a way to talk about a sequence of numbers. ("There is an %$s\cdot (n+2)$%-tuple of numbers such that ...")

The standard way of coding sequences of numbers as a single number is to use exponents on prime numbers. Unfortunately, elementary arithmetic does not include exponentiation, only addition and multiplication. Of course, we can define exponentiation, but only by using finite sequences. We thus, once, have to code finite sequences without exponentiation. Then, we can use the trick to define exponentiation and never look back.

We need a more elementary coding of finite sequences. We'll use the one everyone does, the one Gödel invented, using the so-called Gödel %$\beta$% function.

With the %$\beta$% function, we can, in effect, quantify over arbitrary finite sequences of numbers and so we can write down a formula %$\chi(\overline{x},z,\overline{y})$%, where %$\overline{p}$% abbreviates %$p_{0},\dots ,p_{n}$% that says: %\[\exists s\exists p\exists t (\phi_{\beta}(t,p,0,0)\land\phi_{\beta}(t,p,1,x_{0}\land\dots\land\phi_{\beta}(t,p,n+1,x_n))\]%

-- ProfessorShaughanLavine - 30 Mar 2005