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

  • 5
    $\begingroup$ The order seems determined by refinement of the pre-image partitions. $\endgroup$ – Joel David Hamkins Jan 29 '20 at 10:24
  • $\begingroup$ Thanks @JoelDavidHamkins for your comment! So if I remember correctly, there is a surjective homomorphism from the collection of partitions on a set $X$ (ordered by refinement) onto ${\cal P}(X)$? $\endgroup$ – Dominic van der Zypen Jan 29 '20 at 10:47
  • 1
    $\begingroup$ If $X$ is a singleton, then $X^X$ is a singleton and there cannot exist a surjective map to the power set $P(X)$ (which has cardinality $2$). $\endgroup$ – Philipp Lampe Jan 29 '20 at 12:00
  • 4
    $\begingroup$ This is Green's L-preorder on the full transformation monoid. It is easy to see that two functions are equivalent iff they give the same partition of X into fibers over the image and hence this is the set partition lattice of X but with the order reversed (since the identity has singleton fibers and constant maps universal fibers). $\endgroup$ – Benjamin Steinberg Jan 29 '20 at 12:44
  • $\begingroup$ Sorry I see Joel already said this. $\endgroup$ – Benjamin Steinberg Jan 29 '20 at 12:46


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


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.


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.