PlanetMath: Gödel numbering

(more info)

Math for the people, by the people.

Main Menu

sections Encyclopædia
Papers
Books
Expositions

meta Requests (232)
Orphanage
Unclass'd
Unproven (519)
Corrections (20)
Classification

talkback Polls
Forums
Feedback
Bug Reports

downloads Snapshots
PM Book

information News
Docs
Wiki
ChangeLog
TODO List
Legalese
About

Gödel numbering

(Definition)

A Gödel numbering is any way off assigning numbers to the formulas of a language. This is often useful in allowing sentences of a language to be self-referential. The number associated with a formula $\phi$ is called its Gödel number and is denoted $\ulcorner\phi\urcorner$ .

More formally, if $\mathcal{L}$ is a language and $\mathcal{G}$ is a surjective partial function from the terms of $\mathcal{L}$ to the formulas over $\mathcal{L}$ then $\mathcal{G}$ is a Gödel numbering. $\ulcorner\phi\urcorner$ may be any term such that $\mathcal{G}(t)=\phi$ . Note that $\mathcal{G}$ is not defined within $\mathcal{L}$ (there is no formula or object of $\mathcal{L}$ representing $\mathcal{G}$ ), however properties of it (such as being in the domain of $\mathcal{G}$ , 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 $\phi$ is a subformula of $\psi$ then $\ulcorner\phi\urcorner<\ulcorner\psi\urcorner$
For every number , there is some $\phi$ such that $\ulcorner\phi\urcorner=n$
$\mathcal{G}$ is injective