Skip to main content
Gave reference to the paper
Source Link
Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k

Update. This answer and those of the related questions have known grown into the following paper:

F. G. Dorais and J. D. Hamkins, When does every definable nonempty set have a definable element? (arχiv:1706.07285)

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)$.
Read more [at the blog post](http://jdh.hamkins.org/when-does-every-definable-nonempty-set-have-a-definable-element/).

Update. This answer and those of the related questions have known grown into the following paper:

F. G. Dorais and J. D. Hamkins, When does every definable nonempty set have a definable element? (arχiv:1706.07285)

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)$.
Read more [at the blog post](http://jdh.hamkins.org/when-does-every-definable-nonempty-set-have-a-definable-element/).
replaced http://mathoverflow.net/ with https://mathoverflow.net/
Source Link

Meanwhile, over at my question Can $V\neq\text{HOD}$ if every $\Sigma_2$-definable set has an ordinal-definable element?Can $V\neq\text{HOD}$ if every $\Sigma_2$-definable set has an ordinal-definable element?, Emil made a suggestion leading to the observation that if $V\neq\text{HOD}$, then there is a $\Pi_2$-definable set with no ordinal-definable elements. The set is simply $U=A\times V_\theta$, where $A$ is as above and $\theta$ is least such that $V_\theta$ thinks $A$ is the set of minimal-rank non-OD sets. So I refer the reader to theorem 2 in that answer, which provides the content of the implication ($5\to 1$).

Update. I edited to the improved statement 5, which we've now got down to the case of mere $\Pi_2$-definability, using the answer to my question Can $V\neq\text{HOD}$ if every $\Sigma_2$-definable set has an ordinal-definable element?Can $V\neq\text{HOD}$ if every $\Sigma_2$-definable set has an ordinal-definable element?.

Meanwhile, over at my question Can $V\neq\text{HOD}$ if every $\Sigma_2$-definable set has an ordinal-definable element?, Emil made a suggestion leading to the observation that if $V\neq\text{HOD}$, then there is a $\Pi_2$-definable set with no ordinal-definable elements. The set is simply $U=A\times V_\theta$, where $A$ is as above and $\theta$ is least such that $V_\theta$ thinks $A$ is the set of minimal-rank non-OD sets. So I refer the reader to theorem 2 in that answer, which provides the content of the implication ($5\to 1$).

Update. I edited to the improved statement 5, which we've now got down to the case of mere $\Pi_2$-definability, using the answer to my question Can $V\neq\text{HOD}$ if every $\Sigma_2$-definable set has an ordinal-definable element?.

Meanwhile, over at my question Can $V\neq\text{HOD}$ if every $\Sigma_2$-definable set has an ordinal-definable element?, Emil made a suggestion leading to the observation that if $V\neq\text{HOD}$, then there is a $\Pi_2$-definable set with no ordinal-definable elements. The set is simply $U=A\times V_\theta$, where $A$ is as above and $\theta$ is least such that $V_\theta$ thinks $A$ is the set of minimal-rank non-OD sets. So I refer the reader to theorem 2 in that answer, which provides the content of the implication ($5\to 1$).

Update. I edited to the improved statement 5, which we've now got down to the case of mere $\Pi_2$-definability, using the answer to my question Can $V\neq\text{HOD}$ if every $\Sigma_2$-definable set has an ordinal-definable element?.

added 782 characters in body
Source Link
Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k
  1. $M$ is a model of $\text{ZFC}+\text{V}=\text{HOD}$.

  2. $M$ has 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 $(\Sigma_2\wedge\Pi_2)$$\Pi_2$-definable nonempty set in $M$ has an an ordinalordinal-definable element.

  6. Every ordinal-definable nonempty set in $M$ has an ordinal-definable element.

($5\to 1$) For theThe stronger implication — thanks to Françoishas now undergone a few in the comments! — we analyze the complexity of theimprovements, so let me discuss it. I had proposed considering as definition ofabove the set $A$ in the previous case. The main observationof all minimal-rank non-OD sets, which is that $x\in\text{OD}$ isdefinable and nonempty in any model of $\Sigma_2$$V\neq\text{HOD}$, as every instance ofbut has definability is witnessed by reflection inside some $V_\theta$no ordinal-definable elements. I had guessed that $\Sigma_5$ would be Thesufficient to define $\Sigma_2$ assertions are precisely$A$. In the semi-local propertiescomments, thoseFrançois refined this, arguing that can bethis set was actually verified in some rank initial segment of the universe$\Sigma_3$-definable and indeed $V_\theta$$\Delta_3$-definable.

If $V\neq\text{HOD}$ Using his idea, then the setI was able to push this down to show that $A$ of minimal-rank non-OD setsis is characterized$\Sigma_2\wedge\Pi_2$ definable, by the following properties: $A$ is not empty; allempty; all elements of $A$ have the same rank; every element of    $A$ is not not in OD; every set of rank less than an element of $A$ is in OD; everyin OD; every set not in $A$, but of the same rank as an element of    $A$, is is in OD. Each of these properties is either $\Sigma_2$ or $\Pi_2$, making the set $A$ to be $\Sigma_2\wedge\Pi_2$-definable. Specifically, the first two requirements are $\Sigma_2$, being witnessed in a rank-initial segment of the universe; the third is $\Pi_2$; the fourth and fifth are both $\Sigma_2$, since they are true just in case there is a large $V_\theta$ which believes them to be true. Thus, the definition ofI also noted that $A$ has complexity $\Sigma_2\wedge\Pi_2$is not provably $\Sigma_2$-definable.

Meanwhile, which allowsover at my question Can $V\neq\text{HOD}$ if every $\Sigma_2$-definable set has an ordinal-definable element?, Emil made a suggestion leading to the implicationobservation that if ($5\to 1$)$V\neq\text{HOD}$, then there sinceis a $A$ has$\Pi_2$-definable set with no ordinal-definable memberselements. The set is simply $U=A\times V_\theta$, where $A$ is as above and $\theta$ is least such that $V_\theta$ thinks $A$ is the set of minimal-rank non-OD sets. So I refer the reader to theorem 2 in that answer, which provides the content of the implication ($5\to 1$).

($1\to 6$) Immediate, since under statement $1$, every set in $M$ is ordinalis ordinal-definable in $M$.

Conclusion. Thus Thus, case (1) of the question occurs in exactly the the models of    $V=\text{HOD}$ that are not pointwise definable. There There are such models models, if ZFC is consistent, since one may take any uncountable modelany uncountable model of $\text{ZFC}+V=\text{HOD}$.

Meanwhile, case (2) of the question — ignoring the issue of real parameters — does not occur at all, since if if a set has sets sets that are not ordinal-definable, then it will have have a definable set set with no ordinal-definable members, namely, the the set of all non non-OD sets of minimal rank, as in the implication of of statement 4 to to statement 1.

Update. I edited to the improved statement 5, which we've now got down to the case of mere $\Pi_2$-definability, using the answer to my question Can $V\neq\text{HOD}$ if every $\Sigma_2$-definable set has an ordinal-definable element?.

  1. $M$ is a model of $\text{ZFC}+\text{V}=\text{HOD}$.

  2. $M$ has 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 $(\Sigma_2\wedge\Pi_2)$-definable nonempty set in $M$ has an ordinal-definable element.

  6. Every ordinal-definable nonempty set in $M$ has an ordinal-definable element.

($5\to 1$) For the stronger implication — thanks to François in the comments! — we analyze the complexity of the definition of $A$ in the previous case. The main observation is that $x\in\text{OD}$ is $\Sigma_2$, as every instance of definability is witnessed by reflection inside some $V_\theta$. The $\Sigma_2$ assertions are precisely the semi-local properties, those that can be verified in some rank initial segment of the universe $V_\theta$.

If $V\neq\text{HOD}$, then the set $A$ of minimal-rank non-OD sets is characterized by the following properties: $A$ is not empty; all elements of $A$ have the same rank; every element of  $A$ is not in OD; every set of rank less than an element of $A$ is in OD; every set not in $A$, but of the same rank as an element of  $A$, is in OD. Each of these properties is either $\Sigma_2$ or $\Pi_2$, making the set $A$ to be $\Sigma_2\wedge\Pi_2$-definable. Specifically, the first two requirements are $\Sigma_2$, being witnessed in a rank-initial segment of the universe; the third is $\Pi_2$; the fourth and fifth are both $\Sigma_2$, since they are true just in case there is a large $V_\theta$ which believes them to be true. Thus, the definition of $A$ has complexity $\Sigma_2\wedge\Pi_2$, which allows the implication ($5\to 1$), since $A$ has no ordinal-definable members.

($1\to 6$) Immediate, since under statement $1$, every set in $M$ is ordinal-definable in $M$.

Conclusion. Thus, case (1) of the question occurs in exactly the models of  $V=\text{HOD}$ that are not pointwise definable. There are such models, if ZFC is consistent, since one may take any uncountable model of $\text{ZFC}+V=\text{HOD}$.

Meanwhile, case (2) of the question does not occur at all, since if a set has sets that are not ordinal-definable, then it will have a definable set with no ordinal-definable members, namely, the set of all non-OD sets of minimal rank, as in the implication of statement 4 to statement 1.

  1. $M$ is a model of $\text{ZFC}+\text{V}=\text{HOD}$.

  2. $M$ has 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 $\Pi_2$-definable nonempty set in $M$ has an ordinal-definable element.

  6. Every ordinal-definable nonempty set in $M$ has an ordinal-definable element.

($5\to 1$) The stronger implication has now undergone a few improvements, so let me discuss it. I had proposed considering as above the set $A$ of all minimal-rank non-OD sets, which is definable and nonempty in any model of $V\neq\text{HOD}$, but has no ordinal-definable elements. I had guessed that $\Sigma_5$ would be sufficient to define $A$. In the comments, François refined this, arguing that this set was actually $\Sigma_3$-definable and indeed $\Delta_3$-definable. Using his idea, I was able to push this down to show that $A$ is $\Sigma_2\wedge\Pi_2$ definable, by the properties: $A$ is not empty; all elements of $A$ have the same rank; every element of  $A$ is not in OD; every set of rank less than an element of $A$ is in OD; every set not in $A$, but of the same rank as an element of  $A$, is in OD. Each of these properties is either $\Sigma_2$ or $\Pi_2$, making the set $A$ to be $\Sigma_2\wedge\Pi_2$-definable. Specifically, the first two requirements are $\Sigma_2$, being witnessed in a rank-initial segment of the universe; the third is $\Pi_2$; the fourth and fifth are both $\Sigma_2$, since they are true just in case there is a large $V_\theta$ which believes them to be true. I also noted that $A$ is not provably $\Sigma_2$-definable.

Meanwhile, over at my question Can $V\neq\text{HOD}$ if every $\Sigma_2$-definable set has an ordinal-definable element?, Emil made a suggestion leading to the observation that if $V\neq\text{HOD}$, then there is a $\Pi_2$-definable set with no ordinal-definable elements. The set is simply $U=A\times V_\theta$, where $A$ is as above and $\theta$ is least such that $V_\theta$ thinks $A$ is the set of minimal-rank non-OD sets. So I refer the reader to theorem 2 in that answer, which provides the content of the implication ($5\to 1$).

($1\to 6$) Immediate, since under statement $1$, every set in $M$ is ordinal-definable in $M$.

Conclusion. Thus, case (1) of the question occurs in exactly the models of  $V=\text{HOD}$ that are not pointwise definable. There are such models, if ZFC is consistent, since one may take any uncountable model of $\text{ZFC}+V=\text{HOD}$.

Meanwhile, case (2) of the question — ignoring the issue of real parameters — does not occur at all, since if a set has sets that are not ordinal-definable, then it will have a definable set with no ordinal-definable members, namely, the set of all non-OD sets of minimal rank, as in the implication of statement 4 to statement 1.

Update. I edited to the improved statement 5, which we've now got down to the case of mere $\Pi_2$-definability, using the answer to my question Can $V\neq\text{HOD}$ if every $\Sigma_2$-definable set has an ordinal-definable element?.

added 1212 characters in body
Source Link
Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k
Loading
added 976 characters in body
Source Link
Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k
Loading
added 440 characters in body
Source Link
Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k
Loading
Source Link
Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k
Loading