Gödel numbering is a method of assigning natural numbers to symbols, expressions, proofs, and other discrete objects so that their structure and manipulation can be studied arithmetically. In its standard logical use, it is an effective, uniquely decodable encoding: syntactic operations correspond to computable operations on numbers. Developed by Kurt Gödel for his 1931 work on the incompleteness theorems, it makes it possible for a formal theory of arithmetic to express statements about formulas and proofs—including statements concerning its own provability.
Purpose and basic idea
A formal system consists of a specified language, axioms, and rules for deriving conclusions. Its formulas and proofs are finite symbolic objects. Ordinarily, statements about those objects belong to a separate level of discourse: saying that a particular sequence is a proof is a statement about the formal system, rather than a statement within its language.
Gödel numbering bridges these levels. Once symbolic objects have numerical codes, a property such as
“This sequence is a valid proof of that formula”
can be translated into a property of natural numbers. A sufficiently expressive theory of arithmetic can then contain formulas expressing such numerical properties.
The essential point is not merely that finite strings can be assigned numbers. It is that the assignment preserves effective access to their structure. There must be algorithms for recognizing codes and performing operations such as extracting symbols, joining strings, and substituting terms into formulas.
A Gödel number has no intrinsic connection to the meaning of the expression it encodes. Different coding conventions generally assign different numbers to the same expression.
A prime-power construction
A standard illustrative construction proceeds in two stages.
Coding individual symbols
Assign each symbol of the formal language a distinct positive integer. For example, part of a symbol table might be:
| Symbol | Code |
|---|---|
| 1 | |
| 2 | |
| 3 | |
| 4 | |
| 5 | |
| 6 |
Additional symbols, including variables, receive further distinct codes. If the language has infinitely many variables, their codes must follow an effective rule.
These assignments are conventional. No particular symbol table is required by the method.
Coding finite sequences
Let be the -th prime number. Encode a finite sequence of positive symbol codes by
Under the illustrative symbol table, the formula has the symbol-code sequence , giving
The fundamental theorem of arithmetic guarantees unique prime factorization, so the exponents recover the original sequence. Requiring positive symbol codes prevents trailing entries from disappearing as zero exponents. The empty sequence can be assigned the code .
Under this convention, not every natural number codes a symbol string. A valid nonempty sequence code must use an initial segment of the primes, with positive exponents that are valid symbol codes. A number such as , which skips the prime , is not such a sequence code.
The same method can encode sequences of formulas and hence candidate proofs. Because formula codes may include zero in other coding conventions, a general sequence encoding can use exponents instead of .
Prime-power coding is transparent but can produce extremely large numbers. Its theoretical usefulness depends on recoverability and effective manipulation, not on numerical compactness.
What makes a numbering suitable?
At its simplest, a numbering is an injective function from a class of syntactic objects into the natural numbers. Injection alone, however, is not sufficient for the usual logical applications. An arbitrary assignment could conceal noncomputable information.
A useful Gödel numbering normally supports effective procedures for:
- recognizing valid symbol, term, and formula codes;
- determining the length and components of a coded sequence;
- constructing compound expressions from their components;
- identifying free and bound variables;
- carrying out substitution, including the necessary treatment of bound variables;
- checking whether a coded sequence is a valid proof.
In standard presentations, these operations and relations are arranged to be primitive recursive, a particularly well-behaved class of computable operations. This provides precise control over their expression in arithmetic.
For a formal theory with an effectively presented proof system, proof verification can be made effective even when theoremhood is not decidable. If the axioms are only computably enumerable, proof objects can include finite certificates recording the enumeration evidence for each nonlogical axiom used. This avoids silently assuming that membership in the axiom set is decidable.
The effectiveness requirements depend on the application. In computability theory, numberings may encode programs, machines, or computably enumerable sets rather than just formulas.
Arithmetization of syntax
The systematic translation of syntactic objects and operations into arithmetic is called arithmetization of syntax.
For a suitably chosen numbering, numerical predicates can express statements such as:
and
Checking a formal proof involves finite structural tests: each line must be an axiom or follow from earlier lines by an allowed rule of inference. With a standard effective presentation, these tests can be expressed arithmetically.
A corresponding provability predicate is defined by
This distinction is fundamental. Checking a proposed formal proof is an effective finite task, whereas deciding whether some proof exists need not be possible. Searching through all candidate proofs will eventually find a proof of a theorem, but may continue forever when the formula is not a theorem.
For standard coding conventions, the provability predicate can be chosen to be a formula: informally, it asserts the existence of a finite numerical certificate whose correctness can be checked by bounded arithmetic conditions.
Codes and numerals
The code of an expression must be distinguished from the expression used to name that code inside arithmetic.
If is a formula, its Gödel number is often written
This notation denotes a natural number in the surrounding mathematical discussion. To refer to that number within a formal theory, one uses its numeral. In a language with zero and successor, the numeral for is
Thus a formula about the provability of formally contains a numeral naming its code. Many presentations suppress this distinction typographically, but it matters when describing how self-reference is constructed.
Diagonalization and self-reference
Gödel numbering enables a controlled form of self-reference through the diagonal lemma. In a sufficiently expressive arithmetic theory , for every formula with one free variable, there is a sentence such that
The sentence is therefore provably equivalent to applying to the numeral for 's own code.
The construction relies on the effective operation of substituting a numeral into a coded formula. It does not require a finite sentence literally to contain its complete written form. Instead, the sentence refers to itself indirectly through arithmetic coding.
Choosing
produces a sentence satisfying
This is the precise basis for the informal description of as saying, “This sentence is not provable in .”
The interpretation requires care. “Not provable in ” is relative to a particular theory, proof predicate, and coding. It is not an unrestricted claim about every possible method of mathematical reasoning.
Role in incompleteness and undefinability
Gödel numbering is an enabling technique, not itself an incompleteness theorem. The incompleteness results additionally require hypotheses about the theory, including effective axiomatizability and enough arithmetic to represent the relevant syntactic operations.
For the usual Gödel sentence, consistency rules out its provability. Establishing that its negation is also unprovable requires an additional assumption in Gödel's original argument, such as -consistency; appropriate soundness assumptions also suffice. Rosser's refinement uses a modified sentence to obtain incompleteness from consistency alone, under the standard effectiveness and arithmetic-strength conditions.
Arithmetized provability also allows a theory to formulate a standard consistency statement:
Under the hypotheses of the second incompleteness theorem, a consistent theory cannot prove this standard formalization of its own consistency. The treatment of the proof predicate and its formal properties is essential to that result.
A related application is Tarski's undefinability theorem. Gödel coding makes it possible to ask whether an arithmetic formula can correctly express truth for every sentence of arithmetic. Diagonalization shows that no such formula defines full arithmetical truth in the standard natural numbers.
This separates two notions:
- Provability in an effectively axiomatized theory can be expressed by an arithmetic formula.
- Truth in the standard natural numbers cannot be defined by an arithmetic formula that correctly covers all arithmetic sentences.
Coding syntax does not eliminate the difference between syntactic derivation and semantic truth.
Alternative encodings and broader uses
Prime-power encoding is only one option. Other constructions use:
- strings in a fixed base, with conventions preserving length;
- pairing functions iterated to encode tuples and finite sequences;
- binary encodings of syntax trees;
- numerical indices for programs or machines.
For example, the Cantor pairing function
assigns a unique natural number to each ordered pair of natural numbers. With suitable tags and length information, pairing can encode nested expressions and finite lists.
Gödel numbering is consequently relevant to proof theory, first-order logic, and the study of algorithms. Encoding programs as numbers permits algorithms to take program descriptions as inputs, supporting results about universal computation and the halting problem. Related encodings are also used in formal verification, although practical systems generally store syntax as strings or structured data rather than enormous prime products.
Limitations and dependence on conventions
There is no single canonical Gödel numbering. Numerical values depend on the alphabet, grammar, sequence encoding, and treatment of variables and proofs. A claim that a particular sentence has a particular Gödel number is meaningful only after those conventions have been fixed.
For conventional effective encodings with computable translations between them, computability and undecidability results do not depend on the particular numbers assigned. Finer properties may depend on the encoding, especially when discussing computational complexity or what a very weak arithmetic theory can prove about coding operations.
Finally, a Gödel number records a symbolic object, not its meaning. An encoding can distinguish valid formulas from malformed strings and valid proofs from invalid derivations when the relevant checks are effective. It does not, merely by assigning numbers, provide a decision procedure for mathematical truth or theoremhood.