Theory R

Origin. Tarski, Mostowski, and Robinson, Undecidable Theories (1953), chapter 2, where R and Q are isolated together as the two minimal base theories for metamathematical arguments. R was the weaker half and was long treated as Q's shadow; Visser's "Why the theory R is special" (in Foundational Adventures, 2012) is where its interpretability class was explained. Cobham proved a minimality result for R (reported in Jones–Shepherdson 1983); Pakhomov, Murwanashyaka, and Visser (2022) settled the question R poses.

Models. Essential undecidability with no finite axiomatization, no induction, and no theorems about variables to speak of. R's axioms are schemas indexed by numerals: they say what the addition and multiplication tables are, that distinct numerals denote distinct things, and that everything below a numeral is one of the numerals below it. That is enough for Gödel's argument and it is strictly less than Q — R does not interpret Q, because R is locally finitely satisfiable and Q is not.

Formalism.

Language: 0, S, +, ×, ≤. Numerals n̄ = Sⁿ(0).

Axioms — five schemas, one instance per numeral or pair of numerals: Ω1. n̄ + m̄ = (n+m)‾ for all n, m ∈ ℕ Ω2. n̄ · m̄ = (n·m)‾ for all n, m ∈ ℕ Ω3. n̄ ≠ m̄ for all n ≠ m Ω4. x ≤ n̄ → (x = 0̄ ∨ x = 1̄ ∨ ⋯ ∨ x = n̄) for each n Ω5. x ≤ n̄ ∨ n̄ ≤ x for each n

Every axiom is about numerals. Ω4 and Ω5 are the only ones with a free variable, and they say only that the numerals below n̄ exhaust the region below n̄ and that n̄ is comparable with everything. R proves nothing general: not S(x) ≠ 0, not S(x) = S(y) → x = y, not that ≤ is transitive.

Essential undecidability (TMR 1953, ch. 2): every consistent extension of R is undecidable. R has the two properties the Gödel–Rosser argument needs — the numerals behave, and Σ₁ facts are provable — and nothing else.

Local finite satisfiability: every finite subtheory of R has a finite model. Take enough of ℤ/k for the finitely many numerals mentioned; Ω1–Ω5 restricted to those numerals hold. Consequence, and the point of the entry: R does not interpret Q. Q is finitely axiomatized and has no finite models, so a theory whose finite subtheories all have finite models cannot interpret it. R is essentially undecidable and strictly below Q in the interpretability order. R is not finitely axiomatizable, and by Cobham's result the schemas are minimal as groups — dropping one destroys essential undecidability.

No minimal theory (Pakhomov–Murwanashyaka–Visser 2022): There is no interpretability-minimal essentially undecidable theory. For every essentially undecidable r.e. theory U there is a class of theories that do not interpret U, whose members realize prescribed recursion-theoretic properties. So neither Q nor R nor anything else is the bottom, and "the weakest theory to which Gödel's argument applies" names no object. The same authors show there is no interpretability-minimal essentially hereditarily undecidable theory either (Visser 2022).

The R-degree: Every r.e. locally finite extension-in-the-same-language of a suitable base is interpretable in R. Mutually interpretable with R: WD (Kristiansen–Murwanashyaka), WT — the weak theory of full binary trees, WTC^{−ε} (Higuchi–Horihata), and WQT* (Damnjanović), a hybrid theory of strings and trees. So R has its own degree with number, string, and tree presentations, exactly as Q does — two degrees, each with three faces. Visser: in a generalized sense, R is the false Σ⁰₁ sentences.

Essential undecidability in weak logics: Q is essentially undecidable over intuitionistic logic; Hájek proved it in the fuzzy logic BL for a relational variant of Q; a relational version of R is essentially undecidable in a substructural logic well below Boolean (Hájek, Švejdar et al. 2020) — the argument survives further down for R than for Q.

Symbols.

Metatheory. R is here to correct a claim that Q invites and that this collection made: that Q is the floor. It is not. R is essentially undecidable, does not interpret Q, and is therefore strictly weaker in the interpretability order while still being subject to Gödel's argument — so the property that makes incompleteness apply does not have Q as its minimum. Pakhomov, Murwanashyaka, and Visser close the question by showing there is no minimum at all: below any essentially undecidable theory there is another that does not interpret it. What R and Q each have is a degree, and the useful statements are about degrees rather than about a bottom. The mechanism separating them is local finite satisfiability: R's finite subtheories have finite models, Q's finite axiomatization forbids that, and this single fact both explains why R cannot interpret Q and why R's interpretability class is as broad as it is.

Applies to. Undecidability by interpretation, where R is the target for theories too weak to admit Q — the standard alternative in the Tarski–Mostowski–Robinson method. The interpretability degree structure on essentially undecidable r.e. theories. Weak logics: the essential undecidability argument for R survives into substructural and fuzzy settings where Q's does not. Locally finite theories generally, whose r.e. extensions land in R's degree.

Limitations. R proves nothing with variables ranging over anything but the numerals it names, so it is not a theory of arithmetic in any working sense — it is a table with two order axioms. Not finitely axiomatizable, which makes it useless for the Church-undecidability argument that Q's finite axiomatization supplies. Its minimality (Cobham) holds for the schemas as groups, not for individual axioms, and the framing depends on the chosen axiomatization: any finitely axiomatizable theory is axiomatizable by one axiom, so minimality claims about axiom counts are claims about presentations.

© 2026 Lingenic LLC