9
$\begingroup$

I consider definability to mean one of either cases:

  1. Definability without parameters (in the language of set theory), or

  2. Definability from ordinals and a real (in the same language).

So my question is: Is there a model $M$ of ZFC (or at least of ZF) such that every definable family of sets (not necessarily of reals) contains at least one definable member (in the sense 1. or 2. respectively) but such that $M$ contains nonetheless many non-definable members (i.e. $M$ is not pointwise definable)?

$\endgroup$

3 Answers 3

16
$\begingroup$

The following theorem seems to express how the various definability witness properties are connected with each other and with $V=\text{HOD}$.

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

Proof. ($1\to 2$) The usual HOD order is a definable well-ordering of the universe.

($2\to 3$) Select the least element with respect to the definable order, as in Bjorn's answer.

($3\to 4$) Immediate.

($4\to 5$) Immediate.

($4\to 1$) If $M$ thinks there is a non-OD set, then the set $A$ of all non-OD sets in $M$ of minimal rank is a definable nonempty set in $M$ with no ordinal-definable elements.

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

($6\to 4$) Immediate. QED

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?.

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.

$\endgroup$
11
  • $\begingroup$ See also this ancient MO post with essentially (eventually) the same idea: mathoverflow.net/a/10415/1946 $\endgroup$ Sep 12, 2014 at 20:36
  • $\begingroup$ I think you can replace 5 by 2: mathoverflow.net/questions/72807/sigma-n-version-of-hod/… $\endgroup$ Sep 13, 2014 at 13:28
  • $\begingroup$ @FrançoisG.Dorais But in that argument, you have an ordinal parameter, whereas here, we want to have no parameters. The question is, how complicated is the definition of the set of minimal-rank non-OD sets, if there are such sets? This cannot be $\Sigma_2$, since we could make those elements definable by coding into the GCH high up, above the witness of the $\Sigma_2$ statement, and this would preserve the $\Sigma_2$ assertion, while destroying that set as consisting of non-OD sets. $\endgroup$ Sep 13, 2014 at 13:37
  • 1
    $\begingroup$ In more detail... There is a (parameter-free) $\Sigma_2$ formula $OD(x)$ which says '$x$ is OD'. The smallest rank $\alpha$ of a non-OD set is $\Sigma_3$-definable by $$\exists U,x(Ord(\alpha) \land U = V_\alpha \land (\forall z \in U)OD(z) \land x \subseteq U \land \lnot OD(x)).$$ So the set of all minimal-rank non-OD sets is $\Sigma_3$-definable. It's actually $\Delta_3$ since the ordinal $\alpha$ is unique. $\endgroup$ Sep 13, 2014 at 14:27
  • 1
    $\begingroup$ I just noticed that the question also asks about allowing reals as parameters, which I didn't really consider in my answer. $\endgroup$ Sep 14, 2014 at 0:53
8
$\begingroup$

Yes, fix a definable relation $\le_L$ that well-orders all of $L$.

If $V=L$ then every definable nonempty set $A$ has a definable member $a$, namely:

$a :=$ the $\le_L$-least element of $A$.

$\endgroup$
5
  • $\begingroup$ Could you give other examples please? $\endgroup$
    – user38200
    Sep 12, 2014 at 18:04
  • 2
    $\begingroup$ The same argument applies if V=HOD. There are no other examples, at least for (a): if every definable family has a definable element, then the collection of definable elements forms an elementary submodel in which every element is definable. This implies the submodel (hence the original model) satisfies V=HOD. $\endgroup$ Sep 12, 2014 at 18:15
  • $\begingroup$ Not every model of $V=L$ or $V=\text{HOD}$ is an example, though, since the OP requested that not every set in the model should be definable. So as Jonas says, one should take a non-pointwise definable model of $V=HOD$, such as any uncountable model of that theory. $\endgroup$ Sep 12, 2014 at 22:04
  • $\begingroup$ @JoelDavidHamkins Right. I guess I was reasoning within $V$. So if $V=L$ then $L$ is uncountable and therefore not pointwise definable. $\endgroup$ Sep 12, 2014 at 22:10
  • 3
    $\begingroup$ I don't think you can reason like that, since if it was legitimate, it would work inside a pointwise definable model of $V=L$. The point is that being "definable" is not generally expressible in set theory, and so one really has to talk about models, rather than $V$ like this. $\endgroup$ Sep 12, 2014 at 22:19
3
$\begingroup$

The answer in case 1. is also yes. In fact, a stronger assertion is true: there exist models of set theory in which every set is definable without parameters. Such models are called pointwise definable, and (as a first observation) are necessarily countable. A collection of results surrounding pointwise definable models of ZFC and GBC (in which every set and every class are definable without parameters) are presented in "Pointwise Definable Models of Set Theory," joint work by Joel Hamkins, David Linesky and me. Here's a link to Joel's blog post on the paper, which gives an overview & link to the paper itself: http://jdh.hamkins.org/pointwisedefinablemodelsofsettheory/

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.