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: Category equivalence and equivalence classes

Jencel Panic (Jun 08 2023 at 12:52):

I was thinking about the following:

Given a category $A$ , if we can construct $A'$ the category of equivalence classes in $A$, using isomorphism as an equivalence relation, then it seems that we have the theorem that two arbitrary categories $C$ and $D$ are equivalent iff $C'$ is isomorphic to $D'$.

Is this legit?

I seem to have seen this equivalence class category, but only for preorders, I think.

Tim Hosgood (Jun 08 2023 at 13:36):

I think you'll find a counter example pretty quickly when you think about categories as preorders which can have multiple relations between objects, instead of just some yes/no. For example, consider the category with one point and just the identity morphism, and the category with just one point but with one (or more) non-trivial self-isomorphism(s). Then "the" functor from the former to the latter will never be full (i.e. it won't be surjective on morphisms), and any functor from the latter to the former will never be faithful (i.e. it won't be injective on morphisms), so they're not equivalent as categories, but their category of equivalence classes are the same: a single point in each.

Josselin Poiret (Jun 08 2023 at 14:02):

related is the notion of a [[skeleton]] of a category

Martti Karvonen (Jun 08 2023 at 15:06):

Two categories are equivalent iff their skeletons are isomorphic

Jacques Carette (Jun 08 2023 at 15:45):

That's true in the presence of the axiom of choice. You'll find that quite a bit more difficult to prove otherwise...

Martti Karvonen (Jun 08 2023 at 16:01):

I guess the issue is that you can't prove that an arbitrary cat has a skeleton without AC?

Jacques Carette (Jun 08 2023 at 16:08):

Correct: consider an arbitrarily large indiscrete category. It's contractible. But you still have to "choose" an object to contract it to. You can likewise be forced to choose an arbitrarily large number of things.

Kevin Arlin (Jun 08 2023 at 16:31):

I think it's just a bit unclear what "the category of equivalence classes" was supposed to be here, and trying to construct that more explicitly might be clarifying.

Jencel Panic (Jun 08 2023 at 16:37):

Yes, it probably can be defined in a ways that work and ones that doesn't.

What I had in mind was basically the same concept as that of the skeleton of a category, only instead of taking one object in each isomorphism class to take the whole class.
image.png

Kevin Arlin (Jun 08 2023 at 16:59):

Yes, but I'm suggesting you try to spell that all the way out to notice something enlightening. (What are the morphisms between two equivalence classes, and how can you show that the set of morphisms is well-defined if you switch objects representing a class?)

Morgan Rogers (he/him) (Jun 08 2023 at 19:00):

@Jacques Carette that's a bad example, I don't need the axiom of choice to make a single choice, but I guess the point was the end of the sentence that as soon as there are infinitely many isomorphism classes we need some version of AC to deduce that we can collapse them all in a reversible way.

Jencel Panic (Jun 09 2023 at 07:47):

@Kevin Arlin I guess the main reason it works with skeletons, but not equivalence classes directly is that with skeletons you can represent all morphisms that go between objects that are part of the equivalence class as a morphisms between your object of choice and itself, whereas if you go with equivalence classes there is no simple way to represent them.

Jencel Panic (Jun 09 2023 at 07:49):

image.jpg

John Baez (Jun 09 2023 at 14:38):

I think most people agree that taking a category C and trying to form a new category C' where objects are equivalence classes of objects of C is an idea that runs into problems when you try to make it precise, and that taking a [[skeleton]] is the closest thing that actually works (thought it requires being able to choose a representative of each isomorphism class, which fails in some contexts). But I don't actually know a theorem that makes precise the sense in which this idea inevitably runs into problems.

John Baez (Jun 09 2023 at 14:44):

Maybe you could try to do this: assume $F: \mathbf{Cat} \to \mathbf{Cat}$ is a 2-functor that maps any category $C$ to some category $F(C)$ for which the set of objects is the set of isomorphism classes of objects of $C$. (There are various 2-functors like this.) Also assume that $F(C)$ is equivalent to $C$ for all $C$. Is that enough to get a contradiction? If not, maybe also assume there is a natural equivalence

$\alpha: 1_{\mathbf{Cat}} \Rightarrow F$.

Is that enough to get a contradiction? If not, assume also that for each $C \in \mathbf{Cat}$,

$\alpha_C : C \to F(C)$

sends each object of $C$ to its isomorphism class. Is that enough to get a contradiction?

John Baez (Jun 09 2023 at 14:50):

If not, maybe also assume that $\alpha_C$ sends each functor $f: C \to D$ to a functor $F(f) : F(C) \to F(D)$ that maps each isomorphism class $[c]$ to the isomorphism class $[f(c)]$. Is that enough to get a contradiction?

John Baez (Jun 09 2023 at 14:51):

And so on: keep on listing the desired properties of this desired 2-functor $F$ until you're able to prove a contradiction, and thus make precise the sense in which this idea is a bad idea.

John Baez (Jun 09 2023 at 14:52):

It could be that you get a contradiction only if you assume the negation of the axiom of choice.

Mike Shulman (Jun 09 2023 at 15:02):

Well, if you assume AC, then it's possible to define a skeleton of C whose objects are the isomorphism classes of C.

John Baez (Jun 09 2023 at 15:34):

Okay, so you're saying that in this outline of mine you'll only hit a contradiction if you assume some anti-choice, e.g. assume that it's not possible to find, for every category $C$, a map sending isomorphism classes of objects of $C$ to objects of $C$, that's a left inverse to the map sending objects to their isomorphism classes.

Mike Shulman (Jun 09 2023 at 15:57):

Yeah, I think so.

Kevin Arlin (Jun 09 2023 at 16:45):

Yeah, I don't know how to do this myself but I would hope you could show that in some models of set theory there exists a specific category $C$ such that the set of isomorphism classes of its objects admits no category structure equivalent to $C.$

John Baez (Jun 09 2023 at 16:56):

By the way, this is fairly easy (and also important) if instead of working with ordinary small categories (which are "internal to the category of sets") we look at categories internal to something else, like categories internal to the category of smooth manifolds.

John Baez (Jun 09 2023 at 17:00):

All this stuff about "failures of the axiom of choice" becomes a lot more vivid, at least to me, if we leave the category of sets and go to categories that topologists and differential topologists care about.

Mike Shulman (Jun 09 2023 at 17:22):

We don't need to talk about specific models at all -- we can just show that if such a thing can be done for every category $C$, then we can prove AC. This then implies contrapositively that in a model where AC fails, our statement must be false. And this is pretty easy: for any surjection $p:E\to B$, let $B$ be a discrete category and let $E$ be a category in such a way that $p$ is fully faithful. Then $B$ is isomorphic to the set of isomorphisms classes of $E$, so if the latter were equivalent to $E$, then $p$ would have a section.

Kevin Arlin (Jun 09 2023 at 17:26):

Ahh, nice, it's the same thing as saying that if every ffeso functor is an equivalence then AC holds, which somehow feels more obvious.

John Baez (Jun 09 2023 at 18:18):

Nice - I was figuring that out that as I ate breakfast. By the way, is "ffeso" something people actually write? I've seen "eso" and "bijo".

Mike Shulman (Jun 09 2023 at 18:20):

I haven't seen "ffeso" or "bijo", though I have seen "bo" and "bo+ff" and "ff+eso".

John Baez (Jun 09 2023 at 18:25):

Those are fun words to pronounce, though probably nobody actually says them.

Jencel Panic (Jun 10 2023 at 16:33):

Thanks for the responses.

Jencel Panic (Jun 29 2023 at 06:30):

In general, it seems like equivalence is much easier to define for pre-orders than for categories. You can just say that two functors $F$ and $G$ are isomorphic if $a \cong F(G(a))$

Jencel Panic (Aug 21 2023 at 12:50):

For future reference, here is a summary of my findings on this topic:

• Two categories are equivalent when there is a functor that is fully faithful and essentially surjective.

• Two preorders are equivalent when there is an essentially surjective functor (as all functors in orders are fully faithful).

• If we have an essentially surjective functor, then the categories' equivalence classes are isomorphic.

• If we have an fully-faithful and essentially surjective functor, then the categories' skeletons are isomorphic (and the categories are equivalent).

Kevin Arlin (Aug 21 2023 at 15:25):

It's not quite clear what you mean by "the categories' equivalence classes."

James Deikun (Aug 21 2023 at 15:53):

Seems to be "set/class of isomorphism classes".

John Baez (Aug 21 2023 at 16:08):

Jencel Panic said:

• Two preorders are equivalent when there is an essentially surjective functor [....]

I don't think so. Let 1 stand for a preorder with just one object. Then for any preorder P there exists a unique functor from P to 1. This is essentially surjective whenever P has at least one object. But that does not imply that every preorder with at least one object is equivalent to 1.

• If we have an essentially surjective functor, then the categories' equivalence classes are isomorphic.

The same counterexample disproves this claim.

John Baez (Aug 21 2023 at 16:14):

The rest of the claims in your bulleted list look correct to me.

This is an example of why it's very good for us to summarize what we've learned in discussions here, but maybe not so good to mark topics as "resolved".

Jencel Panic (Aug 21 2023 at 20:00):

Thanks for the response, @John Baez

but maybe not so good to mark topics as "resolved".

Just to make sure, is this a joke? I am getting it as such.

Jencel Panic (Aug 21 2023 at 20:02):

Or you meant to say that someone might get confused by the fact that the topic is resolved by thinking that everything is correct?

John Baez (Aug 21 2023 at 20:43):

It's not a joke. I've been trying to convince people here that the ability to "resolve" topics on Zulip is good for teams of programmers who want to know which issues with their software have been resolved, but not so good in math. In math almost any discussion is potentially endless. Even when it seems like a question has been settled there can be useful new points of view. And if someone declares a question is officially "resolved", it may reduce the chance that people will look at the discussion and catch mistakes.

Josselin Poiret (Aug 22 2023 at 13:50):

John Baez said:

It's not a joke. I've been trying to convince people here that the ability to "resolve" topics on Zulip is good for teams of programmers who want to know which issues with their software have been resolved, but not so good in math. In math almost any discussion is potentially endless. Even when it seems like a question has been settled there can be useful new points of view. And if someone declares a question is officially "resolved", it may reduce the chance that people will look at the discussion and catch mistakes.

I wouldn't say it's necessarily a math vs. programming question, you've surely heard of bike-shedding, and that can apply equally well to math or to code imo

Morgan Rogers (he/him) (Aug 22 2023 at 14:07):

I hadn't heard of bikeshedding. Apparently it refers to "Futile expenditure of time and energy in discussion of marginal technical issues."
Since the point of this stream is to discuss technical issues (and there is no objective point of view from which to judge them as marginal...), time and energy expended to that end is unlikely to be futile.

Jason Erbele (Aug 22 2023 at 14:08):

I hadn't heard of bikeshedding, either. You beat me to the clarification by a few seconds, Morgan. (:

Jencel Panic (Aug 22 2023 at 15:05):

@John Baez Noted, I agree that marking topics as resolved does not make sense for the way discussions are held here, even for the #questions channel.

Jencel Panic (Aug 22 2023 at 15:14):

John Baez said:

Jencel Panic said:

• Two preorders are equivalent when there is an essentially surjective functor [....]

I don't think so. Let 1 stand for a preorder with just one object. Then for any preorder P there exists a unique functor from P to 1. This is essentially surjective whenever P has at least one object. But that does not imply that every preorder with at least one object is equivalent to 1.

Whoa, I didn't see that coming :)
Now I am wondering whether there is a way to make it correct by adding more conditions. I will look into it.

Morgan Rogers (he/him) (Aug 22 2023 at 17:01):

A map between preorders is always faithful, but not necessarily full. You need the map to be order-reflecting as well as order-preserving to get an equivalence!

David Egolf (Aug 22 2023 at 17:13):

I found it interesting to figure out why the unique functor from a discrete preorder 2 (with two objects) to a discrete preorder 1 (with one object) isn't full. I think this is because there's no morphism between the two objects in 2, but there is a morphism between the images of these objects in 1.

John Baez (Aug 22 2023 at 20:10):

I think this is a nice example of why you usually shouldn't say "a morphism between two objects", but instead say "a morphism from one object to another". The direction matters a lot!

John Baez (Aug 22 2023 at 20:12):

There's definitely a morphism between the two objects of 2. Namely, there's a morphism from the first object to the second object. But there's not a morphism from the second object to the first object. And that's why the functor from 2 to 1 is not full!

John Baez (Aug 22 2023 at 20:13):

Saying "there's a morphism between two objects" is a bit like saying "a gunshot was exchanged between Fred and John". It leaves you wondering about something very important: who shot whom!

David Egolf (Aug 22 2023 at 20:16):

Note that I define 2 as a discrete preorder with two objects. So, there are no morphisms between the two objects of my 2. Maybe there's a better name I could have given this category!

John Baez (Aug 22 2023 at 20:19):

Oh, yikes! Well, you are using 2 differently than most category theorists. Often it means the ordinal 2, which is the poset

$0 \to 1$

John Baez (Aug 22 2023 at 20:22):

The unique a functor from this 2 of mine to 1 isn't full, even though "there's a morphism between the two objects in 2".

David Egolf (Aug 22 2023 at 20:24):

Thanks for pointing that out! That's another nice example that helps me better understand what fullness looks like.

John Baez (Aug 22 2023 at 20:24):

Yes, I think it's cute!

But if I'd been reading more carefully I would have seen you said your 2 was a discrete preorder, so I can't accuse you of not explaining yourself clearly!

Jason Erbele (Aug 22 2023 at 22:40):

I have seen the category with two objects and no morphisms aside from the requisite identity morphisms referred to as $1+1$. Taking $2$ to be the ordinal as described by John, we find that in category theory, $1+1$ is not equivalent to $2$, which is also cute, but takes a bit of getting used to.

John Baez (Aug 23 2023 at 06:30):

At least there's a functor $1 + 1 \to 2$ that's bijective on objects. So when you go to math grad school you learn that

$1 + 1 = 2$

is not quite right: there's a map going one way, but it doesn't have an inverse. :upside_down:

Jules Hedges (Aug 23 2023 at 09:52):

On posets there's an "ordinal sum" operation (disjoint union then make everything on the left less than everything on the right) that does satisfy $1 \oplus 1 = 2$. I never checked it extends to a monoidal product on $\mathbf{Cat}$, but I think it probably should

Jules Hedges (Aug 23 2023 at 09:54):

Personally speaking I prefer to always define $2$ as $1 + 1$ whenever that has a reasonable interpretation. I call the category with 2 objects and 1 nontrivial morphism "$\to$", which has the nice property that if you write $G^H$ for the exponential in $\mathbf{Cat}$, ie. the category whose objects are functors $H \to G$, then the arrow category of $G$ is $G^\to$

John Baez (Aug 23 2023 at 10:41):

I agree that $\to$ is clearer than 2, but $\to\to\to\to\to\to$ is harder to write than 7, and when we get to $\omega$ I think ordinal notation is definitely better.

John Baez (Aug 23 2023 at 10:42):

But I'm just kidding: people who study simplicial sets write [7] for the ordinal $\to\to\to\to\to\to$, not 7. So you can do that.

John Baez (Aug 23 2023 at 10:46):

Jules Hedges said:

On posets there's an "ordinal sum" operation (disjoint union then make everything on the left less than everything on the right) that does satisfy $1 \oplus 1 = 2$. I never checked it extends to a monoidal product on $\mathbf{Cat}$, but I think it probably should.

We discussed this recently here: to add two categories $C$ and $D$ this way, take the collage of the terminal profunctor from $C$ to $D$. On the nLab it's called the ordinal sum of categories.

Mike Shulman (Aug 23 2023 at 18:45):

I also prefer the meaning $2=1+1$. Sometimes I write $\to$ for the walking arrow, other times $\mathbf{2}$ or \mathbb{2} (the latter from package bbold), and the latter generalize better to higher ordinals.

Mike Shulman (Aug 23 2023 at 18:45):

By the way, the simplicial notation is actually offset by one: the walking arrow is $[1]$, not $[2]$.