8
$\begingroup$

Does every nonempty definable finite set $S$ have a definable member?

EDIT: Here are a few ways to formalize the question, so you can pick your favorite and answer it. Assume whatever large cardinals you like.

(1) Is it consistent with ZFC that there is an inaccessible cardinal $\delta$ and a nonempty finite set that is first-order definable without parameters over $(V_\delta,\in)$ but has no elements that are first-order definable without parameters over $(V_\delta,\in)$?

(2) Is there any model of ZFC that has a finite nonempty set, first-order definable without parameters over the model, with no element that is first-order definable without parameters over the model?

(3) Is it consistent with ZFC that there is an ordinal-definable finite nonempty set with no ordinal-definable member? (I am aware of the question https://mathoverflow.net/questions/17608/a-question-about-ordinal-definable-real-numbers, but that question asks about sets of real numbers and I already know the answer to my question for sets of real numbers as explained below.

(4) Any of the above formulations with ZFC replaced by ZF.

If a definble set $S$ is contained in a set with a definable linear ordering $\le$, e.g., the usual ordering on $\mathbb{R}$, or more generally the lexicographical ordering on $\mathcal{P}(\kappa)$ for some ordinal $\kappa$, then of course the $\le$-least element of $S$ is definable.

Any nonempty set admits a definable surjection from $\mathcal{P}(\kappa)$ for some ordinal $\kappa$ (just code sets in $H(\kappa)$ by subsets of $\kappa$ in the usual way) but this does not seem to help because I don't know of any definable linear ordering on $\mathcal{P}(\mathcal{P}(\kappa))$.

  • 0
    The question has been answered by François G. Dorais on MO. If he does not post the answer here within a day or so I will copy it over here as a CW answer. Or maybe this question here should be closed as no longer relevant; I don't know what the proper procedure is.2012-09-18

1 Answers 1

5

My answer from MathOverflow:

I believe the answers to these questions are all positive. This kind of problem was discussed by Groszek and Laver in Finite groups of OD-conjugates [Period. Math. Hungar. 18 (1987), 87-97, MR0895774]. Answering a question of Mycielski, they show that there can be two sets of reals $x,y$ such that $\lbrace x,y\rbrace$ is ordinal definable but neither $x$ nor $y$ is ordinal definable. They also prove a lot of other interesting things about OD conjugates.

Here is the brief argument from the intro to that paper. Suppose $u, v$ are two mutually Sacks generic reals over $L$. Both $u$ and $v$ have minimal degree over $L$. Let $x$ and $y$ be the $L$-degrees of $u$ and $v$ respectively. Then $x$ and $y$ satisfy the same formulas with ordinal parameters because Sacks forcing is homogeneous. However, $\lbrace x, y \rbrace$ is definable (without parameters) since these are the only two minimal $L$-degrees in $L[u,v]$.