Pointwise definable models of set theory

[bibtex key=HamkinsLinetskyReitz2013:PointwiseDefinableModelsOfSetTheory]

One occasionally hears the argument—let us call it the math-tea argument, for perhaps it is heard at a good math tea—that there must be real numbers that we cannot describe or define, because there are are only countably many definitions, but uncountably many reals.  Does it withstand scrutiny?

This article provides an answer.  The article has a dual nature, with the first part aimed at a more general audience, and the second part providing a proof of the main theorem:  every countable model of set theory has an extension in which every set and class is definable without parameters.  The existence of these models therefore exhibit the difficulties in formalizing the math tea argument, and show that robust violations of the math tea argument can occur in virtually any set-theoretic context.

A pointwise definable model is one in which every object is definable without parameters. In a model of set theory, this property strengthens V=HOD, but is not first-order expressible. Nevertheless, if ZFC is consistent, then there are continuum many pointwise definable models of ZFC. If there is a transitive model of ZFC, then there are continuum many pointwise definable transitive models of ZFC. What is more, every countable model of ZFC has a class forcing extension that is pointwise definable. Indeed, for the main contribution of this article, every countable model of Godel-Bernays set theory has a pointwise definable extension, in which every set and class is first-order definable without parameters.

The complexity of quickly decidable ORM-decidable sets

[bibtex key=HamkinsLinetskyMiller2007:ComplexityOfQuicklyDecidableORMSets]

The Ordinal Register Machine (ORM) is one of several different machine models for infinitary computability. We classify, by complexity, the sets that can be decided quickly by ORMs. In particular, we show that the arithmetical sets are exactly those sets that can be decided by ORMs in times uniformly less than $\omega^\omega$. Further, we show that the hyperarithmetical sets are exactly those sets that can be decided by an ORM in time uniformly less than $\omega_1^{CK}$.