Gödel numbering

A Gödel numbering is any way of assigning numbers to the formulasMathworldPlanetmathPlanetmath of a languagePlanetmathPlanetmath. This is often useful in allowing sentencesMathworldPlanetmath of a language to be self-referential. The number associated with a formula ϕ is called its Gödel number and is denoted ϕ.

More formally, if is a language and 𝒢 is a surjectivePlanetmathPlanetmath partial functionMathworldPlanetmath from the terms of to the formulas over then 𝒢 is a Gödel numbering. ϕ may be any term t such that 𝒢(t)=ϕ. Note that 𝒢 is not defined within (there is no formula or object of representing 𝒢), however properties of it (such as being in the domain of 𝒢, being a subformula, and so on) are.

Athough anything meeting the properties above is a Gödel numbering, depending on the specific language and usage, any of the following properties may also be desired (and can often be found if more effort is put into the numbering):

  • If ϕ is a subformula of ψ then ϕ<ψ

  • For every number n, there is some ϕ such that ϕ=n

  • 𝒢 is injectivePlanetmathPlanetmath

Title Gödel numbering
Canonical name GodelNumbering
Date of creation 2013-03-22 12:58:21
Last modified on 2013-03-22 12:58:21
Owner Henry (455)
Last modified by Henry (455)
Numerical id 8
Author Henry (455)
Entry type Definition
Classification msc 03B10
Related topic BeyondFormalism
Defines Gödel number