representability in arithmetic


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.


This concept has the prerequisites:


  • 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)


See also

-No Additional Notes-