The Structure of Arithmetic and Definability

Soundness and completeness tie provability to truth across all structures at once: $\Gamma ⊢\phi$ exactly when $\Gamma \models \phi$. Number theory fixes attention on a single structure, the natural numbers under their arithmetic, and asks a sharper question. Take the sentences true in that one structure: can any manageable set of axioms prove all of them and only them? The answer is no, and the obstruction is exact.

The language of number theory

The language of number theory is the first-order language with equality whose non-logical vocabulary names the standard arithmetic operations.¹ Its parameters are:

• $\forall$, the quantifier, read for all natural numbers.
• $0$, a constant symbol, denoting the number zero. Zero is a natural number throughout.
• $S$, a one-place function symbol for the successor function $S(n)=n+1$.
• $<$, a two-place predicate symbol for the strict ordering on $\mathbb{N}$.
• $+$, $\cdot$, $E$, two-place function symbols for addition, multiplication, and exponentiation ($E$ meaning raised to the power).

The intended structure for this language is written $\mathfrak{N}$, with universe $\mathbb{N}=\{0,1,2,\dots \}$ and each symbol interpreted by the operation it names:

More precisely $|\mathfrak{N}|=\mathbb{N}$, $0^{\mathfrak{N}}=0$, $S^{\mathfrak{N}}$ is the successor function, and so on for the other symbols.

Two features of $\text{Th }\mathfrak{N}$ are settled before any argument. It is complete: for every sentence $\sigma$, either $\sigma$ or $\neg \sigma$ is true in $\mathfrak{N}$, so exactly one lies in $\text{Th }\mathfrak{N}$. And it is satisfiable, since $\mathfrak{N}$ itself is a model. Completeness bears directly on axiomatizability: a complete theory that were also axiomatizable would be decidable, and the main results show $\text{Th }\mathfrak{N}$ is not.

Numerals name every number

For each natural number $k$ the term $S^{k}0$ (the symbol $S$ prefixed $k$ times to $0$) denotes $k$. These terms are the numerals:

The set of numerals is generated from $\{0\}$ by prefixing $S$. Every natural number is named by a closed term of the language, a feature used constantly once the discussion turns to what axioms can prove about specific numbers.¹ As a concession to ordinary usage, the two-place symbols are written infix,

in place of the official prefix forms $<xy$, $+xy$, $\cdot xy$, $Exy$.

Reducts of the standard structure

Before studying $\mathfrak{N}$ in full, consider its reducts: restrictions of $\mathfrak{N}$ to sublanguages that keep only some of the symbols. Dropping vocabulary can only shrink what is expressible, and the reducts turn out to behave very differently from the full structure.

• ${\mathfrak{N}}_S=(\mathbb{N};0,S)$ — successor alone.
• ${\mathfrak{N}}_L=(\mathbb{N};0,S,<)$ — successor and order.
• ${\mathfrak{N}}_A=(\mathbb{N};0,S,<,+)$ — with addition (Presburger's structure).
• ${\mathfrak{N}}_M=(\mathbb{N};0,S,<,+,\cdot )$ — with multiplication, studied for definability of exponentiation.

For each of these structures the same three questions are posed:

• (A) Decidability and axioms. Is the theory of the structure decidable? If so, is there a manageable set of axioms, and can it be finite?
• (B) Definability. Which subsets of $\mathbb{N}$ can a formula define in the structure?
• (C) Nonstandard models. What do the models not isomorphic to the intended structure look like?

The successor and Presburger reducts answer (A)–(C) cleanly and positively: decidable, well-axiomatized, definable sets classified. The full structure fails (A) completely.

Definability

A relation on $\mathbb{N}$ is definable in $\mathfrak{N}$ when a single formula picks out exactly its members.

Only countably many relations are definable, since there are only countably many formulas, while $\mathbb{N}$ has uncountably many subsets. Yet almost every relation from ordinary arithmetic is among the countably many. The set of primes, for example, is defined in $\mathfrak{N}$ by

read: $v_1$ is not $1$, and in any factorization $v_1=v_2\cdot v_3$ one factor is $1$. The divisibility relation $a$ divides $b$ is defined by $\exists v_3(v_1\cdot v_3=v_2)$, and from these a long catalog of definable relations follows.

Definability is semantic: whether a formula is true of exactly the right tuples. A syntactic notion sits beside it, representability, which concerns whether the axioms can prove the right instances. The two agree for the full structure and diverge for weak subtheories, and that divergence drives the incompleteness results.

Truth against provability

The central comparison is between two sets of sentences: those true in $\mathfrak{N}$, and those provable from a chosen set $A$ of axioms. The apparatus that connects them is Gödel numbering. To each formula $\alpha$ one assigns an integer $\lceil \alpha \rceil$, its Gödel number, in any sufficiently straightforward way that $\lceil \alpha \rceil$ can be found effectively from $\alpha$ and conversely. To each finite sequence $D$ of formulas, such as a deduction, one assigns an integer $G(D)$. A set $A$ of formulas then has a corresponding set $\{\lceil \alpha \rceil :\alpha \in A\}$ of numbers, and statements about proofs become statements about numbers.

Three routes exploit the coding, and they are three faces of one argument.²

• Self-reference. Build a sentence $\sigma$ that, decoded, asserts its own unprovability.
• Diagonalization. Build a set of numbers that differs from every definable set, without visible self-reference.
• Computability. Compare what is effectively enumerable with what is true.

The self-reference route already yields a true, unprovable sentence for any sound and definable axiom set.

The construction makes $\sigma$ express, through the coding, that $\sigma$ itself is not a theorem of $A$. If $A⊢\sigma$, then what $\sigma$ says is false, contradicting that every member of $A$ is true; so $A⊬\sigma$, which is precisely what $\sigma$ asserts, making $\sigma$ true.³ The hypothesis that $A$'s Gödel numbers are definable is what lets the relation codes a deduction from $A$ be captured by a formula.

Taking $A=\text{Th }\mathfrak{N}$ itself would make the hypothesis collapse, and the contradiction that results proves a limit on definability.

Part (a) is the semantic result, later sharpened into Tarski's theorem on the undefinability of truth. Part (b) follows once one grants that every decidable set of numbers is definable in $\mathfrak{N}$ (a consequence of Church's thesis): if $\text{Th }\mathfrak{N}$ were decidable its set of Gödel numbers would be definable, which (a) forbids. Part (c) is then immediate, because a complete theory that were axiomatizable would be decidable.⁴ The computability route states the same failure as a mismatch of set sizes, comparing $\text{Th }\mathfrak{N}$ against the consequence set$\text{Cn }A=\{\sigma :A\models \sigma \}$ of the axioms.

The no-adequate-axioms theorem poses the dilemma directly. Any effectively given axiom set $A$ for arithmetic is either unsound, proving some false sentence, or incomplete, leaving some true sentence unproved. No effective axiomatization escapes both horns.⁵

Undecidability of stronger theories

$\text{Th }\mathfrak{N}$ is undecidable because a finitely axiomatized subtheory of arithmetic already represents facts about decision procedures, which lets a diagonal argument run inside arithmetic itself. Any satisfiable theory at least as strong as that fragment — full number theory and set theory among them — inherits undecidability, so cannot be both complete and axiomatizable.⁶

The reducts run the other way. The successor reduct is decidable, its definable sets exactly the finite and cofinite ones; order and addition keep decidability up to the point where addition and multiplication together break it. The finite subtheory $A_E$ carries representability, which links computation to provability and underlies the incompleteness theorems.