Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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 http://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))$.

share|improve this question
    
I don't see why non-empty sets should admit a "definable" surjection from $\mathscr{P}(\kappa)$. Can you explain that in more detail, so that it's clearer what you mean by "definable"? –  Zhen Lin Sep 17 '12 at 4:49
    
If the transitive closure $\text{TC}(X)$ of $X$ has size $\le \kappa$, then $(\text{TC}(X);X,\in)$ is the transitive collapse of $(\kappa;A,E)$ for some $A \subset \kappa$ and $E \subset \kappa \times \kappa$. So a large enough $\mathcal{P}(\kappa)$ has elements mapping onto every element $X \in S$ in this way. –  Trevor Wilson Sep 17 '12 at 4:53
    
Hmmm, that's not what I would call definable! Otherwise, I'd argue: a non-empty finite set is in bijection with some finite ordinal, so fixing such a bijection, I can pick the least element. –  Zhen Lin Sep 17 '12 at 4:55
    
The surjection that I gave is most certainly definable by a formula in the language of set theory. Your element is definable from the bijection you fixed, but what if there is no definable such bijection? –  Trevor Wilson Sep 17 '12 at 4:56
2  
I have now posted the question to MO: mathoverflow.net/questions/107441. I hope this is okay. –  Trevor Wilson Sep 18 '12 at 6:34
show 5 more comments

1 Answer

up vote 4 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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