Reducts: Order, Addition, and Multiplication

The successor reduct 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

Its theory is decidable and admits quantifier elimination, like the successor theory. Two things change: $\text{Th }{\mathfrak{N}}_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\ne 0\to \exists xy=Sx)$
• (L1) $\forall x\forall y(x<Sy\leftrightarrow x\le y)$
• (L2) $\forall xx\nless 0$
• (L3) $\forall x\forall y(x<y\vee x=y\vee y<x)$ — trichotomy
• (L4) $\forall x\forall y(x<y\to y\nless x)$
• (L5) $\forall x\forall y\forall z(x<y\to y<z\to x<z)$ — transitivity

Every axiom is true in ${\mathfrak{N}}_L$, so $\text{Cn }{A}_L\subseteq \text{Th }{\mathfrak{N}}_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\nless x$, the equivalence $x<y\leftrightarrow Sx<Sy$, and then S1, S2, and every S4.$n$.¹ So any model of $A_L$, with $<$ ignored, is a model of $A_S$: a standard part followed by Z-chains, now additionally ordered.

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.¹

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 $\{⟨m,n⟩:m<n\}$ is now definable (it is a primitive), whereas in ${\mathfrak{N}}_S$ it was not. What order still cannot express is addition.

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.¹

Presburger arithmetic

The next step adds the addition symbol:

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 $\mathfrak{A}$, the induced order on Z-chains is dense with no endpoints: for an infinite element $a$, the element $a{+}^{\mathfrak{A}}a$ lies in a strictly larger chain, some $b$ has $b{+}^{\mathfrak{A}}b$ equal to $a$ or its successor and lies in a smaller chain, and between any two chains a similar halving lands a third.²

Despite this richer structure, the theory is decidable.

The proof is again quantifier elimination, but $\text{Th }{\mathfrak{N}}_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 ${\mathfrak{N}}_A$. The fix is to add, for each $k$, a binary predicate ${\equiv }_k$ for congruence modulo $k$, giving the expanded structure

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 }^{\prime }$, and effectively decide whether ${\sigma }^{\prime }$ is true.²

The elimination procedure

Every term reduces to $S^{n_0}0+n_1{x}_1+\cdots +n_k{x}_k$, where $nx$ means $x+\cdots +x$ with $n$ summands. Starting from $\exists y({\beta }_1\wedge \cdots \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(\mathrm{mod}m)$.²

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.³

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\leftrightarrow n+p\in D$ for all $n$, and eventually periodic if this holds for all $n$ past some threshold $M$.

A definable set is defined in ${\mathfrak{N}}_{\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: $n{v}_1+t=u$ and $n{v}_1+t<u$ define finite and cofinite sets (period $1$ eventually), and $n{v}_1+t{\equiv }_{m}u$ defines a genuinely periodic set of period $m$.²

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.²

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.

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.

Carrying that encoding takes the full language and a finite subtheory strong enough for it. The mechanism is representability, the last step before the incompleteness theorems.