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: adding morphisms

David Egolf (Feb 23 2022 at 16:38):

The discussion in #learning: questions > enriched graphs got me thinking. Sometimes it is the case that we have a collection of objects we would like to study. For example, we may wish to study graphs, or groups, or sets, or statements in predicate logic, or electrical circuits. One can consider a basic category in each case by creating a category where the objects are the things of interest and there are no morphisms (besides the required identity morphisms). However, doing this doesn't seem to gain anything. There is then the (I think tricky) process of adding morphisms to this category in a way that the result is something interesting and useful.

What are some strategies for adding morphisms to get an interesting category in the end? As a more specific question, say I have some property that I want to talk about - e.g. I want to be able to talk about "bipartite" graphs - then: how should morphisms be added to enable discussion of this property in terms of morphisms?

As a related question, how can one make precise what is "gained" by adding more morphisms? For example, consider (1) a category $Set_i$ where the objects are sets and the morphisms are bijective functions and (2) the category $Set$ where the objects are sets and the morphisms are (unrestricted) functions. What properties of sets can we talk about in $Set$ that we can't in $Set_i$?

Joe Moeller (Feb 23 2022 at 17:25):

Maybe more of a guiding principle than a technique, but it's very fruitful to try to build your new category out of known categories in a way that's as natural/canonical as possible. E.g. directed graphs can be realized as two sets (edges and vertices) equipped with two functions (source and target). So there's a very natural way to define morphisms between such things: you want functions between the sets such that any diagram you could feasibly form with them and the source and target maps commutes. This sort of process is generalizable, it's presheaf categories. A variation of this is algebras of a Lawvere theory, or PROPs, or monads, or operads... In all these cases there's a sense in which the maps are determined by the definition of the objects. And when you define your category in one of these ways, there are general results about how nice it is.

Simon Burton (Feb 23 2022 at 17:53):

This question is already interesting in the case of groups (as one object categories). Cutting out the morphisms, corresponds to taking various subgroups, and this leads to the idea of Kleinian geometry. Symmetry breaking = adding structure.

John Baez (Feb 23 2022 at 17:57):

David Egolf said:

As a related question, how can one make precise what is "gained" by adding more morphisms?

This is an amazingly broad question. I'm glad you narrowed it down:

For example, consider (1) a category $Set_i$ where the objects are sets and the morphisms are bijective functions and (2) the category $Set$ where the objects are sets and the morphisms are (unrestricted) functions. What properties of sets can we talk about in $Set$ that we can't in $Set_i$?

One could write a little book just about this example!

Notice that $\mathsf{Set}_i$ is a groupoid, while $\mathsf{Set}$ is a topos (indeed the most famous topos).

One does very different things with groupoids than one does with topoi. Roughly speaking, groupoids describe symmetries, or topological spaces whose homotopy groups become trivial above dimension 1. (The fact that these are 'the same' is an important chapter in mathematics.) Topoi, on the other hand, are roughly worlds in which one can do 'all of mathematics'.

For example: topoi have all finite limits and colimits. $\mathsf{Set}$ has all (small) limits and colimits. At the other extreme, groupoids only have rather trivial limits and colimits.

As a little puzzle to get a sense for this, figure out when two objects in $\mathsf{Set}_i$ have a product. (Not often.)

David Egolf (Feb 23 2022 at 19:07):

John Baez said:

As a little puzzle to get a sense for this, figure out when two objects in $\mathsf{Set}_i$ have a product. (Not often.)

Let's see. A product of two objects $A$ and $B$ is a limit over the diagram containing just those two objects. So, we need an object with morphisms to $A$ and $B$, to start with. That means that the elements of $A \times B$ must be in bijection with those of $A$ and with those of $B$, which means that $A$ and $B$ need to have a bijection between them. However, for any object $C$ having morphisms to both $A$ and $B$, we need there to be a unique morphism from $C$ to $A \times B$. There is a unique bijection between two sets exactly when: either the two sets contain a single element, or the two sets are empty.
So, I think, two objects $A$ and $B$ in $\mathsf{Set}_i$ have a product exactly when either (1) both $A$ and $B$ contain a single element or (2) both $A$ and $B$ are empty.

Morgan Rogers (he/him) (Feb 23 2022 at 19:20):

David Egolf said:

However, for any object $C$ having morphisms to both $A$ and $B$, we need there to be a unique morphism from $C$ to $A \times B$.

This part is not quite right, but the conclusion seems right to me.

David Egolf (Feb 23 2022 at 19:31):

Morgan Rogers (he/him) said:

David Egolf said:

However, for any object $C$ having morphisms to both $A$ and $B$, we need there to be a unique morphism from $C$ to $A \times B$.

This part is not quite right, but the conclusion seems right to me.

Hmmm. I probably should have talked about things being required to commute. Let $\pi_a: A \times B \to A$ and $\pi_b: A \times B \to B$ be the morphisms used to define our product. Then for any object $C$ with morphisms $c_a: C \to A$ and $c_b: C \to B$ we need there to exist a unique morphism $f: C \to A \times B$ so that $\pi_a \circ f = c_a$ and $\pi_b \circ f = c_b$.
Now that I think about it a bit more carefully, I don't immediately see why we can't have products of sets with two elements. Hmm.

Morgan Rogers (he/him) (Feb 23 2022 at 19:34):

The only sets with any morphisms to a two-element set are two-element sets. So now you just have to count :wink:

David Egolf (Feb 23 2022 at 19:36):

Morgan Rogers (he/him) said:

The only sets with any morphisms to a two-element set are two-element sets. So now you just have to count :wink:

I'm not following your hint, unfortunately, although I appreciate it.

David Egolf (Feb 23 2022 at 19:36):

I have drawn out a little example on paper for sets with two elements, and it seems (?) like once I set the morphisms $c_a$ and $c_b$ then the morphism $f$ is forced to be unique by virtue of requiring the things described above to commute.

David Egolf (Feb 23 2022 at 19:39):

Oh, interesting. There are two conditions on $f$: $f = \pi_a^{-1} \circ c_a$ and $f = \pi_b^{-1} \circ c_b$. These two things aren't always equal. If they aren't, then that means that there is no $f$ that exists that makes all the required things commute. If that can happen, then that means that we don't have a product.

Morgan Rogers (he/him) (Feb 23 2022 at 19:40):

I can be a bit more precise: how many automorphisms would the product of a pair of 2-element sets have? (okay, I'm not actually sure this will help you, but either this or the argument you're developing will get you where you want to go)

David Egolf (Feb 23 2022 at 19:43):

Morgan Rogers (he/him) said:

I can be a bit more precise: how many automorphisms would the product of a pair of 2-element sets have?

So, the product of a pair of 2-element sets must have two elements. An automorphism is a bijection from such a product to itself. I believe there would be two such automorphisms.
However, I don't immediately see how this helps figure out the products in $\mathsf{Set}_i$.

Morgan Rogers (he/him) (Feb 23 2022 at 19:45):

What I was alluding to is: if $A$, $B$ and $C$ are two-element sets, with $C$ our candidate product of $A$ and $B$, then how many spans of the form $A \leftarrow C \rightarrow B$ are there? If $C$ were the product, each such span would produce an endomorphisms of $C$ (and hence an automorphism, since the only the morphisms are bijections)

Joe Moeller (Feb 23 2022 at 19:46):

What's the product of a 2-element set and a 3-element set?

David Egolf (Feb 23 2022 at 19:46):

Joe Moeller said:

What's the product of a 2-element set and a 3-element set?

It doesn't exist in this setting, to my understanding.

Joe Moeller (Feb 23 2022 at 19:49):

Sorry, it's actually not clear to me what you don't know about products in $\mathsf{Set}_i$.

David Egolf (Feb 23 2022 at 19:52):

Morgan Rogers (he/him) said:

What I was alluding to is: if $A$, $B$ and $C$ are two-element sets, with $C$ our candidate product of $A$ and $B$, then how many spans of the form $A \leftarrow C \rightarrow B$ are there? If $C$ were the product, each such span would produce an endomorphisms of $C$ (and hence an automorphism, since the only the morphisms are bijections)

We need a bijection from $C$ to $A$ - and there are two of these. We also need a bijection from $C$ to $B$, and there are also two of these. So, it seems like there should be four such spans.
If $C$(together with particular morphisms $\pi_a: C \to A$ and $\pi_b: C \to B$) is the product, there needs to be a unique morphism to that span from any of the four spans from $C$ to $A$ and $B$. Each of these morphisms corresponds to an endomorphism (and hence an automorphism) of $C$.
I think this is roughly what you are saying?
And then there is presumably some problem related to wanting four endomorphisms of $C$, but $C$ only having two. I think this is going to work out to a similar argument to what I was saying above, where we can't always form morphisms from spans to our proposed product so that everything required commutes.

David Egolf (Feb 23 2022 at 19:53):

Joe Moeller said:

Sorry, it's actually not clear to me what you don't know about products in $\mathsf{Set}_i$.

I would like to know when the product of two sets $A$ and $B$ exists in $\mathsf{Set}_i$. We for sure need $A$ and $B$ to have the same number of elements, but the question is if any (common) number of elements will let us form a product.

Morgan Rogers (he/him) (Feb 23 2022 at 20:08):

I think you've worked it out. A concise way of saying this is that the universal property of the product can be expressed as $\mathrm{Hom}(C,A\times B) \cong \mathrm{Hom}(C,A) \times \mathrm{Hom}(C,B)$, where this is an isomorphism of sets natural in $C$. But from your very first argument, assuming that the product exists, we have $A \cong A \times B \cong B$, which means that we can up to chosen isomorphisms replace everything with copies of $A$ to deduce...
$\mathrm{Hom}(C,A) \cong \mathrm{Hom}(C,A) \times \mathrm{Hom}(C,A)$,
for all sets $C$. Choosing $C \cong A$ too, we arrive at the counting problem I was alluding to.

But this "reduction to counting" argument loses a bit too much information! After all, we can have $X \cong X \times X$ for infinite sets too! So can you refine your 'no-go' argument to work for infinite sets? Or are there products of infinite sets too?

David Egolf (Feb 23 2022 at 20:11):

Thanks @Morgan Rogers (he/him) . I'll have to give what you wrote a proper think and response once I have a bit more energy!

John Baez (Feb 23 2022 at 20:11):

David Egolf wrote:

So, I think, two objects $A$ and $B$ in $\mathsf{Set}_i$ have a product exactly when either (1) both $A$ and $B$ contain a single element or (2) both $A$ and $B$ are empty.

However you got this answer, I think it's right! So people living in the groupoid of finite sets learn their times table very easily:

$0 \times 0 \cong 0$

$1 \times 1 \cong 1$

John Baez (Feb 23 2022 at 20:20):

Note that $\mathbf{Set}_i$ is the 'disjoint union' (coproduct) of a bunch of groupoids:

• the groupoid of 0-element sets and bijections between these
• the groupoid of 1-element sets and bijections between these
• the groupoid of 2-element sets and bijections between these

and so on for every cardinality. So my question really boils down to asking which of these groupoids have (binary) products. And most of them don't. It turns out that the two that do - the first two - are the groupoids where there is just one morphism from any object to any other.

It's pretty easy to see that any groupoid with just one morphism from any object to any other has binary products. So if anyone wants another puzzle, this one is pretty natural: is the converse true?

John Baez (Feb 23 2022 at 20:40):

(By the way, I urge experts not to step in and crush these puzzles, which are more for beginners.)

David Egolf (Feb 24 2022 at 17:07):

Morgan Rogers (he/him) said:

I think you've worked it out. A concise way of saying this is that the universal property of the product can be expressed as $\mathrm{Hom}(C,A\times B) \cong \mathrm{Hom}(C,A) \times \mathrm{Hom}(C,B)$, where this is an isomorphism of sets natural in $C$.

I'm trying to understand this. $\mathrm{Hom}(C, A \times B)$ is the set of bijective functions from $C$ to $A \times B$, $\mathrm{Hom}(C,A)$ is the set of bijective functions from $C$ to $A$, and $\mathrm{Hom}(C,B)$ is the set of bijective functions from $C$ to $B$. The statement $\mathrm{Hom}(C, A \times B) \cong \mathrm{Hom}(C,A) \times \mathrm{Hom}(C,B)$ corresponds to the claim that $\mathrm{Hom}(C, A \times B)$ has elements in bijection with the elements of $\mathrm{Hom}(C,A) \times \mathrm{Hom}(C,B)$. This claim is not immediately obvious to me, but if I understand, it follows from the universal property of the product.

Let's see if I can figure out how it follows from the universal property of the product. For finite sets, at least, the number of different spans from $C$ to $A$ and $B$ is given by the number of elements of $\mathrm{Hom}(C,A) \times \mathrm{Hom}(C,B)$. For each such span, by the universal property of the binary product, we have a unique morphism from $C$ to $A \times B$ so that all the required things commute. If each of these morphisms from $C$ to $A \times B$ were distinct, that would imply that $\mathrm{Hom}(C, A \times B)$ would have at least as many elements as $\mathrm{Hom}(C,A) \times \mathrm{Hom}(C,B)$. How can we show that different choices for the span morphisms from $C$ to $A$ and $B$ will induce different morphisms to $A \times B$ from $C$, though?

To try and show this, call $f_{a,b}: C \to A \times B$ the unique morphism that makes the required things commute in the definition of the product for choice of morphisms $a: C \to A$ and $b: C \to B$. Then we must have $f_{a,b}= \pi_a^{-1} \circ a$ and $f_{a,b} = \pi_b^{-1} \circ b$ for $\pi_a: A \times B \to A$ and $\pi_b: A \times B \to B$ the morphisms in the span corresponding to the product. So, the choice of $a$ and $b$ forces a particular value for $f_{a,b}$, and because all these morphisms are isomorphisms, different choices for $a$ and $b$ will result in different values for $f_{a,b}$. I think this means that $\mathrm{Hom}(C, A \times B)$ has at least as many elements as $\mathrm{Hom}(C,A) \times \mathrm{Hom}(C,B)$.

It think it remains to show that $\mathrm{Hom}(C, A \times B)$ has no more elements than $\mathrm{Hom}(C,A) \times \mathrm{Hom}(C,B)$.

David Egolf (Feb 24 2022 at 17:15):

To do that, pick some $f: C \to A \times B$. Then set $a = \pi_a \circ f$ and $b = \pi_b \circ f$. So, given an element of $Hom(C, A \times B)$, we have identified (uniquely) an element of $Hom(C,A) \times Hom(C,B)$.
Ok, hopefully I've done this close to right.
I am now willing to believe that $\mathrm{Hom}(C, A \times B) \cong \mathrm{Hom}(C,A) \times \mathrm{Hom}(C,B)$.

John Baez (Feb 24 2022 at 17:18):

Instead of focusing on "at least as many" and "no more than", which is about cardinalities of sets, a more modern approach is to get a bijection between $\mathrm{Hom}(C,A) \times \mathrm{Hom}(C,B)$ and $\mathrm{Hom}(C, A \times B)$.

One standard way to do this is to first get a map from $\mathrm{Hom}(C,A) \times \mathrm{Hom}(C,B)$ to $\mathrm{Hom}(C, A \times B)$, and then get a map from $\mathrm{Hom}(C, A \times B)$ to $\mathrm{Hom}(C,A) \times \mathrm{Hom}(C,B)$, and then prove these maps are inverses.

I think you did all of this except the last step: proving these maps are inverses.

John Baez (Feb 24 2022 at 17:20):

David Egolf said:

I am now willing to believe that $\mathrm{Hom}(C, A \times B) \cong \mathrm{Hom}(C,A) \times \mathrm{Hom}(C,B)$.

I'd probably be willing to believe it at that point too. But to really prove it you need to show the two maps you've gotten are inverses. (I'm not pressuring you to do it, just making sure it's clear this is the remaining bit of work necessary for a complete proof.)

David Egolf (Feb 24 2022 at 17:35):

John Baez said:

I think you did all of this except the last step: proving these maps are inverses.

Oh, good point! Also, thinking in terms of maps does seem better than focusing on "at least as many" and "no more than", because it makes it easier to talk about infinite sets.

We need two maps. For the first map, define $v: \mathrm{Hom}(C,A) \times \mathrm{Hom}(C,B) \to \mathrm{Hom}(C, A \times B)$ by $v(a,b) =\pi_a^{-1} \circ a$. By the universal property of the product, there exists a unique morphism from $C$ to $A \times B$ that makes the needed things commute in the definition of the product. This means that $v(a,b) = \pi_a^{-1} \circ a = \pi_b^{-1} \circ b$, actually.
For the second map, define $w: \mathrm{Hom}(C, A \times B) \to \mathrm{Hom}(C,A) \times \mathrm{Hom}(C,B)$ by $w(f) = (\pi_a \circ f, \pi_b \circ f)$.

Now we want to see if these are inverses.
$v \circ w(f) = v(\pi_a \circ f, \pi_b \circ f) = \pi_{a}^{-1} \circ \pi_a \circ f = f$
$w \circ v(a,b) = w(\pi_a^{-1} \circ a) = (\pi_a \pi_a^{-1} \circ a, \pi_b \pi_a^{-1} \circ a) = (a, \pi_b \pi_a^{-1} \circ a)$.
I think we can use $v(a,b) = \pi_a^{-1} \circ a = \pi_b^{-1} \circ b$ at this point to conclude $w \circ v(a,b) = (a,b)$, although I'm a bit hazy on this point.
If that's true, then I think $v$ and $w$ are inverses.

David Egolf (Feb 24 2022 at 17:43):

Now, accepting $\mathrm{Hom}(C, A \times B) \cong \mathrm{Hom}(C,A) \times \mathrm{Hom}(C,B)$, let's see what we can conclude regarding the existence of the product of $A$ and $B$. For it to exist, we need $A \cong B \cong A \times B$. Assuming we can replace sets with sets that are isomorphic to them, and setting $C = A$, we get that $\mathrm{Hom}(A, A) \cong \mathrm{Hom}(A,A) \times \mathrm{Hom}(A,A)$ must hold if the product of $A$ and $B$ exists in $\mathsf{Set}_i$.
If $A$ has a finite number of elements $|A|$, then this corresponds to $|A|! = |A|! |A|!$ setting $x = |A|!$, we find $x = x^2 \implies x^2 - x = 0 \implies x(x-1) = 0$ which implies $|A|! = 0$ or $|A|! = 1$. This I believe implies that $A$ must have either 0 or 1 elements, as we concluded above.

David Egolf (Feb 24 2022 at 17:46):

Morgan Rogers (he/him) said:

But this "reduction to counting" argument loses a bit too much information! After all, we can have $X \cong X \times X$ for infinite sets too! So can you refine your 'no-go' argument to work for infinite sets? Or are there products of infinite sets too?

And so we arrive at this question! I'm not really sure where to start with this. I'm not even sure how to show that for some infinite set $A$ we can have $\mathrm{Hom}(A,A) \cong \mathrm{Hom}(A,A) \times \mathrm{Hom}(A,A)$ in $\mathsf{Set}_i$.

John Baez (Feb 24 2022 at 18:41):

David Egolf said:

Now, accepting $\mathrm{Hom}(C, A \times B) \cong \mathrm{Hom}(C,A) \times \mathrm{Hom}(C,B)$, let's see what we can conclude regarding the existence of the product of $A$ and $B$. For it to exist, we need $A \cong B \cong A \times B$.

No.

John Baez (Feb 24 2022 at 18:42):

You didn't prove we need it, in fact we don't need it, and indeed any pair of sets has a product in the category $\mathsf{Set}$.

John Baez (Feb 24 2022 at 18:48):

Or are you working in $\mathsf{Set}_i$ here, your name for the category of sets and bijections?

David Egolf (Feb 24 2022 at 18:56):

John Baez said:

Or are you working in $\mathsf{Set}_i$ here, your name for the category of sets and bijections?

Yeah, I'm working in $\mathsf{Set}_i$, where I believe this is required.

Morgan Rogers (he/him) (Feb 24 2022 at 20:37):

Nice one @David Egolf! Seems like you got to exactly what I was hinting at.

David Egolf (Feb 25 2022 at 15:15):

So, to summarize what we've been talking about, in context of the first post in this thread -
In the category $\mathsf{Set}_i$, where the objects are sets and the morphisms are bijective functions, we can only take certain products. In particular, a product of two finite sets $A$ and $B$ exists exactly when both $A$ and $B$ are empty, or both $A$ and $B$ have a single element.
In the category $\mathsf{Set}$, where the objects are sets and the morphisms are (unrestricted) functions, the product of any two sets exists.

So, by adding additional morphisms (going from bijective functions to all functions), we have added the ability to consider more products of sets.

A related question - what's the minimum of morphisms that would need to be added between sets to make the product of any pair of finite sets exist in the resulting category? As a first (somewhat random) guess, I'd be tempted to see if $\mathsf{Set}_s$ would have all these products, where $\mathsf{Set}_s$ is the category having sets as its objects, and surjective functions as its morphisms.

John Baez (Feb 25 2022 at 17:26):

It's a very good exercise to show that's false. It's a good guess. Well, what I mean by that is that it fooled me too for a while. :upside_down:

John Baez (Feb 25 2022 at 17:29):

One nice fact is that the category of finite sets and all functions between them is the "free category with finite coproducts on one object". In other words, if you posit that your category has one object, and assume it has finite coproducts, and throw in no extra equations than those that are required by this, you get a category equivalent to $\mathsf{FinSet}$.

John Baez (Feb 25 2022 at 17:34):

This is a more high-powered version of the fact that the natural numbers are the free commutative monoid on one element.

I.e., if you have a number $1$ and you start adding it to itself following the rules of a commutative monoid and no others, you get something isomorphic to the natural numbers.

Reid Barton (Feb 26 2022 at 00:32):

David Egolf said:

As a first (somewhat random) guess, I'd be tempted to see if $\mathsf{Set}_s$ would have all these products, where $\mathsf{Set}_s$ is the category having sets as its objects, and surjective functions as its morphisms.

In fact this is wrong for two different reasons, one of which is a bit trivial and boring, the other of which is more interesting.

David Egolf (Feb 26 2022 at 01:31):

Thanks for the interesting responses. I plan on thinking about this once I have a bit more energy. (I unfortunately suffer from chronic fatigue, which is acting up this week).

Jade Master (Feb 27 2022 at 00:44):

More handwavily, adding more morphisms gives you more ways to distinguish two objects from each other. It's sort of like how more open sets in a topology gives you more ways to distinguish elements and is called a "finer topology". It's late and I'm having trouble figuring out how to make this intuition more precise but I'm sure there's a way. Maybe something to do with the Yoneda lemma.

Mike Shulman (Feb 27 2022 at 00:55):

I would have said the opposite, that adding more morphisms gives you more ways to identify two objects with each other. Surely that's the case when the morphisms are invertible. And isn't it easiest to distinguish objects in a discrete category that has no nonidentity morphisms?

Jade Master (Feb 27 2022 at 11:32):

identify is a form of distinguishing ;) but yeah I think distinguish is not quite the right word. The analogy I stand by is that more morphisms is like a finer topology and less morphisms is like a coarser one.

Jade Master (Feb 27 2022 at 11:51):

So the Yoneda lemma says that $a \cong b \Leftrightarrow hom(c,a) \cong hom(c,b)$ for all c. So if there are more morphisms you really need to do more work to prove that the two objects are isomorphic...there's a greater burden of proof.

Mike Shulman (Feb 27 2022 at 16:34):

How can making two things the same be a way of telling them apart?

Mike Shulman (Feb 27 2022 at 16:34):

If your category is a preorder, like the preorder of open sets in a topology, then adding more morphisms in the extreme would make it into a chaotic category, which is the indiscrete topology in which nothing at all ca be told apart.

Jade Master (Feb 27 2022 at 17:00):

Mike Shulman said:

How can making two things the same be a way of telling them apart?

This sounds like a zen koan, it's a paradox but I definitely do think there is a lot of truth to it. When you have more ways of making two things the same you also have more ways of explaining their difference. And besides, not every morphism is an isomorphism.