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

Update. (June, 2017) François Dorais and I have completed a paper growing out of this answer and our others on related posts.

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/).

$\newcommand\ZFC{\text{ZFC}} \newcommand\HOD{\text{HOD}} \newcommand\P{\mathbb{P}} \newcommand\Q{\mathbb{Q}}$

Original answer. It turns out that question 1 has a positive answer, while question 2 has a negative answer.

$\newcommand\ZFC{\text{ZFC}} \newcommand\HOD{\text{HOD}} \newcommand\P{\mathbb{P}} \newcommand\Q{\mathbb{Q}}$

It turns out that question 1 has a positive answer, while question 2 has a negative answer.

Update. (June, 2017) François Dorais and I have completed a paper growing out of this answer and our others on related posts.

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/).

$\newcommand\ZFC{\text{ZFC}} \newcommand\HOD{\text{HOD}} \newcommand\P{\mathbb{P}} \newcommand\Q{\mathbb{Q}}$

Original answer. It turns out that question 1 has a positive answer, while question 2 has a negative answer.

replaced http://mathoverflow.net/ with https://mathoverflow.net/
Source Link

Proof. Let $A$ be the set of minimal-rank non-OD sets. That is, $A$ consists of all non-OD sets of rank $\alpha$, where $\alpha$ is minimal such that there is any non-OD set of rank $\alpha$. In my answer to this related questionmy answer to this related question, I had proved that $A$ is characterized by a $\Sigma_2\wedge\Pi_2$ property.

Proof. Let $A$ be the set of minimal-rank non-OD sets. That is, $A$ consists of all non-OD sets of rank $\alpha$, where $\alpha$ is minimal such that there is any non-OD set of rank $\alpha$. In my answer to this related question, I had proved that $A$ is characterized by a $\Sigma_2\wedge\Pi_2$ property.

Proof. Let $A$ be the set of minimal-rank non-OD sets. That is, $A$ consists of all non-OD sets of rank $\alpha$, where $\alpha$ is minimal such that there is any non-OD set of rank $\alpha$. In my answer to this related question, I had proved that $A$ is characterized by a $\Sigma_2\wedge\Pi_2$ property.

added 4836 characters in body
Source Link
Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k

$\newcommand\ZFC{\text{ZFC}} \newcommand\HOD{\text{HOD}} \newcommand\P{\mathbb{P}} \newcommand\Q{\mathbb{Q}}$

It turns out that question 1 has a positive answer, while question I2 has a negative answer.

The reader may find it useful to know of the characterization of the $\Sigma_2$ properties as the semi-local properties, those which are equivalent to an assertion of the form $\exists\theta\ V_\theta\models\psi$, where $\psi$ can have foundany complexity. In particular, whenever a $\Sigma_2$ property $\varphi(A)$ is true of a set $A$, it is because there is some $V_\theta$ satisfying something about $A$. We may therefore preserve that $\Sigma_2$ fact about $A$, while forcing over $V$, provided that we only force up high and preserve $V_\theta$, the rank-initial-segment of the universe up to $\theta$.

First, let's consider the positive answer to question 1.

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

Proof idea: perform a forcing iteration, considering each $\Sigma_2$ formula in turn, where we try to freeze the set defined by that formula and then code one of its elements (if any) into the GCH pattern high above the witness to that $\Sigma_2$ property. In the end, every nonempty $\Sigma_2$-definable set will contain an ordinal-definable element.

Proof. Start inwith $V$ as a ground model. Without loss, by forcing if necessaryif necessary, we may assume that $V$ satisfies $V=\HOD$, so that there is a definable well-ordering of the universe. Enumerate the $\Sigma_2$ formulas $\varphi_0,\varphi_1,\ldots$, and so on. Note that wethat we may refer to $\Sigma_2$-truth since there is a universal truth predicatetruth predicate for truth of bounded complexity (so there will be no issuesno issues with Tarski's theorem on the non-definability of truth). We defineWe define a full-support forcing iteration $\P$ of length    $\omega$, where the forcing at each stage will become progressively more highly closed. At the first stage stage, we consider the the formula $\varphi_0$. Let $\theta_0$ be any fixed cardinal, and ask: is there a $\leq\theta_0$-closed forcing extension extension $V[g_0]$ in which $\varphi_0$ definesholds of a nonempty set    $A_0$? If so so, we perform such a forcing (choose the least poset forcing forcing thisthis), and let $\lambda_0$ be the smallest $\beth$-fixed point point aboveabove the size of that forcing and $\theta_0$ so that also    $\varphi_0$ is witnessed witnessed in $V_{\lambda_0}^{V[g_0]}$. Next, perform perform additional    $\leq\lambda_0$-closed forcing over $V[g_0]$ to an an extension    $V[g_0][h_0]$, where $h_0$ forces to code one of the elements of $A_0$ into the GCH pattern above $\lambda_0$. This preserves the definition of $A_0$ by $\varphi_0$, while ensuring that $A_0$ has an ordinal definable element. Now, let $\theta_1$ be well above this this coding, and continue.

At stage $n$, we have the partial extension $V^{(n)}=V[g_0][h_0]\cdots[g_{n-1}][h_{n-1}]$, which performed forcing below the cardinal $\theta_n$. We ask whether we can perform perform $\leq\theta_n$-forcing so that $\varphi_n$ definesholds of a nonempty set nonempty set $A_n$ in the extension. If so, we do that forcing, let let $\lambda_n$ be be large enough to witness the $\Sigma_2$ property for for $\varphi_n$, and then perform GCH coding above that so as to make anmake an element of $A_n$ ordinal-definable, and let $\theta_{n+1}$ larger than all that. (Otherwise, we ignore $\varphi_n$ and let $\theta_{n+1}=\theta_n$.)

Consider the corresponding extension $V[G]$, where $G\subset\P$ is $V$-generic, and we use full support in $\P$. Finally, we force to add add a Cohen subset    $H\subset\delta$, where $\delta$ is a regular cardinal cardinal above    $\sup_n\theta_n$, since this will force $V\neq\HOD$ in $V[G][H]$. The The final desired model is $V[G][H]$. Because Because we used full support support, it follows that the tail forcing in    $\P$ after stage $n$ is is $\leq\theta_n$-closed, as is the forcing to to add $H$, and so preserves preserves sets of rank below $\lambda_n$. Thus, if if $\varphi_n$ defines defines a nonempty set in $V[G][H]$, then itat stage $n$ we would have done so in someobserved that it was possible to force it to hold of a nonempty set (with forcing that was sufficiently closed extension of the model at), and so stagewe would have treated it at stage $n$. That is, and we would have forced to add an ordinal-definable elementforced to code one of its elements into the GCH pattern, afterwards always preserving that definition and this coding. So in the case that $\varphi_n$ does define a nonempty set in $V[G][H]$, afterwards preservingthen the definition ofstage $n$ forcing exactly ensured that one of set andthe elements of this set was coded into the GCH pattern of $V[G][H]$ and was therefore ordinal-definable elementthere. The later stages of forcing were arranged so as to preserve all these definitions.

Thus, $V[G][H]$ is a model of $V\neq\HOD$, as the forcing to add $H$ is weakly homogeneous, such that every $\Sigma_2$-definable nonempty set has an ordinal-definable element. QEDQED

The argument reminds me of the forcing iteration proof of the maximality principle, where one forces a given statement to be true, if it is possible to force it in such a way that it remains true in all further forcing extensions. The end result is a model where any statement that could become necessarily true by forcing, is already true, and this is precisely what the maximality principle asserts.

Meanwhile, Emil's ideainsightful suggestion in the comments seems to leadleads to a negative answer tonegative answer to question 2. Perhaps he will post

Theorem 2. If $V\neq\HOD$, then there is a fuller account of itnonempty $\Pi_2$-definable set (orwith no parameters) containing no ordinal-definable element.

Proof. Let $A$ be the set of minimal-rank non-OD sets. That is, $A$ consists of all non-OD sets of rank $\alpha$, where $\alpha$ is minimal such that there is any non-OD set of rank $\alpha$. In my answer to this related question, I can later if he doesn't carehad proved that $A$ is characterized by a $\Sigma_2\wedge\Pi_2$ property.

Emil's idea was to) consider not $A$, but a related set, namely the set $U=A\times V_\theta$, where $\theta$ is the smallest ordinal such that $A\in V_\theta$ and $V_\theta\models A$ is the set of minimal-rank non-OD sets.

The set $U$ is defined by the following property: $U$ consists of the cartesian product $U=A\times B$ of two sets $A$ and $B$ such that the set $B$ has the form $B=V_\theta$ for some ordinal $\theta$ such that $A\in V_\theta$ and $V_\theta\models "A$ is the set of minimal-rank OD sets and there is no $\theta'<\theta$ for which $V_{\theta'}\models A$ is the set of minimal-rank non-OD sets"; and finally, the elements of $A$ really are not in OD.

This property altogether has complexity $\Pi_2$, due mainly to the last clause. The first part, requiring that $U$ has the form $A\times B$, is $\Delta_0$. The next part, asserting that $B$ has the form $B=V_\theta$ for some ordinal $\theta$ has complexity $\Pi_1$, essentially because one need only assert that $B$ is transitive and satisfies some minimal set theory such that it thinks it is a $V_\theta$, and such that $B$ contains all subsets of any of its elements, so that it is using the true power set operation. The properties asserting that $V_\theta$, that is, $B$, satisfies certain complication assertions has complexity $\Delta_0$, since all quantifiers are bounded by $B$ and hence ultimately by $U$. And finally, asserting that the elements of $A$ are really not ordinal-definable has complexity $\Pi_2$, since "$x\in\text{OD}$'' has complexity $\Sigma_2$, as any instance of ordinal-definability reflects to some $V_\theta$ and hence is locally verifiable; thus, the assertion $\forall x\in A\ x\notin\text{OD}$ has complexity $\Pi_2$.

So altogether, the set $U=A\times V_\theta$ is $\Pi_2$-definable, but it can have no ordinal-definable elements, since every element of $U$ has the form $(a,b)$ for some $a\in A, b\in V_\theta$, and if the pair $(a,b)$ were ordinal-definable, then $a$ would be ordinal-definable, contradicting $a\in A$ and the fact that every member of $A$ is not ordinal-definable. QED

Note that the proof is completely uniform, in that the definition of the set does not depend on the model in any way. Rather, we have a $\Pi_2$ definition that $\ZFC+V\neq\HOD$ proves is a nonempty set disjoint from OD.

$\newcommand\ZFC{\text{ZFC}} \newcommand\HOD{\text{HOD}} \newcommand\P{\mathbb{P}} \newcommand\Q{\mathbb{Q}}$ I have found a positive answer to question 1.

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

Proof. Start in $V$ as a ground model. Without loss, by forcing if necessary, we may assume that $V$ satisfies $V=\HOD$, so that there is a definable well-ordering of the universe. Enumerate the $\Sigma_2$ formulas $\varphi_0,\varphi_1,\ldots$. Note that we may refer to $\Sigma_2$-truth since there is a universal truth predicate for truth of bounded complexity (so there will be no issues with Tarski's theorem on the non-definability of truth). We define a forcing iteration $\P$ of length  $\omega$. At the first stage, we consider the formula $\varphi_0$. Let $\theta_0$ be any fixed cardinal, and ask: is there a $\leq\theta_0$-closed forcing extension $V[g_0]$ in which $\varphi_0$ defines a nonempty set  $A_0$? If so, we perform such a forcing (choose the least poset forcing this), and let $\lambda_0$ be the smallest $\beth$-fixed point above the size of that forcing and $\theta_0$ so that also  $\varphi_0$ is witnessed in $V_{\lambda_0}^{V[g_0]}$. Next, perform additional  $\leq\lambda_0$-closed forcing over $V[g_0]$ to an extension  $V[g_0][h_0]$, where $h_0$ forces to code one of the elements of $A_0$ into the GCH pattern above $\lambda_0$. This preserves the definition of $A_0$ by $\varphi_0$, while ensuring that $A_0$ has an ordinal definable element. Now, let $\theta_1$ be well above this coding, and continue.

At stage $n$, we have the partial extension $V^{(n)}=V[g_0][h_0]\cdots[g_{n-1}][h_{n-1}]$, which performed forcing below $\theta_n$. We ask whether we can perform $\leq\theta_n$-forcing so that $\varphi_n$ defines a nonempty set $A_n$ in the extension. If so, we do that forcing, let $\lambda_n$ be large enough to witness the $\Sigma_2$ property for $\varphi_n$, and then perform GCH coding above that so as to make an element of $A_n$ ordinal-definable, and let $\theta_{n+1}$ larger than all that. (Otherwise, we ignore $\varphi_n$ and let $\theta_{n+1}=\theta_n$.)

Consider the corresponding extension $V[G]$, where $G\subset\P$ is $V$-generic, and we use full support in $\P$. Finally, we force to add a Cohen subset  $H\subset\delta$, where $\delta$ is a regular cardinal above  $\sup_n\theta_n$, since this will force $V\neq\HOD$ in $V[G][H]$. The desired model is $V[G][H]$. Because we used full support, it follows that the tail forcing in  $\P$ after stage $n$ is $\leq\theta_n$-closed, as is the forcing to add $H$, and so preserves sets of rank below $\lambda_n$. Thus, if $\varphi_n$ defines a nonempty set in $V[G][H]$, then it would have done so in some sufficiently closed extension of the model at stage $n$, and we would have forced to add an ordinal-definable element to that set, afterwards preserving the definition of that set and of the ordinal-definable element.

Thus, $V[G][H]$ is a model of $V\neq\HOD$, as the forcing to add $H$ is weakly homogeneous, such that every $\Sigma_2$-definable nonempty set has an ordinal-definable element. QED

Meanwhile, Emil's idea in the comments seems to lead to a negative answer to question 2. Perhaps he will post a fuller account of it (or I can later if he doesn't care to).

$\newcommand\ZFC{\text{ZFC}} \newcommand\HOD{\text{HOD}} \newcommand\P{\mathbb{P}} \newcommand\Q{\mathbb{Q}}$

It turns out that question 1 has a positive answer, while question 2 has a negative answer.

The reader may find it useful to know of the characterization of the $\Sigma_2$ properties as the semi-local properties, those which are equivalent to an assertion of the form $\exists\theta\ V_\theta\models\psi$, where $\psi$ can have any complexity. In particular, whenever a $\Sigma_2$ property $\varphi(A)$ is true of a set $A$, it is because there is some $V_\theta$ satisfying something about $A$. We may therefore preserve that $\Sigma_2$ fact about $A$, while forcing over $V$, provided that we only force up high and preserve $V_\theta$, the rank-initial-segment of the universe up to $\theta$.

First, let's consider the positive answer to question 1.

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

Proof idea: perform a forcing iteration, considering each $\Sigma_2$ formula in turn, where we try to freeze the set defined by that formula and then code one of its elements (if any) into the GCH pattern high above the witness to that $\Sigma_2$ property. In the end, every nonempty $\Sigma_2$-definable set will contain an ordinal-definable element.

Proof. Start with $V$ as a ground model. Without loss, by forcing if necessary, we may assume that $V$ satisfies $V=\HOD$, so that there is a definable well-ordering of the universe. Enumerate the $\Sigma_2$ formulas $\varphi_0,\varphi_1,\ldots$, and so on. Note that we may refer to $\Sigma_2$-truth since there is a universal truth predicate for truth of bounded complexity (so there will be no issues with Tarski's theorem on the non-definability of truth). We define a full-support forcing iteration $\P$ of length  $\omega$, where the forcing at each stage will become progressively more highly closed. At the first stage, we consider the formula $\varphi_0$, and ask: is there a forcing extension $V[g_0]$ in which $\varphi_0$ holds of a nonempty set  $A_0$? If so, we perform such a forcing (choose the least poset forcing this), and let $\lambda_0$ be the smallest $\beth$-fixed point above the size of that forcing so that also  $\varphi_0$ is witnessed in $V_{\lambda_0}^{V[g_0]}$. Next, perform additional  $\leq\lambda_0$-closed forcing over $V[g_0]$ to an extension  $V[g_0][h_0]$, where $h_0$ forces to code one of the elements of $A_0$ into the GCH pattern above $\lambda_0$. This preserves the definition of $A_0$ by $\varphi_0$, while ensuring that $A_0$ has an ordinal definable element. Now, let $\theta_1$ be well above this coding, and continue.

At stage $n$, we have the partial extension $V^{(n)}=V[g_0][h_0]\cdots[g_{n-1}][h_{n-1}]$, which performed forcing below the cardinal $\theta_n$. We ask whether we can perform $\leq\theta_n$-forcing so that $\varphi_n$ holds of a nonempty set $A_n$ in the extension. If so, we do that forcing, let $\lambda_n$ be large enough to witness the $\Sigma_2$ property for $\varphi_n$, and then perform GCH coding above that so as to make an element of $A_n$ ordinal-definable, and let $\theta_{n+1}$ larger than all that. (Otherwise, we ignore $\varphi_n$ and let $\theta_{n+1}=\theta_n$.)

Consider the corresponding extension $V[G]$, where $G\subset\P$ is $V$-generic. Finally, we force to add a Cohen subset  $H\subset\delta$, where $\delta$ is a regular cardinal above  $\sup_n\theta_n$, since this will force $V\neq\HOD$ in $V[G][H]$. The final desired model is $V[G][H]$. Because we used full support, it follows that the tail forcing in  $\P$ after stage $n$ is $\leq\theta_n$-closed, as is the forcing to add $H$, and so preserves sets of rank below $\lambda_n$. Thus, if $\varphi_n$ defines a nonempty set in $V[G][H]$, then at stage $n$ we would have observed that it was possible to force it to hold of a nonempty set (with forcing that was sufficiently closed), and so we would have treated it at stage $n$. That is, we would have forced to code one of its elements into the GCH pattern, afterwards always preserving that definition and this coding. So in the case that $\varphi_n$ does define a nonempty set in $V[G][H]$, then the stage $n$ forcing exactly ensured that one of the elements of this set was coded into the GCH pattern of $V[G][H]$ and was therefore ordinal-definable there. The later stages of forcing were arranged so as to preserve all these definitions.

Thus, $V[G][H]$ is a model of $V\neq\HOD$, as the forcing to add $H$ is weakly homogeneous, such that every $\Sigma_2$-definable nonempty set has an ordinal-definable element. QED

The argument reminds me of the forcing iteration proof of the maximality principle, where one forces a given statement to be true, if it is possible to force it in such a way that it remains true in all further forcing extensions. The end result is a model where any statement that could become necessarily true by forcing, is already true, and this is precisely what the maximality principle asserts.

Meanwhile, Emil's insightful suggestion in the comments leads to a negative answer to question 2.

Theorem 2. If $V\neq\HOD$, then there is a nonempty $\Pi_2$-definable set (with no parameters) containing no ordinal-definable element.

Proof. Let $A$ be the set of minimal-rank non-OD sets. That is, $A$ consists of all non-OD sets of rank $\alpha$, where $\alpha$ is minimal such that there is any non-OD set of rank $\alpha$. In my answer to this related question, I had proved that $A$ is characterized by a $\Sigma_2\wedge\Pi_2$ property.

Emil's idea was to consider not $A$, but a related set, namely the set $U=A\times V_\theta$, where $\theta$ is the smallest ordinal such that $A\in V_\theta$ and $V_\theta\models A$ is the set of minimal-rank non-OD sets.

The set $U$ is defined by the following property: $U$ consists of the cartesian product $U=A\times B$ of two sets $A$ and $B$ such that the set $B$ has the form $B=V_\theta$ for some ordinal $\theta$ such that $A\in V_\theta$ and $V_\theta\models "A$ is the set of minimal-rank OD sets and there is no $\theta'<\theta$ for which $V_{\theta'}\models A$ is the set of minimal-rank non-OD sets"; and finally, the elements of $A$ really are not in OD.

This property altogether has complexity $\Pi_2$, due mainly to the last clause. The first part, requiring that $U$ has the form $A\times B$, is $\Delta_0$. The next part, asserting that $B$ has the form $B=V_\theta$ for some ordinal $\theta$ has complexity $\Pi_1$, essentially because one need only assert that $B$ is transitive and satisfies some minimal set theory such that it thinks it is a $V_\theta$, and such that $B$ contains all subsets of any of its elements, so that it is using the true power set operation. The properties asserting that $V_\theta$, that is, $B$, satisfies certain complication assertions has complexity $\Delta_0$, since all quantifiers are bounded by $B$ and hence ultimately by $U$. And finally, asserting that the elements of $A$ are really not ordinal-definable has complexity $\Pi_2$, since "$x\in\text{OD}$'' has complexity $\Sigma_2$, as any instance of ordinal-definability reflects to some $V_\theta$ and hence is locally verifiable; thus, the assertion $\forall x\in A\ x\notin\text{OD}$ has complexity $\Pi_2$.

So altogether, the set $U=A\times V_\theta$ is $\Pi_2$-definable, but it can have no ordinal-definable elements, since every element of $U$ has the form $(a,b)$ for some $a\in A, b\in V_\theta$, and if the pair $(a,b)$ were ordinal-definable, then $a$ would be ordinal-definable, contradicting $a\in A$ and the fact that every member of $A$ is not ordinal-definable. QED

Note that the proof is completely uniform, in that the definition of the set does not depend on the model in any way. Rather, we have a $\Pi_2$ definition that $\ZFC+V\neq\HOD$ proves is a nonempty set disjoint from OD.

Source Link
Joel David Hamkins
  • 236.5k
  • 44
  • 777
  • 1.4k
Loading