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)
→ A Mathematical Introduction to Logic
An undergraduate textbook in mathematical logic, with proofs.
Location: Section 3.4, "Arithmetization of syntax," pages 224-234
- The definition of recursive functions (i.e. those representable in axiomatic number theory) is different from (but equivalent to) the usual one.
Supplemental resources (the following are optional, but you may find them useful)
Location: Article "Godel numbering"
-No Additional Notes-
- create concept: shift + click on graph
- change concept title: shift + click on existing concept
- link together concepts: shift + click drag from one concept to another
- remove concept from graph: click on concept then press delete/backspace
- add associated content to concept: click the small circle that appears on the node when hovering over it
- other actions: use the icons in the upper right corner to optimize the graph placement, preview the graph, or download a json representation