Implicit definability in arithmetic

Stephen G. Simpson Department of Mathematics Pennsylvania State University http://www.math.psu.edu/simpson/

November 20, 2013

This is my abstract for an invited seminar talk in the Department of Mathematics at Cornell University, January 27–30, 2014.

We begin with a discussion of implicit and explicit definability in general, mentioning Beth’s Definability Theorem. We then specialize to definability over the ring of integers. (So now we are talking about what recursion theorists call arithmetical singletons versus arithmetical sets.) The main part of the talk consists of three examples. Example 1: a set X which is implicitly definable but not explicitly definable. Namely, X = the Tarski truth set for arithmetic. Example 2: an implicitly definable pair of sets X, Y such that Y by itself is not implicitly definable. Namely, X = the Tarski truth set and Y = a set which is explicitly definable from X and Cohen-generic for arithmetic. Example 3: a pair of sets X, Y such that X is implicitly definable, Y is implicitly definable, X is not explicitly definable from Y, and Y is not explicitly definable from X. This result is due to Leo Harrington.