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 $=$ , $\forall$ , $\neg$ , $\rightarrow$ , $0$ , $S$ , $<$ , $+$ , $\cdot$ , the variables $v_{i}$ 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(v_{i})=\langle 0,i\rangle$
•

$e(\phi=\psi)=\langle 1,e(\phi),e(\psi)\rangle$
•

$e(\forall v_{i}\phi)=\langle 2,e(v_{i}),e(\phi)\rangle$
•

$e(\neg\phi)=\langle 3,e(\phi)\rangle$
•

$e(\phi\rightarrow\psi)=\langle 4,e(\phi),e(\psi)\rangle$
•

$e(0)=\langle 5\rangle$
•

$e(S\phi)=\langle 6,e(\phi)\rangle$
•

$e(\phi<\psi)=\langle 7,e(\phi),e(\psi)\rangle$
•

$e(\phi+\psi)=\langle 8,e(\phi),e(\psi)\rangle$
•

$e(\phi\cdot\psi)=\langle 9,e(\phi),e(\psi)\rangle$

Clearly $e^{-1}$ is a Gödel numbering, with $\ulcorner\phi\urcorner=e(\phi)$ .

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