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)$ .