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: equivalent categories and equivalence relations

David Egolf (May 26 2023 at 20:06):

I was reading about how a map from a set can induce a map from a suitable quotient of that set. I'm wondering if this situation can be generalized to a statement about equivalent categories.

My (short) question is at the end, preceded by some (longer) motivation.

As the motivating example (following Jacobson's "Basic Algebra I"), let $S$ be a set and let $E$ be an equivalence relationship on $S$. Let $\alpha: S \to T$ be a function to a set $T$ that is compatible with $E$, in the sense that if any $a$ and $b$ in $S$ are equivalent under $E$ then $\alpha(a) = \alpha(b)$. We then define a map $v: S \to S/E$ which sends $s \in S$ to its equivalence class $[s]$ under the equivalence relationship $E$. Given $\alpha$ and $v$, I believe there is then a unique $\alpha': S/E \to T$ so that $\alpha' \circ v = \alpha$. This map sends an equivalence class $[s]$ to the value $\alpha(s)$, and this is well-defined because if $s,t \in [s]$ then $\alpha(s) = \alpha(t)$.

I believe that the set $S$ together with the equivalence relationship $E$ induces a groupoid. The objects of the groupoid are the elements of $S$, and there is a morphism from $a$ to $b$ if $a$ is equivalent to $b$ under $E$. I'll refer to this induced category as $S_E$. We can also view $T$ as a discrete category, where the objects are the elements of $T$. Then a functor $\alpha: S_E \to T$ is a function from the set $S$ to the set $T$ such that if there is a morphism $m: a \to b$, then $\alpha(a) = \alpha(b)$. So, a function $\alpha: S \to T$ that is compatible with an equivalence relationship on $E$ corresponds to a functor $\alpha: S_E \to T$.

We can also view $S/E$ as a discrete category. I think $S/E$ and $S_E$ are equivalent categories, with $v: S_E \to S/E$ and some inclusion functor $u: S/E \to S_E$ (which sends each equivalence class to an element in that equivalence class) providing an equivalence.

David Egolf (May 26 2023 at 20:08):

So, I think the situation is as follows. We have a functor $\alpha: S_E \to T$, and a category $S/E$ which is equivalent to $S_E$ by an equivalence with data $v: S_E \to S/E$ and $u: S/E \to S_E$. Then there is a unique functor $\alpha': S/E \to T$ so that $\alpha' \circ v = \alpha$. I am wondering if this situation generalizes.

My question is this: If $v: S \to S'$ and $u: S' \to S$ is an equivalence of categories, and $\alpha :S \to T$ is a functor, is there a unique $\alpha'$ so that $\alpha' \circ v = \alpha$, or at least $\alpha' \circ v \cong \alpha$? My guess is the answer is "yes", with $\alpha' \cong \alpha \circ u$, but I don't understand the algebra for manipulating equivalences well enough to prove this yet.

John Baez (May 26 2023 at 20:26):

Everything you said about sets and equivalence relations sounds correct! And before getting into your question, I want to say that a lot of what you did generalizes from $\mathsf{Set}$ to other sufficiently nice categories. I believe any [[regular category]] will be good enough.

Let me list some examples, since the general definition is a bit scary! Examples of regular categories include the category of groups or abelian groups or vector spaces or graphs (defined the way category theorists define graphs, aka [[quivers]]).

John Baez (May 26 2023 at 20:27):

We can define and work with equivalence relations in any regular category $\mathsf{C}$! An equivalence relation on $X \in \mathsf{C}$ is a special sort of groupoid internal to $\mathsf{C}$ - so instead of getting groupoids from equivalence relations the way you just did, we define an equivalence relation to be a special sort of groupoid - but living in $\mathsf{C}$, not $\mathsf{Set}$.

In any regular category, given an object $X$ with an equivalence relation $E$ on it, we can get a new object $X/E$.

Furthermore, in any regular category, a morphism $f: X \to Y$ determines an equivalence relation $E$ on $X$. The naive idea is that elements of $X$ that get mapped by $f$ to the same element of $Y$ are equivalent. But we are able to express this idea without mentioning "elements"!

Then we can form the quotient object $X/E$, and $f$ becomes equal to the composite of two morphisms:

$X \to X/E \to Y$

The naive idea is that first we scrunch down elements of $X$ that map to the same element of $Y$, and then we map them to $Y$. This idea is made precise here.

John Baez (May 26 2023 at 20:34):

TL;DR: while you are interested in connecting equivalence relations on sets to category theory, there is also something else people like to do: generalize the theory of equivalence relations from $\mathsf{Set}$ to other categories!

John Baez (May 26 2023 at 20:36):

Okay, now your actual question:

David Egolf said:

My question is this: If $v: S \to S'$ and $u: S' \to S$ is an equivalence of categories, and $\alpha :S \to T$ is a functor, is there a unique $\alpha'$ so that $\alpha' \circ v = \alpha$, or at least $\alpha' \circ v \cong \alpha$? My guess is the answer is "yes", with $\alpha' \cong \alpha \circ u$, but I don't understand the algebra for manipulating equivalences well enough to prove this yet.

John Baez (May 26 2023 at 20:39):

A functor $\alpha'$ with $\alpha' \circ v = \alpha$ may not exist. Find a counterexample where all the categories involved have at most 2 objects!

John Baez (May 26 2023 at 20:40):

This is just an example of a general lesson: equations between functors are evil; natural isomorphisms are better.

Morality aside, if you are working with equivalences, which are wisely not defined using equations between functors, you will have trouble getting equations to work.

John Baez (May 26 2023 at 20:42):

A functor $\alpha'$ with $\alpha' \circ v \cong \alpha$ does exist, and you guessed what it could be: $\alpha' = \alpha \circ u$. Check that this works!

(This equation is not evil since I'm defining $\alpha'$ this way! [[Definitional equality]] is okay.)

John Baez (May 26 2023 at 20:44):

But a functor $\alpha'$ with $\alpha' \circ v \cong \alpha$ is typically not unique. Morally, that's because uniqueness here would be stating an equation between functors, and that's evil. But it's good to find a small counterexample.

John Baez (May 26 2023 at 20:45):

But this is okay, since a functor $\alpha'$ with $\alpha' \circ v \cong \alpha$ is unique up to natural isomorphism.

David Egolf (May 26 2023 at 21:18):

Awesome, thanks for your very interesting response! When I have energy, I'll have to take a look at several of the things you've mentioned, and type up something about them in this thread.

David Egolf (May 26 2023 at 22:42):

John Baez said:

A functor $\alpha'$ with $\alpha' \circ v = \alpha$ may not exist. Find a counterexample where all the categories involved have at most 2 objects!

Let $S$ be a category with two isomorphic objects and the minimum of morphisms, and let $S'$ be category with a single object and just its identity morphism. $S$ and $S'$ are equivalent. Now let $T=S$. We have a functor $\alpha$ from $S$ to $T$ (the identity functor) that has two objects in its image. However, there is only one object in $S'$ so there can be no functor $\alpha': S \to T$ so that $\alpha = \alpha' \circ v$ for some $v: S \to S'$ that is part of an equivalence of $S$ and $S'$.

It's interesting to notice that we can add or delete objects from an isomorphism class of objects and still obtain an equivalent category.

David Egolf (May 26 2023 at 22:52):

John Baez said:

A functor $\alpha'$ with $\alpha' \circ v \cong \alpha$ does exist, and you guessed what it could be: $\alpha' = \alpha \circ u$. Check that this works!

Let $\alpha' = \alpha \circ u$. Then $\alpha' \circ v = (\alpha \circ u) \circ v = \alpha \circ (u \circ v)$.
And this is where I get stuck. I know that $u \circ v \cong Id_S$, so what I want to say next is that $\alpha ' \circ v = \alpha \circ (u \circ v) \cong \alpha \circ (Id_S) = \alpha$.

I'm guessing that for functors in general if $F \cong G$ then $H \circ F \cong H \circ G$. I'll have to draw some commutative squares for natural isomorphisms and see if I can check this, though!

John Baez (May 26 2023 at 23:49):

David Egolf said:

It's interesting to notice that we can add or delete objects from an isomorphism class of objects and still obtain an equivalent category.

Yes. In fact that's the only way to get equivalent categories.

John Baez (May 26 2023 at 23:53):

David Egolf said:

I'm guessing that for functors in general if $F \cong G$ then $H \circ F \cong H \circ G$. I'll have to draw some commutative squares for natural isomorphisms and see if I can check this, though!

This is definitely a good thing to show! Here's one way to approach it: if you have functors $F,G: \mathsf{C} \to \mathsf{D}$, a natural transformation $\alpha : F \Rightarrow G$, and a functor $H: \mathsf{D} \to \mathsf{E}$ you can cook up a natural transformation

$H \bullet \alpha: H \circ F \to H \circ G$

This trick is called [[whiskering]] and you can show it obeys

$H \bullet (\alpha \beta) = (H \bullet \alpha)(H \bullet \beta)$

Here I'm using plain old juxtaposition to denote composition of natural transformations.

John Baez (May 26 2023 at 23:54):

I hope you see why this implies what you're trying to show now.

John Baez (May 26 2023 at 23:56):

After you learn how to compose functors and how to compose natural transformations, the next thing to study is whiskering of functors by natural transformations, and the rules obeyed by whiskering. Above I'm talking about "right whiskering", but there's also "left whiskering". Once you have all this material under control you'll be able to do a lot with functors and natural transformations!

Mike Shulman (May 27 2023 at 10:51):

John Baez said:

We can define and work with equivalence relations in any regular category $\mathsf{C}$! An equivalence relation on $X \in \mathsf{C}$ is a special sort of groupoid internal to $\mathsf{C}$ - so instead of getting groupoids from equivalence relations the way you just did, we define an equivalence relation to be a special sort of groupoid - but living in $\mathsf{C}$, not $\mathsf{Set}$.

In any regular category, given an object $X$ with an equivalence relation $E$ on it, we can get a new object $X/E$.

Furthermore, in any regular category, a morphism $f: X \to Y$ determines an equivalence relation $E$ on $X$. The naive idea is that elements of $X$ that get mapped by $f$ to the same element of $Y$ are equivalent. But we are able to express this idea without mentioning "elements"!

Then we can form the quotient object $X/E$, and $f$ becomes equal to the composite of two morphisms:

$X \to X/E \to Y$

So, the precise conditions on the category here are a bit confusing.

1. We can define internal equivalence relations (sometimes called [[congruences]]) in any category with finite limits.
2. To construct the quotient $X/E$ of an arbitrary internal equivalence relation, the category has to be not just regular but a (Barr) [[exact category]].
3. However, the equivalence relation determined by a morphism $f$ (sometimes called its [[kernel pair]]) exists in any category with finite limits, and it has a quotient in any regular category.

Essentially, a regular category is one that has well-behaved "image factorizations" $X \twoheadrightarrow X/E \hookrightarrow Y$, which in particular entails that the intermediate object $X/E$ is the quotient of the kernel pair of the morphism. But it may not have quotients of arbitrary equivalence relations that don't arise as the kernel pair of anything.

David Egolf (May 28 2023 at 20:58):

John Baez said:

David Egolf said:

I'm guessing that for functors in general if $F \cong G$ then $H \circ F \cong H \circ G$. I'll have to draw some commutative squares for natural isomorphisms and see if I can check this, though!

This is definitely a good thing to show! Here's one way to approach it: if you have functors $F,G: \mathsf{C} \to \mathsf{D}$, a natural transformation $\alpha : F \Rightarrow G$, and a functor $H: \mathsf{D} \to \mathsf{E}$ you can cook up a natural transformation

$H \bullet \alpha: H \circ F \to H \circ G$

This trick is called [[whiskering]] and you can show it obeys

$H \bullet (\alpha \beta) = (H \bullet \alpha)(H \bullet \beta)$

Here I'm using plain old juxtaposition to denote composition of natural transformations.

Assuming that these categories $H,F,G$ are small categories, so that they are objects in the strict 2-category $\mathsf{Cat}$, we have a notion of horizontal composition of natural transformations available to us. I tried setting $H \bullet \alpha: H \circ F \to H \circ G$ as $id_H * (\alpha \circ \beta)$ where $id_H$ is the identity natural transformation from $H$ to $H$, $*$ denotes horizontal composition, and $\circ$ denotes vertical composition. Then I think I was able to show that $H \bullet (\alpha \beta) = (H \bullet \alpha) \circ (H \bullet \beta)$ is implied by the fact that horizontal composition is a functor. (I think this is a special case of the interchange law).

Now we want to show that if $F \cong G$ then $H \circ F \cong H \circ G$. Since $F$ and $G$ are naturally isomorphic, there is an isomorphism $\phi: F \to G$ with an inverse $\phi^{-1}: G \to F$. If we use the interchange law (or what we just figured out about whiskering) we see that $id_H * (\phi^{-1} \circ \phi) = (id_H * \phi^{-1}) \circ (id_H * \phi)$. Using the functoriality of horizontal composition, we find that $id_H * (\phi^{-1} \circ \phi) = id_H*id_F = id_{H \circ F}$. That's half of what we need to do to show that $H \circ G \cong H \circ F$. The other half should follow analogously by composing $\phi$ after $\phi^{-1}$.

David Egolf (May 28 2023 at 21:00):

Horizontal composition has always scared me. So it's good to start getting over that fear a bit. It seems very useful!

John Baez (May 28 2023 at 21:07):

Yes, all this looks good!

John Baez (May 28 2023 at 21:09):

When you understand the rules governing horizontal and vertical composition of natural transformations - there aren't many! - and the rules governing whiskering - which is a special case! - then you're really up and running when it comes to dealing with $\mathbf{Cat}$.

(Your remarks about small categories is not really relevant here; all this stuff works for large categories too, you just have to pay the cops a bribe to let you do it.)