Godel numbering

cosmos 8th December 2016 at 8:51pm
Formal system Number theory

An Isomorphism between Formal systems (typographical systems), and Number theory.

CENTRAL PROPOSITION: If there is a typographical rule which tells how certain digits are to be shifted, changed, dropped, or inserted in any number represented decimally, then this rule can be represented equally well by an arithmetical counterpart which involves arithmetical operations with powers of 10 as well as additions, subtractions, and so forth.

More briefly:

Typographical rules for manipulating numerals are actually arithmetical rules for operating on numbers.

This is central to the proof of Godel incompleteness theorems.

See also Godel, Escher, Bach

Producible numbers

Just as any set of typographical rules generates a set of theorems, a corresponding set of natural numbers will be generated by repeated applications of arithmetical rules. These producible numbers play the same role inside number theory as theorems do inside any formal system.