When does every definable nonempty set have a definable element?

  • F. G. Dorais and J. D. Hamkins, “When does every definable nonempty set have a definable element?.” (manuscript under review)  
    @ARTICLE{DoraisHamkins:When-does-every-definable-nonempty-set-have-a-definable-element,
    author = {Fran\c{c}ois G. Dorais and Joel David Hamkins},
    title = {When does every definable nonempty set have a definable element?},
    journal = {},
    year = {},
    volume = {},
    number = {},
    pages = {},
    month = {},
    note = {manuscript under review},
    abstract = {},
    keywords = {},
    source = {},
    doi = {},
    eprint = {1706.07285},
    archivePrefix = {arXiv},
    primaryClass = {math.LO},
    url = {http://jdh.hamkins.org/definable-sets-with-definable-elements},
    }

Abstract. The assertion that every definable set has a definable element is equivalent over ZF to the principle $V=\newcommand\HOD{\text{HOD}}\HOD$, and indeed, we prove, so is the assertion merely that every $\Pi_2$-definable set has an ordinal-definable element. Meanwhile, every model of ZFC has a forcing extension satisfying $V\neq\HOD$ in which every $\Sigma_2$-definable set has an ordinal-definable element. Similar results hold for $\HOD(\mathbb{R})$ and $\HOD(\text{Ord}^\omega)$ and other natural instances of $\HOD(X)$.

It is not difficult to see that the models of ZF set theory in which every definable nonempty set has a definable element are precisely the models of $V=\HOD$. Namely, if $V=\HOD$, then there is a definable well-ordering of the universe, and so the $\HOD$-least element of any definable nonempty set is definable; and conversely, if $V\neq\HOD$, then the set of minimal-rank non-OD sets is definable, but can have no definable element.

In this brief article, we shall identify the limit of this elementary observation in terms of the complexity of the definitions. Specifically, we shall prove that $V=\HOD$ is equivalent to the assertion that every $\Pi_2$-definable nonempty set contains an ordinal-definable element, but that one may not replace $\Pi_2$-definability here by $\Sigma_2$-definability.

Theorem. The following are equivalent in any model $M$ of ZF:

  1. $M$ is a model of $\text{ZFC}+\text{V}=\text{HOD}$.
  2. $M$ thinks there is a definable well-ordering of the universe.
  3. Every definable nonempty set in $M$ has a definable element.
  4. Every definable nonempty set in $M$ has an ordinal-definable element.
  5. Every ordinal-definable nonempty set in $M$ has an ordinal-definable element.
  6. Every $\Pi_2$-definable nonempty set in $M$ has an ordinal-definable element.

Theorem. Every model of ZFC has a forcing extension satisfying $V\neq\HOD$, in which every $\Sigma_2$-definable set has a definable element.

The proof of this latter theorem is reminiscent of several proofs of the maximality principle (see A simple maximality principle), where one undertakes a forcing iteration attempting at each stage to force and then preserve a given $\Sigma_2$ assertion.

This inquiry grew out of a series of questions and answers posted on MathOverflow and the exchange of the authors there.

A brief history of set theory…

A few months ago, Peter Doyle sent me a cryptic email, containing only the following photo and a subject line containing the title of this post.

A brief history of set theory, by François Dorais (photo by Peter Doyle)

I was mystified, until François Dorais subsequently explained that he had given a short presentation on recent progress in foundations for prospective graduate students at Dartmouth.

I’m glad to know that the upcoming generation will have an accurate historical perspective on these things!  🙂