7
$\begingroup$

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

$\endgroup$
7
  • 7
    $\begingroup$ @Ivan: Maybe a shower can help... $\endgroup$ – Asaf Karagila Sep 27 '18 at 12:47
  • 3
    $\begingroup$ Don't force him @Asaf! Gerhard "Sometimes Can't Resist The Setup" Paseman, 2018.09.27. $\endgroup$ – Gerhard Paseman Sep 27 '18 at 17:16
  • 6
    $\begingroup$ @Gerhard: He left me no choice. $\endgroup$ – Asaf Karagila Sep 27 '18 at 17:29
  • 3
    $\begingroup$ @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). $\endgroup$ – Todd Trimble Sep 27 '18 at 18:11
  • 4
    $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Sep 27 '18 at 18:28
18
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ That's right, working with equivalence relations makes things conceptually easier - thanks for your answer! $\endgroup$ – Dominic van der Zypen Sep 27 '18 at 12:42
6
$\begingroup$

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

$\endgroup$
0

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.