# Definable collections without definable members (in ZF)

Denote Zermelo Fraenkel set theory without choice by ZF. Is the following true: In ZF, every definable non empty class A has a definable member; i.e. for every class $A = \lbrace x : \phi(x)\rbrace$ for which ZF proves "A is non empty", there is a class $a = \lbrace x : \psi(x)\rbrace$ such that ZF proves "a belongs to A"?

• Writing "id est" is really really pedantic. – Harry Gindi Jan 1 '10 at 23:57
• @HarryGindi: Why? – Ramiro de la Vega Mar 12 '15 at 18:57

Update. (June, 2017) François Dorais and I have completed a paper that ultimately grew out of this questions and several follow-up questions.

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.

Click on the history to see the original answer. Related questions and answers appear at:

• I need a class A such that ZF proves "A is non empty" and for every class b, ZF doesn't prove "b is in A". Does the difference V \ OD qualify as such a class A? Similarly can ZF prove that the set of Cohen reals over L is nonempty - I'd confess that I've never seen forcing extensions over a class? Probably I'm missing something but it would be great if you can explicitly write the class A. Thanks a lot – Ashutosh Jan 2 '10 at 0:05
• Well, V-OD might be empty, and it is in the pointwise definable models. But there is a way to get around this difficulty, and I'll edit my answer above to explain it. Similarly, it is consistent that there are no L-generic Cohen reals. – Joel David Hamkins Jan 2 '10 at 0:31
• For ZFC, I know a particularly nice formula for which this fails: A = set of all well orderings of reals. A is non empty but ZFC doesn't prove that A has a definable member. This example, however, depends on axiom of choice. – Ashutosh Jan 2 '10 at 2:16
• I noticed that your argument for ZF + property (A) -> AC gives a nice characterization of the theories that satisfy property (A): If T is any consistent extension of ZF then, T has property (A) iff T proves V = HOD. – Ashutosh Jan 2 '10 at 19:19
• I see! So the property IS first-order expressible (contrary to what I had said in my first bullet point), and is just equivalent to V=HOD. That is, if a model satisfies V=HOD, then there is a definable well-ordering of the universe, so every nonempty definable set will have a definable element (the least one), and conversely, if the model does not have V=HOD, then the set of minimal rank sets not in OD is definable, but has no definable element. – Joel David Hamkins Jan 2 '10 at 19:44

There is a nice model-theoretic interpretation of the property you state, which I will call property (A).

By a theory of sets, I mean any theory $T$ with an extensional relation ${\in}$.

Fact 1. If $T$ is a theory of sets with property (A) then so does every extension of $T$.

Fact 2. If $T$ is a complete theory of sets with property (A) then $T$ has a unique prime model.

Fact 3. If $T$ is a complete theory of sets with a wellfounded prime model then $T$ has property (A).

The fact that ZF does not have property (A) follows from Fact 1 and the (simpler) observation that ZFC does not have property (A). However, Facts 2 and 3 give nice ways of finding extensions of ZF which do have property (A).

Without loss of generality, $T$ has enough closed terms so that if $T$ proves that the formula $\phi(x)$ has a unique solution then $T \vdash \phi(c)$ for some closed term $c$. (Otherwise, add a new constant $c$ for each such formula $\phi(x)$ together with the defining axiom $\phi(c)$. This is a conservative extension of $T$ with the desired property.) If $M$ is any model of $T$, then let $K_M$ be the substructure of $M$ whose ground set consists of all interpretations of the closed terms. Note that $K_M$ is completely determined by the complete theory of $M$.

Observe that if $\theta(z)$ is any formula, then $\psi(x) \equiv \forall z(z \in x \leftrightarrow \theta(z))$ has at most one solution by extensionality. Therefore, $T$ proves that $\phi(x) \equiv \psi(x) \lor (\forall z\lnot\psi(z) \land x = c_0)$ has exactly one solution (where $c_0$ is any fixed closed term). So there is a constant $c$ such that, in any model of $T$, if $\{z : \theta(z)\}$ is a set then $c = \{z:\theta(z)\}$. Of course, we always have $c = \{z:z\in c\}$. So in any model $M$ of $T$ the constants $c$ are precisely all the (parameter-free) instances of comprehension which exist in $M$.

In view of this, property (A) can be formulated as:

(A) For every formula $\phi(x)$, if $T \vdash \exists x\phi(x)$ then $T \vdash \phi(c)$ for some constant $c$.

Replacing $\phi(x)$ with $\phi(x) \lor \forall z\lnot\phi(z)$, we see that property (A) implies the seemingly stronger statement:

(A') For every formula $\phi(x)$ there is a constant $c$ such that $T \vdash \exists x \phi(x) \leftrightarrow \phi(c)$.

This reformulation of property (A) immediately implies Fact 1. By the Tarski-Vaught Test, property (A') says that if $M$ is any model of $T$ then the substructure $K_M$ of $M$ is an elementary submodel of $M$. Therefore, $K_M$ is the necessarily unique prime model of the complete theory of $M$, which establishes Fact 2.

For Fact 3, suppose that $T$ is complete and that $M$ is a wellfounded prime model of $T$. I will show that $M = K_M$, which immediately implies that $T$ has property (A). For the sake of contradiction, suppose that $M \neq K_M$. Since $M$ is wellfounded, there is an $a \in M \setminus K_M$ such that $a \subseteq K_M$. Since $M$ is prime, $a$ realizes a principal type $\phi(x)$. If $b$ also realizes $\phi(x)$, then $b \cap K_M = a$ since all elements of $K_M$ are definable. Therefore, $\phi(x)$ must imply $\forall z(\phi(z) \rightarrow x \subseteq z)$ over $T$. This means that $T$ proves that $\phi(x)$ has a unique solution, which contradicts the fact that $a \notin K_M$.

To partly answer Joel's comment whether wellfoundedness can be eliminated from Fact 3, Ali Enayat [Models of set theory with definable ordinals Arch. Math. Logic 44 (2005), 363-385. MR2140616] has shown that for a completion $T$ of $ZF$ the following three properties are equivalent:

1. $T \vdash V = OD$.
2. $T$ has a unique Paris model up to isomorphism.
3. $T$ has a prime model.

A Paris model is a model where every ordinal is first-order definable. This is slightly weaker than property (A), but it is equivalent when $T \vdash V = OD$.

• This is very nice. – Joel David Hamkins Jan 2 '10 at 14:47
• By the way, I noticed that property (A) implies the Axiom of Choice---see the edit to my answer. A question: Do you need the prime model to be well-founded in (3)? – Joel David Hamkins Jan 2 '10 at 14:49
• I suspect that Fact 3 is false assuming only extensionality and not wellfoundedness. I don't know what happens when one assumes much more than just extensionality, like ZF. – François G. Dorais Jan 2 '10 at 19:40