Skolem Arithmetic

Origin. Thoralf Skolem, "Über einige Satzfunktionen in der Arithmetik" (1930), claiming decidability for multiplication alone; the first complete proof is Mostowski's "On direct products of theories" (1952), and Feferman and Vaught (1959) generalized the method to arbitrary direct products. The result is the mirror of Presburger's, and the pair is the point.

Models. The naturals with multiplication and nothing else. Unique factorization turns the structure into a direct sum: every positive integer is its exponent vector over the primes, so ⟨ℕ_{>0}, ×⟩ is the weak direct power of ⟨ℕ, +⟩ indexed by primes. Multiplication becomes coordinatewise addition, the Feferman–Vaught machinery reduces the theory to Presburger's, and decidability follows. Nothing here knows what a prime is in order; the order on primes is exactly what cannot be added.

Formalism.

Language: ×, = (the constants 1, and optionally others, may be added without loss of decidability)

Structure: Th(⟨ℕ, ×⟩), the complete theory of the multiplicative naturals.

The isomorphism that does the work: ⟨ℕ_{>0}, ×⟩ ≅ ⊕_{p prime} ⟨ℕ, +⟩ Every n ↦ (v_p(n))_p, the vector of prime valuations, with finite support. Multiplication ↦ pointwise addition. The index set is countably infinite and the theory does not see which prime is which — only how many coordinates behave a given way.

Decidability, by Feferman–Vaught: The truth value of a first-order sentence in a weak direct power reduces effectively to (i) truth values of sentences in the factor — here Presburger arithmetic, decidable; and (ii) a Boolean combination counting how many indices satisfy each factor condition. Both are decidable, so Skolem arithmetic is decidable.

Complexity: Ferrante and Rackoff (1979, ch. 5) give a triply exponential space upper bound for weak direct powers, hence for Skolem arithmetic. Grädel (1989): the satisfiability problem for the quantifier-free fragment is in NP.

What destroys decidability: Adding + gives PA — undecidable. Adding a free unary predicate: Π¹₁-complete (Bès). Adding the order < on all of ℕ: undecidable, since + is then definable. Adding < restricted to primes: still decidable (Bès, Cégielski).

Symbols.

Metatheory. Decidable and complete, by reduction to Presburger arithmetic through the Feferman–Vaught theorem for weak direct powers — a proof that is entirely structural and never touches number theory. With Presburger, Skolem arithmetic settles what makes PA undecidable: neither operation does it alone, since each is decidable in isolation; undecidability is a property of the interaction, and specifically of the fact that + and × together define the graph of exponentiation and hence code sequences. Neither P nor Sk interprets Q, so neither is essentially undecidable, and neither is subject to Gödel's argument. The multiplicative structure is a direct sum whose factor is the additive structure — the same additive theory reappears one level up, which is why the two decidability results are one result.

Applies to. Circuit satisfiability and constraint satisfaction over set expressions with multiplication (Glaßer et al.; Dorfer, Martin et al.), where decidability follows from Skolem arithmetic with constants. Definability results for multiplicative structures. The boundary analysis of undecidable arithmetic. Feferman–Vaught reductions generally — Skolem arithmetic is the standard nontrivial instance.

Limitations. No addition, therefore no arithmetic anyone does: primality is definable but "p is the n-th prime" is not, and no statement about additive relations among primes (Goldbach, twin primes) can even be posed. Triply exponential complexity makes decidability theoretical. The theory is fragile — almost any expansion that reintroduces order across primes collapses it into undecidability. Its interest is comparative: alone it is a curiosity, opposite Presburger it is half of an explanation.

© 2026 Lingenic LLC