Robinson arithmetic

Robinson arithmetic
Name	Robinson arithmetic
Domain	Arithmetical theories
Introduced	1950
Introduced by	Raphael M. Robinson
Main subjects	Mathematical logic, Peano axioms, Gödel's incompleteness theorems

Robinson arithmetic is a finitely axiomatized first-order theory of natural number arithmetic designed to capture a minimal fragment of Peano axioms strong enough for basic arithmetical reasoning yet weak enough to be decidable about certain metamathematical phenomena. It was introduced by Raphael M. Robinson and quickly became central in investigations by figures associated with Kurt Gödel, Alfred Tarski, and Andrey Kolmogorov into incompleteness, undecidability, and model theory. The theory provides a compact setting where results about Gödel's incompleteness theorems, Tarski's undefinability theorem, and Church's thesis can be formulated and shown to hold.

Definition

Robinson arithmetic is defined as a first-order theory in the language of arithmetic with symbols for zero, successor, addition, multiplication, and equality, together with a finite list of quantifier-free axioms. The axioms are chosen to reflect basic algebraic properties of Peano axioms without including the induction schema characteristic of Peano arithmetic. Because of its finite axiomatization and minimal commitments, the theory is frequently used in constructions appearing in the work of Kurt Gödel, Alonzo Church, Emil Post, and Stephen Kleene when demonstrating incompleteness, undecidability, or representability of computable functions.

Language and Axioms

The language of Robinson arithmetic contains constant symbol 0, unary function symbol S (successor), binary function symbols + and ×, and the equality predicate. The axioms assert: Sx ≠ 0; Sx = Sy → x = y; x + 0 = x; x + Sy = S(x + y); x × 0 = 0; x × Sy = x × y + x; and a schema asserting that every nonzero number is a successor of some number. These specific axioms are modeled after the classical list used by Raphael M. Robinson and are sufficient to derive basic facts about numerals and operations that are exploited by later work of Kurt Gödel and Gerald Sacks. The omission of the induction schema distinguishes this language from the full Peano arithmetic language used by Giuseppe Peano and influences metamathematical behavior studied by Morris Kline and Hilbert-inspired programs.

Metamathematical Properties

Robinson arithmetic is recursively axiomatizable and essentially undecidable: any consistent, recursively enumerable extension of it is undecidable, a fact used in arguments by Alonzo Church and Alan Turing concerning decision problems. The theory is Σ1-complete, meaning it proves every true Σ1-arithmetic statement expressible in its language under standard encoding, a property central to proofs of Gödel's incompleteness theorems and exploited in works by Martin Davis and Hilary Putnam. Despite its weakness, Robinson arithmetic can represent all primitive recursive functions, a representability result that figures in the research of Stephen Kleene, Raymond Smullyan, and J.B. Rosser. The lack of induction permits nonstandard models, a phenomenon analyzed using techniques from Model theory developed by Abraham Robinson (not to be confused with Raphael Robinson) and Saharon Shelah.

Models and Interpretations

The standard model of the theory is the usual natural numbers ℕ with zero and successor defined in the classical way; nonstandard models exist by compactness and completeness arguments first systematized in work related to Lowenheim–Skolem theorem and Compactness theorem by contributors such as Jerzy Łoś and Thoralf Skolem. Such nonstandard models may contain infinite descending chains of predecessors and nonstandard integers, phenomena examined in expositions by Wilfrid Hodges and Joel David Hamkins. Model-theoretic constructions permit interpretations of fragments of set theory and fragments of recursive function theory inside models of the theory, techniques used by Dana Scott and Paul Cohen to relate arithmetic to broader logical frameworks. Interpretability relations between this theory and others, including mutual interpretability results with weaker or stronger arithmetical systems, have been investigated by Samuel Buss and Vladimir Sazonov.

Historical Context and Influence

Introduced in a 1950 paper by Raphael M. Robinson, the theory was developed in the milieu of postwar mathematical logic alongside breakthroughs by Kurt Gödel, Alonzo Church, and Alan Turing. Robinson arithmetic became a standard tool in demonstrating the ubiquity of undecidability and incompleteness, influencing later research by Hilary Putnam, Martin Davis, Robert Solovay, and Harvey Friedman. Its role in clarifying which axioms are essential for particular metamathematical consequences shaped subsequent investigations into reverse mathematics conducted by Stephen Simpson and influenced perspectives in the Foundations of mathematics debates involving figures such as Hermann Weyl and L.E.J. Brouwer.

Variants and Extensions

There are several variants and extensions obtained by adding induction schemas, additional function symbols, or axioms to strengthen expressiveness toward Peano arithmetic or weaken toward even more minimal theories studied by Richard Kaye. Fragments such as IΔ0, IΣn, and Robinson-like theories adapted to different signatures are central in proof-theoretic and computational investigations by Pavel Pudlák and Benedikt Löwe. Conservative extensions and interpretability hierarchies relating these variants have been mapped out through work by Frederick Mostowski, Leo Harrington, and Gerald Sacks, informing modern studies in reverse mathematics and the proof-theoretic analysis carried out by William Tait.

Category:Mathematical logic