In mathematical logic, a Gödel numbering is a function that assigns to each symbol and well-formed formula of some formal language a unique natural number, called its Gödel number. Kurt Gödel developed the concept for the proof of his incompleteness theorems.

A Gödel numbering can be interpreted as an encoding in which a number is assigned to each symbol of a mathematical notation, after which a sequence of natural numbers can then represent a sequence of symbols. These sequences of natural numbers can again be represented by single natural numbers, facilitating their manipulation in formal theories of arithmetic.

Since the publishing of Gödel's paper in 1931, the term "Gödel numbering" or "Gödel code" has been used to refer to more general assignments of natural numbers to mathematical objects.

Simplified overview

Gödel noted that each statement within a system can be represented by a natural number (its Gödel number). The significance of this was that properties of a statement—such as its truth or falsehood—would be equivalent to determining whether its Gödel number had certain properties. The numbers involved might be very large indeed, but this is not a barrier; all that matters is that such numbers can be constructed.

In simple terms, Gödel devised a method by which every formula or statement that can be formulated in the system gets a unique number, in such a way that formulas and Gödel numbers can be mechanically converted back and forth. There are many ways to do this. A simple example is the way in which English is stored as a sequence of numbers in computers using ASCII. Since ASCII codes are in the range 0 to 127, it is sufficient to pad them to 3 decimal digits and then to concatenate them:

  • The word is represented by .
  • The logical formula is represented by .

Gödel's encoding

{| class=wikitable style="float:right;"

|-

| COLSPAN=8 |

! COLSPAN=4 | number variables

! COLSPAN=3 | property variables

| ...

|-

! Symbol

| 0

| s

| ¬

| ∨

| ∀

| (

| )

| x<sub>1</sub>

| x<sub>2</sub>

| x<sub>3</sub>

| ...

| P<sub>1</sub>

| P<sub>2</sub>

| P<sub>3</sub>

| ...

|-

! Number

| 1

| 3

| 5

| 7

| 9

| 11

| 13

| 17

| 19

| 23

| ...

| 289

| 361

| 529

| ...

|+Gödel's original encoding