# Infima and suprema in the “transfer” function ordering

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?

• Isn't $\text{Fct}(X, X)/\simeq_t$ equivalent to the set of partitions of $X$? More generally, isn't $\text{Fct}(X, Y)/\simeq_t$ equivalent to the set of partitions of $X$ of cardinality at most $|Y|$ (i.e. with at most $|Y|$ equivalence classes)? In the former case, the meet is the transitive closure of the union of the equivalence relations, and the join is the set of all pair-intersections of equivalence classes, no? – user44191 Jan 13 at 11:46
• Thanks for your comment! I was thinking that for $\text{Fct}(\omega,\omega)$ the identity and the map sending 0 to 0 and $n\mapsto n-1$ for $n\geq 1$ do not belong to the same eq class but correspond to the same partition, or did I misunderstand it? – Dominic van der Zypen Jan 13 at 14:50
• @DominicvanderZypen They do not correspond to the same partition, because the partition of the latter has $0,1$ in the same part, while the former doesn't. – Wojowu Jan 13 at 16:16
• I see @Wojowu . The interesting thing is that I thought that user44191's argument was correct, implying that $\text{Fct}(X,X)/\simeq_t$ is a lattice - and now, Joel David Hamkins' answer shows it's not! – Dominic van der Zypen Jan 13 at 16:48
• @DominicvanderZypen Joel's answer below shows the quotient of $Fct(X,Y)$ is not in general a lattice, and is correct. However, for $Y=X$, it is a lattice. – Wojowu Jan 13 at 16:59

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

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.

• You are not quite answering the question asked - the question was about the quotient of $Fct(X,X)$, not of general $Fct(X,Y)$. You are right that the latter is not a lattice, but, as noted in the comments, the former is. – Wojowu Jan 13 at 17:00
• My counterexample works in the quotient of $\text{Fct}(X,Y)$, since $f$ and $g$ have no upper bounds at all, and so $[f]$ and $[g]$ have no upper bounds in the quotient. But I see now that he had switched to $\text{Fct}(X,X)$ in the question. Was that a typo? – Joel David Hamkins Jan 13 at 17:11
• Since Dominic repeated the thing in response to the comment of Wojowu, I doubt it's a typo. Meanwhile, I've given an answer to that. – Todd Trimble Jan 13 at 18:25
• Great, it seems we have all the bases covered now. – Joel David Hamkins Jan 13 at 18:32