# Powers of 2 (Or ‘Representing Primative Recurrsive functions in PA’)

The question was raised on how to represent the operation $2^n$ in Peano Arithmetic.

It is easily recursively defined as follows:

We want to represent it in Peano Arithmetic. That means we want to find some formula p, consisiting of just the basic logical and mathematical operations, such that:

$n = 2^m \iff p(n,m)$

The first thought might be to try this:

$p(n,m) := (m=0 \wedge n = 1) \vee (m \ne 0 \wedge \exists k( [k+k = n] \wedge p(k,m-1)$

But there is a problem; we cannot actually define a formula in terms of itself. If you use a formula in another formula, it is really just a shorthand that you could replace with the real formula if you wanted. In this case, it isn’t a shorthand, as you absolutely replace it with itself, as each time you try it introduces another p.

Gödel proved in “On Formally Undecidable Propositions of Principia Mathematica and Related Systems” that you can in fact represent any recursively defined function inside Peano Arithmetic, providing the functions it is made up of are representable in it. The rest of this article is the proof.

What is recursion, formally? Suppose we have two functions, $\psi$ and $\mu$. It is possible to define a third function, $\phi$, by combining them together as follows: Then we can define another function  as follows:

$\phi(0,\bar{x}) = \psi(\bar{x})$

$\phi(k+1,\bar{x}) = \mu(k,\phi(k,\bar{x}),\bar{x})$

We want to show that $\phi$ is representable in PA providing that both $\psi$ and $\mu$ are.

To do this we need to recast the idea of recursion into something more manageable. Recursion lets you determine new values from the old values, and so really it is about of a sequence of numbers which are all related to each other. Specifically,

$y = \phi(z,\bar{x})$

is the same as saying there is a sequence of numbers $f_0, f_1, \ldots , f_z$ with:

• $f_0 = \psi(\bar{x})$
• $f_z = y$

and

• $f_{k+1} = \mu( k , f_k , \bar{x} )$

So if the relation holds, there is such a sequence; if there is such a sequence, the relation holds. Therefore, if we could quantify across sequences, we could represent it as:

$\exists \mbox{ sequence } f : \{ (f_0 = \psi(\bar{x}))\:\wedge\: (f_z = y) \:\wedge\:(\forall k: k < z \rightarrow (f_{k+1} = \mu(k,f_k,\bar{x})))\}$

The problem is First-order Peano does not allow us to quantify across sequences, and so we need a way to get rid of them.

Enter Gödel’s trick: His idea is to generate a  sequence by taking a fixed number modulo different numbers.

For example, take the sequence 3, 5, 9, 6, 3, 0. We can generate this sequence by taking the number 19 modulo the bases 4, 7, 10, 13 and 16.

So given a sequence $f_0, f_1, \ldots, f_{k-1}$ how do we find a number, n, and an easily generatable set of k numbers, call them $g_0, \ldots , g_{k-1}$ to use as moduli. If all the g numbers are coprime then we can easily find n: The Chinese Remainder Theorem!

So the problem is we want an easily generatable sequence. How much easier can we get than a linear progression? So if we decide that the moduli are in the form $g_i = a+bi$ then the work is cut down. We wish to apply the Chinese Remainder Theorem to it, so we need each of the k terms to be coprime.

So where have we previously seen a trick which lets you get a number which is coprime to a given set of other numbers? Euclid’s classic proof of there being an infinite number of prime numbers!

So the idea there is that $1+\Omega$ is coprime to every number lower or equal to $\Omega$. This is because it is one greater than a factor of 2, one greater than a factor of 3, and so forth.

$1+ t\Omega$ and $1+ s\Omega!$. If they are not coprime then there is some prime p which divides both. Hence it must divide the difference also. The difference is $(t-s)\Omega!$. But each of the numbers was coprime to all numbers lower or equal to $\Omega$, so definitely the prime is not in $\Omega!$ and so must be in the other term. If we have $|s-t| \le \Omega$, then s-t is also an integer smaller or equal to $\Omega$, and so it must be coprime to that as well. Hence we have that the numbers:

$1+ \Omega! \: , \: 1+ 2\Omega! \: , \: 1+ 3\Omega! \: , \: 1+ 4\Omega! \: , \:\ldots\:, \: 1 + (k-1)\Omega!$

are pairwise coprime providing $\Omega \ge k$.

Thus we can have a set of simultaneous linear congruence equations, in the unknown n, as below, and by the Chinese Remainder Theorem there is a solution:

At this point you need to verify that the CRT works in Peano. If you recall, the proof is very simple – you just take a number which is the sum of k terms, where each term has all the moduli except for one multiples together, and then multiples by a constant. It definitely works in PA.

So now we have a number, n, such that modulo certain numbers in an arithmetic progression, we have the original numbers from the sequence. This isn’t quite what we want, as we want the actual number, not something congruent to it.

The solution is as follows: If $\Omega$ is also greater than each $f_i$, then we would definitely have $f_i$ being less than $1+i\Omega!$.  Now not only is n congruent to $f_i$, modulo $1+i\Omega!$, for each i, but also $f_i$ is the least positive number than is congruent to n.

If we let $[n]_p$ denote the least positive number that is congruent to n mod p, then this can be represented as the following relation in PA:

$[n]_p = q \iff [\exists m : n = mp + q] \wedge [0 \le q < p]$

So in summary, given a sequence $f_0, f_1, \ldots , f_z$, there is are numbers n and $\Omega$ such that:

$0 \le i < k \implies [n]_{1+i\Omega!} = f_i$

So now there is no need to quantify across sequences. Instead of saying:

$\exists \mbox{ sequence } f : \{ (f_0 = \psi(\bar{x}))\:\wedge\: (f_z = y) \:\wedge\:(\forall k: k < z \rightarrow (f_{k+1} = \mu(k,f_k,\bar{x})))\}$

We can now say:

$\exists n , N : \{ ([n]_{1+N} = \psi(\bar{x})) \wedge ([n]_{1+Nz} = y) \wedge [\forall k < z : ([n]_{1+N(k+1)} = \mu(k,[n]_{1+kN},\bar{x}))]\}$

And so we have represented recursion in Peano!

Providing that the two functions used to represents it are representable in PA, then so can the result of them combined using recursion.

It is also obvious that substitution of variables for functions forms something that can be represented in PA if the original functions can be,  and that the successor function, identity function and zero function are all representable in PA too. It hence follows that every primitively recursive function is representable in Peano Arithmetic.

So how do we represent the power of two problem? As follows:

$n = 2^m \iff \exists a, A : \{[n]_{1+A} = 1 \wedge [n]_{1+{mA}} = n\ \wedge [\forall k < m : [n]_{1+A(k+1)} = 2[n]_{1+kA}]\}$

Of course, the definition of the $[n]_p$ could be substituted in there in order to show the formula in all its entirety.