Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

For any nonempty set $X$ and any function $f:P(X)\to X$, there exist different $A,B\subseteq X$ such that $A\subseteq B$ and $f(A)=f(B)$.

One attempt is trying to find a chain A s.t. $|X|<|A|\leq |P(X)|$ from here

Thank you.

share|improve this question
You probably want to require $A\neq B$ –  Jan Ladislav Dussek Jan 5 at 23:08
How did you prove it for countable $X$? I don't see where induction comes in. –  bof Jan 6 at 0:25
I know what a chain is, but what is an ascending chain? –  bof Jan 6 at 0:33
If I understand the question, perhaps a clearer formulation would be: for any cardinal $\kappa$, prove that $P(\kappa)$, partially ordered by $\subseteq$, is not the union of $\kappa$ antichains. –  bof Jan 6 at 1:24
The case $|X|=\aleph_1$ follows from the answer to this question which shows that there is a chain of cardinality $\aleph_2$ in $P(\omega_1)$. –  bof Jan 6 at 1:32

2 Answers 2

The argument for this is originally due to Zermelo. Just build the chain inductively: Start with $f(\emptyset)=x_0$; in general, given $A_\beta=\{x_\alpha\mid \alpha<\beta\}$, let $x_\beta$ be $f(A_\beta)$. Eventually you reach a repetition, that is, $x_\alpha=x_\beta$ for some $\alpha<\beta$, and we are done. That there is a repetition can be seen as a consequence of Hartogs's result that for any set $X$ there is a first ordinal that cannot be embedded into $X$. See here (section 4) for more details.

Note that we did not use choice anywhere. In fact, this shows that it suffices to have $f$ defined on $\mathcal W(X)$, the collection of well-orderable subsets of $X$, and so proves in $\mathsf{ZF}$ that this set is strictly larger than $X$, a result originally due to Tarski. (In particular, in Solovay's model, or under determinacy, there are more countable sets of reals than there are reals, even though there is a bijection between $\mathbb R^\omega$ and $\mathbb R$.)

In the spirit of the other answer, let me sketch a stronger result, from

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

As Stevo indicates, the result is due to Galvin (unpublished) under choice. Stevo's proof works in $\mathsf{ZF}$.

Theorem ($\mathsf{ZF}$). For any (well-ordered) cardinal $\kappa\ge\omega$ and any $\alpha<\kappa^+$, if $f:\mathcal P(\kappa)\to\kappa$, then there is a $\subseteq$-chain of order type $\alpha$ of subsets of $\kappa$ that is constant under $f$.

Stevo's proof builds on ideas of Kurepa. The notation below is Stevo's. It is a bit unfortunate, since these "embeddings" need not be injective.

Let ${\mathcal A}=(A,R)$ and ${\mathcal B}=(B,S)$ be two structures where $R,S$ are binary relations. Then ${\mathcal A}$ is ${\mathcal B}$-embeddable, in symbols $$ {\mathcal A}\hookrightarrow{\mathcal B},$$ iff there is a map $f:A\to B$ (an embedding) such that whenever $a\ne b$ are elements of $A$ with $a\mathrel{R}b$, we have $f(a)\ne f(b)$ and $f(a)\mathrel{S}f(b)$. We write $f:{\mathcal A}\hookrightarrow {\mathcal B}$ to indicate that $f$ is such an embedding.

Let ${\mathcal A}=(A,R)$ be a set equipped with a binary relation. Define $\sigma{\mathcal A}=(\sigma A,{\subseteq})$, where $$ \begin{array}{rl} \sigma A&=\{s\mid\mbox{ There is an }\alpha\in\mathsf{ORD}\,(s:\alpha\hookrightarrow{\mathcal A})\}\\ &=\{s\mid\mbox{ There is an }\alpha\in\mathsf{ORD}\,(s:\alpha\to A\mbox{ is injective }\mathrel{\&}\forall\xi<\eta<\alpha\,(s(\xi)\mathrel{R}s(\eta)))\}. \end{array} $$

The following is straightforward. We are only interested here in the case where $r=1$ and all the $\varphi_i$ are identical.

Lemma 1. If $P,Q$ are posets and $P\hookrightarrow Q$, then for all $r$ with $0<r\in\omega$, all $I$, and all sequences $(\varphi_i\mid i\in I)$ of order-types of linear orders, we have $$ P\to(\varphi_i)^r_{i\in I}\Longrightarrow Q\to(\varphi_i)^r_{i\in I}. $$

(The proof is the natural one, modulo notation, for which I suggest looking at the Hajnal-Larson survey, Partition relations:

Given $f:[Q]^r\to I$ and $g:P\hookrightarrow Q$, define $h:[P]^r\to I$ by $$ h(\langle a_1,\dots,a_r\rangle)=f(\langle g(a_1),\dots,g(a_r)\rangle), $$ noting that this makes sense since $a_1<_P a_2<_P\dots<_P a_r$ implies $g(a_1)<_Q g(a_2)<_Q\dots<_Q g(a_r)$ since $g$ is an embedding.

Since $P\to(\varphi_i)^r_{i\in I}$, we can find $i\in I$ and $H\in[P]^{\varphi_i}$ such that $h''[H]^r=\{i\}$. But then $g''H\in[Q]^{\varphi_i}$, again by virtue of $g$ being an embedding (and $\varphi_i$ being the type of a linear order), and $$ f''[g''H]^r=h''[H]^r=\{i\}, $$ by definition of $h$.

This shows that $Q\to(\varphi_i)^r_{i\in I}$.)

The relevance here is that the theorem we want to prove is, in the partition calculus notation, that if $\kappa\ge\omega$ is a cardinal, then $(\mathcal P(\kappa),\subseteq)\to(\alpha)^1_\kappa$ for all $\alpha<\kappa^+$.

First, given a set $A$, set $$ S(A)=\{\tau\mid\mbox{ There is an }\alpha\in\mathsf{ORD}\,(\tau:\alpha\to A\mbox{ is injective})\}, $$ considered as a structure with the binary relation $\subseteq$.

Note that $(S(A),\subseteq)=\sigma(A,A^2)$, and that $S(A)\hookrightarrow\mathcal W(A)$, where $\mathcal W(A)$ is the collection of subsets of $A$ that are well-orderable, again seen as a structure with binary relation $\subseteq$ (the embedding being the map sending each $\tau$ to its range).

Hartogs's theorem generalizes to

Lemma 2. $\sigma\mathcal A\not\hookrightarrow\mathcal A$ for any $\mathcal A$.

(To see this, note that if $f:\sigma A\hookrightarrow A$, then the map $s$ given recursively by $s(\alpha)=f(s\upharpoonright\alpha)$ injects the ordinals into $A$.)

Corollary. If $\kappa\ge\omega$ and $\alpha<\kappa^+$, then $$ S(\kappa)\to(\alpha)^1_\kappa. $$

Todorcevic indicates in his paper that this is due to Laver for $\kappa=\omega$, and to Galvin in general but assuming $\mathsf{AC}$, both unpublished.

We proceed to prove the corollary: Since $S(\kappa)=\sigma(\kappa,\kappa\times\kappa)$, no $f:S(\kappa)\to\kappa$ is an embedding (by Lemma 2), so there are $\tau\subsetneq\mu$ such that $f(\tau)=f(\mu)$, since trivially $(f(\tau),f(\mu))\in\kappa\times\kappa$.

Consider $g:S(\kappa)\to\kappa$, fix $\alpha<\kappa^+$, and suppose that there is no $g$-monochromatic chain in $S(\kappa)$ of type $\alpha$. Let $\varphi:\alpha\to\kappa$ be injective, and let $\langle\cdot,\cdot\rangle:\kappa\times\kappa\to\kappa$ be a bijection. Let $f:S(\kappa)\to\kappa$ be the function given by $$ f(\tau)=\langle g(\tau),\varphi(o(\tau))\rangle, $$ where $o(\tau)$ is the order-type of $\tau$ in $\{\mu\sqsubseteq\tau\mid g(\mu)=g(\tau)\}$, where $\sqsubseteq$ is the initial-segment relation.

We are done, because $f$ is $1$-$1$, contradicting the first paragraph.

And this also concludes the proof of the theorem, by Lemma 1, because $S(\kappa)\hookrightarrow\mathcal W(\kappa)=\mathcal P(\kappa)$.

(The write-up above comes from a book I'm working on. Any feedback or suggestions are of course encouraged and greatly appreciated. Let me add that Stevo's results from this paper have proven key in the theory of the partition calculus of non-special posets $\mathbb P$, those for which $\mathbb P\to(\omega)^1_\omega$ holds.)

share|improve this answer

Update: a stronger result

The question asks for a proof of the fact that a function $f:P(X)\to X$ is constant on some $2$-element chain. A simple proof of that fact is provided in Andres Caicedo's answer. Here is a more involved argument which proves, in the case where $|X|=\kappa$ is a regular cardinal, the stronger result that $f$ is constant on some chain of order type $\kappa+1$. Without loss of generality we may assume that $X=\kappa$.

Theorem. If $\kappa$ is a regular infinite cardinal, then for any function $f:P(\kappa)\to\kappa$ there is a chain $\mathcal C\subseteq P(\kappa)$ of order type $\kappa+1$ such that $f$ is constant on $\mathcal C$.

Proof. For $\kappa=\omega$ this follows from the fact that $P(\omega)$ contains a chain which is order-isomorphic to the real line. From now on we assume that $\kappa$ is an uncountable regular cardinal. Let a function $f:P(\kappa)\to\kappa$ be given. Choose a function $\varphi:\kappa\to\kappa$ such that $|\{\alpha\in\kappa:\varphi(\alpha)=\xi\}|=\kappa$ for each $\xi\in\kappa$.

We construct a sequence $(A_\alpha:\alpha\lt\kappa)$ of subsets of $\kappa$ by transfinite induction, as follows. Suppose that $\alpha\lt\kappa$, and that $A_\beta$ has already been defined for all ordinals $\beta\lt\alpha$. We define $A_\alpha$ so that the following conditions are satisfied:

(1) $\bigcup_{\beta\lt\alpha}A_\beta\subseteq A_\alpha\subseteq\kappa$;
(2) $A_\alpha\setminus\bigcup_{\beta\lt\alpha}A_\beta$ is a nonempty subset of the open interval $(\alpha,\kappa)$;
(3) $A_\alpha$ is a nonstationary (or "thin") subset of $\kappa$;
(4) and, if possible, $f(A_\alpha)=\varphi(\alpha)$.

That is, at step $\alpha$ we choose a set $A_\alpha$ satisfying conditions (1)-(4) if such a set exists; otherwise, we choose $A_\alpha$ satisfying (1)-(3).

Finally, let $A=\bigcup_{\alpha\lt\kappa}A_\alpha$. I claim that $A$ is nonstationary. To see this, define a function $\rho:A\to\kappa$ by setting $\rho(\xi)=\min\{\alpha:\xi\in A_\alpha\}$, i.e., $\rho(\xi)$ is the index of the step where $\xi$ was added to $A$. It follows from (2) that $\rho$ is a regressive function, i.e., $\rho(\xi)\lt\xi$ for all $\xi\in A$. If A were stationary, then by Fodor's lemma $\rho$ would be constant on some stationary set; it follows from (3) that that doesn't happen.

It is now easy to see that replacing any $A_\alpha$ with $A$ would satisfy conditions (1)-(3), as well as satisfying (4) whenever $\varphi(\alpha)=f(A)$.

Let $\mathcal C=\{A_\alpha:\alpha\lt\kappa,\varphi(\alpha)=f(A)\}\cup\{A\}$; then $\mathcal C$ is a chain in $P(\kappa)$ of order type $\kappa_1$, and $f$ is constant on $\mathcal C$.

share|improve this answer
can you elaborate on why $B$ is nonstationary at the end? –  Paul McKenney Jan 6 at 13:43
That works, thanks! –  Paul McKenney Jan 6 at 14:19

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.