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: image subcategories structure

David Egolf (Jan 16 2022 at 01:04):

Let $F: A \to B$ be a functor, and let $Im F$ be the smallest subcategory of $B$ that contains $F(A)$.

I think we can view $Im F$ as "information about $A$ observed by $B$ through $F$". From this perspective some functors will be more informative than others, I think. For example, if $Im G$ is a proper subcategory of $Im F$, we might say that $G$ is a less informative observation of $A$ in $B$. Perhaps similarly, we might say that $F$ is no more informative than $G$ if there is a functor $H: B \to B$ so that $H \circ G = F$.

Consider now the collection of all subcategories of $B$ of the form $Im F$ for some functor $F: A \to B$. Does this collection have some natural kind of structure (perhaps ordered with respect to "informativeness")? Intuitively it feels like it should reflect in some way the structure of the subobjects of $A$.

John Baez (Jan 16 2022 at 02:32):

If $A$ is any subcategory of $B$, there is a functor $F: A \to B$ that is the identity on objects of $A$ and morphisms of $A$: this is usually called "the inclusion of $A$ in $B$".

Note that $A = Im F$, i.e. $A$ is the smallest subcategory of $B$ that contains $F(A)$ ($= A$).

So when you say

John Baez (Jan 16 2022 at 02:33):

Consider now the collection of all subcategories of $B$ of the form $Im F$ for some functor $F: A \to B$.

this is equivalent to saying "consider now the collection of all subcategories of $B$". I think this is a simpler way to think about things.

John Baez (Jan 16 2022 at 02:34):

Does this collection have some natural kind of structure (perhaps ordered with respect to "informativeness")?

It is partially ordered by inclusion: that is, we can say $A \le A'$ if every object (resp. morphism) of $A$ is an object (resp. morphism) of $A'$, and this relation $\le$ is a partial order.

David Egolf (Jan 16 2022 at 02:56):

Thanks @John Baez for your thoughts above. It makes sense that the subcategories of $B$ are ordered by inclusion.
However, I am actually primarily interested in the case where $A$ is fixed (maybe I didn't convey that very clearly, though). Then, it often isn't the case that we can express any subcategory of $B$ as the smallest subcategory containing the image of some functor $F$ mapping from $A$.
For example, consider two sets $A$ and $B$ as discrete categories, with a functor $F: A \to B$ being a function between them. Then if $A$ has fewer elements than $B$, then we can't express every subcategory (subset) of $B$ as the image of some function $F: A \to B$.
I suppose, however, that the resulting subcategories are still ordered by inclusion.

David Egolf (Jan 16 2022 at 03:01):

It can also be interesting to think about what happens as $B$ varies, but $A$ is held fixed. For example, consider the case where $A$ and $B$ are sets viewed as discrete categories, and $B$ has a single element. Then we only have one functor from $A$ to $B$ - the functor that sends everything to a single object. The fact that this image subcategory of $B$ exists tells us that $A$ has at least one element, but not anything more. If $B$ has two elements, then functors into $B$ can start to detect a bit more about $A$. Although, it is interesting to note here that not all functors from $A$ in this case are equally informative. I suppose an ordering on these can be inherited from the ordering by inclusion of the subcategories they induce.

David Egolf (Jan 16 2022 at 03:05):

For context, I was learning a bit about reflective subcategories. The "reflection" in a subcategory of an object I think corresponds to the one that detects as much as possible in that subcategory about the object being reflected.

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

This is the diagram I have in mind motivating this line of thought, although the notation used here annoyingly swaps $A$ and $B$ compared to what I said above:
reflection

(image from "Abstract and Concrete Categories", here $\mathbf{A}$ is a subcategory of $\mathbf{B}$, also $A$ is an object of $\mathbf{A}$ and $B$ an object of $\mathbf{B}$)

John Baez (Jan 16 2022 at 03:11):

David Egolf said:

Thanks John Baez for your thoughts above. It makes sense that the subcategories of $B$ are ordered by inclusion. However, I am actually primarily interested in the case where $A$ is fixed (maybe I didn't convey that very clearly, though).

Oh, wow! Okay, that's more subtle.

Although, it is interesting to note here that not all functors from $A$ in this case are equally informative.

I wish you'd give a formal definition of what you mean here by "equally informative". Maybe you have some intuition for it but are still struggling to formalize it. But it's a bit hard for mathematicians to help until you do.

John Baez (Jan 16 2022 at 03:14):

Here's a simple and interesting case to think about.

Suppose $B$ is the category whose objects are natural numbers, with a single morphism from $m$ to $n$ if $m \le n$ and none otherwise. Category theorists might draw this as

$\bullet \to \bullet \to \bullet \to \cdots$

Then taking $A = B$, there are infinitely many functors $F : A \to B$ with different images. You can probably think of infinitely many rather quickly. But in fact there are uncountably many, so maybe it's a fun puzzle to see why.

John Baez (Jan 16 2022 at 03:15):

Or, maybe you'll decide that this infinite stuff is not at all what you're interested in!

David Egolf (Jan 16 2022 at 03:16):

John Baez said:

I wish you'd give a formal definition of what you mean here by "equally informative". Maybe you have some intuition for it but are still struggling to formalize it. But it's a bit hard for mathematicians to help until you do.

I think this is what I mean (trying to express some intuition precisely): let $F: A \to B$ and $G: A \to B$ be functors. Then we say that $F$ is "at least as informative as $G$ about $A$" exactly if there exists a functor $H: B \to B$ so that $G = H \circ F$.

David Egolf (Jan 16 2022 at 03:17):

The idea is - that whatever $G$ is calculating about $A$, that calculation can still be performed using the results of whatever $F$ is doing to $A$.

David Egolf (Jan 16 2022 at 03:18):

So, two functors $F$ and $G$ should be equally informative about $A$ if there exists $H_1$ and $H_2$ so that $G = H_2 \circ F$ and $F = H_1 \circ G$.

John Baez (Jan 16 2022 at 03:21):

Oh, wow! The great thing about this definition is that mathematicians will automatically find it familiar and interesting. In this situation we say "$G$ factors through $F$". This concept makes sense and is widely studied, not just for categories and functors, but for objects and morphisms in any category.

Given objects $A$ and $B$ in any category, there's a preorder on the set of morphisms from $A$ to $B$ such that $G \le F$ if $G$ factors through $F$. You might enjoy checking that it's a preorder.

It's not a partial ordering because it's not true that

$F \le G \text{ and } G \le F \implies F = G$

John Baez (Jan 16 2022 at 03:23):

Whenever we have any preorder, we can define $F \sim G$ to mean $F \le G$ and $G \le F$. Then $\sim$ is an equivalence relation.

John Baez (Jan 16 2022 at 03:24):

In the particular case where the category is Cat, when $G \le F$ you're saying "$F$ is at least as informative as $G$", and when $F \sim G$ you're saying "$F$ and $G$ are equally informative".

John Baez (Jan 16 2022 at 03:25):

You'll notice I'm telling you the various facts at a fairly high level of generality: "in any category" and "whenever we have any preorder". This is what category theorists like to do.

John Baez (Jan 16 2022 at 03:26):

That way we build up an arsenal of widely useful tools.

David Egolf (Jan 16 2022 at 03:27):

Ah, excellent! I will probably indeed enjoy checking that this "informativeness" (or factoring through) gives a preorder.
One reason I care about this is that one could imagine using this concept to put an ordering on some observation-generating part of an imaging system.

David Egolf (Jan 16 2022 at 03:27):

Although I guess it's not a very subtle ordering. But perhaps one could do more complex things like considering "informative with respect to observing property $P$".

David Egolf (Jan 16 2022 at 03:28):

And then consider a few properties at the same time.

David Egolf (Jan 16 2022 at 03:28):

Anyways, thanks!

Zhen Lin Low (Jan 16 2022 at 03:32):

Before you get too excited it might be good to check that your definition lives up to your expectations. For example, according to your definition, if A is a single point, then all functors A → B are "equally informative". Is that what you expect?

John Baez (Jan 16 2022 at 03:35):

I don't think that's actually true, but it's definitely worth thinking about.

I'm pretty sure that if B is a single point then all functors A → B are "equally informative".

David Egolf (Jan 16 2022 at 03:35):

Ok, I see it does indeed form a preorder.
$F \leq F$ because $F = id_B \circ F$
If $M \leq G$ and $G \leq F$ then we have $M=H_2 \circ G$ and $G = H_1 \circ F$.
But then $M = (H_2 \circ H_1) \circ F$. So $M \leq F$.

John Baez (Jan 16 2022 at 03:38):

Right, the second one is the interesting part of the definition of preorder: the transitive law. The first part, the reflexive law, is kinda obvious.

Zhen Lin Low (Jan 16 2022 at 03:39):

@John Baez It doesn't matter whether B is a point or not. You can collapse B to a point and then map it to any other point. The relevant triangle commutes because A is just a point and cannot see that you have collapsed B to a point.

John Baez (Jan 16 2022 at 03:40):

You're right. Good point (pardon the pun).

David Egolf (Jan 16 2022 at 03:41):

I'm considering the statement "if A is a single point, then all functors $A \to B$ are equally informative".
Let $A$ be the category with a single object and its identity morphism.
Let $F, G$ be functors to $B$.
Then $F$ is specified by the object it sends the single object of $A$ to.
Similarly, $G$ is specified by the object it sends the single object of $A$ to.
It seems like there exists a functor $H: B \to B$ that sends one distinguished object to another.
It seems like $F$ and $G$ are always "equally informative" in this case.

David Egolf (Jan 16 2022 at 03:42):

But this makes intuitive sense to me. There isn't a lot to say about $A$ besides "it has one object". We can look at $Im F$ and $Im G$ and see that both $F$ and $G$ are informing us that $A$ has at least one object. Since there isn't anything else to say, it makes sense any observations need to be equally informative.

Zhen Lin Low (Jan 16 2022 at 03:48):

Well, if you believe the conclusion then I suppose you can go ahead with your definition. Personally, I do not agree – for me it is intuitive that some objects in a category are more informative than others. What is more, which objects are more informative depend on the context.

David Egolf (Jan 16 2022 at 03:51):

Zhen Lin Low said:

Well, if you believe the conclusion then I suppose you can go ahead with your definition. Personally, I do not agree – for me it is intuitive that some objects in a category are more informative than others. What is more, which objects are more informative depend on the context.

I think it depends on how broadly one considers the "informativeness" of an object. As you say, it depends on context.

Here I am considering a concept that describes how informative functors are with respect to a fixed object. One could consider a more broad concept that considers how informative objects are (in terms of the informativeness of the functors they support) with respect to a collection of objects, and that should lead to different conclusions.

David Egolf (Jan 16 2022 at 04:29):

I suppose a follow up question would be: Does this preoder on functors from $A$ to $B$ (ordered by "informativeness" or by saying $G \leq F$ if $G$ factors though $F$) have meets or joins?

David Egolf (Jan 16 2022 at 17:26):

Incidentally, I'm pretty sure that $G \leq F$ implies that $Im G$ is a subcategory of $Im F$.

David Egolf (Jan 16 2022 at 17:26):

So this is (if correct) a more concrete way of saying that "$F$ observes at least as much about $A$ as $G$ does"

John Baez (Jan 16 2022 at 17:33):

David Egolf said:

Incidentally, I'm pretty sure that $G \leq F$ implies that $Im G$ is a subcategory of $Im F$.

I don't think so. For a simple counterexample, take $A$ to be (i.e. a category with one object and one morphism), take $B$ to be a category with just two objects and their identity morphisms, and let $F$ and $G$ be the two different functors $F, G: A \to B$.

Zhen Lin showed that if $A$ is just a point, and $B$ is any category whatsoever, and $F, G : A \to B$ are any functors whatsoever, then $G$ always factors through $F$... which we're writing as $G \le F$.

John Baez (Jan 16 2022 at 17:34):

In this situation $Im F$ and $Im G$ can each be any subcategory of $B$ that consists of a single object and its identity morphism.

John Baez (Jan 16 2022 at 17:34):

So, typically $Im G$ is not a subcategory of $Im F$.

David Egolf (Jan 16 2022 at 17:47):

Oh yes, good point.
I'll have to think about this some more.

David Egolf (Jan 16 2022 at 17:51):

So, if $G \leq F$, then there exists an $H$ so that $G = H \circ F$.
The idea I'm trying to get at is that $H$ should be sending $Im F$ to $Im G$.

John Baez (Jan 16 2022 at 17:52):

It probably does.

John Baez (Jan 16 2022 at 17:52):

But that's really different than saying $Im F = Im G$.

John Baez (Jan 16 2022 at 17:55):

Maybe you're trying to dream up a preorder on the subcategories of a category.

David Egolf (Jan 16 2022 at 18:14):

For context, I was reading a paper on "generalized congruences". I think from that paper that $Im F$ is isomorphic to a "quotient category" of $A$ induced by $F$, which is called $A/\sim_F$ in that paper. The intuition I'm trying to figure out here is that more informative observations should correspond to observing quotient categories of $A$ with less quotienting of things.
Maybe we can say that one subcategory $Im G$ is "contained inside of" $Im F$ in a general sense if there is a monomorphic functor from $Im G$ to $Im F$. So, then, I guess I am hoping that if $G \leq F$ then there is a monomorphic functor sending $Im G$ to $Im F$.

David Egolf (Jan 16 2022 at 18:16):

If this was the case, I think this could indeed end up leading to a preorder on these image subcategories.

David Egolf (Jan 16 2022 at 18:22):

Maybe a better way to think about this - Can we quotient $Im(F)$ to get $Im(G)$?

David Egolf (Jan 16 2022 at 18:23):

I am tempted to guess that $Im(F)/\sim_H \cong Im(G)$ if $G = H \circ F$.

David Egolf (Jan 16 2022 at 18:25):

For reference, this is the quotienting operation I'm referring to:
quotient

(from "Generalized Congruences — Epimorphisms in Cat")

David Egolf (Jan 16 2022 at 18:27):

(Every functor $F$ induces a "generalized congruence" defined by identifying objects sent to the same object by $F$, and identifying morphism sequences that are sent to the same morphism by $F$ upon composition in the image).

David Egolf (Jan 16 2022 at 18:51):

One possible chain of reasoning to relate $Im(F)$ and $Im(G)$:
$Im(G) = Im(H \circ F) \cong A/(\sim_{H \circ F}) \cong (A / \sim_F) / (\sim_H) \cong Im(F) /\sim _H$

David Egolf (Jan 16 2022 at 18:51):

However, I need to check that each step of this is actually valid. (Note: I would need to define what I mean by successive quotienting).

David Egolf (Jan 16 2022 at 19:30):

One thing that would be helpful to know is this:
Does $H(Im(F)) = Im(H \circ F)$ for $F: A \to B$ and $H: B \to B$?

David Egolf (Jan 16 2022 at 19:32):

(where $Im(F)$ is the smallest subcategory of $B$ containing $F(A)$)

David Egolf (Jan 16 2022 at 19:33):

Actually, I think we want to know if the smallest subcategory containing $H(Im(F))$ is the same as $Im(H \circ F)$.

David Egolf (Jan 16 2022 at 19:39):

This feels really painfully messy. Maybe there is a better way to think about this.

David Egolf (Jan 16 2022 at 20:28):

I think this picture helps;

diagram

The quotient functor $Q_{\sim_F}$ for $F: A \to B$ sends $A$ to $A/\sim_F$.
I believe that $A/\sim_F$ is isomorphic to $Im F$, and so is isomorphic to a subcategory of $B$.

David Egolf (Jan 16 2022 at 20:29):

That's why I have drawn monic arrows from those quotient categories into $B$.

David Egolf (Jan 16 2022 at 20:37):

The top two cells and the bottom-most cell should commute.
If this is true, then $G = H \circ F = k \circ Q_{\sim (H \circ F) } = j \circ Q_{\sim (H \circ i)} \circ Q_{\sim F}$.
I think this means that $A/{\sim_{H \circ F}}$ is mapped into the same subcategory of $B$ as is $(A_{\sim F})/\sim_{ H \circ i}$

David Egolf (Jan 16 2022 at 20:39):

So, I think $Im(G)$ is isomorphic to $Im(F)/\sim_{H}$.

David Egolf (Jan 16 2022 at 20:45):

If this is true, this describes how different observations of the same category are related in terms of the smallest subcategory of the image they specify. If $F$ is "at least as informative as $G$", then you can compute the subcategory $Im G$ by quotienting $Im F$.

David Egolf (Jan 16 2022 at 20:52):

As a test, say $A$ is a set with two elements viewed as a discrete category, and say $B$ is also a set with two elements. Let $F: A \to B$ be a function that sends $a_1 \mapsto b_1$ and $a_2 \mapsto b_2$. Let $G: A \to B$ be a function that sends both elements to $b_1$. Then $G = H \circ F$, where $H: B \to B$ sends both elements to $b_1$.
In this case $Im F = B$ and $A/\sim_F \cong A$. We also have that $Im G$ is the subcategory of $B$ corresponding to the single element $b_1$ and $B /\sim_G$ is a category with a single object and no non-identity morphisms.

David Egolf (Jan 16 2022 at 20:54):

Now, we want to compute $Im(F)/\sim_H$. This is a category with a single object and no non-identity morphisms, as $H$ sends each element of $Im(F)$ to the same element. This is indeed isomorphic to $Im(G)$.

David Egolf (Jan 16 2022 at 20:55):

So, at least in this case, we were able to compute $Im G$ from $Im F$ by doing a quotienting specified by $H$.

David Egolf (Jan 16 2022 at 20:55):

I'm not sure I have the willpower to take the sketch based on that picture above and make a proper proof, but this has been interesting anyways.