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: subobject classifiers

Benjamin Merlin Bumpus (he/him) (Aug 30 2024 at 18:37):

Hi all :wave:, I've officially fallen in love with topos theory and I have a vague question (maybe more of a reference request) about the construction of subobject classifiers. Please bear with me as I wave my hands. Here's the question:

• The way one constructs subobject classifiers in (co)pre-sheaf categories is just beautiful: it's done in terms of sieves on any object. Is there an analogue of this construction in any elementary topos? By this I mean, is there a formulaic construction which will always yield the definition of a subobject classifier in a category $\mathsf{C}$ whenever subobject classifiers exists in $\mathsf{C}$?

fosco (Aug 30 2024 at 19:05):

as it is stated, the question admits "yes" as answer, but I think it's not what you wanted to ask

fosco (Aug 30 2024 at 19:10):

Maybe you want to ask: there's a particularly elegant way to prove that categories of the form $Set^{C^o}$ have a subobject classifier. Is there a similar way to prove that elementary toposes [of the form...?] have a subobject classifier?

Benjamin Merlin Bumpus (he/him) (Aug 30 2024 at 19:38):

hmm, probably, I guess I'm asking if there's something like a formula for subobject classifiers in the same way as there's a formula for Kan extensions :man_shrugging:

fosco (Aug 30 2024 at 20:31):

ah, I understand (probably) what you want. Say you have a category and you know it has a subobject classifier; is there a way to compute it?

fosco (Aug 30 2024 at 20:32):

If yes, I've never seen one besides the one for Grothendieck toposes. For elementary toposes.. maybe the keyword is something something Lawvere-Tierney topologies?

fosco (Aug 30 2024 at 20:33):

At a very naive level, a subobject classifier is a representing object for the subobject functor, which means a terminal object in its category of elements

fosco (Aug 30 2024 at 20:35):

so whatever recipe you have to find the terminal object of $\int Sub_C$ gives $C$ a subobject classifier

John Baez (Aug 30 2024 at 21:01):

Am I hallucinating, or is the terminal object of a category the colimit of the 'full diagram': the diagram consisting of all objects and morphisms in the category?

For example, this is true for a poset.

Benjamin Merlin Bumpus (he/him) (Aug 30 2024 at 21:17):

fosco said:

ah, I understand (probably) what you want. Say you have a category and you know it has a subobject classifier; is there a way to compute it?

Yes, this is exactly it! :thank_you:

Benjamin Merlin Bumpus (he/him) (Aug 30 2024 at 21:18):

John Baez said:

Am I hallucinating, or is the terminal object of a category the colimit of the 'full diagram': the diagram consisting of all objects and morphisms in the category?

this sounds correct to me!

Benjamin Merlin Bumpus (he/him) (Aug 30 2024 at 21:19):

Thanks a lot for the answers, I'll ponder it a bit!

John Baez (Aug 30 2024 at 21:28):

Okay, thanks. So then I guess you can get get the subobject classifier of $\mathsf{C}$, if it exists, using the philosophy that $1 \xhookrightarrow{T} \Omega$ is the 'walking subobject' or 'mother of all subobjects': any subobject of any object $X$ is obtained via pullback from some morphism $X \to \Omega$.

So, this makes me want to build it as a colimit of a diagram whose objects are all possible object/subobject pairs $A \hookrightarrow B$ in $\mathsf{C}$, and whose arrows are all maps between these. Or something like that.

Even if I'm right this is a thoroughly impractical method, but when the colimit exists it should be a terminal object in some category of object-subobject pairs, and this should match Fosco's description.

John Baez (Aug 30 2024 at 21:30):

I'm a bit fuzzy about a lot of the details here, but to the extent I understand them, all I'm doing it dramatizing what Fosco said, using the philosophy that the subobject classifier is the "walking subobject" (i.e. it's an object, and a subobject of that, which is universal among such object-subobject pairs).

fosco (Aug 30 2024 at 21:38):

It's late evening for me, but I think these two descriptions we gave are equivalent and equally tautological; a terminal object of $C$ exists iff the identity functor has a colimit; this poses the problem of non-existence of a general formula to compute a colimit of a diagram that "$C$ recognizes as large"

fosco (Aug 30 2024 at 21:39):

it's a nice observation anyway, that one can just reduce to $\Omega \cong colim(id_{\int Sub})$ (woah, that's a lot of nested notation)

fosco (Aug 30 2024 at 21:41):

let's wait for the true topos theorists (=not me)

Peva Blanchard (Aug 30 2024 at 21:43):

Is it possible to "present" an elementary topos as a presheaf topos?

John Baez (Aug 30 2024 at 21:45):

Not always! For example: the category of finite sets is an elementary topos, but not a presheaf topos.

John Baez (Aug 30 2024 at 21:46):

Any presheaf topos (or more generally any [[Grothendieck topos]]) has all small colimits and limits, while an elementary topos need only have finite ones.

fosco (Aug 30 2024 at 21:51):

[Forgive the late night blasphemy]: I would then say it's not true that every elementary topos arises as a left exact localization of $Fin^{C^o}$?

fosco (Aug 30 2024 at 21:52):

(for a small C)

fosco (Aug 30 2024 at 21:52):

morally, C should be the subcategory of compact objects, and I don't see why the elementary topos axioms make it a generator.

fosco (Aug 30 2024 at 21:54):

also true or false that every category of the form $Fin^{C^o}$ is a fairly canonical example of an elementary topos? I must admit I have never thought about this banality and I feel ashamed!

John Baez (Aug 30 2024 at 22:00):

I can't answer your sophisticated question but what I call $\mathsf{FinSet}^{\mathsf{C}^{\textrm{op}}}$ is indeed an elementary topos. (I seem to use more letters than you.)

John Baez (Aug 30 2024 at 22:03):

I guess $\mathsf{X}^{\mathsf{C}^{\textrm{op}}}$ is an elementary topos whenever $\mathsf{X}$ is the category of all sets whose cardinality is less than some [[inaccessible cardinal]]. The countably infinite cardinal $\omega_0$ would count as an inaccessible cardinal except some jerk stuck a clause into the definition explicitly excluding it.

Kevin Carlson (Sep 01 2024 at 07:14):

An elementary topos need not have any generator, so you definitely can’t restrict to $C$ small, and you definitely can’t restrict to presheaves valued only in finite sets. A locally small cocomplete topos is pretty close to the same as a lex total category, ie a left exact localization of the category of presheaves of small sets on some locally small category (ie itself) though.

Kevin Carlson (Sep 01 2024 at 07:18):

As to your original question, @Benjamin Merlin Bumpus (he/him), I think the answer is mostly no; this construction is so nice because $C$-presheaves have $C$ as a dense small generator. If $C$ is a site you get something worse but still something, but in general with no generator I see little hope of anything that feels nontrivially analogous. I’m not super confident in this claim except insofar as arbitrary toposes are pretty weird so I have priors on things being weird.

fosco (Sep 01 2024 at 07:34):

So in an elementary topos there is no way to compute $\Omega$, so to speak.

Kevin Carlson (Sep 02 2024 at 06:08):

I’m saying I guess there’s no general nontrivial way to do so, yeah.

Morgan Rogers (he/him) (Sep 02 2024 at 08:14):

Benjamin Merlin Bumpus (he/him) said:

Hi all :wave:, I've officially fallen in love with topos theory

Welcome!

Morgan Rogers (he/him) (Sep 02 2024 at 08:32):

John Baez said:

I can't answer your sophisticated question but what I call $\mathsf{FinSet}^{\mathsf{C}^{\textrm{op}}}$ is indeed an elementary topos. (I seem to use more letters than you.)

Are you sure? Think about what happens for a poset $P$ of infinite depth, or more specifically a poset in which some element $x$ has infinitely many elements below it, such as the terminal object in the ordinal $\omega + 1$. We have a Yoneda embedding $P \to \mathsf{FinSet}^{P^{\mathrm{op}}}$, since $P$ is locally finite (beware that this is not necessarily the free finite cocompletion of $P$, as Kevin pointed out in another topic). Moreover, the [[Yoneda lemma]] holds: elements of $F(x)$ are in bijection with natural transformations $y_x \Rightarrow F$ (you can inspect the proof and see that it applies as soon as the representable presheaf exists, since it only relies on the naturality condition), and hence the preservation of limits by the Yoneda embedding holds, whence $y_x$ has infinitely many subobjects -- in a poset, all morphisms are monomorphisms.
So if the subobject functor were represented by some object $\Omega$, we would have $\Omega(x)$ being infinite (corresponding to $y_x$ having infinitely many subobjects), which is not allowed since our presheaves have to take values in finite sets!

Morgan Rogers (he/him) (Sep 02 2024 at 08:38):

In summary, for $\mathsf{FinSet}^{\mathcal{C}^{\mathrm{op}}}$ to be a topos when $\mathcal{C}$ has finite homsets, it is necessary for $\mathcal{C}$ to also be 'finitely powered'. I am a little curious if:

1. this is also sufficient (I think it isn't: we can certainly take finite colimits of representables, so if there are infinitely many finitely generated sieves over an object, we hit the same problem!)
2. you can avoid this condition when $\mathcal{C}$ has larger homsets (I think not).
   I think the latter may be a distraction from @Benjamin Merlin Bumpus (he/him) 's original question, but the former should be a little informative.

John Baez (Sep 02 2024 at 14:23):

Are you sure?

Rapidly getting less so.... :sweat_smile:

John Baez (Sep 02 2024 at 14:27):

Thanks for disabusing me of that notion, and then going the extra mile to find extra conditions to fix my guess.

John Baez (Sep 02 2024 at 14:29):

I guess this generalization for larger cardinalities also needs to be fixed, at least when $\mathsf{C}$ has more than $\kappa$ objects (or morphisms):

John Baez said:

I guess $\mathsf{X}^{\mathsf{C}^{\textrm{op}}}$ is an elementary topos whenever $\mathsf{X}$ is the category of all sets whose cardinality is less than some [[inaccessible cardinal]] $\kappa$.

James Deikun (Sep 02 2024 at 14:31):

Yeah I think this is basically because $\omega + 1$ is a "large category" from the perspective of $\mathsf{FinSet}$, and that for similar reasons $\mathsf{Set}^{\mathcal{C}^\mathsf{op}}$ isn't in general a topos when $\mathcal{C}$ is large ... so the same should happen for various inaccessible cardinals.

Mike Shulman (Sep 02 2024 at 14:33):

If anyone has access to Sketches of an Elephant, check out Example A2.1.5: if $C$ is a category all of whose slice categories are essentially small, then $\mathrm{Set}^{C^{\mathrm{op}}}$ is an elementary topos.

James Deikun (Sep 02 2024 at 14:36):

Ah, so $\mathsf{FinSet}^{\omega^\mathsf{op}}$ is kind of a "scaled down" version of that, and $\omega + 1$ fails because it has a terminal object and the slice over that is as large as the original category.

James Deikun (Sep 02 2024 at 15:11):

Having read Elephant A2.1.5, plus the above, it seems like the "if" can be strengthened to "iff" ... am I dreaming?

Mike Shulman (Sep 02 2024 at 15:34):

So you'd need to argue that if every representable presheaf has only a small number of subobjects, then all slice categories are essentially small. That's not obvious to me; a priori it seems like there could be other "accidental" ways for representables to have small subobject lattices. Is there an argument for it contained somewhere in this thread?

James Deikun (Sep 02 2024 at 16:15):

It seems more obvious to me when you look at the exponential objects than the subobject classifier. Or at least it did--I'm no longer sure I understand the argument for why exponentials turn out as small presheaves in the first place! (for the A2.1.5 case, not the $\mathcal{C}$ small case.)

Mike Shulman (Sep 02 2024 at 16:24):

Maybe it's easier to understand why power objects turn out small.

Benjamin Merlin Bumpus (he/him) (Sep 02 2024 at 16:40):

Thanks everyone for the comments; I’ve learned a lot from reading all of this!

Ryan Wisnesky (Sep 02 2024 at 19:48):

btw, old fql can compute sub-object classifiers for the category of copresheaves on certain finitely presented categories. Here's a picture of the subobject classifier for the category of copreshaves on the category with a single generating arrow f:a->b.
Screenshot-2024-09-02-at-12.42.57PM.png

Josselin Poiret (Sep 03 2024 at 09:21):

Ryan Wisnesky said:

btw, old fql can compute sub-object classifiers for the category of copresheaves on certain finitely presented categories. Here's a picture of the subobject classifier for the category of copreshaves on the category with a single generating arrow f:a->b.
Screenshot-2024-09-02-at-12.42.57PM.png

that seems very cool but i wouldn't know how to interpret this screenshot. would you mind adding an explanation for how to read it?

Peva Blanchard (Sep 03 2024 at 13:12):

The copresheaf $\Omega : C \to \text{Set}$ is described in the two tables $a$ and $b$.

Table $a$ represents the set $\Omega(a)$ lying over $a$. Similarly for table $b$.
You see a column $f$ in table $a$, containing ids of rows from table $b$ (aka a foreign key if you are familiar with relational database). This column encodes the function $\Omega(f) : \Omega(a) \to \Omega(b)$.

Explicitly, $\Omega(a) = \{6, 7, 8\}$ and $\Omega(b) = \{9, 10\}$. The function $\Omega(f)$ is

$$\begin{align*} \Omega(f): \Omega(a) &\to \Omega(b) \\ 6, 8 &\mapsto 10 \\ 7 &\mapsto 9 \\ \end{align*}$$

(However, I have to think about it a bit more to see why this is the subobject classifier)

Josselin Poiret (Sep 03 2024 at 13:31):

I'm expecting $\Omega(a) = 2$ and $\Omega(b) = 1$ though
Edit: Oops, forgot the empty cosieves, my bad. that matches up then!