Pointwise definable models of set theory

  • J. D. Hamkins, D. Linetsky, and J. Reitz, “Pointwise definable models of set theory,” J. Symbolic Logic, vol. 78, iss. 1, pp. 139-156, 2013.  
    @article {HamkinsLinetskyReitz2013:PointwiseDefinableModelsOfSetTheory,
    AUTHOR = {Hamkins, Joel David and Linetsky, David and Reitz, Jonas},
    TITLE = {Pointwise definable models of set theory},
    JOURNAL = {J. Symbolic Logic},
    FJOURNAL = {Journal of Symbolic Logic},
    VOLUME = {78},
    YEAR = {2013},
    NUMBER = {1},
    PAGES = {139--156},
    ISSN = {0022-4812},
    MRCLASS = {03E55},
    MRNUMBER = {3087066},
    MRREVIEWER = {Bernhard A. K{\"o}nig},
    DOI = {10.2178/jsl.7801090},
    URL = {http://jdh.hamkins.org/pointwisedefinablemodelsofsettheory/},
    eprint = "1105.4597",
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    }

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

  • J. D. Hamkins, D. Linetsky, and R. Miller, “The Complexity of Quickly Decidable ORM-Decidable Sets,” in Computation and Logic in the Real World – Third Conference of Computability in Europe CiE 2007, Siena, Italy, 2007, pp. 488-496.  
    @INPROCEEDINGS{HamkinsLinetskyMiller2007:ComplexityOfQuicklyDecidableORMSets,
    AUTHOR = "Joel David Hamkins and David Linetsky and Russell Miller",
    TITLE = "The Complexity of Quickly Decidable {ORM}-Decidable Sets",
    BOOKTITLE = "Computation and Logic in the Real World - Third Conference of Computability in Europe CiE 2007",
    YEAR = "2007",
    editor = "Barry Cooper and Benedikt {L\"owe} and Andrea Sorbi",
    volume = "4497",
    number = "",
    series = "Proceedings, Lecture Notes in Computer Science",
    pages = "488--496",
    address = "Siena, Italy",
    month = "",
    organization = "",
    publisher = "",
    note = "",
    abstract = "",
    keywords = "",
    doi = {10.1007/978-3-540-73001-9_51},
    ee = {http://dx.doi.org/10.1007/978-3-540-73001-9_51},
    bibsource = {DBLP, http://dblp.uni-trier.de},
    file = F
    }

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}$.