Gödel numbering

Show Summary Details

Quick Reference

Of a formal system. A one-to-one mapping (i.e. an injection) of the symbols, formulas, and finite sequences of formulas of the formal system onto some subset of the natural numbers. The mapping must be such that there is an algorithm that, for any symbol, formula, or finite sequence of formulas, identifies the corresponding natural number; this is the Gödel number of that object. There must also be an algorithm that, given any natural number, indicates whether it is the Gödel number of the object; if it is, the algorithm must identify the object.

Conferring Gödel numberings has the effect of permitting statements about elements in the nonnumeric system to be transformed into statements about natural numbers. Conversely, since much is known about natural numbers, it becomes possible to prove assertions about aspects of nonnumeric systems. The mapping was first used by the German mathematician Kurt Gödel.

Subjects: Computing.

Reference entries

Users without a subscription are not able to see the full content. Please, subscribe or login to access all content.