A Model-Based Gödel Numbering Scheme

Now for a model-based explanation of the concept of Gödel numbering. The basic idea here is to regiment a scheme for associating a natural number with a first-order formula, and vice versa -- where this association must be completely mechanical. Sometimes this ingenious concept is presented in impenetrable ways, but with help from our simian machines, and simple diagrammatic aids (viz., tables), the concept becomes transparent.⁴

To begin, recall that a particular use of first-order logic is based on the selection of constants, and function and relation symbols. The set S_ar = $\{+, \times, 0, 1, <\}$, central to Gödel I, contains two (binary) function symbols, two constants, and one (binary, or 2-place) relation symbol, respectively. But what about the general case? If we leave aside constants, and we write f_n^m for a the mth n-ary function symbol, and R^m_n for the mth n-ary relation symbol, then all first-order formulas are built by concatenating symbols from this (infinite) table.

$$\begin{array}{cccccccccccc} ( & ) & \wedge & \exists & x_0 &... ... & . & . &\\ & & & & . & . & . & & . & . & . &\\ \end{array}$$

Next, consider this corresponding (infinite) table, which has a structure isomorphic to the one just given.

$$\begin{array}{llllllllllll} 1 & 2 & 3 & 4 & 5 & 6 & 68 & \ld... ... & . & . &\\ & & & & . & . & . & & . & . & . &\\ \end{array}$$

Now, recall our monkey and simian machines; fix again the relevant mental images. It's a trivial matter to have our monkey obtain the Gödel number of a given formula (or to have him work in the opposite direction), using the the two tables. An example should make this clear. Consider the formula

$$\psi = \forall x_0 \exists x_1 R_2^2 x_1 x_0.$$

This formula has a (unique) Gödel number of

49545978899595.

In order to produce this result, visualize our monkey simply matching up the symbols in $\psi$ with their corresponding numbers in the second table, writing these numbers down, and continuing, left to right. Of course, the monkey could also work in the opposite direction: from number to corresponding formula. Finally, some simple notation that will prove crucial below: Where $\phi$ is a formula, let $n^\phi$ denote the Gödel number of $\phi$.