Does the lattice of partitions map onto the lattice of subsets?

Question

Let $X\neq \emptyset$ be a set and let $X^X$ denote the collection of all functions $f:X\to X$. We put a binary relation (reflexive and transitive), the composition preorder on $X^X$ by setting for $f,g\in X^X$: $$ f\leq_{\text{comp}} g \text{ if and only if } \exists h\in X^X (f = h \circ g).$$ It is easy to see that this relation is reflexive and transitive, but not anti-symmetric, so we say for $f,g\in X^X$ that $f\simeq_{\text{comp}} g$ if and only if $f\leq _{\text{comp}} g$ and $g \leq_{\text{comp}} f$.

So $X^X/\simeq_{\text{comp}}$ is a poset with the composition preorder applied to equivalence classes. The class consisting of constant functions is the smallest element, and the class containing the identity function is the largest element of $X^X/\simeq_{\text{comp}}$.

Given a non-empty set $X$, is there a surjective order-preserving map $f:X^X/\simeq_{\text{comp}} \to {\cal P}(X)$, where ${\cal P}(X)$ is ordered by $\subseteq$?

Answer 1

Comments:

I. This question reduces to the question of whether the lattice $\textrm{Eq}(X)$ of equivalence relations on $X$ has an order-preserving map onto the lattice ${\mathcal P}(X)$ of subsets of $X$.

II. The answer to this question is Yes if $X$ is infinite.

III. The argument in the infinite case can be applied in the finite case to show that $\textrm{Eq}(n+1)$ has an order-preserving map onto ${\mathcal P}(n)$ when $n\in\omega$, but it does not resolve the question of whether $\textrm{Eq}(n)$ has an order-preserving map onto ${\mathcal P}(n)$ when $n\in\omega$.

---

Reasons.

I. $f\leq_\textrm{comp} g$ iff $\ker(f)\subseteq \ker(g)$, as observed in the comments. Thus, $(X^X/\simeq)\;\;\cong\;\; \textrm{Eq}(X)$.

II. Let $X=\kappa$ be an infinite cardinal. View it as a graph with edge set consisting of all $(\alpha,\alpha+1)$ for $\alpha< \kappa$. Call $(\alpha,\alpha+1)$ a successor pair and call $\alpha$ the initial element of the pair. Define a map

$$ \Phi: \textrm{Eq}(\kappa)\to {\mathcal P}(\kappa): \theta\mapsto \{\alpha\;|\;(\alpha,\alpha+1)\in\theta\}. $$ That is, $\Phi$ maps an equivalence relation to the set of initial elements of successor pairs that are in relation.

$\Phi$ is order-preserving, since if $\theta\leq \theta'$, then $\theta'$ has at least as many successor pairs as $\theta$, hence $\Phi(\theta')$ has at least as many initial elements of successor pairs as $\Phi(\theta)$.

It is easy to construct a right inverse to $\Phi$, namely $$\Psi: {\mathcal P}(\kappa)\to \textrm{Eq}(\kappa): U\mapsto \textrm{equiv. reln. generated by} \{(\alpha,\alpha+1)\;|\;\alpha\in U\}. $$ To see that $\Psi$ is a section of $\Phi$ you must convince yourself that an equivalence relation generated by successor pairs will contain no successor pairs other than the generators.

III. This argument can be applied in the finite case to show that $$\Phi: \textrm{Eq}(n+1)\to {\mathcal P}(n): \theta\mapsto \{i\;|\;(i,i+1)\in\theta\}$$ is an order-preserving surjection. To make the argument work, we need that every element $i\in n$ is the initial element of a successor pair, so our domain lattice needs to be $\textrm{Eq}(n+1)$ rather than $\textrm{Eq}(n)$.

---

My guess is that there is no order-preserving surjection $\textrm{Eq}(n)\to {\mathcal P}(n)$ when $n\in\omega$. Surely there can be no $\wedge$-preserving surjection, nor can there be any $\vee$-preserving surjection. The reason there is no $\wedge$-preserving surjection is: for any $\wedge$-preserving surjection $\Phi: \textrm{Eq}(n)\to {\mathcal P}(n)$, there is a $\vee$-preserving section $\Psi: {\mathcal P}(n)\to \textrm{Eq}(n)$ defined by $\Psi(U)$ = least element of $\Phi^{-1}(U)$. But then $\Psi$ is an order-preserving injection, and no such map exists from ${\mathcal P}(n)$ to $\textrm{Eq}(n)$, as was pointed out on this page.