Rosser's trick

Rosser's trick
Name	Rosser's trick
Field	Mathematical logic
Introduced	1936
Introduced by	J. Barkley Rosser
Key contributors	Kurt Gödel, Alonzo Church, Alan Turing, Emil Post
Notable results	Rosser's theorem, Gödel's incompleteness theorems, Church–Turing thesis
Related	Peano arithmetic, Hilbert's program, proof theory, recursion theory

Rosser's trick is a technique in mathematical logic that refines Kurt Gödel's incompleteness method to obtain stronger independence results for formal systems such as Peano arithmetic, Principia Mathematica, and systems axiomatized by recursive axioms. Developed by J. Barkley Rosser in 1936 as a modification of Gödel's approach, the method replaces the reliance on the assumption of ω-consistency with a milder assumption of simple consistency. Rosser's trick influenced subsequent work by Alonzo Church, Alan Turing, Emil Post, and later proof theorists in clarifying the limits of formalization pursued by proponents of David Hilbert's program and related foundational projects.

Background and motivations

Rosser's work arose in the wake of Gödel's 1931 incompleteness theorems, which had been discussed by contemporaries including David Hilbert, John von Neumann, Hilbert and Ackermann, Hermann Weyl, and Kurt Gödel himself. Gödel's original proof used a self-referential sentence constructed via arithmetization and diagonalization and required the hypothesis of ω-consistency to derive undecidability for a sufficiently strong recursively axiomatized theory like Peano arithmetic. Motivations for Rosser's modification included criticisms and analyses by Alonzo Church and attempts to streamline the foundational consequences articulated at venues where scholars such as Norbert Wiener, Emil Post, Alonzo Church, and Alan Turing debated the scope of formal systems. Rosser aimed to show that the stronger ω-consistency assumption could be weakened to ordinary consistency, an issue relevant to discussions involving Hilbert's program and the work of Gerhard Gentzen on consistency proofs.

Statement of Rosser's trick

Rosser's trick produces, for any effectively axiomatized consistent theory T strong enough to represent primitive recursive functions and relations—examples include Peano arithmetic, Zermelo–Fraenkel set theory, and Principia Mathematica—a sentence R_T with the following property: if T is consistent, then neither R_T nor its negation is provable in T. The construction replaces Gödel's self-referential "This sentence is unprovable" with a sentence that informally asserts, "For any proof of me there is a shorter proof of my negation," thereby exploiting a comparison of proof lengths. The result, attributed to J. Barkley Rosser, yields an undecidable sentence under mere consistency rather than ω-consistency, affecting interpretations advanced by David Hilbert and debated by contemporaries such as Alonzo Church and Alan Turing.

Proof outline and construction

The technical core uses arithmetization of syntax, representing proofs, formulas, and the proof predicate inside arithmetic via recursive encodings developed in work by Kurt Gödel, Alonzo Church, and Emil Post. One defines a primitive recursive binary relation Proof_T(p, φ) formalizing "p is a T-proof of φ" and a provability predicate Prov_T(φ) as ∃p Proof_T(p, φ). Rosser's trick introduces a modified provability-like relation, RosserProv_T(φ), that asserts the existence of a proof p of φ with the property that no smaller proof q exists of ¬φ; this uses a primitive recursive ordering on code numbers. Using diagonalization techniques akin to those in Gödel's original construction and methods found in Kurt Gödel's proof, one constructs a sentence R_T that asserts ¬RosserProv_T(R_T). The argument then shows that if T proved R_T then, by the definition of RosserProv_T and the existence of that proof, T would also prove ¬R_T via a shorter proof, contradicting consistency; similarly, if T proved ¬R_T one obtains the converse contradiction. Thus consistency suffices to conclude undecidability.

Consequences for incompleteness and consistency

Rosser's improvement tightened the logical boundary established by Gödel, demonstrating that the first incompleteness theorem holds under the weaker hypothesis of simple consistency rather than ω-consistency, with direct implications for systems considered by David Hilbert's program, Gerhard Gentzen's consistency proofs, and analyses by John von Neumann and Alonzo Church. It reinforced the conclusion that any effectively axiomatizable theory capable of encoding elementary arithmetic cannot be both consistent and complete. The trick influenced subsequent results in recursion theory and proof theory by clarifying which meta-mathematical assumptions are necessary for incompleteness phenomena studied by scholars such as Stephen Kleene, Alfred Tarski, Solomon Feferman, and Wilfrid Hodges.

Variants and generalizations

Several variants of Rosser's idea appear in later work. Proof-theoretic refinements by Gerhard Gentzen and metamathematical adaptations by Solomon Feferman use alternative proof predicates, ordinal analyses, and Feferman-style reflection principles to obtain independence results. In computability theory, related constructions employ priority arguments and self-referential codings used by Emil Post, Alan Turing, and Stephen Kleene to produce nontrivial recursively enumerable degrees and fixed-point theorems. Extensions consider weaker base theories, such as Robinson arithmetic (Q) and fragments explored by Solovay and Jeffrey Paris, and connect to completeness issues in systems studied by Kurt Gödel and Gerhard Gentzen.

Historical context and reception

Rosser's 1936 note was read and evaluated by contemporaries active in foundational debates, including Alonzo Church, Alan Turing, Emil Post, David Hilbert, and John von Neumann, and it quickly became part of the standard logical canon alongside Gödel's work. Philosophers and logicians such as W. V. O. Quine, Hartry Field, Paul Benacerraf, and Hilary Putnam discussed its philosophical implications for formalism and realism. Rosser's trick remains a standard topic in graduate texts on logic, proof theory, and computability, influencing later expositions by Stephen Kleene, Solomon Feferman, George Boolos, and Richard K. Guy.

Category:Mathematical logic