--- title: The Structure of Arithmetic and Definability module: Number Theory and Definability moduleNumber: 6 lessonNumber: 1 order: 601 summary: > Number theory is the theory of one fixed structure, the natural numbers under successor, order, addition, multiplication, and exponentiation. Every number is named by a numeral, and a relation is definable when a single formula picks out exactly its tuples. The central gap separates the sentences true in that structure from those any reasonable set of axioms can prove. topics: [Number Theory and Definability] sources: - book: Enderton ref: "Ch. 3 — Undecidability; §3.0 Number Theory" draft: false --- Soundness and completeness tie provability to truth across all structures at once: $\Gamma \vdash \varphi$ exactly when $\Gamma \models \varphi$. 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.[^lang] 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 $\fN$, with universe $\mathbb{N} = \{0, 1, 2, \dots\}$ and each symbol interpreted by the operation it names: $$ \fN = (\mathbb{N};\ 0,\ S,\ <,\ +,\ \cdot,\ E). $$ More precisely $|\fN| = \mathbb{N}$, $0^{\fN} = 0$, $S^{\fN}$ is the successor function, and so on for the other symbols. > **Definition (Number theory).** _Number theory_ is the theory of the intended > structure, $\Th\fN = \{\sigma : \models_{\fN} > \sigma\}$, the set of all sentences of the language true in $\fN$. Two features of $\Th\fN$ are settled before any argument. It is **complete**: for every sentence $\sigma$, either $\sigma$ or $\neg\sigma$ is true in $\fN$, so exactly one lies in $\Th\fN$. And it is **satisfiable**, since $\fN$ itself is a model. Completeness bears directly on axiomatizability: a complete theory that were also axiomatizable would be decidable, and the main results show $\Th\fN$ is not. $$ % caption: The intended structure: the successor function walks along the number % line, order runs left to right, and addition, multiplication, and exponentiation % act on pairs. \begin{tikzpicture}[>=stealth, font=\small] \definecolor{acc}{HTML}{4A6FA5} \foreach \x/\n in {0/0, 1.6/1, 3.2/2, 4.8/3, 6.4/4, 8.0/5} { \fill[acc] (\x,0) circle (2.2pt); \node[below=3pt] at (\x,0) {\n}; } \foreach \a/\b in {0/1.6, 1.6/3.2, 3.2/4.8, 4.8/6.4, 6.4/8.0} \draw[->, acc, thick] (\a,0.12) .. controls +(0.5,0.7) and +(-0.5,0.7) .. (\b,0.12); \node[acc, anchor=south] at (0.8,0.7) {successor}; \node[anchor=west, font=\footnotesize] at (8.7,0) {order runs to the right}; \node[draw, minimum width=42mm, minimum height=8mm, align=center, font=\footnotesize] (ops) at (4,-1.5) {addition, multiplication, exponentiation}; \node[font=\footnotesize, anchor=north] at (4,-2.1) {act on pairs of numbers}; \end{tikzpicture} $$ ### 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**: $$ S^0 0 = 0, \qquad S^1 0 = S0, \qquad S^2 0 = SS0, \qquad \dots $$ 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.[^lang] As a concession to ordinary usage, the two-place symbols are written infix, $$ x < y, \qquad x + y, \qquad x \cdot y, \qquad x E y, $$ in place of the official prefix forms ${<}\,x\,y$, ${+}\,x\,y$, ${\cdot}\,x\,y$, $E\,x\,y$. ## Reducts of the standard structure Before studying $\fN$ in full, consider its **reducts**: restrictions of $\fN$ 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. - **$\fN_S = (\mathbb{N};\ 0, S)$** — successor alone. - **$\fN_L = (\mathbb{N};\ 0, S, <)$** — successor and order. - **$\fN_A = (\mathbb{N};\ 0, S, <, +)$** — with addition (Presburger's structure). - **$\fN_M = (\mathbb{N};\ 0, S, <, +, \cdot)$** — with multiplication, studied for definability of exponentiation. $$ % caption: The reducts nest by vocabulary; each row adds one operation, and the % questions of decidability and definability are re-asked at every level. \begin{tikzpicture}[font=\footnotesize] \definecolor{acc}{HTML}{4A6FA5} \foreach \i/\lab/\w in {0/{successor}/22, 1/{plus order}/34, 2/{plus addition}/46, 3/{plus multiplication}/58, 4/{plus exponentiation}/70} { \node[draw, minimum width=\w mm, minimum height=8mm, align=center] (r\i) at (0, -\i*0.95) {\lab}; } \node[anchor=west, font=\scriptsize] at (3.9,0) {$N_S$}; \node[anchor=west, font=\scriptsize] at (3.9,-0.95) {$N_L$}; \node[anchor=west, font=\scriptsize] at (3.9,-1.9) {$N_A$}; \node[anchor=west, font=\scriptsize] at (3.9,-2.85) {$N_M$}; \node[anchor=west, font=\scriptsize] at (3.9,-3.8) {full arithmetic}; \end{tikzpicture} $$ 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 $\fN$** when a single formula picks out exactly its members. > **Definition (Definable relation).** An $m$-ary relation $R \subseteq > \mathbb{N}^m$ is _definable in $\fN$_ iff there is a formula > $\rho$, with only $v_1, \dots, v_m$ free, such that for all > $a_1, \dots, a_m \in \mathbb{N}$, > $$ > \langle a_1, \dots, a_m \rangle \in R \iff\ \models_{\fN} \rho[[a_1, \dots, a_m]]. > $$ > A set (unary relation) is definable in the same sense with $m = 1$. 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 $\fN$ by $$ v_1 \neq S 0 \ \wedge\ \forall v_2\, \forall v_3\, \bigl( v_1 = v_2 \cdot v_3 \rightarrow v_2 = S 0 \vee v_3 = S 0 \bigr), $$ 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. > **Worked example (The prime formula tested on 5 and 6).** Write $\pi(v_1)$ for > the defining formula > $$ > v_1 \neq S 0 \ \wedge\ \forall v_2\, \forall v_3\, \bigl( v_1 = v_2 \cdot v_3 > \rightarrow v_2 = S 0 \vee v_3 = S 0 \bigr). > $$ > Evaluate $\models_{\fN} \pi[[5]]$. The first conjunct holds, since $5 \neq 1$. > For the second, run over every factorization $5 = a \cdot b$ in $\mathbb{N}$: > the only ones are $1 \cdot 5$ and $5 \cdot 1$, and each has a factor equal to > $1$, so the implication holds for all $v_2, v_3$. Both conjuncts hold, so $5$ > satisfies $\pi$. > Now $\models_{\fN} \pi[[6]]$ fails. The factorization $6 = 2 \cdot 3$ gives > $v_2 = 2 \neq 1$ and $v_3 = 3 \neq 1$, so the implication has a true antecedent > and a false consequent. The second conjunct is false, and $6$ does not satisfy > $\pi$. The formula holds of exactly the primes. $$ % caption: A defining formula selects a subset of the number line; here the prime % formula marks 2, 3, 5, 7 and rejects the composites 0, 1, 4, 6, 8, 9. \begin{tikzpicture}[>=stealth, font=\footnotesize] \definecolor{acc}{HTML}{4A6FA5} % composites 0,1,4,6,8,9 as open circles \foreach \x/\n in {0/0, 1/1, 4/4, 6/6, 8/8, 9/9} { \draw[black] (\x*0.95,0) circle (3pt); \node[black, below=3pt] at (\x*0.95,0) {\n}; } % primes 2,3,5,7 filled \foreach \x/\n in {2/2, 3/3, 5/5, 7/7} { \fill[acc] (\x*0.95,0) circle (3pt); \node[acc, below=3pt] at (\x*0.95,0) {\n}; } \node[anchor=west, acc] at (9.7*0.95,0) {primes}; \node[draw, acc, align=center, font=\scriptsize, anchor=south] at (4.75,1.0) {formula true of $v_1$}; \draw[->, acc] (4.75,0.75) -- (4.75,0.2); \end{tikzpicture} $$ Definability is semantic: whether a formula is _true_ of exactly the right tuples. A syntactic notion sits beside it, [representability](/logic/arithmetic-and-definability/a-subtheory-and-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 $\fN$, 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.[^approaches] - **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. > **Theorem (A true unprovable sentence).** Let $A \subseteq > \Th\fN$ be a set of sentences true in $\fN$ > whose set of Gödel numbers $\{\lceil \alpha \rceil : \alpha \in A\}$ is > definable in $\fN$. Then there is a sentence $\sigma$ true in > $\fN$ but not deducible from $A$. The construction makes $\sigma$ express, through the coding, that $\sigma$ itself is not a theorem of $A$. If $A \vdash \sigma$, then what $\sigma$ says is false, contradicting that every member of $A$ is true; so $A \nvdash \sigma$, which is precisely what $\sigma$ asserts, making $\sigma$ true.[^30a] 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 = \Th\fN$ itself would make the hypothesis collapse, and the contradiction that results proves a limit on definability. > **Theorem (Undefinability of truth).** > - (a) The set $\{\lceil \tau \rceil : \models_{\fN} \tau\}$ of Gödel > numbers of true sentences is not definable in $\fN$. > - (b) $\Th\fN$ is undecidable. > - (c) $\Th\fN$ is not axiomatizable. 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 $\fN$ (a consequence of Church's thesis): if $\Th\fN$ 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.[^30c] The computability route states the same failure as a mismatch of set sizes, comparing $\Th\fN$ against the [consequence set](/logic/models-and-theories/theories-elementary-classes-and-categoricity) $\Cn A = \{\sigma : A \models \sigma\}$ of the axioms. > **Worked example (Diagonalizing out of the definable sets).** Enumerate the > formulas with only $v_1$ free as $\alpha_0, \alpha_1, \dots$ by Gödel number, > and set > $$ > a \mathbin{P} b \iff a = \lceil \alpha \rceil \text{ for some } \alpha(v_1) > \text{ and } \models_{\fN} \alpha(S^b 0). > $$ > Every set definable in $\fN$ is a vertical section $P_a = \{b : a \mathbin{P} > b\}$: take $a = \lceil \alpha \rceil$ for a formula $\alpha$ defining it. Now > define > $$ > H = \{b : \langle b, b\rangle \notin P\}, > $$ > so $b \in H$ reads "$b$ is not true of $b$." $H$ is no section $P_a$: at the > diagonal point $b = a$, membership flips, since $a \in H \iff \langle a, > a\rangle \notin P \iff a \notin P_a$. So $H$ differs from $P_a$ at $a$, for > every $a$, and $H$ is not definable in $\fN$. The one ingredient that resists > translation into arithmetic is the clause $\models_{\fN} \alpha(S^b 0)$, which > pins the undefinability on truth itself. > **Theorem (No effective axiomatization of true arithmetic).** For any decidable, or even effectively > enumerable, set $A$ of axioms, > $$ > \Cn A \neq \Th\fN, > $$ > because $\Cn A$ is effectively enumerable and > $\Th\fN$ is not. 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.[^30d] $$ % caption: The chapter's path: a definable set is representable in a finite % subtheory, representability equals recursiveness, and the diagonal argument on % recursive sets forces the gap between provable and true. \begin{tikzpicture}[>=stealth, font=\footnotesize, b/.style={draw, minimum width=26mm, minimum height=10mm, align=center}] \definecolor{acc}{HTML}{4A6FA5} \node[b] (def) at (0,0) {def\/inable}; \node[b] (rep) at (3.4,0) {representable}; \node[b] (rec) at (6.8,0) {recursive}; \node[b, draw=acc, text=acc] (inc) at (10.4,0) {incompleteness}; \draw[->, acc, thick] (def) -- (rep); \draw[->, acc, thick] (rep) -- (rec); \draw[->, acc, thick] (rec) -- (inc); \node[font=\scriptsize, anchor=south] at (1.7,0.55) {in a f\/inite theory}; \node[font=\scriptsize, anchor=south] at (5.1,0.55) {equivalent}; \node[font=\scriptsize, anchor=south] at (8.6,0.55) {diagonal argument}; \end{tikzpicture} $$ ## Undecidability of stronger theories $\Th\fN$ 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.[^why] The reducts run the other way. The [successor reduct](/logic/arithmetic-and-definability/natural-numbers-with-successor) is decidable, its definable sets exactly the finite and cofinite ones; [order and addition](/logic/arithmetic-and-definability/presburger-and-reducts) keep decidability up to the point where addition and multiplication together break it. The finite [subtheory $A_E$](/logic/arithmetic-and-definability/a-subtheory-and-representability) carries representability, which links computation to provability and underlies the [incompleteness theorems](/logic/incompleteness/incompleteness-and-undecidability). [^lang]: Enderton, §3.0 — the parameters of the language of number theory, the intended structure $\fN$, and the numerals $S^k 0$ naming each natural number. [^approaches]: Enderton, §3.0, "Preview" — the self-reference, diagonalization, and computability approaches, presented as three aspects of one argument. [^30a]: Enderton, §3.0, Theorem 30A — construction of $\sigma$ asserting its own unprovability from a true, definable axiom set. [^30c]: Enderton, §3.0, Corollary 30B and Theorem 30C — the set of Gödel numbers of truths is undefinable in $\fN$; $\Th\fN$ is undecidable and unaxiomatizable, the last via completeness (Corollary 26I). [^30d]: Enderton, §3.0, Theorem 30D — for effectively enumerable axioms $A$, $\Cn A \neq \Th\fN$, since the former is effectively enumerable and the latter is not. [^why]: Enderton, §3.0 — number theory is chosen because a subtheory is an undecidable set of sentences, and any satisfiable theory at least as strong is undecidable, hence not both complete and axiomatizable.