arithmetization of syntax
E446861
Arithmetization of syntax is a method in mathematical logic that encodes formal language expressions and proofs as natural numbers so that syntactic properties can be studied using arithmetic.
Statements (49)
| Predicate | Object |
|---|---|
| instanceOf |
method in mathematical logic
ⓘ
technique in proof theory ⓘ |
| aimsTo |
represent syntactic objects as numbers
ⓘ
study syntax using arithmetic ⓘ |
| allowsDefinitionOf |
Prov_T(x) as a provability predicate for a theory T
ⓘ
formula(x) as an arithmetical predicate ⓘ proof(x,y) as an arithmetical predicate ⓘ |
| appliesTo |
Peano arithmetic
NERFINISHED
ⓘ
first-order arithmetic ⓘ formal theories of arithmetic strong enough to represent computable functions ⓘ |
| associatedWith |
Gödel's incompleteness theorems
NERFINISHED
ⓘ
Kurt Gödel NERFINISHED ⓘ |
| characterizedBy |
effectiveness of the coding scheme
ⓘ
faithfulness to syntactic structure ⓘ use of primitive recursive relations to capture syntactic notions ⓘ |
| enables |
construction of self-referential sentences
ⓘ
definition of provability predicates ⓘ expression of syntactic predicates as arithmetical predicates ⓘ formalization of consistency statements ⓘ formalization of metamathematics inside arithmetic ⓘ proof of incompleteness theorems ⓘ |
| encodes |
derivations in formal calculi
ⓘ
formal language expressions ⓘ formulas of formal theories ⓘ proofs in formal systems ⓘ |
| field |
mathematical logic
ⓘ
proof theory ⓘ recursion theory ⓘ |
| historicalPeriod | 20th century ⓘ |
| relatedConcept |
Gödel coding
ⓘ
Hilbert's program NERFINISHED ⓘ Löb's theorem NERFINISHED ⓘ diagonal lemma ⓘ formal provability logic ⓘ metamathematics ⓘ representability of recursive functions ⓘ self-reference in arithmetic ⓘ |
| represents |
finite strings by natural numbers
ⓘ
proof relations by arithmetical relations ⓘ symbols by natural numbers ⓘ |
| requires |
effective coding of finite sequences
ⓘ
primitive recursive functions ⓘ |
| studies | syntactic properties via arithmetic properties of numbers ⓘ |
| usedIn |
analysis of consistency and ω-consistency
ⓘ
construction of Rosser sentences ⓘ formalization of completeness and incompleteness proofs ⓘ proofs of undefinability results ⓘ |
| uses |
Gödel numbering
NERFINISHED
ⓘ
natural numbers ⓘ |
Referenced by (1)
Full triples — surface form annotated when it differs from this entity's canonical label.