example of Gödel numbering

We can define by recursion a function e from formulasMathworldPlanetmathPlanetmath of arithmeticPlanetmathPlanetmath to numbers, and the corresponding Gödel numbering as the inversePlanetmathPlanetmathPlanetmathPlanetmath.

The symbols of the languagePlanetmathPlanetmath of arithmetic are =, , ¬, , 0, S, <, +, , the variables vi for any integer i, and ( and ). ( and ) are only used to define the order of operations, and should be inferred where appropriate in the definition below.

We can define a function e by recursion as follows:

  • e(vi)=0,i

  • e(ϕ=ψ)=1,e(ϕ),e(ψ)

  • e(viϕ)=2,e(vi),e(ϕ)

  • e(¬ϕ)=3,e(ϕ)

  • e(ϕψ)=4,e(ϕ),e(ψ)

  • e(0)=5

  • e(Sϕ)=6,e(ϕ)

  • e(ϕ<ψ)=7,e(ϕ),e(ψ)

  • e(ϕ+ψ)=8,e(ϕ),e(ψ)

  • e(ϕψ)=9,e(ϕ),e(ψ)

Clearly e-1 is a Gödel numbering, with ϕ=e(ϕ).

Title example of Gödel numbering
Canonical name ExampleOfGodelNumbering
Date of creation 2013-03-22 12:58:28
Last modified on 2013-03-22 12:58:28
Owner Henry (455)
Last modified by Henry (455)
Numerical id 7
Author Henry (455)
Entry type Example
Classification msc 03B10