Definable collections without definable members (in ZF)

Question

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

Answer 1

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:

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

Answer 2

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