# 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 ExampleOfGodelNumbering 2013-03-22 12:58:28 2013-03-22 12:58:28 Henry (455) Henry (455) 7 Henry (455) Example msc 03B10