Rosser’s trick in incompleteness proofs

E943475

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

Rosser’s trick in incompleteness proofs is a refinement of Gödel’s incompleteness argument that strengthens the result by avoiding the need for the assumption that the underlying formal system is ω-consistent.

Try in SPARQL Jump to: Statements Referenced by

Statements (44)

Predicate	Object
instanceOf	method in mathematical logic ⓘ proof technique ⓘ refinement of Gödel’s incompleteness argument ⓘ
appearsIn	expositions of incompleteness theorems ⓘ standard textbooks on mathematical logic ⓘ
appliesTo	Peano arithmetic NERFINISHED ⓘ formal arithmetic ⓘ sufficiently strong recursively axiomatized theories ⓘ
assumptionRequired	simple consistency ⓘ
assumptionWeakened	ω-consistency ⓘ
avoids	use of ω-consistency in the incompleteness proof ⓘ
category	self-reference constructions in logic ⓘ techniques in incompleteness proofs ⓘ
consequence	every consistent, effectively axiomatized, sufficiently strong theory is incomplete ⓘ
contrastWith	Gödel’s original use of ω-consistency ⓘ
ensures	existence of a sentence undecidable under mere consistency ⓘ
field	mathematical logic ⓘ metamathematics ⓘ proof theory ⓘ
formalProperty	constructs a sentence undecidable if the theory is consistent ⓘ
historicalContext	developed after Gödel’s 1931 incompleteness theorems ⓘ
influenced	later refinements of incompleteness theorems ⓘ
involves	construction of a Rosser sentence ⓘ formalization of proof length comparisons ⓘ
keyIdea	encode a statement that any proof of the sentence has a shorter proof of its negation ⓘ use of a sentence comparing proofs of itself and its negation ⓘ
logicalFramework	first-order arithmetic ⓘ
modifies	Gödel’s original self-referential sentence construction ⓘ
namedAfter	J. Barkley Rosser NERFINISHED ⓘ
relatedConcept	Gödel sentence NERFINISHED ⓘ Rosser sentence ⓘ
relatedTo	Hilbert’s program NERFINISHED ⓘ limitations of formal systems ⓘ
reliesOn	Gödel numbering NERFINISHED ⓘ arithmetization of syntax ⓘ representability of provability in arithmetic ⓘ
requires	ability to formalize provability predicates ⓘ ability to reason about proofs within the theory ⓘ
strengthens	Gödel’s first incompleteness theorem NERFINISHED ⓘ
typicalAssumptionOnTheory	recursively enumerable axioms GENERATED ⓘ sufficient arithmetic strength to represent primitive recursive functions GENERATED ⓘ
usedFor	avoiding the ω-consistency assumption ⓘ proving incompleteness results ⓘ
usedIn	Rosser’s incompleteness theorem NERFINISHED ⓘ

Referenced by (1)

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

Barkley Rosser → notableConcept → Rosser’s trick in incompleteness proofs ⓘ