Definition
Gödel Numbering
A Gödel numbering is an injective encoding of syntactic objects—such as language expressions, proofs or programs—as natural numbers. For a set
of such objects, The number
is the Gödel number of . In computability settings, encoding and decoding valid codes are also required to be computable. No particular encoding scheme is required; pairing functions are one possible construction.
Arithmetic represents syntax
Numbering makes syntactic objects available to arithmetic. With an effective encoding, operations and decision problems about syntax become operations and questions about numerical codes, enabling undecidability arguments. An injective encoding also shows that