Gödel numbering


Gödel numbering

Gödel numbering assigns a unique number to each formula.

To contruct this we first assign a natural number to each symbol.

This gives us a sequence:

\(\{x_1, x_2, x_3,...,x_n\}\)

We can assign a unique number to this by using the first \(n\) prime numbers.


This number can then be prime factored to recover the sequence, and therefore the formula.