MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

This was inspired by this recent question.

In my answer there, I pointed out that, given $F:{\mathcal P}(X)\to X$, an argument dating back to Zermelo allows us to define a pair $(A,B)$ of distinct subsets of $X$ witnessing that $F$ is not injective. The pair is defined in terms of a well-ordering that is constructed using $F$.

Of course, the usual Cantor argument also shows that $F$ is not injective: One considers $$ A=\{F(Z)\mid F(Z)\notin Z\},$$ and argues that there must be a $B$ with $A\ne B$ and $F(A)=F(B)$.

My question is:

Can we exhibit such a set $B$ (definably from $F$)?

share|cite|improve this question
A small comment: If the answer is positive, I expect it will be an explicit construction, and that's what I'm hoping for. It also explains the "combinatorics" tag. If the answer is negative, though, perhaps the tag was misplaced after all. I apologize for the possible inaccuracy. – Andrés E. Caicedo Nov 26 '10 at 20:41
One thing that makes me pessimistic about this problem is that it is easy to construct (non-injective) examples where the solution B is unique. Contrary to the usual Cantor proof of non-surjectivity where there is a plethora of solutions, which allows a "gross", "greedy" diagonalization construction to work, whatever "definable" construction we find must be sharp in many cases. – Ewan Delanoy Nov 27 '10 at 14:32
@Ewan: If $B$ is unique, it is obviously definable, so the issue is really when this is not the case. Note I am not requiring $B$ to be first order definable on $({\mathcal P}(X)\sqcup X,\subseteq, F)$, simply to be definable from $F$ in the language of set theory; this is a much more generous notion of definability. – Andrés E. Caicedo Nov 27 '10 at 19:25
Just a question: Clearly the restriction of $F$ to $A$ maps $F: {\cal P}(A) \to A$ so we could take $$A'=\lbrace F(Z) | Z\subseteq A, F(Z) \not\in Z\rbrace.$$ Can one define the limit of this process? That is, some $Y \subseteq X$ so that $F: {\cal P}(Y) \to Y$ and $$Y=\lbrace F(Z) | Z\subseteq Y, F(Z) \not\in Z\rbrace?$$ – Aaron Meyerowitz Nov 28 '10 at 17:06
@ Aaron : more generally, call a subset $X'$ of $X$ stable if F maps ${\cal P}(X')$ to $X'$ (thus $X$ and $A$ are stable). Then the operation $\Phi(X')=\lbrace F(Z) | Z \subseteq X, F(Z) \not\in Z \rbrace $ preserves stable sets : $\Phi(X')$ stays stable if $X'$ is. Also, any intersection of stable sets is again stable, so we may consider for exemple the smallest stable set containing $F(A)$. However, if you want to use some limiting process you need Zorn's lemma and AC somewhere (my answer proves this). – Ewan Delanoy Nov 28 '10 at 17:32
up vote 10 down vote accepted

If I understood the OP correctly, the problem can be stated as follows :

Problem 1. Let $X$ be a set, let $F:{\cal P}(X) \to X$, and let $A$ be defined as above: $$A=\lbrace F(Z) | Z\subseteq X, F(Z) \not\in Z\rbrace.$$ Find a definable $B$ (in terms of $F$) such that $B \neq A$ and $F(B)=F(A)$.

Now Problem 1 is equivalent to the simpler problem :

Problem 2. Let $Y$ be a set and let $Y'$ be a nonempty subset of $Y$. Find a definable $y_0$ (in terms of $Y$ and $Y'$) which is in $Y'$.

The interesting and nontrivial part of the equivalence is of course, to show that we can solve Problem 2 if we can solve Problem 1. Here is how. Let $Y$ and $Y'$ be as above. Take two elements $a,b$ and a countable set $W=\lbrace w_k \rbrace_{k \geq 0}$ outside of $Y$. Now define $X$ to be the disjoint union of $\lbrace a,b \rbrace$ and $Y \times W$, and define $F : {\cal P}(X) \to X$ by:

  1. $F(\lbrace (y,w_0) \rbrace)=a$, if $y\in {Y'} $,
  2. $F(\lbrace (y,w_{k+1}) \rbrace)=(y,w_k)$ , for all $y\in Y$ and $k\ge0$,
  3. $F(X)=a$, and
  4. $F(Z)=b$ for all other subsets $Z$ of $X$ (thus $F(\emptyset)=b$).

Now, by construction, $A=X$, and any solution $B$ to Problem 1 is of the form $\lbrace (y,w_0) \rbrace$ for some $y\in Y'$, thereby solving Problem 2.

share|cite|improve this answer
I'm not sure I follow your reduction. Are you saying that we could take Y'=Y to be the set of all $B$ in ${\cal P}(X)$ such that $F(B)=F(A)$ but $B \ne A$? I am sure that that is not what you intend, but wouldn't that be a way to use your problem 2 to solve problem 1? Can you give an example where it is worth having $Y' \ne Y?$ Couldn't we always make that simplification? And then what is the point of the construction? (Although I do enjoy the construction!) – Aaron Meyerowitz Nov 28 '10 at 15:47
@Ewan : Thanks. Hope you do not mind the minor editing I made. I have a question: How does solving problem 2 solve problem 1? If you do something as Aaron suggests (or, say $Y={\mathcal P}(X)$ and $Y'$ as he suggests), I do not see how losing $F$ is not affecting definability in general. Anyway, I agree that your construction shows that solving problem 1 solves problem 2, which is not possible in general, thus showing problem 1 has a negative solution in general. – Andrés E. Caicedo Nov 28 '10 at 16:14
@Ewan : Hmm. If we can solve problem 2 "uniformly", then of course we can well-order any set, which gives a solution to problem 1. Is this how you meant the reduction to proceed? – Andrés E. Caicedo Nov 28 '10 at 16:42
@ Aaron : you asked "what is the point of the construction" ? Andreas' comments answer this : it shows that Andreas' definition does not exist in ZF (without AC), because if it existed we could prove AC. – Ewan Delanoy Nov 28 '10 at 17:36
@Andreas : many thanks for your editing, now my answer is finally readable! I have several problems with editing answers on MO : my latex preview appears only during a fraction of a second. – Ewan Delanoy Nov 28 '10 at 17:39

It has been pointed out in the comments that Ewan's insightful solution shows that a negative answer to the question is consistent with ZF, since a positive answer implies AC.

But let me go one further. In fact, Ewan's solution shows that a negative answer to the main question is consistent with full ZFC. The reason is that a positive answer to Ewan's problem 2 actually implies the set-theoretic assertion $V=HOD$, that the universe consists of the hereditarily-ordinal-definable sets. To see this, supoose that $V\neq HOD$, then there is some cardinal $\kappa$ such that $Y=P(\kappa)$ has some non-ordinal definable elements. Let $Y'$ be the set of non-HOD subsets of $\kappa$. Both $Y$ and $Y'$ are ordinal definable, but $Y'$ has no ordinal definable elements. This contradicts any positive solution to problem 2.

Thus, any model of set theory having a positive answer to problem 2 must also satisfy $V=HOD$. And so any model of $ZFC+V\neq HOD$ is a model of a negative answer to the main question, with full ZFC.

Meanwhile, a positive answer to the main question is also consistent with ZFC, since there are models of ZFC in which every object is definable without parameters. For example, this is true in the minimal transitive model of set theory. Indeed, Reitz and Linetsky and I have recently proved that every countable model of ZFC and indeed of GBC can be extended to a pointwise definable model, in which every set and class whatsoever is definable without parameters. In such a model, we may definably find the desired B, since every B is definable. (But there is little uniformity in this definition.)

So the full answer to the main question is that it is independent of ZFC. Of course, the question of "definable" is not directly formalizable in set theory, so one should understand this assertion as the claim that if ZFC is consistent, then there are models of ZFC in which there is a positive solution, and models in which there is a negative solution, even when interpreted as the literal second-order claim. However, if one understands "definable" as "ordinal-definable", then the claim is formalizable in the language of set theory, and this claim is also independent of ZFC, for the same reasons.

share|cite|improve this answer
Hi Joel. Good observation, thanks! – Andrés E. Caicedo Nov 28 '10 at 23:14
@Joel : Your result with Reitz & Linetsky sounds very interesting. Is there a preprint I could take a look at? (If so, could you email it to me, or point me to a link?) – Andrés E. Caicedo Nov 28 '10 at 23:32
We are finalizing the draft now, and will post it to the arXiv fairly soon. – Joel David Hamkins Nov 28 '10 at 23:34
Nice to hear, Joel. Thanks. – Andrés E. Caicedo Nov 29 '10 at 2:58

Your Answer


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.