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

[external website]