Rosser trick

E943471

method in mathematical logic proof technique refinement of Gödel’s incompleteness proof

The Rosser trick is a refinement of Gödel’s incompleteness proof that avoids using ω-consistency by constructing a self-referential sentence asserting that a shorter proof of its negation exists.

Try in SPARQL Jump to: Statements Referenced by

Statements (47)

Predicate	Object
instanceOf	method in mathematical logic ⓘ proof technique ⓘ refinement of Gödel’s incompleteness proof ⓘ
appearsIn	expositions of incompleteness theorems ⓘ standard textbooks on mathematical logic ⓘ
appliesTo	formal arithmetic ⓘ recursively axiomatized theories ⓘ sufficiently strong consistent theories ⓘ
assumes	consistency ⓘ
avoidsAssumption	ω-consistency ⓘ
basedOn	Gödel numbering NERFINISHED ⓘ diagonalization ⓘ
constructs	Rosser sentence NERFINISHED ⓘ self-referential sentence ⓘ
differsFrom	Gödel’s original construction by using proof-length comparison ⓘ
ensures	if theory is consistent, Rosser sentence is undecidable ⓘ no proof of the Rosser sentence exists without a shorter proof of its negation ⓘ no proof of the negation exists without a shorter proof of the sentence ⓘ
field	mathematical logic ⓘ metamathematics ⓘ proof theory ⓘ
generalizes	Gödel’s first incompleteness theorem NERFINISHED ⓘ
hasConsequence	even mere consistency implies incompleteness for strong enough theories ⓘ
historicalContext	developed after Gödel’s 1931 incompleteness theorems ⓘ
influenced	later work on provability logic ⓘ refinements of incompleteness theorems ⓘ
involves	coding of finite sequences ⓘ formalization of provability within arithmetic ⓘ partial truth definitions for arithmetic ⓘ primitive recursive relations ⓘ
keyIdea	compare lengths of proofs of a sentence and its negation ⓘ encode proof minimality into the sentence ⓘ sentence asserts existence of a shorter proof of its negation ⓘ
logicalProperty	yields a sentence independent of the theory if the theory is consistent ⓘ
namedAfter	J. Barkley Rosser NERFINISHED ⓘ
namedInHonorOf	J. Barkley Rosser NERFINISHED ⓘ
relatesTo	Gödel sentence NERFINISHED ⓘ
requires	arithmetization of syntax ⓘ effective proof predicate ⓘ
strengthens	hypotheses of Gödel’s original incompleteness proof ⓘ
typicalDomain	first-order arithmetic ⓘ theories extending Robinson arithmetic ⓘ
usedFor	proving incompleteness of Peano arithmetic ⓘ proving incompleteness of stronger arithmetic theories ⓘ removing ω-consistency from incompleteness assumptions ⓘ
usedInProofOf	Rosser’s incompleteness theorem NERFINISHED ⓘ first incompleteness theorem without ω-consistency ⓘ

Referenced by (1)

Full triples — surface form annotated when it differs from this entity's canonical label.

Barkley Rosser → notableWork → Rosser trick ⓘ