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: Is there a notion dual to that of subobject classifier?

Peva Blanchard (Apr 13 2024 at 08:43):

A sub-object classifier $\Omega$ in a category $C$ classifies sub-objects, or more precisely, monic arrows $U \hookrightarrow X$.
image.png

The way I understand it is that the (contravariant) functor $Sub$ that maps any object to its set of monic arrows into it is represented by $\Omega$, i.e., we have a natural iso

$$Sub~X \cong Hom(X, \Omega)$$

My question is: is there something similar for epic arrows $X \twoheadrightarrow Q$ ?

For instance, let's define the (covariant) functor $F$ that maps any object to its set of epic arrows out of it. If $f : X \rightarrow Y$ is a morphism, then $Ff$ is the function obtained by pushing out epics out of $X$ (assuming the ambient category $C$ has push-outs).
image.png

One may ask whether $F$ is representable or not

$$F~X \cong Hom(I, X)~~(?)$$

Morgan Rogers (he/him) (Apr 13 2024 at 08:49):

It's not representable in a topos, but it certainly is in the dual of a topos ;)
Try it in Set and see what happens

Peva Blanchard (Apr 13 2024 at 09:09):

thanks for the hint, challenge accepted :)

Peva Blanchard (Apr 13 2024 at 21:43):

Ok, I think I got it. I delved into the proof that the subobject classifier is a representing object of the functor $Sub$. The naturality of $Sub~X \cong Hom(X, \Omega)$ yields the following commutating diagram
image.png

This says that any subobject of $X$ is the pullback of a special subobject $T$ of $\Omega$. A bit of work shows that $T$ is then a terminal object.

Similarly, if we had a natural iso $FX \cong Hom(I, X)$, then we would have a diagram
image.png

This says that any epic $X \twoheadrightarrow Q$ is the push-out of an epic $I \twoheadrightarrow S$.

image.png

The same kind of work as above shows that $S$ must be an initial object.

In $Set$, this means that $S = \emptyset$, which implies that $I = \emptyset$, because there cannot be a function into the empty set with a non-empty domain. Then $F X \cong Hom(\emptyset, X) \cong 1$. But there exists a set $X$ with more than one iso class of surjective functions out of it. Contradiction.

Julius Hamilton (Apr 13 2024 at 21:56):

Can you explain what “classify” means, in this case?

Peva Blanchard (Apr 13 2024 at 22:07):

I'll try to answer, although I guess there are many ways to respond.

In my case, "classify" really means "representing" a functor. More precisely, let's say we have a contravariant functor $F$ that associates with every $X$ a specific set $FX$. We can picture an element of $FX$ as a sort of data structure related to $X$, e.g., sub-object, or epic arrows, or etc. Let's call an element of $FX$ a $F$-structure over $X$.

The functor $F$ is representable when there exists an object $\Omega$ such that we have a Set bijection

$$FX \cong Hom(X, \Omega)$$

natural in the variable $X$. Intuitively, this means that specifying a $F$-structure over $X$ is the same as specifying a morphism from $X$ to the special object $\Omega$. In other words, the $F$-structures are classified by the morphisms with codomain $\Omega$.

Peva Blanchard (Apr 13 2024 at 22:15):

The advantage is that $Hom(X, \Omega)$ is a $Hom$ set, so it can be acted upon by pre/post-composing with other morphisms! In particular, when $X = \Omega$, we have $F\Omega \cong Hom(\Omega,\Omega)$.

The element $S \in F\Omega$ that corresponds to $id \in Hom(\Omega,\Omega)$ is quite special, as witnessed by the diagram below.

image.png

This says that any $F$-structure on an arbitrary object $X$ can be obtained by transforming (pulling-back) the $F$-structure $S$ on $\Omega$ along a characteristic morphism $X \rightarrow \Omega$. The $F$-structure $S$ is a sort of "universal $F$-structure".

Peva Blanchard (Apr 13 2024 at 22:18):

(note: just a word of caution, I am using the term "$F$-structure" in an informal way. I am not referring to an actual mathematical concept. Above, it really just means an element of the set $FX$.)

Julius Hamilton (Apr 13 2024 at 22:55):

A functor $F$ is “representable” if there is an object $\Omega$ in the source category where the Hom-set between any object in the source category and $\Omega$ is “in bijection” with whatever object F maps X to?

$Hom(X, \Omega)$ is a set. How do we know $FX$ will be one?

Julius Hamilton (Apr 13 2024 at 23:00):

I think this is a requirement of $F$, that it is a contravariant functor into $Set$. Isn’t that the definition of a ‘presheaf’?

So we think of $F$ as associating with an object $X$ a set of something meaningfully related. It can be the set of sub-objects of $X$, of epic arrows, or something else, but we imagine it will be some related “categorical notion”. For example, you could fix an object $A$, and map each $X$ to $Hom(A, X)$. I think this is called a Hom-functor.

Julius Hamilton (Apr 13 2024 at 23:04):

So if there is a bijection between whatever set $F$ maps $X$ to and some Hom-set already in the source category, it means that $F$ is a special kind of functor - a functor which is just mapping each object to a Hom-set with that object and the special object $\Omega$. This means that $\Omega$ is a categorical representation of a particular “property”. Is that the idea?

Kevin Carlson (Arlin) (Apr 13 2024 at 23:50):

That all looks pretty much right to me. The one refinement I'd point out is that while the functors $\mathrm{Sub}$ and (therefore) $X\mapsto \mathrm{Hom}(X,\Omega)$ are presheaves, i.e. contravariant functors into $\mathbf{Set},$ the functor $X\mapsto \mathrm{Hom}(A,X)$ is covariant and thus not a presheaf. However since covariant hom-functors do exist you can certainly still ask the representability question for covariant functors $\mathcal C\to \mathbf{Set}.$ For complicated reasons, in practice it's often easier to prove that a presheaf is representable than that a covariant functor is, but both problems are very important.

Peva Blanchard (Apr 14 2024 at 06:27):

Here is another example of representable functor.

Fix two objects $A$ and $B$ in a category $\mathcal{C}$. Let $F$ be the functor that maps any object $X$ to the set $Hom(X, A) \times Hom(X, B)$, i.e., pairs of arrows from $X$ to $A$ and $B$ respectively. It is a contravariant functor: for any $f : X \rightarrow Y$, we obtain a function $FX \leftarrow FY$ as described in this diagram:
image.png

We just pre-compose the two arrows out of $Y$ with $f$.

Then we can wonder if $F$ is representable: is there an object $P$ of $\mathcal{C}$ such that

$$Hom(X, A) \times Hom(X, B) \cong Hom(X, P)~(?)$$

It turns out that a representing object for $F$ (if it exists) is exactly the cartesian product $A \times B$ of $A$ and $B$.

Peva Blanchard (Apr 14 2024 at 06:30):

More generally, the limit (resp. co-limit) of a diagram can be defined as a representing object of a well-chosen contravariant functor (resp. covariant functor) with values in $Set$.

Morgan Rogers (he/him) (Apr 14 2024 at 08:18):

Peva Blanchard said:

The same kind of work as above shows that $S$ must be an initial object.

In $Set$, this means that $S = \emptyset$, which implies that $I = \emptyset$, because there cannot be a function into the empty set with a non-empty domain. Then $F X \cong Hom(\emptyset, X) \cong 1$. But there exists a set $X$ with more than one iso class of surjective functions out of it. Contradiction.

Very thorough, well done, that argument rules out the existence of a quotient classifier in any category with a strict initial object :D
A somewhat simpler argument for Set is to observe that each subset of $X$ with at least two elements corresponds to a unique quotient by taking the cokernel (pushout with 1). So for a quotient classifier we must have $|X^I|\geq |2^X - X - 1|$;
one can choose $X$ large enough for this to fail. I think $X = 2^{(2^I)}$ does the trick (in fact $X= 2^I$ is enough for $|I| \geq 3$).

Peva Blanchard (Apr 14 2024 at 14:04):

The cardinality argument is nice!

Actually, I tried to look at cardinality too, but I got a bit lost in counting the isomorphism classes of surjective functions out of $X$. It turns out that it is related to Bell numbers as pointed out by Oscar and John on the other thread.

By the way, I am always a bit sloppy with proofs involving isomorphism classes of things. Usually, I select one representative of an iso class, and go on with my proof. Most of the time, it seems alright, but how can I know for sure?

It would be nice to work with the representative, build a proof, and check that the proof is "equivariant" with respect to the choice of a representative. Or even better, composing a proof with constructions that have been proved to be "equivariant" so that I don't even have to check the "equivariance" of the proof, i.e., the proof would be equivariant by construction.

John Baez (Apr 14 2024 at 15:43):

The latter is what most of us do. Just make sure you use constructions that are 'natural' with respect to isomorphisms. Category theorists try to use such constructions whenever possible, and we don't bother to keep saying they are. We should say when our constructions are not equivariant under isomorphisms!

Mike Shulman (Apr 14 2024 at 16:12):

Moreover, there is a syntactic criterion that ensures that a construction is invariant under isomorphisms: if it can be written using the dependently-typed definition of a category without reference to equality of objects.

Eric M Downes (Apr 15 2024 at 00:13):

@Mike Shulman
That's huge, and very cool. "the dependently-typed definition of a category" ... I'm looking at [[categorical semantics of dependent type theory]]; is that a good reference for the definition you're thinking of, or should I look in the HoTT book?

Mike Shulman (Apr 15 2024 at 00:13):

No, that's something totally different. I mean https://ncatlab.org/nlab/show/category#AFamilyOfCollectionsOfMorphisms.

Kevin Carlson (Arlin) (Apr 15 2024 at 05:51):

I think Mike is referring to FOLDS, by the way, if anybody wants a reference.

Noah Chrein (Apr 15 2024 at 12:00):

Yeah send some good folds refs! I learned it in elements wondering how it relates to Mike's comment above

Mike Shulman (Apr 15 2024 at 15:08):

FOLDS is a very general approach to results of that sort, but for ordinary categories the fact is older, I believe attributed to Freyd's 1976 "Properties invariant within equivalence types of categories" and Blanc's 1979 "Equivalence naturelle et formules logiques en theorie des categories".

Mike Shulman (Apr 15 2024 at 15:10):

And nowadays we have HoTT with univalent categories.

Noah Chrein (Apr 15 2024 at 23:29):

In relation to FOLDS in elements on page 338

Finally, relations, such as equality, are only permitted on the maximal sorts. For example, in the language of categories it is permissible to write “for all objects 𝑥 and 𝑦 and for all arrows 𝑓 and 𝑔 from 𝑥 to 𝑦, 𝑓 equals 𝑔,” asserting that the category is a pre-order. But it is not permissible to write “there exists an object 𝑥 so that for all arrows ℎ, ℎ equals $1_𝑥$ ”

is this getting at what you were saying above, in the context of FOLDS?

Mike Shulman (Apr 16 2024 at 00:19):

Yes, that's the sense in which phrasing something in FOLDS is "writing it without equality of objects".

Sam Staton (Apr 21 2024 at 09:53):

Sorry I'm late: just to say, the original question reminds me a bit of this paper by Toby Kenney. "In this paper, we examine a new approach to topos theory -- rather than considering subobjects, look at quotients."