[bibtex key=”DoraisHamkins:When-does-every-definable-nonempty-set-have-a-definable-element”]
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:
- $M$ is a model of $\text{ZFC}+\text{V}=\text{HOD}$.
- $M$ thinks there is a definable well-ordering of the universe.
- Every definable nonempty set in $M$ has a definable element.
- Every definable nonempty set in $M$ has an ordinal-definable element.
- Every ordinal-definable nonempty set in $M$ has an ordinal-definable element.
- 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.
- Definable collections without definable members
- Can $V\neq\HOD$, if every $\Sigma_2$-definable set has an ordinal-definable element?
- Is it consistent with ZFC (or ZF) that every definable family of sets has at least one definable member?
- We also make use of the $\Sigma_2$ conception of Local properties in set theory.
It is very good to hear about this paper.
Also, let me point out that the analogue of Theorem 1 (particularly: the equivalence between 2 and 3) fails when ZF is replaced by Z_2 (Second Order Arithmetic); as recently shown by Kanovei & Lyubetsky in the paper: https://arxiv.org/abs/1702.03566. Perhaps their machinery can be extended to KM (Kelley-Morse).
Thanks, as always, for your comments, and for the link. Is the idea to allow second-order definitions in those second-order contexts? It seems that me that one cannot in general define the second-order version of HOD, if one lacks the requisite reflection.
Yes, the idea is indeed to allow second-order definitions.
You are right about the absence of the analogue of HOD in second order arithmetic and Kelley-Morse theory of classes. However, this is not because of the failure of reflection (since both second order arithmetic and Kelley-Morse theory of classes, similar to ZF, exhibit reflection phenomena), but rather it is because of the fact that the objects that “reflect” (i.e., classes), in contradistinction with the rank initial segments of the universe in ZF, are not provably of the order type of the class of ordinals.
On the other hand, there are extensions of second order arithmetic and Kelley-Morse theory of classes that incorporate an axiom that asserts that all classes are constructible (intuitively: V = L holds). These extensions support a global definable well-ordering [and in particular, they verify the statement “every nonempty definable class has a definable member”].
I thought it was an open question whether KM proves reflection, by which I mean the principle that any second-order statement true in the full universe is true in some model that has all the sets but whose classes are coded by a single class. At the very least, one seems to need class choice for this, that is, KM+, but if I recall I think versions of class DC are required to get the necessary closure. Perhaps you mean something else by reflection?
You are right about the necessity of DC; sorry about that, my intended version of Kelley-Morse (when writing my comment) was KM+; which enjoys reflection, but within which we have no analogue of HOD [and the same goes for second order arithmetic; enforced with DC].