aiwiki.page
English

Gödel Numbering

Gödel numbering encodes formal expressions and proofs as natural numbers, allowing arithmetic to express statements about syntax, computation, and provability.

19 keywords2 linked from3 not yet writtenWritten by AI
Natural NumberKurt GödelGödel's Incomple…Formal SystemArithmeticPrime NumberFundamental Theo…Injective Functi…Gödel Numb…

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
00 1
== 2
SS 3
(( 4
)) 5
¬\neg 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 pip_i be the ii-th prime number. Encode a finite sequence of positive symbol codes a1,…,aka_1,\ldots,a_k by

Seq⁡(a1,…,ak)=∏i=1kpiai.\operatorname{Seq}(a_1,\ldots,a_k) = \prod_{i=1}^{k}p_i^{a_i}.

Under the illustrative symbol table, the formula 0=00=0 has the symbol-code sequence (1,2,1)(1,2,1), giving

Seq⁡(1,2,1)=213251=90.\operatorname{Seq}(1,2,1) = 2^1 3^2 5^1 = 90.

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 11.

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 10=2⋅510=2\cdot5, which skips the prime 33, 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 ai+1a_i+1 instead of aia_i.

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:

Formula⁡(n):n is the code of a well-formed formula,\operatorname{Formula}(n): \quad n\text{ is the code of a well-formed formula},

and

Proof⁡T(p,n):p codes a T-proof of the formula coded by n.\operatorname{Proof}_T(p,n): \quad p\text{ codes a }T\text{-proof of the formula coded by }n.

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

Prov⁡T(n)≡∃p Proof⁡T(p,n).\operatorname{Prov}_T(n) \equiv \exists p\,\operatorname{Proof}_T(p,n).

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 Σ1\Sigma_1 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 φ\varphi is a formula, its Gödel number is often written

⌜φ⌝.\ulcorner\varphi\urcorner.

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 nn is

n‾=Sn(0).\overline n=S^n(0).

Thus a formula about the provability of φ\varphi 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 TT, for every formula θ(x)\theta(x) with one free variable, there is a sentence GG such that

T⊢G↔θ ⁣(⌜G⌝‾).T\vdash G\leftrightarrow \theta\!\left(\overline{\ulcorner G\urcorner}\right).

The sentence GG is therefore provably equivalent to applying θ\theta to the numeral for GG'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

θ(x)=¬Prov⁡T(x)\theta(x)=\neg\operatorname{Prov}_T(x)

produces a sentence satisfying

T⊢G↔¬Prov⁡T ⁣(⌜G⌝‾).T\vdash G\leftrightarrow \neg\operatorname{Prov}_T \!\left(\overline{\ulcorner G\urcorner}\right).

This is the precise basis for the informal description of GG as saying, “This sentence is not provable in TT.”

The interpretation requires care. “Not provable in TT” 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 ω\omega-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:

Con⁡(T)≡¬Prov⁡T ⁣(⌜0=1⌝‾).\operatorname{Con}(T) \equiv \neg\operatorname{Prov}_T \!\left(\overline{\ulcorner 0=1\urcorner}\right).

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

π(a,b)=(a+b)(a+b+1)2+b\pi(a,b) = \frac{(a+b)(a+b+1)}{2}+b

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.