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: theory: category theory

Topic: Category theoretic definitions of a category

Ralph Sarkis (Dec 07 2023 at 19:10):

Inspired by Matteo's post I am thinking of ending my intro course to category theory by defining a category using the category theoretic tools we learned in class. So I am fishing for other similar definitions that could be fun to give without too much background (you can look at the contents of my book to see what we had time to do.

Ralph Sarkis (Dec 07 2023 at 19:11):

The example in Matteo's post is already a bit out of reach because we only talked about strict 2-categories, but I could sweep some things under the rug (I am only trying to end the semester with some fun stuff).

Simon Burton (Dec 07 2023 at 21:32):

Yeah you don't have to mention spans, just the object of composable pairs as a pullback, and then the composition morphism, and associativity diagrams, etc. And then at some point you can say, but wait we don't need to do this in the category of sets, we can do this in any category with pullbacks...

John Baez (Dec 07 2023 at 22:16):

I think that could be a nice grand finale for your class, Ralph: follow Simon's suggestion, leading up to the definition of a category internal to any category with pullbacks. Then maybe look briefly at categories internal to Grp, or Vect, or Cat, or some other categories the students know.

John Baez (Dec 07 2023 at 22:19):

The concept of a category internal to Cat is pretty mind-blowing at first, which can be unpleasant to some students, so one approach is to just say that these are interesting things, and they're called "double categories", and let the braver students work out what they are if they feel like it.

John Baez (Dec 07 2023 at 22:20):

I remember when I first learned about internal categories, the phrase "the object of objects" scared and confused me.

John Baez (Dec 07 2023 at 22:22):

At this stage of development it can be rather unpleasant to hear someone say "the object of objects of a category internal to Cat is a category" - you feel like you're in an echo chamber!

Mike Shulman (Dec 07 2023 at 22:22):

I tend to think it's easier to first get used to other kinds of internal structures that only involve structure on a single object, like an internal group object leading to topological groups, Lie groups, etc.

John Baez (Dec 07 2023 at 22:24):

Yes, indeed! I learned this stuff from someone who seemed to be following the philosophy "whatever doesn't kill you makes you stronger".

John Baez (Dec 07 2023 at 22:25):

But I think a bit of this scary stuff can be quite exciting - in small doses.

Mike Shulman (Dec 07 2023 at 22:26):

I think there's a certain kind of person who gets unhealthily excited by this sort of thing, and another kind of person who gets unhealthily turned off by it.

John Baez (Dec 07 2023 at 22:26):

I guess I'm the former.

Mike Shulman (Dec 07 2023 at 22:30):

The other day I was talking to someone who was concerned by the apparent circularity of definitions like this: how can we "define" a category to be a monad in the bicategory of spans when we already need to know what a category is in order to define a bicategory?

John Baez (Dec 07 2023 at 22:34):

Yes, I think in category theory more than some other subjects one sees this rhetorical move of calling a theorem of this sort a "definition", which produces the appearance of circularity.

Mike Shulman (Dec 07 2023 at 22:35):

Are there similar sorts of theorems in other subjects that people just don't call "definitions"?

John Baez (Dec 07 2023 at 22:36):

I think so. I think the word "characterization" is often used.

Ralph Sarkis (Dec 08 2023 at 09:59):

I think I would like to present the "category" $\mathbf{Span}(\mathbf{Set})$ and talk about monads there because it makes uses of more things we have seen to arrive at the first definition of the course (pedagogically, I am not trying to teach them about internal categories, I am rather looking at making a lasting impression).

Ralph Sarkis (Dec 08 2023 at 10:01):

I could also do this with $\mathbf{Mat}(\mathbf{Set})$ right?

Ralph Sarkis (Dec 08 2023 at 10:01):

But I was also looking for other such definitions of categories. Looking for "a category is just a" or "categories are just" on Google only yielded the monads in Span(Set) example.

Graham Manuell (Dec 08 2023 at 11:09):

Ralph Sarkis said:

I could also do this with $\mathbf{Mat}(\mathbf{Set})$ right?

Yes. This generalises to enriched categories instead of internal categories.

Nathanael Arkor (Dec 08 2023 at 11:20):

Ralph Sarkis said:

But I was also looking for other such definitions of categories. Looking for "a category is just a" or "categories are just" on Google only yielded the monads in Span(Set) example.

Categories may also be described as polynomial comonads, and this doesn't require any 2-categorical machinery.

Nathanael Arkor (Dec 08 2023 at 11:21):

For instance, David Spivak has a talk explaining this (the result is due to Ahman and Uustalu): https://www.youtube.com/watch?v=2mWnrgPIrlA

Bruno Gavranović (Dec 08 2023 at 15:31):

Mike Shulman said:

The other day I was talking to someone who was concerned by the apparent circularity of definitions like this: how can we "define" a category to be a monad in the bicategory of spans when we already need to know what a category is in order to define a bicategory?

An answer to this question that resonates with me is from the essay What is Category Theory?:

Category theory provides an overall conceptual frame for mathematics. This frame, it must be said, has no “starting point” or “basement”. One should imagine that we are building a space station, not a skyscraper or any other similar building that has to stand on solid grounds. Building in space must be done according to general principles, according to general laws of physics and engineering, but the construction does not have to have a definite orientation, an up and a down, a foundation in a geocentric sense of that expression. Perhaps category theory is forcing us to make a conceptual Copernican revolution.

When teaching, choosing a trajectory through these definitions always seems dependent on the context of the person learning it; and it doesn't seem to me that there is one right answer. (Maybe this is not the most helpful answer, but I found this a useful perspective to have in mind!)

Mike Shulman (Dec 08 2023 at 15:53):

Ralph Sarkis said:

I could also do this with $\mathbf{Mat}(\mathbf{Set})$ right?

Yes, although $\mathbf{Mat}(\mathbf{Set})$ is equivalent to $\mathbf{Span}(\mathbf{Set})$.

Mike Shulman (Dec 08 2023 at 16:00):

Another bicategory that's equivalent to both of them is the locally-full sub-2-category of $\mathbf{Cat}$ whose objects are slices $\mathbf{Set}/A$ and whose morphisms are "linear functors", those isomorphic to one of the form $F(X)_b = M_{a,b} \bullet X_a$ for some $A\times B$ matrix of sets $M$. This is an instance of "Lack's coherence theorem": "every naturally occurring bicategory is equivalent to a naturally-occurring 2-category".

Mike Shulman (Dec 08 2023 at 16:02):

As for other definitions of category, how about "a category is an algebra for the paths monad on the category of quivers"?

Mike Shulman (Dec 08 2023 at 16:13):

Of course there's "a category is a simplicial set satisfying the strict Segal condition" or "with unique inner horn fillers".

John Onstead (Dec 09 2023 at 01:43):

There are a lot of interesting ideas in the "What is Category Theory" essay and I agree with many points, though I do happen to disagree with this one, that things like category theory can lack foundations. Generally, when some circularity becomes apparent in any system of two constructions, the circularity can usually be resolved by identifying a third construction which underlies both of the others. The circularity is then explained simply as the fact both of the other constructions are just different "faces" this third, more underlying structure is wearing. Certain circularities between limits/colimits, Kan extensions, adjoint functors, ends/coends, and so on can for instance be explained as them all being different "faces" of the concept of universal properties and morphisms, which is something the nlab notes on its page for universal constructions. One of the goals of a project I am working on is to find this third construction underlying the circularity between monads and categories, but I have yet to settle on a definite construction yet, or even if such a thing can be defined.

Astra Kolomatskaia (Dec 09 2023 at 04:01):

There is a series of variations of higher categories inspired defenitions of something like a category, albeit with various weakenings. My personal favourite is the following [which drops the completeness condition and gives the collection of quasi-categories that are homotopy equivalent to nerves of categories under the restriction of being 2-coskeletal and Prop valued in the top dimension]:
Screenshot-2023-12-08-at-10.56.54-PM.png

Astra Kolomatskaia (Dec 09 2023 at 04:04):

An example of a weak category is the the fundemental groupoid of some space [or fundemental category of some directed space], constructed without passing to homotopy equivalence classes of paths and instead encoding the relation of homotopy in the data of the 2-cells

Astra Kolomatskaia (Dec 09 2023 at 04:15):

The way that I would pitch this definition is that it is a formulation of [non-complete] categories that does not refer to equality [supposing that we can talk about propositions without equality]. This works in theories that don't have a primitive notion of equality by way of having the user specify bespoke data specifying what equality should be. One then asks: What are the conditions necessary for user specified data to define a notion of equality?, and the inner horn filling conditions provide the answer

Astra Kolomatskaia (Dec 09 2023 at 04:16):

The fact that identities and composition are given as functions means that this definition satisfies the Segal condition

Ralph Sarkis (Dec 09 2023 at 07:37):

This is a weak category because associativity does not hold? Or do the horn fillers imply associativity?

Ralph Sarkis (Dec 09 2023 at 16:16):

In order to be as rigorous as possible, I was trying to change $\mathbf{Span}(\mathbf{Set})$ for the category $\mathbf{MRel}$ of sets and multirelations which is a strict 2-category. However, this "strictification" step (I am not sure if it is formally a strictification) loses some information, so we find that a monad in $\mathbf{MRel}$ is a quiver/directed graph where:

• each node $X$ has a loop $X \to X$, and
• there are more arrows $X\to Z$ than pairs of arrows $(X \to Y, Y \to Z)$.

These properties are kind of proof irrelevant reflexivity and transitivity of the quiver.

Ralph Sarkis (Dec 09 2023 at 16:24):

A multirelation from $A$ to $B$ is a multisubset of $A \times B$, i.e. a map $m: A \times B \to \N$ where $m(a,b)$ is the number of times $(a,b)$ is contained the multirelation.

John Baez (Dec 09 2023 at 16:28):

Are you at all worried about how natural numbers are only good for classifying finite sets up to isomorphism? If you're trying to define a notion of multirelation that acts sort of like a span of arbitrary sets, you'd have to replace $\mathbb{N}$ by $\mathrm{Card}$, the rig of cardinals.

John Baez (Dec 09 2023 at 16:28):

Or, alternatively, go finitistic and require $A$ and $B$ be finite.

John Baez (Dec 09 2023 at 16:29):

I think if you allow $A$ and $B$ to be infinite yet use $m: A \times B \to \mathbb{N}$, then composing multirelations will give infinite sums whose values may no longer lie in $\mathbb{N}$.

Ralph Sarkis (Dec 09 2023 at 16:37):

Hmm, ok, restricting everything to be finite would give finite quivers which are "kind of" reflexive and transitive. But in this paper, they only use $\N^{\omega}$ which is $\N$ extended with a top element (so when the sum is not finite, you get top), and they say $\mathbf{MRel}$ and a quotiented version of $\mathbf{Span}(\mathbf{Set})$ are equivalent categories. This seems weird to me after reading your message.

Ralph Sarkis (Dec 09 2023 at 16:37):

The quotient they are doing does not seem to get back to finite things.
image.png

John Baez (Dec 09 2023 at 16:45):

Hmm, I looked at the paper and it does seem like they are making a mistake. After some preliminaries they use "span of sets" to mean "isomorphism class of spans of sets" (they say "equivalence"), and build a category $\mathsf{Span}(\mathsf{Set})$ with sets as objects and such isomorphism classes as morphisms. That's fine.

They define a functor $\mathcal{M}$ from $\mathsf{Span}(\mathsf{Set})$ to a category $\mathsf{MRel}$ where objects are sets and a morphism from $A$ to $B$ is a "multirelation", which they define as a function $m: A \times B \to \mathbb{N}^\omega$. That's fine - though at one point they slip and say $\mathcal{M}$ is a "function" when they mean "functor".

John Baez (Dec 09 2023 at 16:47):

But then they try to define a functor $\mathcal{P}$ back from $\mathsf{MRel}$ to the category $\mathsf{Span}(\mathsf{Set})$ and claim that $\mathcal{M}$ and $\mathcal{P}$ give an equivalence between $\mathsf{Span}(\mathsf{Set})$ and $\mathsf{MRel}$. And that last part seems very wrong.

John Baez (Dec 09 2023 at 16:50):

They claim that "it is easy to verify" that $\mathcal{M}$ followed by $\mathcal{P}$ is the identity functor. Typically whenever I write that something is "easy to verify", that's when I make a mistake - and that seems to be happening here, unless somewhere earlier in the paper they've decreed that all infinite sets are isomorphic.

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

Just consider two spans from $1$ to $1$, one of which is (the isomorphism class of) $1 \leftarrow \mathbb{N} \to 1$ and the other of which is (the isomorphism class) of $1 \leftarrow \mathbb{R} \to 1$. These are not equal, yet $\mathcal{M}$ sends them to the same multirelation.

Ralph Sarkis (Dec 09 2023 at 17:17):

They say what is easy to verify is that $\mathscr{P}$ followed by $\mathscr{M}$ is the identity, which is true and they give the short explaination. The other composite however is not the identity (as suggested by your example).

Ralph Sarkis (Dec 09 2023 at 17:17):

Their functor $\mathscr{M}$ is not even well-defined because they take the cardinality of a set which might not be finite and do not say what to do when it is not. If we assume we should take top when it is not finite, when they use it to define $\tilde{A}$, we always get a countable set, so there is no way $\mathscr{P}\circ \mathscr{M}$ is the identity (in other words, $\mathscr{M}$ is not essentially surjective).

Ralph Sarkis (Dec 09 2023 at 17:17):

They do not seem to use that section in the rest of the paper, but I will contact the authors out of courtesy.

Todd Trimble (Dec 09 2023 at 17:21):

John Baez said:

They claim that "it is easy to verify" that $\mathcal{M}$ followed by $\mathcal{P}$ is the identity functor. Typically whenever I write that something is "easy to verify", that's when I make a mistake - and that seems to be happening here, unless somewhere earlier in the paper they've decreed that all infinite sets are isomorphic.

One of my favorite referee tricks is to look for such claims, and zero in.

Ralph Sarkis (Dec 09 2023 at 17:49):

John Baez said:

Are you at all worried about how natural numbers are only good for classifying finite sets up to isomorphism? If you're trying to define a notion of multirelation that acts sort of like a span of arbitrary sets, you'd have to replace $\mathbb{N}$ by $\mathrm{Card}$, the rig of cardinals.

Apparently, most people only consider multisets with finite multiplicities. Your approach was taken in this paper, but multiplicities are still bounded. In this one, they deal with multisets with unbounded multiplicities, but their definition really comes back to the quotient we saw done on $\mathbf{Span}(\mathbf{Set})$.

Matteo Capucci (he/him) (Dec 11 2023 at 13:58):

Ralph Sarkis said:

Inspired by Matteo's post I am thinking of ending my intro course to category theory by defining a category using the category theoretic tools we learned in class.

Hehe that's a fun way to end a CT course! I'll keep it in mind if ever find myself teaching one

Bruno Gavranović (Dec 13 2023 at 21:46):

John Onstead said:

There are a lot of interesting ideas in the "What is Category Theory" essay and I agree with many points, though I do happen to disagree with this one, that things like category theory can lack foundations.

I don't think that's what the essay is saying.

Generally, when some circularity becomes apparent in any system of two constructions, the circularity can usually be resolved by identifying a third construction which underlies both of the others. The circularity is then explained simply as the fact both of the other constructions are just different "faces" this third, more underlying structure is wearing. Certain circularities between limits/colimits, Kan extensions, adjoint functors, ends/coends, and so on can for instance be explained as them all being different "faces" of the concept of universal properties and morphisms, which is something the nlab notes on its page for universal constructions.

Sure! And you can also see every universal property as a kind of a (co)limit, and thus and adjunction/kan extension/...

I think what the blog post is advocating that there is no canonical reference frame in CT. It's sort of like assuming a category has an initial object: it's an assumption, and doesn't hold for an arbitrary category. It's also why people in the field seem to have a preferred concept they recast everything through. I.e. you can rightfully study CT through the lens that everything is a coalgebra, or a polynomial functor, or a weighted colimit, or a fibration...

That's at least how I understand it!

John Onstead (Dec 13 2023 at 22:35):

@Bruno Gavranović Thanks for your insight! I'm curious, how is a universal property a kind of (co)limit? Is this because terminal and initial objects can be defined in terms of (co)limits, and universal morphisms, which define universal properties, are expressed as terminal or initial objects in a comma category? Or is there some other trick I'm not aware of? :)
As for there being no canonical reference frames within CT, I would actually agree to some extent. Though I'm not sure how fibrations or polynomial functors can be seen as central objects, maybe enlighten me here? In any case, while there may not be such a frame from within CT, my goal with the third object behind both categories and monads is to establish a canonical reference frame for CT outside of CT!

Bruno Gavranović (Dec 14 2023 at 00:19):

John Onstead said:

Bruno Gavranović Thanks for your insight! I'm curious, how is a universal property a kind of (co)limit? Is this because terminal and initial objects can be defined in terms of (co)limits, and universal morphisms, which define universal properties, are expressed as terminal or initial objects in a comma category? Or is there some other trick I'm not aware of? :)

No, that's pretty much it. I'm not referring to anything exotic, merely the fact that the statements of the kind "there exists a ... such that ... for every ..., which is defined up to isomorphism" all can be shuffled around and stated as Kan extensions, adjunctions, limits...
So I don't see "one right way" to see any one of those.

Though I'm not sure how fibrations or polynomial functors can be seen as central objects, maybe enlighten me here? In any case, while there may not be such a frame from within CT, my goal with the third object behind both categories and monads is to establish a canonical reference frame for CT outside of CT!

David Spivak & Nelson Niu have an entire book showing how a lot of concepts in CT can be recast through the lens of polynomial functors. Notably, categories can be seen as comonoids in Poly (equipped with monoidal structure of polynomial composition). There's also this paper which expands on this idea.
I think the same goes with fibrations, the more I learn about them, the more it becomes clear how many concepts can be seen as "just" fibrations of a particular kind.