9
$\begingroup$

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

$\endgroup$
13
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 7
    $\begingroup$ 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$.) $\endgroup$ – Andreas Blass Jun 27 at 14:36
  • $\begingroup$ @Andreas Yes, this is in essence the argument. $\endgroup$ – Andrés E. Caicedo Jun 27 at 14:41
8
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • 3
    $\begingroup$ Very nice! $\ \ $ $\endgroup$ – David Roberts Jun 30 at 23:11

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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