Introduction to Metamathematics

Julia Robinson (Lecture Notes by Stephen J. Garland)

Department of Mathematics, University of California at Berkeley, 1963-1964.

These notes are from Julia Robinson's introductory graduate level course in mathematical logic. In the late 1960s, they were a widely used reference for students preparing for the PhD qualifying examination in logic. Topics include

• the completeness, Skolem-Löwenheim, and Craig interpolation theorems for first-order logic,
• the completeness of various first-order theories, including Presburger arithmetic (shown by elimination of quantifiers), real closed fields (shown by model completeness), and fields of characteristic p (shown by the Łoś-Vaught test),
• weak second order logic,
• hyperarithmetic sets, which are shown to be those that are Herbrand definable and which properly include the arithmetically definable sets (because the satisfaction function for arithmetic is Herbrand definable),
• equivalent definitions of recursive sets (by definability from a finite system of functional equations and by Turing computability),
• primitive recursive and diophantine sets,
• Gödel's incompleteness and second theorems,
• the undecidability of the theory of groups (via the interpretability of R. M. Robinson's essentially hereditarily undecidable theory Q), and
• the exponential diophantine definability of recursively enumerable sets (Davis, Putnam, and Robinson, Annals of Mathematics, 1961) and the existential definable of exponentiation in terms of addition, multiplication, and any infinite set of primes (steps towards the solution of Hilbert's tenth problem).

Back to Publications of Stephen J. Garland