# Surjective order-preserving map $f:{\cal P}(X)\to \text{Part}(X)$

Let $$X$$ be a set, and let $$\text{Part}(X)$$ denote the collection of all partitions of $$X$$. For $$A, B\in \text{Part}(X)$$ we set $$A\leq B$$ if $$A$$ refines $$B$$, that is for all $$a\in A$$ there is $$b\in B$$ such that $$a\subseteq b$$. This relation defines a partial order on $$\text{Part}(X)$$.

If $$X$$ is an infinite set, is there a surjective order-preserving map $$f:{\cal P}(X)\to \text{Part}(X)$$ (where $${\cal P}(X)$$ denotes the power-set of $$X$$, ordered by $$\subseteq$$)?

• @Ivan: Maybe a shower can help... Sep 27, 2018 at 12:47
• Don't force him @Asaf! Gerhard "Sometimes Can't Resist The Setup" Paseman, 2018.09.27. Sep 27, 2018 at 17:16
• @Gerhard: He left me no choice. Sep 27, 2018 at 17:29
• @HenrikRüping Right. You get that $P(X \times X) \to \text{Equiv}(X)$ preserves arbitrary sups; it can be seen as a left adjoint to the inclusion $\text{Equiv}(X) \hookrightarrow P(X \times X)$ (this follows easily from the fact that generation of equivalence relations is a closure operator). Sep 27, 2018 at 18:11
• Indeed, since the power set lattice is distributive and the equivalence relation lattice is not, the best you can hope for is an embedding, not a surjective lattice homomorphism. (Or as complete semi lattices, as Todd mentioned.) I am unsure if a lattice embedding exists in this situation when X is infinite. Gerhard "Can't Resist Those Setups Today" Paseman, 2018.09.27. Sep 27, 2018 at 18:28

It may be clarifying to work with equivalence relations $$E$$ on $$X$$ rather than partitions on $$X$$. The two are in natural bijection, with $$E$$ inducing a partitioning quotient map $$q: X \to X/E$$, and $$X/E$$ refines $$X/E'$$ iff $$E \subseteq E'$$ as subsets of $$X \times X$$.

Next, there is a surjective order-preserving map $$P(X \times X) \to \text{Equiv}(X)$$ where a general relation $$R \in P(X \times X)$$ is mapped to the equivalence relation $$E_R$$ that it generates. This is clearly surjective since an equivalence relation $$E$$ is mapped to itself.

Finally, if $$X$$ is infinite, there is a bijection $$X \cong X \times X$$, which induces an isomorphism of orders $$P(X) \to P(X \times X)$$. The composite

$$P(X) \to P(X \times X) \to \text{Equiv}(X)$$

provides what you want.

• That's right, working with equivalence relations makes things conceptually easier - thanks for your answer! Sep 27, 2018 at 12:42

The positive solution uses an equivalent of the Axiom of Choice: for every infinite set $$A$$ there is a bijection $$f:A\to A\times A$$.

In the basic Fraenkel Model (section 4.3 in Jech's Axiom of Choice) there is an infinite set where there is no surjection as in the question.

Let $$A$$ be the infinite set of atoms in the model.

Step 1. Every subset of $$A$$ in the model is finite or cofinite. Let $$X\subseteq A$$ and let $$E\subseteq A$$ be finite such that $$\operatorname{fix} E\subseteq\operatorname{sym} X$$. If $$X\subseteq E$$ then $$X$$~is finite. If $$X\not\subseteq E$$ then $$A\setminus E\subseteq X$$: fix $$x\in X\setminus E$$ and let $$y\in A\setminus E$$ be arbitrary; the permutation~$$\pi$$ that interchanges $$x$$ and $$y$$ is in $$\operatorname{fix} E$$, so $$\pi X=X$$, but this means that $$y=\pi(x)\in\pi X=X$$.

Step 2. Let $$P$$ be partition of $$A$$ in the model and let $$E\subseteq A$$ be finite with $$\operatorname{fix} E\subseteq \operatorname{sym} P$$. Assume there are $$a$$ and $$b$$ in $$A\setminus E$$ that are distinct and $$P$$-equivalent. Let $$c\in A\setminus E$$ be arbitrary and not equal to~$$a$$. Let $$\pi$$ be the permutation that interchanges $$b$$ and $$c$$; then $$\pi\in\operatorname{fix} E$$, hence $$\pi P=P$$. Then $$a,b\in X$$ for some $$X\in P$$, and hence $$a,c\in\pi X$$. As $$\pi X\in\pi P=P$$ this shows that $$a$$ and $$c$$ are $$P$$-equivalent as well. It follows that either there is an element of $$P$$ that contains $$A\setminus E$$, or all elements of $$A\setminus E$$ determine one-element members of $$P$$.

Step 3. Assume $$f:\mathcal{P}(A)\to\operatorname{Part}(A)$$ is an order-preserving surjection. And let $$E\subseteq A$$ be finite such that $$\operatorname{fix} E\subseteq\operatorname{sym} F$$.

Assume $$X$$ and $$Y$$ are finite such that $$X\cap E=Y\cap E$$ and $$|X\setminus E|=|Y\setminus E|$$, and such that $$f(X)$$ and $$f(Y)$$ are partitions that contain $$\{\{a\}:a\in A\setminus E\}$$. Then $$f(X)=f(Y)$$.

To see this let $$\pi$$ be a permutation that maps $$X\setminus E$$ to $$Y\setminus E$$ and vice versa and leaves all other points in place. Then $$\pi\in\operatorname{fix} E$$, so that $$\pi(f(X))=f(X)$$ and $$\pi(f(Y)=f(Y)$$. The ordered pair $$\langle X,f(X)\rangle$$ is in $$f$$, hence $$\langle \pi(X),\pi(f(X))\rangle$$ is in~$$\pi f$$, but $$\pi f=f$$ and $$\pi X=Y$$ so that $$\langle Y,f(X)\rangle\in f$$, that is, $$f(Y)=f(X)$$.

A similar statement holds when $$X$$ and $$Y$$ are infinite, hence cofinite, and $$X\cap E=Y\cap E$$, and $$|A\setminus(E\cup X)|=|A\setminus(E\cup Y)|$$.

Step 4. Now consider the set $$\Pi(E)$$ of partitions of~$$A$$ that contain $$\{\{a\}:a\in A\setminus E\}$$; this is essentially the set of partitions of~$$E$$ where each is augmented with $$\{\{a\}:a\in A\setminus E\}$$.

The argument above also shows the following: if $$X$$ and $$Y$$ are finite such that $$X\cap E=Y\cap E$$, $$|X\setminus E|\le|Y\setminus E|$$ and $$f(X),f(Y)\in\Pi(E)$$ then $$f(X)\le f(Y)$$. This is so because we can find a permutation $$\pi$$ in $$\operatorname{fix} E$$ such that $$\pi(X)\subseteq Y$$.

Likewise: if $$X$$ and $$Y$$ are infinite such that $$X\cap E=Y\cap E$$, $$|A\setminus(X\cup E)|\le|A\setminus(Y\cup E)|$$ and $$f(X),f(Y)\in\Pi(E)$$ then $$f(X)\ge f(Y)$$.

Finally: if $$X$$ is finite and $$Y$$ is infinite such that $$X\cap E=Y\cap E$$ and $$f(X),f(Y)\in\Pi(E)$$ then $$f(X)\ge f(Y)$$.

In conclusion: each subset of $$E$$ determines a chain in the set~$$\Pi(E)$$.

Step 5. If we enlarge $$E$$ then $$\operatorname{fix} E$$ becomes smaller, so we can choose $$E$$ as large as we please.

Let $$n$$ be a natural number. The number of partitions of the set $$\{1,2,\ldots,4n\}$$ into four sets of size $$n$$ is equal to $$\binom{4n}{n}\binom{3n}{n}\binom{2n}{n}$$ This number is larger than $$3^n\cdot 2^n\cdot\frac{4^n}{2n+1} = \frac{24^n}{2n+1}$$ For $$n\ge9$$ we have $$24^n/(2n+1)>16^n$$.

This gives us our contradiction: if necessary enlarge $$E$$ so that $$|E|=4n$$ for some $$n\ge9$$. Then, by 4 above, the map $$f$$ divides $$\Pi(E)$$ into, at most, $$2^{4n}=16^n$$ chains. On the other hand the partitions of $$E$$ into four pieces of size $$n$$ form an antichain of cardinality more than $$24^n/(2n+1)$$, which in turn is larger than $$16^n$$.