---
title: "Reducts: Order, Addition, and Multiplication"
module: Number Theory and Definability
moduleNumber: 6
lessonNumber: 3
order: 603
summary: >
  Adding order to the successor reduct keeps decidability and makes the theory
  finitely axiomatizable; adding addition gives Presburger arithmetic, still
  decidable by quantifier elimination once congruence predicates are included,
  with definable sets exactly the eventually periodic ones. Multiplication is the
  break point: neither addition nor order can define it, and once it joins
  addition the theory stops being decidable.
topics: [Number Theory and Definability]
sources:
  - book: Enderton
    ref: "Ch. 3 — Undecidability; §3.2 Other Reducts of Number Theory"
draft: false
---

The [successor reduct](/logic/arithmetic-and-definability/natural-numbers-with-successor)
is decidable but arithmetically empty: it cannot even define the ordering.
Adding order and then addition tracks which of the three questions —
decidability, definability, nonstandard models — still admit clean answers.
Decidability persists further than the added expressiveness suggests, failing
only when both addition and multiplication are present.

## Adding order

The first step adds the ordering symbol, giving

$$
\fN_L = (\mathbb{N};\ 0, S, <).
$$

Its theory is decidable and admits quantifier elimination, like the successor
theory. Two things change: $\Th\fN_L$ is **finitely
axiomatizable**, and it is **not categorical** in any infinite cardinality. A
finite set $A_L$ of six sentences axiomatizes it, writing $x \le y$ for
$x < y \vee x = y$:

- **(S3)** $\forall y\, (y \neq 0 \rightarrow \exists x\ y = Sx)$
- **(L1)** $\forall x\, \forall y\, (x < Sy \leftrightarrow x \le y)$
- **(L2)** $\forall x\ x \not< 0$
- **(L3)** $\forall x\, \forall y\, (x < y \vee x = y \vee y < x)$ — trichotomy
- **(L4)** $\forall x\, \forall y\, (x < y \rightarrow y \not< x)$
- **(L5)** $\forall x\, \forall y\, \forall z\, (x < y \rightarrow y < z
  \rightarrow x < z)$ — transitivity

Every axiom is true in $\fN_L$, so $\Cn A_L \subseteq
\Th\fN_L$. The reverse inclusion needs work, and the first
move is to derive the successor axioms $A_S$ from $A_L$. Among
the consequences of $A_L$ are $x < Sx$, irreflexivity $x \not< x$, the equivalence
$x < y \leftrightarrow Sx < Sy$, and then S1, S2, and every S4.$n$.[^order] So any
model of $A_L$, with $<$ ignored, is a model of $A_S$: a standard part followed by
Z-chains, now additionally ordered.

> **Theorem (Quantifier elimination for order).** $\Cn A_L$
> admits elimination of quantifiers.

The primitive case is $\exists x\,(\alpha_0 \wedge \dots)$ with each $\alpha_i$ an
equation or inequality $S^k u = S^l t$ or $S^k u < S^l t$. Negations are removed
using trichotomy, and $x$ is arranged to occur on one side only. When some
conjunct is an equation, it fixes $x$ as in the successor proof. Otherwise every
conjunct is an inequality, splitting into lower bounds $t_i < S^{m_i} x$ and upper
bounds $S^{n_j} x < u_j$; the quantifier-free replacement asserts there is a gap
between the greatest lower bound and least upper bound, with the solution not
forced negative.[^order]

> **Corollary (Completeness and decidability of the order theory).** $\Cn A_L$ is complete, equals
> $\Th\fN_L$, and $\Th\fN_L$ is
> decidable.

Definability barely moves. The definable subsets of $\mathbb{N}$ are still exactly
the finite and cofinite sets (Corollary 32C), the same as for successor. But the
definable **binary** relations grow: the ordering $\{\langle m, n\rangle : m < n\}$
is now definable (it is a primitive), whereas in $\fN_S$ it was not. What
order still cannot express is addition.

> **Corollary (Undefinability of addition from order).** The addition relation $\{\langle m, n, p\rangle : m + n =
> p\}$ is not definable in $\fN_L$.

If addition were definable, so would be the even numbers ($\exists y\ v_1 = y +
y$), a set that is neither finite nor cofinite. That contradicts Corollary 32C,
so addition is genuinely new vocabulary.[^order]

## Presburger arithmetic

The next step adds the addition symbol:

$$
\fN_A = (\mathbb{N};\ 0, S, <, +).
$$

Its nonstandard models are more constrained than before. Ignoring $+$, such a
model is still a standard part plus Z-chains, but the ordering among the Z-chains
can no longer be arbitrary. In a nonstandard model $\fA$, the induced
order on Z-chains is **dense with no endpoints**: for an infinite element $a$, the
element $a +^{\fA} a$ lies in a strictly larger chain, some $b$ has
$b +^{\fA} b$ equal to $a$ or its successor and lies in a smaller chain,
and between any two chains a similar halving lands a third.[^presburger]

$$
% caption: In a nonstandard model of Presburger arithmetic the standard part is
% followed by Z-chains whose order is dense without endpoints: doubling moves an
% element to a larger chain, halving to a smaller one, and averaging lands between.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{4A6FA5}
  % standard part block
  \draw[acc, thick] (0,0) -- (2.2,0);
  \fill[acc] (0,0) circle (2pt);
  \node[below=3pt, font=\scriptsize] at (0,0) {0};
  \node[acc, above=1pt, font=\scriptsize] at (1.1,0) {standard part};
  % z-chains as short bars
  \foreach \x/\lab in {3.4/{smaller chain}, 5.2/{$a$}, 7.0/{larger chain}} {
    \draw[black, thick] (\x,0) -- (\x+1.0,0);
    \node[below=4pt, font=\scriptsize] at (\x+0.5,0) {\lab};
  }
  \foreach \bx in {2.85, 4.85, 6.65, 8.15} \foreach \d in {0,1,2} \fill[black] (\bx+\d*0.14,0) circle (0.8pt);
  \draw[->, acc] (5.7,0.55) .. controls (6.4,0.9) .. (7.2,0.55);
  \node[acc, font=\scriptsize, anchor=south] at (6.4,0.85) {doubling};
  \draw[->, acc] (5.0,0.55) .. controls (4.3,0.9) .. (3.7,0.55);
  \node[acc, font=\scriptsize, anchor=south] at (4.3,0.85) {halving};
\end{tikzpicture}
$$

Despite this richer structure, the theory is decidable.

> **Theorem (Decidability of Presburger arithmetic; Presburger, 1929).** The theory of $\fN_A =
> (\mathbb{N};\ 0, S, <, +)$ is decidable.

The proof is again quantifier elimination, but $\Th\fN_A$
does **not** admit it as stated. The even-number formula $\exists y\ v_1 = y + y$
is equivalent to no quantifier-free formula in the language of $\fN_A$.
The fix is to add, for each $k$, a binary predicate $\equiv_k$ for congruence
modulo $k$, giving the expanded structure

$$
\fN_{\equiv} = (\mathbb{N};\ 0, S, <, +, \equiv_2, \equiv_3, \dots),
$$

which does admit elimination of quantifiers. Expanding the language does not by
itself give decidability. For that one needs the elimination to be **effective**:
given a sentence $\sigma$, effectively find a quantifier-free equivalent
$\sigma'$, and effectively decide whether $\sigma'$ is true.[^presburger]

### The elimination procedure

Every term reduces to $S^{n_0} 0 + n_1 x_1 + \dots + n_k x_k$, where $nx$ means $x +
\dots + x$ with $n$ summands. Starting from $\exists y\,(\beta_1 \wedge \dots
\wedge \beta_n)$ with literals $\beta_i$, the steps are:

- **Eliminate negation.** Rewrite $\neg(t_1 = t_2)$ and $\neg(t_1 < t_2)$ by
  trichotomy, and $\neg(t_1 \equiv_m t_2)$ as a disjunction over the nonzero
  residues mod $m$. Each conjunct becomes atomic, with $y$ present in every one.
- **Uniformize the coefficient of $y$.** Let $p$ be the least common multiple of
  the coefficients of $y$. Multiply each atomic formula through so the coefficient
  of $y$ is $p$; for a congruence, the modulus scales too, since $a \equiv_m b$
  iff $ka \equiv_{km} kb$.
- **Eliminate the coefficient.** Replace $py$ by a fresh $x$ and add the conjunct
  $x \equiv_p 0$: "there exists a multiple $x$ of $p$ such that $\dots$."
- **Collapse to bounds.** With equalities removed, the formula asserts an $x$
  above certain lower bounds, below certain upper bounds, and meeting certain
  congruences. Let $M$ be the least common multiple of the moduli. The residue
  pattern has period $M$, so a solution, if any exists, occurs among $M$
  consecutive integers above each lower bound (and among $0, \dots, M-1$ to cover
  all-negative bounds). That finite search is written out as a quantifier-free
  disjunction.

The result is a quantifier-free $\tau$ true exactly when $\sigma$ is. To decide
$\tau$, evaluate its atomic sentences: any closed term reduces to some $S^n 0$,
and $S^n 0 \equiv_m S^p 0$ is true iff $n \equiv p \pmod m$.[^presburger]

> **Worked example (Presburger elimination on a concrete formula).** Eliminate
> the quantifier from
> $$
> \exists y\, (w < 4y \ \wedge\ 2y < u \ \wedge\ 3y < v \ \wedge\ y \equiv_3 t),
> $$
> with $t, u, v, w$ terms not containing $y$.
> - **Uniformize.** The coefficients of $y$ are $4, 2, 3, 1$, with least common
>   multiple $p = 12$. Multiply each conjunct through (by $3, 6, 4, 12$
>   respectively) and raise the congruence modulus from $3$ to $36$:
>   $$
>   \exists y\, (3w < 12y \ \wedge\ 12y < 6u \ \wedge\ 12y < 4v \ \wedge\ 12y \equiv_{36} 12t).
>   $$
> - **Eliminate the coefficient.** Replace $12y$ by $x$ and record that $x$ is a
>   multiple of $12$:
>   $$
>   \exists x\, (3w < x \ \wedge\ x < 6u \ \wedge\ x < 4v \ \wedge\ x \equiv_{36} 12t \ \wedge\ x \equiv_{12} 0).
>   $$
> - **Guard nonnegativity.** Add the artificial lower bound $0 < x + S0$, so the
>   all-negative-bounds case needs no separate treatment: two lower bounds ($3w$
>   and the artificial one), two upper bounds, and two congruences.
> - **Finite search.** The moduli $36$ and $12$ give $M = 36$, so the residue
>   pattern of $x$ repeats with period $36$ and a solution exists iff one of the
>   $36$ consecutive candidates above one of the $2$ lower bounds works. The
>   quantifier-free equivalent is a disjunction of $2 \times 36 = 72$
>   conjunctions, each with six constituents (two bound-orderings, two
>   upper-bound checks, two congruence checks).

The blow-up from one quantifier to $72$ disjuncts is typical, and it compounds:
each nested quantifier multiplies the case count again. Decidability is not the
same as feasibility. Fischer and Rabin showed in 1974
that no decision procedure for Presburger arithmetic runs fast enough to be
practical on long formulas; the problem provably requires more than exponential
time.[^fr]

### Eventually periodic definable sets

The elimination also settles which sets are definable. A set $D \subseteq \mathbb{N}$ is
**periodic** with period $p > 0$ if $n \in D \iff n + p \in D$ for all $n$, and
**eventually periodic** if this holds for all $n$ past some threshold $M$.

> **Theorem (Eventually periodic definable sets).** A subset of
> $\mathbb{N}$ is definable in $(\mathbb{N};\ 0, S, <, +)$ iff it is eventually
> periodic.

A definable set is defined in $\fN_{\equiv}$ by a quantifier-free formula
in $v_1$. Since eventually periodic sets are closed under union, intersection, and
complement, it suffices to check the atomic formulas: $nv_1 + t = u$ and
$nv_1 + t < u$ define finite and cofinite sets (period $1$ eventually), and
$nv_1 + t \equiv_m u$ defines a genuinely periodic set of period $m$.[^presburger]

$$
% caption: A definable set of Presburger arithmetic is finite noise up to some
% threshold, then a residue pattern that repeats forever with a fixed period.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{4A6FA5}
  \definecolor{grn}{HTML}{2E7D46}
  % all positions as open circles with labels
  \foreach \x in {0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15} {
    \draw[black] (\x*0.62,0) circle (2.4pt);
    \node[below=2pt, font=\tiny] at (\x*0.62,0) {\x};
  }
  % members: finite noise before threshold, then period 3
  \foreach \x in {1,4,6,9,12,15} \fill[grn] (\x*0.62,0) circle (2.4pt);
  \draw[acc, thick, dashed] (5.5*0.62,-0.5) -- (5.5*0.62,0.9);
  \node[acc, anchor=south, font=\scriptsize] at (5.5*0.62,0.9) {threshold};
  \node[grn, anchor=west, font=\scriptsize] at (4.4,0.6) {period 3 from here on};
\end{tikzpicture}
$$

> **Worked example (A periodic set and a non-periodic one).** The even numbers
> are defined in $\fN_{\equiv}$ by the single atomic formula $v_1 \equiv_2 0$, so
> they are definable in $\fN_A$ too. As a set they have period $2$,
> $$
> n \in D \iff n + 2 \in D \quad \text{for every } n,
> $$
> which is the eventually-periodic condition with threshold $M = 0$. The perfect
> squares $\{0, 1, 4, 9, 16, 25, \dots\}$ are not eventually periodic: their
> consecutive gaps $1, 3, 5, 7, 9, \dots$ grow without bound. For any candidate
> period $p$ and threshold $M$, pick a gap beyond $M$ that exceeds $p$; then some
> $n > M$ has $n \in D$ while $n + p \notin D$, breaking periodicity. By the
> eventually-periodic theorem the squares are undefinable in $(\mathbb{N};\ 0, S,
> <, +)$, so multiplication is genuinely new vocabulary.

$$
% caption: The even numbers repeat with period two and are definable; the perfect
% squares have gaps that grow without bound, so they are not eventually periodic
% and are undefinable in the addition reduct.
\begin{tikzpicture}[>=stealth, font=\footnotesize]
  \definecolor{acc}{HTML}{4A6FA5}
  \definecolor{grn}{HTML}{2E7D46}
  \node[anchor=east, font=\scriptsize] at (-0.3,0.8) {even};
  \foreach \x in {0,...,16} { \draw[black] (\x*0.55,0.8) circle (2.2pt); }
  \foreach \x in {0,2,4,6,8,10,12,14,16} { \fill[grn] (\x*0.55,0.8) circle (2.2pt); }
  \node[grn, anchor=west, font=\scriptsize] at (9.35,0.8) {def\/inable, period 2};
  \node[anchor=east, font=\scriptsize] at (-0.3,0) {square};
  \foreach \x in {0,...,16} { \draw[black] (\x*0.55,0) circle (2.2pt); }
  \foreach \x in {0,1,4,9,16} { \fill[acc] (\x*0.55,0) circle (2.2pt); }
  \node[acc, anchor=west, font=\scriptsize] at (9.35,0) {not def\/inable};
\end{tikzpicture}
$$

> **Corollary (Undefinability of multiplication).** The multiplication relation $\{\langle m, n, p\rangle : p =
> m \cdot n\}$ is not definable in $(\mathbb{N};\ 0, S, <, +)$.

If multiplication were definable, the squares $\{n^2 : n \in \mathbb{N}\}$ would
be too, contradicting the eventual-periodicity theorem. Multiplication, like addition one level down,
is real new vocabulary.[^presburger]

## The break point

Each reduct is decidable, and each fails to
define the operation the next level adds, until multiplication and addition sit in
the same structure.

| Reduct | Adds | Decidable | Definable subsets of $\mathbb{N}$ | Cannot define |
| --- | --- | --- | --- | --- |
| $\fN_S$ | — | yes | finite / cofinite | order |
| $\fN_L$ | $<$ | yes | finite / cofinite | addition |
| $\fN_A$ | $+$ | yes (Presburger) | eventually periodic | multiplication |
| $\fN$ | $\cdot,\ E$ | no | all arithmetical | — |

Addition alone is decidable. Multiplication alone, the reduct $(\mathbb{N};
\cdot)$, is also decidable. It is the two **together** that produce a structure
whose theory can encode arbitrary computation, and the encoding forces
undecidability.

$$
% caption: Order, addition, and multiplication are each harmless in isolation; the
% full structure that carries both addition and multiplication is where
% decidability fails.
\begin{tikzpicture}[>=stealth, font=\footnotesize,
  op/.style={draw, minimum width=24mm, minimum height=9mm, align=center}]
  \definecolor{acc}{HTML}{4A6FA5}
  \definecolor{red}{HTML}{B23A48}
  \node[op] (add) at (0,1.1)  {addition};
  \node[op] (mul) at (0,-1.1) {multiplication};
  \node[op, draw=red, text=red, thick] (full) at (5.2,0) {both together};
  \draw[->, acc, thick] (add)  -- (full);
  \draw[->, acc, thick] (mul)  -- (full);
  \node[red, anchor=west, font=\footnotesize] at (7.1,0) {undecidable};
  \draw[->, red, thick] (6.5,0) -- (7.0,0);
  \node[acc, anchor=east, font=\scriptsize] at (-1.4,1.1)  {decidable};
  \node[acc, anchor=east, font=\scriptsize] at (-1.4,-1.1) {decidable};
  \draw[->, acc] (-1.35,1.1) -- (-1.15,1.1);
  \draw[->, acc] (-1.35,-1.1) -- (-1.15,-1.1);
\end{tikzpicture}
$$

Carrying that encoding takes the full language and a finite subtheory strong
enough for it. The mechanism is
[representability](/logic/arithmetic-and-definability/a-subtheory-and-representability),
the last step before the
[incompleteness theorems](/logic/incompleteness/incompleteness-and-undecidability).

[^order]: Enderton, §3.2 — the axiom set $A_L$, the derivations of S1, S2, S4.$n$ from it, Theorem 32A (quantifier elimination), and Corollaries 32B–32D on completeness, definable subsets, and the undefinability of addition.
[^presburger]: Enderton, §3.2 — the structure $\fN_A$, dense ordering of its Z-chains, Theorem 32E (Presburger's decidability) with the congruence predicates and elimination procedure, Theorem 32F (eventually periodic definable sets), and Corollary 32G (undefinability of multiplication).
[^fr]: Enderton, §3.2 — Fischer and Rabin's 1974 result that no decision procedure for Presburger arithmetic is fast enough to be feasible on long formulas.