Knowra Diagonal lemma Diagonal lemma The diagonal lemma states that, for any suitable formula with one free variable, a sentence is provably equivalent to that formula applied to the sentence’s own Gödel number.
Gödel numbering : A method that assigns natural numbers to symbols, formulas, and proofs in a formal language. It turns formulas into numbers that arithmetic formulas can mention.
Gödel's incompleteness theorems : Theorems showing that sufficiently expressive consistent formal theories contain statements they cannot decide or prove. The first incompleteness theorem uses the diagonal lemma to build an undecidable sentence.
First-order logic : A formal logic with variables, predicates, quantifiers, and rules for deriving conclusions. The lemma is stated for formulas and sentences in a formal language.
Cantor's diagonal argument : A proof method that constructs an object differing from each listed object at a selected position. It shares the diagonal name but proves non-enumerability rather than formal self-reference.
Substitution function : A function that maps a formula's code and a term's code to the code of the formula obtained by substitution. Its arithmetical representation performs the self-substitution used in the construction.
Löb's theorem : A theorem stating that if a formal theory proves that a sentence is provable, then it proves the sentence itself, under standard derivability conditions. Its proof uses diagonalization to construct a sentence linked to its own provability.
Peano arithmetic : A formal theory of natural numbers based on axioms for zero, successor, addition, and multiplication. It can formalize the coding operations needed for the standard arithmetic form of the lemma.
Kleene recursion theorem : A theorem in computability theory guaranteeing programs that can access their own descriptions through an effective transformation. It gives a program-level fixed-point result closely related to syntactic diagonalization.
Representability in arithmetic : The property that a relation or function on natural numbers can be expressed by a formula in an arithmetic theory. The construction relies on arithmetic formulas representing coding and substitution operations.
Gödel–Rosser sentence : A self-referential sentence used in Rosser's refinement of Gödel's first incompleteness theorem. The lemma supplies the sentence whose provability and unprovability conditions drive Rosser's argument.
Show all 21