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

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

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

• An alternative proof of the result about $F:\mathcal W(S)\to S$ without introducing $\sigma\mathcal M$: If there were such an $F$, then define, by recursion on ordinals $\alpha$, $G(\alpha)=F(\{G(\beta):\beta<\alpha\})$ and note that $G$ maps all the ordinals one-to-one into $S$. (To avoid mentioning the proper class of all ordinals, just restrict to $\alpha<$ Hartogs number of $S$.) – Andreas Blass Jun 27 at 14:36
• @Andreas Yes, this is in essence the argument. – Andrés E. Caicedo Jun 27 at 14:41

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

• Very nice! $\ \$ – David Roberts Jun 30 at 23:11