Gödel numbers are constructed as follows. First we identify the elements we are to represent, and then we assign a natural number to each one. Finally, we assign a natural number to each possible sequence of the elements; these last numbers are our Gödel numbers.

### Elements

A system P is made up of two main types of elements:

These represent all the

operations that we can perform in the system; more complex operations can be constructed from them, as from

the Peano postulates. (Not all these symbols show up in all

browsers, so I'll explain in words after each usage.)

These are classed as:

### Numbering elements

To number the primitive signs, they are assigned the first 7 odd numbers:

- "0" (zero) = 1
- "succ" (successor) = 3
- "¬" (not) = 5
- "⊦" (logical or) = 7
- "∀" (for all) = 9
- "(" (left parenthesis) = 11
- ")" (right parenthesis) = 13

Each variable of type *n* is uniquely assigned a number of the form *p*^{n} where *p* is a prime greater than 13; each variable of a given type will have a different value of *p*.

This allows us to represent every sequence of basic signs as a sequence of natural numbers.

### Numbering sequences

Finally, given the sequence (*n*_{1}, *n*_{2}, ... *n*_{k}), which can be mapped to a given sequence of signs, we seek to represent this sequence as a single number. We do this by mapping (*n*_{1}, *n*_{2}, ... *n*_{k}) to *2*^{n1}.3^{n2} ... p_{k}^{nk}, where *p*_{k} is the *k*th prime. This product of powers of primes is the Gödel number of the expression.

To obtain the components from a given Gödel number, we need simply to represent it as a product of prime factors and decode in the opposite sequence to the above; there is only one possible prime factorization for any natural number, and hence each Gödel number represents a unique expression.

### Example

The expression "*succ(n)*", where *n* is a variable of type 1, can be expressed by the sequence (1,17), where "*succ*" is represented by 1, and "*n*" is represented by 17 to the power of 1. We convert this to a single number by calculating *2*^{1}.3^{17} = 258280326. This rather large number *258280326* is the Gödel number of "*succ(n)*"; however it is not usually necessary to calculate a Gödel number, but just to know that one can be calculated.

### Reference

Kurt Gödel. "On Formally Undecidable Propositions of Principia Mathematica and Related Systems". [www.research.ibm.com/people/h/hirzel/papers/canon00-goedel.pdf]. 1931. Section 2.2.