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?

  • 2
    $\begingroup$ 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? $\endgroup$ – user44191 Jan 13 at 11:46
  • $\begingroup$ 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? $\endgroup$ – Dominic van der Zypen Jan 13 at 14:50
  • $\begingroup$ @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. $\endgroup$ – Wojowu Jan 13 at 16:16
  • $\begingroup$ 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! $\endgroup$ – Dominic van der Zypen Jan 13 at 16:48
  • $\begingroup$ @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. $\endgroup$ – Wojowu Jan 13 at 16:59

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$


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.

  • $\begingroup$ 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. $\endgroup$ – Wojowu Jan 13 at 17:00
  • $\begingroup$ 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? $\endgroup$ – Joel David Hamkins Jan 13 at 17:11
  • $\begingroup$ 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. $\endgroup$ – Todd Trimble Jan 13 at 18:25
  • $\begingroup$ Great, it seems we have all the bases covered now. $\endgroup$ – Joel David Hamkins Jan 13 at 18:32

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.