Infima and suprema in the "transfer" function ordering

Question

Let $X,Y$ be sets, $f, g:X\to Y$ be functions. We say $u:Y\to Y$ is a transfer function for $g$ to $f$ if $$f = u \circ g.$$ In that case we write $f \leq_t g$. Let $\mathrm{Fct}(X,Y)$ denote the collection of all functions from $X$ to $Y$. So $\leq_t$ is reflexive and transitive. The relation $\simeq_t\subseteq \mathrm{Fct}(X,Y) \times \mathrm{Fct}(X,Y)$ is defined by $f\simeq_t g$ iff $f\leq_t g$ and $g \leq_t f$. It is easy to see that $\simeq_t$ is an equivalence relation.

We can make $\mathrm{Fct}(X,Y)/\simeq_t$ into a poset using $\leq_q$ in the obvious way. The smallest element of this poset is the equivalence class consisting of all constant functions. In the case $X=Y$ the equivalence class containing the identity map is the largest element.

Question. Is $\mathrm{Fct}(X,X)/\simeq_t$ a lattice?

Answer 1

Here is an answer to the question as literally asked.

For a function $f: X \to Y$, let $\ker(f) = \{(x, x') \in X \times X: f(x) = f(x')\}$. This is of course an equivalence relation.

Proposition: For $f, g: X \to Y$, we have $f \leq_t g$ iff $\ker(g) \subseteq \ker(f)$.

Proof: For "only if", notice that $g(x) = g(x')$ implies $f(x) = f(x')$ whenever $f$ is of the form $u \circ g$. For "if", define a partial function $u$ from $Y$ to $Y$ by $u(y) = f(x)$ whenever $y$ is of the form $g(x)$; this is well-defined since if $y = g(x)$ and $y = g(x')$, then also $f(x) = f(x')$ by the assumption $\ker(g) \subseteq \ker(f)$. Then extend $u$ to a total function from $Y$ to $Y$ however you please. $\Box$

Hence for $f, g: X \to Y$, we have $f \simeq_t g$ iff $\ker(f) = \ker(g)$.

Letting $\text{Equiv}(X)$ be the set of equivalence relations on $X$, the last observation says that the map $\left(\text{Fct}(X, Y)/\simeq_t\right) \to \text{Equiv}(X)$ that takes the $\simeq_t$ equivalence class $[f]$ to $\ker(f)$ is well-defined and injective.

In the case $Y = X$, it is also surjective by the axiom of choice. In detail, for any $E \in \text{Equiv}(X)$, there exists a section $s$ of the quotient map $r: X \to X/E$ (meaning $r \circ s = 1_{X/E}$), and then $\ker(s \circ r) = E$.

In that case, the map $\ker: \left(\text{Fct}(X, X)/\simeq_t\right) \to \text{Equiv}(X)^{op}$ is an isomorphism by the proposition, and since $\text{Equiv}(X)$ is a complete lattice, so must be $\text{Fct}(X, X)/\simeq_t$.

---

Added later: It seems all we needed in the paragraph above that begins "In the case $Y = X$" is the existence of an injective function $s: X/E \to X$, not that $s$ needs to be a section of $r$. Because just with injectivity, we get $\ker(s \circ r) = \ker(r) = E$. With that in mind, we can say a little more about the situation for general $Y$.

Proposition: For general $Y$, the poset $F = \text{Fct}(X, Y)/\simeq_t$ admits infs of nonempty subsets.

Thus the only obstruction to $F$ being a complete lattice is that it might not have the inf of the empty set, i.e., a top element $\top$ dominating all others. If $Y$ has cardinality greater than or equal to that of $X$, that $\top$ will exist.

Proof: We already saw that $\ker: F \to \text{Equiv}(X)^{op}$ is a poset embedding. Let $\{[X \stackrel{f_i}\to Y]: i \in I\}$ be a nonempty collection inside $F$, and put $E_i = \ker [f_i]$. The inf of the $E_i$ in $\text{Equiv}(X)^{op}$ is the join $E = \bigvee_{i \in I} E_i$ in $\text{Equiv}(X)$, which certainly exists. The cardinality $|X/E|$ is dominated by any $|X/E_i| = |f_i(X)|$, which is dominated by $|Y|$ using the image factorization $f_i = \left(X \to f_i(X) \subseteq Y\right)$. Hence there is an injection $i: X/E \to Y$, and then $\ker f = E$ for $f = \left(X \twoheadrightarrow X/E \stackrel{i}{\to} Y \right)$, making $[f]$ the inf of the $[f_i]$. $\Box$

Answer 2

Here is a counterexample showing that the quotient of $\text{Fct}(X,Y)$ is not necessarily a lattice.

Let $X=\{0,1,2\}$ and let $Y=\{0,1\}$. Let $g(0)=g(1)=0$ and $g(2)=1$, while $f(0)=0$ and $f(1)=f(2)=1$.

These functions are incomparable by your order, since $g$ sends $0$ and $1$ to the same value and $f$ doesn't, and $f$ sends $1$ and $2$ to the same value, but $g$ doesn't.

I claim that $f$ and $g$ have no upper bound in the order. If $f$ and $g$ are both $\leq r$ for some $r:X\to Y$, then $f=u\circ r$ and $g=v\circ r$ for some $u,v:Y\to Y$. But $r$ is a function from a three-element set to a two-element set, and so $r$ must send two points to the same point. But it can't be that $r(0)=r(1)$, since $f(0)\neq f(1)$; and it can't be that $r(0)=r(2)$, since $f(0)\neq f(2)$; and it can't be that $r(1)=r(2)$, since $g(1)\neq g(2)$. So there is no such $r$, and thus $f$ and $g$ have no upper bound.