Definition
Gödel Numbering
A Gödel numbering is an injection from syntactic objects (e.g. formal language expressions, proofs, or programs) to natural numbers. It assigns a unique code to each object in the syntax.
This is typically achieved by encoding the structure of the object recursively using a pairing function, so that algebraic operations on mirror syntactic operations.
Gödel numberings are central to results that reduce syntactic questions to arithmetic ones, such as countability of formal languages and the undecidability of certain decision problems.