Is it consistent to have a function that is sensitive to subset relation from the power set of a set to that set?

Question

Is it consistent with $ZF$ to have a set $S$ and a function $F: P(S) \to S$ such that:

$\forall X,Y \in P(S): X \subsetneq Y \implies F(X) \neq F(Y)$

Answer 1

No, this is not consistent. Todorčević has shown in ZF that, in fact, there is no function $F\!:\mathcal W(S)\to S$ with the property you require. Here, $\mathcal W(S)$ is the collection of subsets of $S$ that are well-orderable.

This is corollary 6 in

MR0793235 (87d:03126). Todorčević, Stevo. Partition relations for partially ordered sets. Acta Math. 155 (1985), no. 1-2, 1–25.

The corollary is a consequence of theorem 5, stating that for any structure $\mathcal M$ with one binary relation, $\sigma \mathcal M$ is not "$\mathcal M$-embeddable". Here, if $\mathcal M=(M,R)$, then $\sigma\mathcal M=(\sigma M,\subseteq)$, where $\sigma M$ is the set of all one-to-one maps $s$ with domain an ordinal $\alpha$ such that whenever $\beta<\gamma<\alpha$, we have $s(\beta)\mathrel R s(\gamma)$. In Stevo's notation, that $(A,S)$ is $(B, T)$-embeddable means that there is a function $f\!:A\to B$ such that $f(a) \mathrel T f(b)$ and $f(a)\ne f(b)$ whenever $a,b\in A$, $a\mathrel S b$, and $a\ne b$.

Answer 2

Here's an argument that doesn't use ordinals, as an alternative to the nice proof described by Andrés and Andreas.

Take $F: P(S) \to S$ satisfying your hypothesis. Define a function $\Phi: P(S) \to P(S)$ by $$ \Phi(X) = \{F(Y): Y \subseteq X\}. $$ Then $\Phi$ is an order-preserving map from the complete lattice $P(S)$ to itself, so there is a least $X \in P(S)$ such that $\Phi(X) \subseteq X$. (That such an $X$ exists is part of the proof of the Knaster-Tarski fixed point theorem, and is in any case easy: put $X = \bigcap\{ Y \in P(S): \Phi(Y) \subseteq Y\}$, then use the fact that $\Phi$ is order-preserving to show that $\Phi(X) \subseteq X$.)

Now:

• $F(X) \in \Phi(X)$ by definition of $\Phi$, so $F(X) \in X$, so if we write $X' = X \setminus\{F(X)\}$ then $X' \subsetneqq X$.

• $\Phi(X') \subseteq \Phi(X) \subseteq X$, so $\Phi(X') \subseteq X$.

• Any subset $Y$ of $X'$ is a proper subset of $X$, so your hypothesis on $F$ gives $F(Y) \neq F(X)$. Hence $F(X) \not\in \Phi(X')$.

Combining the three bullet points, we have a proper subset $X'$ of $X$ satisfying $\Phi(X') \subseteq X'$. This contradicts the minimality of $X$.