Category Theory
Zulip Server
Archive

You're reading the public-facing archive of the Category Theory Zulip server.
To join the server you need an invite. Anybody can get an invite by contacting Matteo Capucci at name dot surname at gmail dot com.
For all things related to this archive refer to the same person.

Stream: learning: questions

Topic: equivalence relationships preserved by endofunctors

David Egolf (Jan 05 2022 at 02:25):

Let $F: \mathsf{C} \to \mathsf{C}$ be a functor. Let $p$ be an equivalence relationship on the objects of $\mathsf{C}$. We say that $F$ preserves $p$ when $a \sim_p b \implies F(a) \sim_p F(b)$.
Two questions:

1. Given an endofunctor $F$, how can one discover which equivalence relationships it preserves?
2. Given an equivalence relationship $p$, how can one discover the endofunctors that preserve $p$?

Matteo Capucci (he/him) (Jan 05 2022 at 20:13):

Notice this is actually a question about maps of sets (for large enough notions of sets)!

Matteo Capucci (he/him) (Jan 05 2022 at 20:13):

For (1), what do you mean discover?

Matteo Capucci (he/him) (Jan 05 2022 at 20:14):

There might be some hope to characterize those ~ preserved by $F$ but enumerating them is a whole other can of worms

Joshua Meyers (Jan 05 2022 at 20:31):

Some easy equivalence relations preserved by all functors:

• Equal: $c=c'$
• Isomorphic: $c\cong c'$
• Homomorphically equivalent: $C(c,c')\neq\varnothing\wedge C(c',c)\neq\varnothing$
• Connected: $\exists\textrm{ zig-zag path } c\to c_1\leftarrow c_2\rightarrow c_3\leftarrow \cdots \to c_n\leftarrow c'$

David Egolf (Jan 05 2022 at 21:48):

Matteo Capucci (he/him) said:

Notice this is actually a question about maps of sets (for large enough notions of sets)!

Could you elaborate on what you mean by the above statement?
Matteo Capucci (he/him) said:

For (1), what do you mean discover?

Both characterization and enumeration sound interesting to me.

David Egolf (Jan 05 2022 at 21:51):

For context, I would like to think about what kinds of "properties" are preserved by an imaging process. Ideally this would help in the following context: I have an imaging process, and I want to figure out what I can detect about objects with it.

David Egolf (Jan 05 2022 at 22:40):

I think this is another equivalence relationship preserved by a functor $F$:
Let $a \sim b$ exactly when $F(a) = F(b)$.
This equivalence relationship is intuitively "sent to same observation by $F$".

David Egolf (Jan 05 2022 at 22:53):

Here's another one, assuming I didn't mix up something:
Let $a \sim b \iff F(a) \cong F(b)$.
First we show this is an equivalence relationship.
$F(a) \cong F(a) \implies a \sim a$ for any $a$.
If $a \sim b$, then $F(a) \cong F(b) \implies F(b) \cong F(a) \implies b \sim a$, with $a,b$ any objects in $C$.
If $a \sim b$ and $b \sim c$ for any objects $a,b,c$ in $C$, then we have $F(a) \cong F(b)$ and $F(b) \cong F(c)$ and so $F(a) \cong F(c)$, which implies $a \sim c$.

Now we show the equivalence relationship is preserved by $F$.
Let $a \sim b$. Then we have $F(a) \cong F(b)$, which implies $F(F(a)) \cong F(F(b))$, because functors send isomorphic objects to isomorphic objects. But $F(F(a)) \cong F(F(b))$ implies that $F(a) \sim F(b)$, by definition of our equivalence relationship. So, $a \sim b \implies F(a) \sim F(b)$.

David Egolf (Jan 05 2022 at 22:53):

This last equivalence relationship is intuitively "sent to isomorphic observations by $F$".

Morgan Rogers (he/him) (Jan 06 2022 at 10:02):

You can do the same for the other two examples that Joshua gave: since "homomorphically equivalent" and "connected" are preserved by any functor, $a \sim b \Leftrightarrow F(a) \sim_{\mathrm{hom.eq.}}F(b)$ or $a \sim b \Leftrightarrow F(a) \sim_{\mathrm{conn.}}F(b)$ are further equivalence relations preserved by $F$.

Sam Speight (Jan 06 2022 at 10:09):

You might find this paper interesting: http://www.tac.mta.ca/tac/volumes/1999/n11/n11.pdf

David Egolf (Jan 06 2022 at 16:46):

Morgan Rogers (he/him) said:

You can do the same for the other two examples that Joshua gave: since "homomorphically equivalent" and "connected" are preserved by any functor, $a \sim b \Leftrightarrow F(a) \sim_{\mathrm{hom.eq.}}F(b)$ or $a \sim b \Leftrightarrow F(a) \sim_{\mathrm{conn.}}F(b)$ are further equivalence relations preserved by $F$.

I suppose this procedure always works? Say $p$ is an equivalence relationship preserved by $F$. Then let $q$ be the equivalence relationship defined by $a \sim_q b \iff F(a) \sim_p F(b)$. We want to show $q$ is preserved by $F$.
Let's check that $q$ really is an equivalence relationship.

• $F(a) \sim_p F(a) \implies a \sim_q a$.
• $a \sim_q b \implies F(a) \sim_p F(b) \implies F(b) \sim_p F(a) \implies b \sim_p a$
• $a \sim_q b$ and $b \sim_q c$ implies $F(a) \sim_p F(b)$ and $F(b) \sim_p F(c)$, and this means $F(a) \sim_p F(c)$, which implies $a \sim_q c$

Let's check that $q$ is preserved by $F$.
$a \sim_q b \implies F(a) \sim_p F(b) \implies F(F(a)) \sim_p F(F(b))$, where we use the fact that $p$ is preserved by $F$.
Then $F(F(a)) \sim_p F(F(b) \implies F(a) \sim_q F(b)$ as desired.

Sam Speight said:

You might find this paper interesting: http://www.tac.mta.ca/tac/volumes/1999/n11/n11.pdf

That is interesting, thanks for sharing it!

David Egolf (Jan 06 2022 at 17:00):

Can we get more equivalence relationships using the strategy above?
Let $p$ be an equivalence relationship on $C$ preserved by $F$.
We saw above that the equivalence relationship $q$ defined by $a \sim _q b \iff F(a) \sim_p F(b)$ is also an equivalence relationship preserved by $F$.
Let us call the equivalence relationship generated from $p$ in this way by the name $F(p)$.

If $p$ is an equivalence relationship preserved by $F$, then so is $F(p)$.
This means that $F(F(p)) = F^2(p)$ is also an equivalence relationship preserved by $F$.
In general $F^n(p)$ should be an equivalence relationship preserved by $F$, for any positive integer $n$.

Let's see what $F^2(p)$ is for $a \sim_p b \iff a \cong b$.
$a \sim_{F^2 (p)} b \iff F(a) \sim_{F(p)} F(b) \iff F^2(a) \sim_p F^2(b) \iff F^2(a) \cong F^2(b)$.
It appears that "isomorphic after two applications of $F$" is another equivalence relationship on $C$ preserved by $F$. More generally, "eventually isomorphic after enough applications of $F$" should be another equivalence relationship preserved by $F$.

Morgan Rogers (he/him) (Jan 06 2022 at 17:28):

You've implicitly discovered that if one has any collection of equivalence relations preserved by $F$ then their intersection is also preserved by $F$. That lends some structure to your search ;)

Joshua Meyers (Jan 06 2022 at 17:56):

Another equivalence relation: the transitive closure of the relation $\exists f:c\to c',g:c'\to c$ such that either $f\circ g$ or $g\circ f$ is identity.

Joshua Meyers (Jan 06 2022 at 17:56):

In general, if $R$ is a relation preserved by $F$, its transitive closure is an equivalence relation preserved by $F$

Joshua Meyers (Jan 06 2022 at 17:57):

Another example: $c\sim c'$ for all $c,c'\in C$