Cantor's argument revisited

Question

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$)?

Answer 1

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.

Answer 2

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.