Representing Exponentiation and the β-Function

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 $⟨a_0,\dots ,a_m⟩={\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 ${\mathfrak{N}}_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 $\epsilon$ in the language of ${\mathfrak{N}}_M$ that behaves like $x^y=z$ without the symbol $E$:

Achieving this makes every representability result hold with $A_M$ and ${\mathfrak{N}}_M$ in place of $A_E$ and $\mathfrak{N}$.

The obstacle in the recursion

Exponentiation satisfies the recursion equations

Primitive recursion is available among the representable functions, so one might define the sequence of partial powers and read off the last entry:

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 $\text{Cn }{A}_E$ but not known to be representable in $\text{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.

Granting the lemma, replace $(s{)}_i$ by $\delta (s,i)$:

The lemma guarantees such an $s$ exists, $E^{\ast \ast }$ is representable in $\text{Cn }{A}_M$ by the minimization operator, and

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

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.

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 $\text{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 $\frac{1}{2}a$ on even inputs, one has

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.

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

This is representable in $\text{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

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.

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.

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 $|c_1-c_2|$, 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 $⟨a_0,\dots ,a_n⟩$, at some $c$.

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

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 $|j-k|\cdot s!$; since it misses $s!$, it divides $|j-k|$. But $|j-k|\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$.

Exponentiation and the primitive recursive functions

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

The consequence propagates through the whole catalog. Up to the prime-listing function, every relation and function shown representable in $\text{Cn }{A}_E$ was already representable in $\text{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 $\text{Cn }{A}_M$, and every recursive function is functionally representable there.
• The undecidability results transfer. Any theory $T$ in the language of ${\mathfrak{N}}_M$ with $T\cup A_M$ consistent fails to be recursive — the strong undecidability of $\text{Cn }{A}_M$. Adding only multiplication to addition already forces undecidability; exponentiation was never required.
• Truth in ${\mathfrak{N}}_M$ is not arithmetical. Exponentiation is definable in ${\mathfrak{N}}_M$, being representable in a subtheory of its own theory, so every arithmetical relation is definable in ${\mathfrak{N}}_M$; by Tarski's theorem $\text{Th }{\mathfrak{N}}_M$ is not definable in ${\mathfrak{N}}_M$ and hence not arithmetical.

In the language of interpretations between theories, there is a faithful interpretation of $\text{Th }\mathfrak{N}$ into $\text{Th }{\mathfrak{N}}_M$: the identity on every symbol except $E$, and on $E$ the formula defining exponentiation in ${\mathfrak{N}}_M$. The two structures have the same complexity even though one lacks a symbol for the other's exponentiation.

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 turns that self-reference into a sentence asserting its own unprovability.