example of Gödel numbering
We can define by recursion a function e from formulas of arithmetic to numbers, and the corresponding Gödel numbering as the inverse.
The symbols of the language 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 |