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$, $\mathrm{\neg }$, $\to$, $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)=⟨0,i⟩$

• $e(\varphi =\psi )=⟨1,e(\varphi ),e(\psi )⟩$

• $e(\forall v_i\varphi )=⟨2,e(v_i),e(\varphi )⟩$

• $e(\mathrm{\neg }\varphi )=⟨3,e(\varphi )⟩$

• $e(\varphi \to \psi )=⟨4,e(\varphi ),e(\psi )⟩$

• $e(0)=⟨5⟩$

• $e(S\varphi )=⟨6,e(\varphi )⟩$

• $e(\varphi +\psi )=⟨8,e(\varphi ),e(\psi )⟩$

• $e(\varphi \cdot \psi )=⟨9,e(\varphi ),e(\psi )⟩$

Clearly $e^{-1}$ is a Gödel numbering, with $\mathrm{⌜}\varphi \mathrm{⌝}=e(\varphi )$.