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.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: