Godel numbering


One can define a system ("Godel numbering") for encoding expressions and derivations (in some logical system) as numbers. All the syntactic operations needed to verify derivations are recursive and can be represented in arithmetic. This shows that any logical theory which includes arithmetic is powerful enough to talk about itself. This idea is used to construct self-referential sentences in Godel's Incompleteness Theorem and related results.


This concept has the prerequisites:


  • Define a system for assigning numbers ("Godel numbers") to expressions and derivations in a first-order language
  • Be aware that all the syntactic manipulations needed to verify a proof are representable in arithmetic
  • Work through the details of the above

Core resources (read/watch one of the following)


Supplemental resources (the following are optional, but you may find them useful)


See also

-No Additional Notes-