Mathematical logic and foundations Definition

Gödel numbering

Builds on Well-formed formula Computable function Computable set

Definition

Let $\Sigma$ be a countable alphabet whose symbols are listed effectively, and let $\Sigma^*$ be the set of finite strings over $\Sigma$ . A Gödel numbering of $\Sigma^*$ is a map $\ulcorner \cdot \urcorner \colon \Sigma^* \to \N$ such that:

$\ulcorner \cdot \urcorner$ is injective;
$\ulcorner \cdot \urcorner$ is computable;
the set of codes $\set{\ulcorner w \urcorner : w \in \Sigma^*}$ is a computable set, and the inverse map from codes to strings is computable.

For a formal language, a Gödel numbering of its formulas or proofs is the restriction of a Gödel numbering of its strings of symbols.

Remarks

Example: give the symbols injective codes $c(s) \ge 1$ , and let $p_1 = 2, p_2 = 3, p_3 = 5, \ldots$ be the primes. Set $\ulcorner s_1 s_2 \cdots s_n \urcorner = p_1^{c(s_1)} p_2^{c(s_2)} \cdots p_n^{c(s_n)}$ . By unique factorization the map is injective, and the exponents of a number can be found by trial division, so all three clauses hold.

Non-example: the map that sends each string to its length is computable but fails clause 1, since different strings of the same length get the same number.

The code of a formula $\varphi$ is written $\ulcorner \varphi \urcorner$ , and in a theory of arithmetic its numeral is also written $\ulcorner \varphi \urcorner$ . Any two Gödel numberings are related by a computable bijection between their sets of codes.

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph

Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.

no evidence level

Tag	`7RP93F2W47`
URI	`m2://7RP93F2W47`
Kind	definition
Writing	W0 stub
MSC	03F40
Defines	Gödel numbering
Uses	Well-formed formula, Computable function, Computable set
Changed	2 November 2026

Gödel numbering

Definition

Remarks

Reading path

Further reading

What this page needs for W1

What links here