Can we take images of equivalence relations?

Question

Given a function $f : X \rightarrow Y$, it is well-known that we can take the image under $f$ of any subset $A \subseteq X$, and we can take the preimage under $f$ of any subset $A \subseteq Y$. This is fundamental.

A little less well-known is that we can take the preimage under $f$ of an equivalence relation $\cong$ on $Y$. In particular, we define $f^{-1}(\cong)$ to be the unique equivalence relation $\sim$ on $X$ such that the following holds.

$$x \sim x' \iff f(x) \cong f(x')$$

It is easy to verify that this is indeed an equivalence relation.

Question. If $f : X \rightarrow Y$ is an arbitrary function (so that, in particular, we're not assuming that $f$ is surjective), is it the case that to every equivalence relation $\sim$ on $X$, there is a naturally corresponding equivalence relation $f(\sim)$ on $Y$?

Basically, I can see at least two possible ways of doing this. In one approach, every two elements in $Y \setminus f(X)$ is equivalent; in the other, no two distinct elements in $Y \setminus f(X)$ are equivalent.

But how do we know which is the "correct" definition?

Answer 1

Here is one way you can pushforward an equivalence relation. If you have any relation $\sim$ on a set $X$, you can think of $\sim$ as a certain subset $R \subset X \times X$. Then $R$ is an equivalence relation if it satisfying the following three conditions:

1. (reflexivity) $(x,x) \in R$ for all $x \in X$,
2. (symmetry) if $(x,x') \in R$ then $(x',x) \in R$.
3. (transitivity) if $(x,x'), (x',x'') \in R$ then $(x,x'') \in R$.

This is just a restatement of the usual definition of equivalence relation. Now, if we have a function $f:X \to Y$, we get an induced function $F:X \times X \to Y \times Y$ given by $F(x,x') = (f(x),f(x'))$. Then, given a relation $R \subset Y \times Y$, we get an relation on $X$ by literally taking the preimage $F^{-1}(R) \subset X \times X$. By definition, $(x,x') \in F^{-1}(R)$ if and only if $(f(x),f(x')) \in R$ so it's clear this is exactly the pullback you described in your question. You can verify that if $R$ is an equivalence relation then $F^{-1}(R)$ will also be an equivalence relation. In this way we get a well defined way to pullback equivalence relations along $f$. Let's denote this $f^*(\sim)$ since we're really taking the preimage by $F$ not $f$.

Now that we've found a way to restate pulback of equivalence relations, how can we use this same $F$ to pushforward equivalence relations? The obvious thing to do is say that if $R \subset X \times X$ is a relation on $X$, then define the pushforward $f_*(\sim)$ by $F(R) \subset Y \times Y$. This is a fine relation. However, when we try to check if $F(R)$ is an equivalence relation when $R$ is, we run into trouble and find that it's not. So the question is what is the simplest or most "universal" way to turn $F(R)$ into an equivalence relation?

Well we know we're looking for some equivalence relation $R' \subset Y \times Y$ such that $F(R) \subset R'$ because we want the equivalence relation $R'$ to still satisfy the relation of $F(R)$. But we don't want to change too much, we want to change $F(R)$ as little as possible while making it an equivalence relation, otherwise we can take something stupid like $R' = Y \times Y$. So in some sense we again do the "obvious" thing and take $R'$ to be the smallest equivalence relation still containing $F(R)$. This is well defined because you can check that the intersection of equivalence relations is an equivalence relation. Then we can define the $f_*(\sim)$ to be the equivalence relation given by $R'$.

Really we could make this construction for any relation $S$ and take the smallest equivalence relation containing $S$ and call it the "equivalence relation generated by $S$" or maybe the "equivalencication" of $S$. Let's call this $S^\sim$ Explicitly this means taking the relation $S$, adding $(y,x)$ whenever $(x,y) \in S$ (the symmetric closure), adding $(x,x)$ for every $x$ (reflexive closure), and adding $(x,y)$ whenever there is a chain of related elements as in Martin Brandenburg's answer (the transitive closure). For this specific case, it is already symmetric but we do need to take the reflexive and transitive closure.

To address Paul's question in the comments, this construction gives us a way to compose pushforwards and pullbacks of relations. It is functorial. Specifically, if we have $f:X \to Y$ and $g:Y \to Z$, let $F$ as above and $G:Y \times Y \to Z \times Z$ given by $G(y,y') = (g(y),g(y'))$. Then the pullback of an equivalence relation $\sim$ on $Z$ given by $R \subset Z \times Z$ clearly satisfies $f^*g^*(\sim) = (gf)^*(\sim)$ since $F^{-1}G^{-1} = (GF)^{-1}$.

For the pushforward, it is less obvious. If $\sim$ is an equivalence relation on $X$ corresponding to $R \subset X \times X$, $g_*f_*(\sim) = (gf)_*(\sim)$ if and only if $(G\circ F)(R)^\sim = G(F(R)^\sim)^\sim$ which isn't too hard to check.

This actually fits into a general picture in math that happens quite often. What we really have here is in categorical terms an adjunction. We have the category $\mathcal{R}$ of relations on $X$ and the subcategory $\mathcal{EqR}$ of equivalence relations along with the forgetful functor $G: \mathcal{EqR} \to \mathcal{R}$ that just views an equivalence relation as a normal relation. Then the "equivalencication" above is the left adjoint of $G$. We have the obvious functorial pullback and pushforward of relations given by $F^{-1}(R)$ and $F(R)$ above and the we use the adjunction to define functorial pullbacks and pushfowards $f^*$ and $f_*$ on equivalence relations.

Sorry this answer is so long, I was on a plane with no internet and already had this page open so figured I could type a really in depth answer!

Answer 2

The only sensible definition is the following: $\cong $ is the smallest equivalence on $Y$ such that $x \sim x' \Rightarrow f(x) \cong f(x')$. Thus, we have $y \cong y'$ iff there is a chain $y=f(x_0)$, $f(x'_0)=f(x_1)$, $f(x'_1)=f(x_2)$, ..., $f(x_n)=y'$ with $x_k \sim x'_k$.

Answer 3

One way to think about this question is in terms of the fact equivalence relations are precisely obtained as kernels of maps between sets:

If $X \to S$ is a funcion, then defining $x \sim x'$ iff $f(x) = f(x')$ gives an equivalence relation on $X$, which we might call the kernel of $f$. Conversely, if $\sim$ is an equivalence relation on $X$, then it is obtained as the kernel of the canonical morphism $X \to X/\sim$ (the quotient of $X$ by $\sim$, or if you prefer, the set of equiv. classes of $\sim$).

Now suppose given $X \to Y$, and an equiv. rel'n $\sim$ on $Y$ arising as the kernel of $Y \to S$, then we have the composite $X \to Y \to S$, and its kernel is precisely the pull-back (what you call the preimage, but I would prefer to say pull-back, as in Dori Bejleri's answer) of $\sim$.

Now suppose instead that we have $f:X \to Y$, and a map $X \to S$ defining an equiv. rel'n $\sim$ on $X$. If the map $X \to S$ factors through $f$, then we get an induced map $Y \to S$, and it would be natural to call the kernel of this map the push-forward of $\sim$ under $f$.

Of course, in general this facorization won't be possible, but we can ask if there is some sort of minimal modification of $S$ (or, better, of $X \to S$), such that such a factorization is possible.

In other words, we are looking for a canonical set $S'$ equipped with $S \to S'$ and $Y \to S'$, such that the composites $X\to S \to S'$ and $X \to Y \to S'$ coincide. Such an $S'$ exists; it is the coproduct of $S$ and $Y$ over $X$ in the category of sets. Concretely, it is the quotient of the disjoint union $S \cup Y$ by the equivalence relation in which we identify $s \in S$ and $y \in Y$ if they arise as the image of the same element $x \in X$.

The natural map $Y \to S'$ determines an equiv. rel'n in $Y$ (its kernel), and this is the pushforward of $\sim$ to $Y$.

(You can check that this coincides with the constructions given in the other two answers. I thought it might be interesting to see a slightly different perspective.)