# How is exponentiation defined in Peano arithmetic?

How would exponentiation be defined in Peano arithmetic? Unless $n$ is fixed natural number, $x^n$ seems to be hard to define.

Edit 2: So, what would be the way to define $x^n+y^n = z^n$ using $\Sigma_1^0$ formula?

Edit: OK, I say Peano arithmetic has addition and multiplication stuffs. This allows additions to be expressed without quantifiers but as for exponentiation Peano arithmetic is silent. That's why I asked this question. Just for clarification.

-
@JyrkiLahtonen, Peano arithmetic deals in natural numbers. – vonbrand Feb 24 '13 at 16:35
Yeah I know that, but then what's the problem? Define $x^n$ by induction on $n$. Oh, you want to build a formula using Peano axioms alone. Sorry, I totally misunderstood. – Jyrki Lahtonen Feb 24 '13 at 17:05

The bare bones answer is something like what Hagen has said. The idea is this: Exponentiation is understood to be a function defined recursively: $y=2^x$ iff there is a sequence $t_0,t_1,\dots,t_x$ such that

• $t_0=1$,
• $t_x=y$, and
• For all $n<x$, $t_{n+1}=2\times t_n$.

In this respect, exponentiation is hardly unique: $y=x!$ is defined similarly, for example. Now you'd say that there is a sequence $z_0,z_1,\dots,z_x$, such that

• $z_0=1$,
• $z_x=y$, and
• For all $n<x$, $z_{n+1}=(n+1)\times z_n$.

(That $t_0=z_0=1$ is coincidence. In one case it is because $2^0=1$; in the other, because $0!=1$.)

So, to define a formula saying that $y=2^x$, you'd like to say that there is a sequence $t_0,\dots,t_x$ as above.

The problem, of course, is that in Peano Arithmetic one talks about numbers rather than sequences. Gödel solved this problem when working on his proof of the incompleteness theorem: He explained how to code finite sequences by numbers, by using the Chinese remainder theorem. Recall that this result states that, given any numbers $n_1,\dots,n_k$, pairwise relatively prime, and any numbers $m_1,\dots,m_k$, there is a number $x$ that simultaneously satisfies all congruences $$x\equiv m_i\pmod {n_i}$$ for $1\le i\le k$.

In particular, given $m_1,\dots,m_k$, let $n=t!$ where $t=\max(m_1,\dots,m_k,k)$. Letting $n_1=n+1$, $n_2=2n+1,\dots$, $n_k=kn+1$, we see that the $n_i$ are relatively prime, and we can find an $x$ that satisfies $x\equiv m_i\pmod{n_i}$ for all $i$. We can then say that the pair $\langle x,n\rangle$ codes the sequence $(m_1,\dots,m_k)$. In fact, given $x,n$, it is rather easy to "decode" the $m_i$: Just note that $m_i$ is the remainder of dividing $x$ by $in+1$.

Accordingly, we can define $y=2^x$ by saying that there is a pair $\langle a,b\rangle$ that, in the sense just described, codes a sequence $(t_0,t_1,\dots,t_x)$ such that $t_0=1$, $t_x=y$, and $t_{n+1}=2t_n$ for all $n<x$. (Again, "in the sense just described" ends up meaning simply that "the remainder of dividing $a$ by $ib+1$ is $t_i$ for all $i\le x$". Note that we are not requiring $b$ to be the particular number we exhibited above using factorials.)

Of course, one needs to prove that any two pairs coding such a sequence agree on the value of $t_x$, but this is easy to establish. And we can code a pair by a number using, for example, Cantor's enumeration of $\mathbb N\times\mathbb N$, so that $\langle a,b\rangle$ is coded as the number $$c=\frac{(a+b)(a+b+1)}2+b.$$ This is a bijection, and has the additional advantages that it is definable and satisfies $a,b\le c$ (so it is given by a bounded formula).

An issue that appears now is that we need to formalize the discussion of the Chinese remainder theorem and the subsequent coding within Peano arithmetic. This presents new difficulties, as again, we cannot (in the language of arithmetic) talk about sequences, and cannot talk about factorials, until we do all the above, so it is not clear how to prove or even how to formulate these results.

This problem can be solved by noting that we can use induction within Peano arithmetic. One then proceeds to show, essentially, that given any finite sequence, there is a pair that codes it, and that if a pair codes a sequence $\vec s$, and a number $t$ is given, then there is a pair that codes the sequence $\vec s{}^\frown(t)$. That is, one can write down a formula $\phi(x,y,z)$, "$y$ codes a sequence, the $z$-th member of which is $x$", such that PA proves:

• For all $z$ and $y$ there is a unique $x$ such that $\phi(x,y,z)$.
• For all $x$ there is a $y$ such that $\phi(x,y,0)$.
• For all $x,y,z$ there is a $w$ such that the first $z$ terms of the sequences coded by $y$ and $w$ coincide, and the next term coded by $w$ is $x$.

In fact, we can let $\phi$ be a bounded formula: Take $\phi(x,y,z)$ to be

There are $a,b\le y$ such that $y=\langle a,b\rangle$ (Cantor's pairing) and $x<zb+1$ and there is a $d\le a$ such that $a=d(zb+1)+x$.

Once we have in PA the existence of coded sequences like this, implementing recursive definitions such as exponential functions is straightforward.

There are two excellent references for these coding issues and the subtleties surrounding them:

1. Richard Kaye. Models of Peano arithmetic. Oxford Logic Guides, 15. Oxford Science Publications. The Clarendon Press, Oxford University Press, New York, 1991. MR1098499 (92k:03034). (See chapter 5.)
2. Petr Hájek, and Pavel Pudlák. Metamathematics of first-order arithmetic. Perspectives in Mathematical Logic. Springer-Verlag, Berlin, 1993. MR1219738 (94d:03001). (See chapter 1.)
-
Curiously, I just gave a talk in the set theory seminar at Boise State on this question: math.stackexchange.com/questions/282865/…, so I had just (re)worked through these details. – Andrés Caicedo Feb 24 '13 at 17:01
As for $\phi (x,y,z)$, bounded formula, it's $\Sigma^0_0$ formula, I guess, right? (But I heard that $\Sigma^0_0$ formula can also refer to quantifier-free formula, so which definition is usually used in this case?) – UQT Feb 28 '13 at 5:33
(There was a typo on my previous comment, it is fixed in this version.) Bounded is the usual definition. Sometimes, in the context of Hilbert's $10$-th problem, one talks of $\Sigma_0=\Pi_0=\Delta_0$ being quantifier free, and $\Sigma_1$ being existential quantification over $\Sigma_0$, so the Davis-Matiyasevich-Putnam-Robinson result can be stated succinctly as $\Sigma^0_1=\Sigma_1$. – Andrés Caicedo Mar 1 '13 at 6:00

Using the following abbreviations

\begin{align}a\le b&\equiv\exists n\colon a+n=b\\ a< b&\equiv Sa\le b\\ \operatorname{mod}(a,b,c)&\equiv \exists n\colon a=b\cdot n+c\land c<b\\ \operatorname{seq}(a,b,k,x)&\equiv \operatorname{mod}(a,S(b\cdot Sk),x)\\ \operatorname{pow}(a,b,c)&\equiv\exists x\exists y\colon\operatorname{seq}(x,y,0,S0)\land\operatorname{seq}(x,y,b,c)\land \\&\quad\forall k\forall z\colon((k<c\land \operatorname{seq}(x,y,k,z))\to \operatorname{seq}(x,y,Sk,a\cdot z))\end{align} we have $\operatorname{pow}(a,b,c)$ if and only if $c=a^b$. Intriguingly, you need some elementary number theory (such as the Chinese remainder theorem) to meta-appreciate this.

-

Peano's axioms don't include addition or multiplication. All you get is zero, the "next" operation $s(n)$, and induction. When deriving things from Peano's axioms, all of the arithmetic operations are usually defined by recursion:

• $0+a = a$
• $s(n) + a = s(n+a)$
• $0\cdot a = 0$
• $s(n) \cdot a = a + (n \cdot a)$
• $a^0 = 1$
• $a^{s(n)} = a \cdot a^n$

(aside: The second-to-last formula implies $0^0=1$. This convention is a good choice for discrete exponentiation operators, but a bad choice for continuous ones. Since we are defining a discrete one, I adopt it)

-
I don't think this is an answer to the question. The language of first-order logic includes $+$ and $\times$, but no symbol for exponentiation. Then the Peano axioms include their inductive properties, and again it obviously doesn't talk at all about exponentiation. In Peano arithmetic, exponentiation, unlike $+$ and $\times$ has to be defined properly by a formula $\phi(x,y,z)$ then you have to prove that the formula has the inductive and functional properties you are thinking about. – mercio Feb 24 '13 at 14:43
@merco: What in the question suggests we're talking about first-order PA? – Chris Eagle Feb 24 '13 at 17:05
The term "Peano arithmetic" itself suggests first-order PA; "Peano axioms" is more neutral. In particular Peano arithmetic is not the set of 5 axioms proposed by Peano. The abbreviation PA, although not used in the question, is universally used for the first-order theory. – Carl Mummert Feb 24 '13 at 18:49

$a^{b}=c$: $\forall x>0\forall y \exists !z((y=0\to z=1)\wedge\forall m\forall n((y=m\to z=n)\to (y=m+1\to z=n*x))\wedge((x=a\wedge y=b)\to z=c))$

Notice that this formula is not unique, you can find some other ways to define it. But it is not neccessary to do it because it's known that every recursive(computable) function is definable, sometimes the formula to define a function may be very long and tedious.

-
This is definitely not correct because of the part $\forall m\forall n ((y=m\to z=n)\to(y=m+1\to z=n\cdot x))$ If $y\ne m+1$, then $y=m+1\to z=n\cdot x$ is true and if $y=m+1$ it reduces to $z=n\cdot x$. But $\forall n(z=n\cdot x)$ is false (unless $x=z=0$). – Hagen von Eitzen Feb 24 '13 at 14:16
Sorry but I can not understand 'If y≠m+1, then y=m+1→z=n⋅x is true and if y=m+1 it reduces to z=n⋅x'? – Chao Chen Feb 24 '13 at 14:36
Please explain why $1^1 = 1$. I pick $a=1,b=1,c=1,x=1,y=1,m=0,n=0$. Please show me an integer $z$ such that $(y=0 \implies z=1) \wedge ((y=m \implies z=n) \implies (y=m+1 \implies z=n*x)) \wedge ((x=a \wedge y=b) \implies z=c)$ – mercio Feb 24 '13 at 15:45

Another approach: Define exponentiation as a binary function on $N$ such that:

If $0\notin N$ then

1. $x^1=x$

2. $x^{y+1}=x^y\cdot x$

If $0\in N$ then

1. $x^0=1$ if $x\neq 0$

2. $0^1=0$

3. $x^{y+1}=x^y\cdot x$

Note that in the latter, we leave only $0^0$ undefined. For a formal development, see "Oh, the ambiguity!" at my math blog.

-
Adding function symbols is not allowed – that is tantamount to changing the logical language. – Zhen Lin Nov 1 '13 at 19:27