---
title: Representing Exponentiation and the β-Function
module: Recursive Functions and Representability
moduleNumber: 8
lessonNumber: 2
order: 802
summary: >
  Coding finite sequences by prime-power exponents already assumes
  exponentiation, so representing exponentiation from addition and multiplication
  alone needs a different encoder. Gödel's β-function, built from a pairing
  function and the Chinese remainder theorem, reads back arbitrary finite
  sequences using only plus and times. This represents exponentiation in the
  addition-multiplication arithmetic and closes the last gap in the
  representability of every recursive syntactic operation.
topics: [Recursive Functions and Representability]
sources:
  - book: Enderton
    ref: "Ch. 3 — Undecidability; §3.8 Representing Exponentiation (pairing function, the β-function, Chinese remainder theorem)"
draft: false
---

The representability argument that drives incompleteness needs the syntactic
operations to be arithmetic, and those operations are defined by recursion over
finite sequences of symbols. Coding a finite sequence into a single number was
done with the prime-power encoding $\langle a_0,\dots,a_m\rangle = \prod_i
p_i^{a_i+1}$, which uses exponentiation. That is fine inside the full language
$A_E$, whose symbol $E$ denotes exponentiation. It is circular the moment one
tries to run the same development in the smaller language with addition and
multiplication only, because there exponentiation is not a primitive and must be
_built_ before it can encode anything.

Let $\fN_M = (\mathbb{N};\,0, S, <, +,
\cdot)$ be the reduct of the standard structure that drops exponentiation, and
let $A_M$ be $A_E$ with the two exponentiation axioms removed. The goal is a
formula $\varepsilon$ in the language of $\fN_M$ that behaves like $x^y
= z$ without the symbol $E$:

$$
A_M \vdash \forall z\,\big[\,\varepsilon(\mathsf{S}^a 0,\, \mathsf{S}^b 0,\, z) \leftrightarrow z = \mathsf{S}^{(a^b)} 0\,\big].
$$

Achieving this makes every representability result hold with $A_M$ and
$\fN_M$ in place of $A_E$ and $\fN$.

## The obstacle in the recursion

Exponentiation satisfies the recursion equations
$$
a^0 = 1, \qquad a^{b+1} = a^b \cdot a.
$$
Primitive recursion is available among the representable functions, so one might
define the sequence of partial powers and read off the last entry:
$$
E^\ast(a,b) = \text{the least } s \text{ such that } (s)_0 = 1 \text{ and } (s)_{i+1} = (s)_i \cdot a \text{ for all } i < b,
$$
after which $a^b = (E^\ast(a,b))_b$. The definition is correct but useless for
the task: the decoding function $(s)_i$ that extracts the $i$-th entry was itself
built from the prime-power encoding, so it is representable in $\Cn A_E$
but not known to be representable in $\Cn A_M$. This particular encoder
does not carry over once $E$ is removed.

The construction does not need _that_ decoder, only _some_ function $\delta$ that
acts like one: a way to read the $i$-th entry of an arbitrary finite sequence,
provided $\delta$ is representable using addition and multiplication.

> **Lemma (Sufficient decoder).** There is a function $\delta$ representable in
> $\Cn A_M$ such that for every $n$ and every $a_0,\dots,a_n$ there is an
> $s$ with $\delta(s,i)=a_i$ for all $i \le n$.

Granting the lemma, replace $(s)_i$ by $\delta(s,i)$:
$$
E^{\ast\ast}(a,b) = \text{the least } s \text{ such that } \delta(s,0)=1 \text{ and } \delta(s,i+1)=\delta(s,i)\cdot a \text{ for all } i < b.
$$
The lemma guarantees such an $s$ exists, $E^{\ast\ast}$ is representable in
$\Cn A_M$ by the minimization operator, and
$$
a^b = \delta\big(E^{\ast\ast}(a,b),\, b\big),
$$
so exponentiation is representable once $\delta$ is. Everything reduces to
building $\delta$ from plus and times.

## A pairing function

The first ingredient encodes and decodes _pairs_ of numbers, using only the
polynomial operations. The map
$$
J(a,b) = \tfrac{1}{2}\big[(a+b)^2 + 3a + b\big]
$$
is a bijection of $\mathbb{N} \times \mathbb{N}$ onto $\mathbb{N}$. It counts
lattice points along successive anti-diagonals: the line $x+y=n$ carries $n+1$
points, so $J$ enumerates the plane diagonal by diagonal, assigning $0,1,2,\dots$
in order.

$$
% caption: The pairing function J numbers the lattice points of the first
% quadrant along successive anti-diagonals x plus y equals n, giving a bijection
% onto the naturals built from addition and multiplication alone.
\begin{tikzpicture}[>=stealth, font=\footnotesize, scale=1.15]
  \definecolor{acc}{HTML}{4A6FA5}
  \draw[->, black] (-0.3,0) -- (4.4,0) node[right, font=\scriptsize] {a};
  \draw[->, black] (0,-0.3) -- (0,4.4) node[above, font=\scriptsize] {b};
  % anti-diagonal guide lines x+y=n for n=1..3
  \foreach \n in {1,2,3} \draw[acc!45, dashed] (0,\n) -- (\n,0);
  % lattice dots with J values offset above-right so no line crosses the label
  \foreach \x/\y/\val in {0/0/0, 1/0/2, 0/1/1, 2/0/5, 1/1/4, 0/2/3, 3/0/9, 2/1/8, 1/2/7, 0/3/6}{
    \fill[black] (\x,\y) circle (1.3pt);
    \node[acc, font=\scriptsize, anchor=south west, inner sep=1.5pt] at (\x,\y) {\val};
  }
  \node[black, font=\scriptsize, anchor=west, align=left] at (2.5,3.3) {dashed lines:\\a plus b constant};
\end{tikzpicture}
$$

The two projection functions $K$ and $L$ invert it, recovering the coordinates:
$K(J(a,b))=a$ and $L(J(a,b))=b$. All three are representable in
$\Cn A_M$, because each has a defining equation in the polynomial
language. Writing $H(a)$ for the least $b$ with $a \le 2b$, which equals
$\tfrac{1}{2}a$ on even inputs, one has
$$
J(a,b) = H\big((a+b)(a+b+1)\big) + a,
$$
$$
K(p) = \text{the least } a \text{ with } J(a,b)=p \text{ for some } b \le p, \qquad
L(p) = \text{the least } b \text{ with } J(a,b)=p \text{ for some } a \le p.
$$
The auxiliary function $H$ turns the halving in $J$ into a representable form;
the projections are then least-witness searches, both covered by the
minimization operator. This pairing function replaces the prime-power
encoding's unbounded exponents with a polynomial that grows only quadratically.

> **Worked example.** The pairing function $J$ numbers lattice points along
> anti-diagonals, and $K,L$ recover the coordinates. Two of the values marked in
> the figure:
>
> $$
> J(2,1)=\tfrac{1}{2}\big[(2+1)^2+3\cdot 2+1\big]=\tfrac{1}{2}(9+6+1)=8,
> $$
>
> $$
> J(0,2)=\tfrac{1}{2}\big[(0+2)^2+3\cdot 0+2\big]=\tfrac{1}{2}(4+0+2)=3.
> $$
>
> The point $\langle 1,2\rangle$ sits on the diagonal $x+y=3$, which carries the
> values $6,7,8,9$ in order of increasing first coordinate; $6$ falls on
> $\langle 0,3\rangle$ and $7$ on $\langle 1,2\rangle$, so $J(1,2)=7$. Inverting,
> $K(7)=1$ and $L(7)=2$ return the coordinates of that point.

## The Gödel β-function

A single pair $(c,d)$ can now stand in for an entire finite sequence, decoded one
entry at a time by remainders. Define
$$
\beta(c,d,i) = \text{the remainder of } c \text{ on division by } 1+(i+1)d
= \text{the least } r \text{ such that } c = q\cdot\big(1+(i+1)d\big) + r \text{ for some } q \le c.
$$
This is representable in $\Cn A_M$: division-with-remainder is a bounded
search over $q$ and $r$, and the modulus $1+(i+1)d$ is a polynomial. Set
$$
\delta(s,i) = \beta\big(K(s),\, L(s),\, i\big),
$$
so a single number $s$ codes the pair $(c,d)=(K(s),L(s))$, and $\delta$ reads
entries out of it. What must be shown is that $\beta$ can hit any prescribed list
of values.

$$
% caption: One pair (c, d) encodes a whole finite sequence; the beta-function
% reads back entry i as the remainder of c on division by the i-th modulus, and
% delta packs the pair into a single number through J.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=20mm, minimum height=9mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[box, draw=acc, text=acc] (c) at (0,0) {pair (c, d)};
  \node[box] (m0) at (4,2)  {modulus m0};
  \node[box] (m1) at (4,0)  {modulus m1};
  \node[box] (m2) at (4,-2) {modulus m2};
  \node[box] (a0) at (8,2)  {entry a0};
  \node[box] (a1) at (8,0)  {entry a1};
  \node[box] (a2) at (8,-2) {entry a2};
  \foreach \m in {m0,m1,m2} \draw[->, acc] (c) -- (\m);
  \draw[->, acc] (m0) -- node[above, font=\scriptsize] {remainder} (a0);
  \draw[->, acc] (m1) -- node[above, font=\scriptsize] {remainder} (a1);
  \draw[->, acc] (m2) -- node[above, font=\scriptsize] {remainder} (a2);
\end{tikzpicture}
$$

> **Claim.** For any $n$ and any $a_0,\dots,a_n$, there are numbers $c$ and $d$
> such that $\beta(c,d,i)=a_i$ for all $i \le n$.

Given the claim, $\delta(J(c,d),i)=\beta(c,d,i)=a_i$ for $i \le n$, which is
exactly the sufficient-decoder lemma. The claim is a statement of number theory,
and its proof rests on two facts about remainders.

## The Chinese remainder theorem

Simultaneous congruences with coprime moduli always have a common solution, so a
single $c$ encodes all the entries at once. Call
$d_0,\dots,d_n$ _relatively prime in pairs_ when no prime divides two of them.

> **Theorem (Chinese remainder).** Let $d_0,\dots,d_n$ be relatively prime in
> pairs and let $a_0,\dots,a_n$ satisfy $a_i < d_i$. Then there is a $c$ with
> $a_i = $ the remainder of $c$ on division by $d_i$, for all $i \le n$.

The proof is a counting argument. Let $p = d_0 d_1 \cdots d_n$ and let $F(c)$ be
the tuple of remainders of $c$ modulo $d_0,\dots,d_n$; there are $p$ possible
tuples. On $\{0,1,\dots,p-1\}$ the map $F$ is one-to-one: if $F(c_1)=F(c_2)$ then
each $d_i$ divides $\lvert c_1-c_2\rvert$, so their product $p$ does too, forcing
$c_1=c_2$ in that range. A one-to-one map from a $p$-element set into a
$p$-element set is onto, so $F$ takes every tuple, including $\langle
a_0,\dots,a_n\rangle$, at some $c$.

To apply the theorem the moduli of the β-function must be made pairwise coprime,
and one choice always works.

> **Lemma (Coprime moduli).** For any $s \ge 0$, the $s+1$ numbers
> $$
> 1 + 1\cdot s!, \quad 1 + 2\cdot s!, \quad \dots, \quad 1 + (s+1)\cdot s!
> $$
> are relatively prime in pairs.

Any prime $q$ dividing one of these numbers cannot divide $s!$, so $q > s$. If
$q$ divided both $1+j\cdot s!$ and $1+k\cdot s!$, it would divide their difference
$\lvert j-k\rvert \cdot s!$; since it misses $s!$, it divides $\lvert
j-k\rvert$. But $\lvert j-k\rvert \le s < q$, so $j=k$.

The claim now follows. Given $a_0,\dots,a_n$, put $s = \max\{n, a_0,\dots,a_n\}$
and $d = s!$. The moduli $1+(i+1)d$ for $i \le n$ are pairwise coprime by the
lemma, and each $a_i \le s < 1+(i+1)d$, so the Chinese remainder theorem produces
a $c$ whose remainder on division by $1+(i+1)d$ is $a_i$. That is
$\beta(c,d,i)=a_i$ for all $i \le n$.

> **Worked example.** Decode the sequence $\langle 2,0,1\rangle$ from a single
> pair. Here $n=2$ and $s=\max\{2,\,2,0,1\}=2$, so $d=s!=2$. The three moduli
> $1+(i+1)d$ are
>
> $$
> 1+1\cdot 2=3,\qquad 1+2\cdot 2=5,\qquad 1+3\cdot 2=7,
> $$
>
> pairwise coprime by the lemma. The Chinese remainder theorem asks for a $c$ with
>
> $$
> c \equiv 2 \pmod 3,\qquad c \equiv 0 \pmod 5,\qquad c \equiv 1 \pmod 7,
> $$
>
> and $c=50$ works, since $50=16\cdot 3+2$, $50=10\cdot 5+0$, and $50=7\cdot 7+1$.
> Reading the entries back,
>
> $$
> \beta(50,2,0)=2,\qquad \beta(50,2,1)=0,\qquad \beta(50,2,2)=1,
> $$
>
> so the pair $(c,d)=(50,2)$ codes $\langle 2,0,1\rangle$, and $\delta(J(50,2),i)$
> recovers each entry.

$$
% caption: The concrete decode of the sequence 2, 0, 1 from d equals 2 and c
% equals 50: index i selects the modulus 1 plus (i plus 1) times d, and the
% entry is the remainder of c on that modulus.
\begin{tikzpicture}[font=\footnotesize,
  cell/.style={draw, minimum width=13mm, minimum height=8mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[anchor=east, font=\scriptsize] at (-0.95,1.6) {index i};
  \node[anchor=east, font=\scriptsize] at (-0.95,0.4) {modulus};
  \node[anchor=east, font=\scriptsize] at (-0.95,-0.8) {entry};
  \foreach \col/\ix/\md/\en in {0/0/3/2, 1/1/5/0, 2/2/7/1}{
    \node[cell] (ix\col) at (\col*1.7,1.6) {\ix};
    \node[cell] (md\col) at (\col*1.7,0.4) {\md};
    \node[cell, draw=acc, text=acc] (en\col) at (\col*1.7,-0.8) {\en};
    \draw[->, black] (md\col) -- (en\col);
  }
\end{tikzpicture}
$$

$$
% caption: Choosing d as s factorial makes the moduli pairwise coprime, so the
% Chinese remainder theorem returns a single c whose remainders spell out the
% prescribed entries; the pair (c, d) is the code of the whole sequence.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=26mm, minimum height=9mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[box] (seq) at (0,0) {entries a0 ... an};
  \node[box] (mod) at (4.6,0) {pairwise coprime\\moduli};
  \node[box, draw=acc, text=acc, thick] (crt) at (9.2,0) {one code (c, d)};
  \draw[->, acc] (seq) -- node[above, font=\scriptsize] {choose d} (mod);
  \draw[->, acc] (mod) -- node[above, font=\scriptsize] {remainder theorem} (crt);
  \draw[->, black] (crt) to[bend left=28] node[below, font=\scriptsize] {read back with beta} (seq);
\end{tikzpicture}
$$

## Exponentiation and the primitive recursive functions

With $\delta$ representable, the earlier reduction goes through.

> **Theorem (Exponentiation is representable).** Exponentiation is representable
> in $\Cn A_M$: there is a formula in the language of addition and
> multiplication that defines the graph of $x^y$ and is proved correct on every
> numeral instance by $A_M$.

> **Worked example.** Assemble $2^3$ through the sufficient decoder. The recursion
> $\delta(s,0)=1$ and $\delta(s,i+1)=\delta(s,i)\cdot 2$ builds the partial powers
>
> $$
> \delta(s,0)=1,\quad \delta(s,1)=1\cdot 2=2,\quad \delta(s,2)=2\cdot 2=4,\quad \delta(s,3)=4\cdot 2=8,
> $$
>
> so the least $s$ meeting these constraints codes $\langle 1,2,4,8\rangle$, and
> $E^{\ast\ast}(2,3)$ is that $s$. Reading the last entry gives
> $2^3=\delta\big(E^{\ast\ast}(2,3),\,3\big)=8$. The β-function supplies the code:
> with entries bounded by $8$, taking $d=8!$ makes the moduli $1+(i+1)d$ pairwise
> coprime, and the Chinese remainder theorem returns a $c$ whose remainders are
> $1,2,4,8$.

The consequence propagates through the whole catalog. Up to the prime-listing
function, every relation and function shown representable in $\Cn A_E$
was already representable in $\Cn A_M$ by the same proof, since those
proofs never used $E$. The prime-listing function was the first to need
exponentiation, and it now has one. So the remaining catalog items, the syntactic
coding functions, and the numeralwise-determined bounded formulas all carry over.

- **Every recursive relation is representable in $\Cn A_M$**, and every
  recursive function is functionally representable there.
- **The undecidability results transfer.** Any theory $T$ in the language of
  $\fN_M$ with $T \cup A_M$ consistent fails to be recursive — the
  strong undecidability of $\Cn A_M$. Adding _only_ multiplication to
  addition already forces undecidability; exponentiation was never required.
- **Truth in $\fN_M$ is not arithmetical.** Exponentiation is definable
  in $\fN_M$, being representable in a subtheory of its own theory, so
  every arithmetical relation is definable in $\fN_M$; by Tarski's
  theorem $\Th \fN_M$ is not definable in $\fN_M$ and
  hence not arithmetical.

In the language of
[interpretations between theories](/logic/models-and-theories/interpretations-between-theories),
there is a faithful interpretation of $\Th \fN$ into
$\Th \fN_M$: the identity on every symbol except $E$, and on $E$
the formula defining exponentiation in $\fN_M$. The two structures have
the same complexity even though one lacks a symbol for the other's exponentiation.

$$
% caption: The dependency chain closed by this section: the pairing function and
% the remainder theorem give the beta-function, which codes finite sequences with
% plus and times, which represents exponentiation, which completes the catalog.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  box/.style={draw, minimum width=24mm, minimum height=11mm, align=center, font=\scriptsize}]
  \definecolor{acc}{HTML}{4A6FA5}
  \node[box] (pair) at (0,0) {pairing plus\\remainder theorem};
  \node[box, draw=acc, text=acc] (beta) at (3.6,0) {beta-function};
  \node[box] (seq) at (7.2,0) {sequences coded\\by plus and times};
  \node[box] (exp) at (10.8,0) {exponentiation};
  \node[box, draw=acc, text=acc, thick] (pr) at (7.2,-2.4) {every recursive\\function represented};
  \draw[->, acc] (pair) -- (beta);
  \draw[->, acc] (beta) -- (seq);
  \draw[->, acc] (seq) -- (exp);
  \draw[->, acc] (exp) to[bend left=12] (pr);
\end{tikzpicture}
$$

Every primitive recursive function — and by the normal form theorem, every
recursive function that arises as a syntactic operation — is now representable in
a finitely axiomatized arithmetic whose only arithmetic symbols are $+$ and
$\cdot$. A theory that can add and multiply can talk about the codes of its own
formulas and deductions, and the
[fixed-point lemma](/logic/incompleteness/incompleteness-and-undecidability)
turns that self-reference into a sentence asserting its own unprovability.