representability in arithmetic
Summary
A relation is definable in a first-order theory T if there is a formula f expressible in the language of T, such that f(x) is provable in T whenever x is in R; otherwise the negation must be provable. It can be shown that the functions representable in arithmetic are exactly those functions which are recursive, or equivalently, computable. The notion of representability is used to construct self-referential sentences in the proof of Godel's Incompleteness Theorem.
Context
This concept has the prerequisites:
- first-order logic (The axioms for arithmetic are typically defined in first-order logic.)
- proofs in first-order logic (Defining representability requires a deductive calculus.)
- functions and relations as sets (Defining representable functions requires viewing functions as relations.)
Goals
- Define a system of axioms for basic arithmetic in first-order logic
- Define what it means for functions and relations to be representable in a logical theory
- Be able to show that simple arithmetic functions are representable in arithmetic (using a suitable set of axioms)
- Show that the set of functions representable in arithmetic is closed under composition
- Show that there is a representable encoding of tuples of numbers into single numbers
Core resources (read/watch one of the following)
-Paid-
→ A Mathematical Introduction to Logic
An undergraduate textbook in mathematical logic, with proofs.
Location:
Section 3.3, "A subtheory of number theory," pages 202-223
See also
-No Additional Notes-