# are quotients by equivalence relations “better” than surjections?

This might be a load of old nonsense.

I have always had it in my head that if $$f:X\to Y$$ is an injection, then $$f$$ has some sort of "canonical factorization" as a bijection $$X\to f(X)$$ followed by an inclusion $$f(X)\subseteq Y$$. Similarly if $$g:X\to Y$$ is a surjection, and if we define an equivalence relation on $$X$$ by $$a\sim b\iff g(a)=g(b)$$ and let $$Q$$ be the set of equivalence classes, then $$g$$ has a "canonical factorization" as a quotient $$X\to Q$$ followed by a bijection $$Q\to B$$. Furthermore I'd always suspected that these two "canonical" factorizations were in some way dual to each other.

I mentioned this in passing to a room full of smart undergraduates today and one of them called me up on it afterwards, and I realised that I could not attach any real meaning to what I've just said above. I half-wondered whether subobject classifiers might have something to do with it but having looked up the definition I am not so sure that they help at all.

Are inclusions in some way better than arbitrary injections? (in my mind they've always been the "best kind of injections" somehow). Are maps to sets of equivalence classes somehow better than arbitrary quotients? I can't help thinking that there might be something in these ideas but I am not sure I have the language to express it. Maybe I'm just wrong, or maybe there's some ncatlab page somewhere which will explain to me what I'm trying to formalise here.

• I guess one could go all the way and say that if $f:X\to Y$ is an arbitrary map of sets then $f$ factors as a quotient by an equivalence relation $X\to X/\sim$, followed by a bijection $X/\sim\to f(X)$, followed by an inclusion $f(X)\subseteq Y$. Is this a thing? – Kevin Buzzard Dec 7 '18 at 21:23
• How could category theory ever tell the difference between an inclusion and an arbitrary injection? Dually: how could it tell the difference between "the" quotient map by an equivalence relation and an arbitrary surjection? If you move away from the category of sets, there is some distinction amongst good and bad epi/monomorphisms. See, e.g. "effective epimorphism" and related notions. – Dylan Wilson Dec 7 '18 at 21:41
• from the category theory perspective, the main fact for sets and functions is that every function factors into a surjection followed by an injection. However, from the perspective of category theory, you can't distinguish inclusion maps from injections, because you are only looking at objects and morphisms: the notion of 'element' is lost. However, for your other comment: there is the notion of factorization system. The same idea holds for groups or rings too: a group homomorphism $\phi: G \to H$ factors into $G \to G/\ker \phi \to \phi(G) \to H$. – Jacob White Dec 7 '18 at 21:47
• A subobject of $A$ is an isomorphism class of monic arrows into $A$ ($f\colon B\to A$ and $f'\colon B' \to A$ are isomorphic if there is an isomorphism $g\colon B\to B'$ such that $f = f'\circ g$). Dually, a quotient object of $A$ is an isomorphism class of epic arrows out of $A$. I suppose you could view the category of sets as being equipped with an extra structure: a choice of a unique representative in each subobject class (the inclusion) and each quotient object class (the "actual quotient"). Then each monic arrow factors uniquely as an isomorphism followed by an inclusion, ... – Alex Kruckman Dec 7 '18 at 22:20
• You may be thinking of a context that abstracts to an M-category (ncatlab.org/nlab/show/M-category). The 'tight morphisms' are the literal subset inclusions, and so have a role distinguished from arbitrary inclusions. In your setup one also seems to be asking that the class of tight morphisms are all regular monomorphisms (ncatlab.org/nlab/show/regular+monomorphism), that is, literally subsets carved out by equations (say by constructing the pullback of {1} --> {0,1} along a characteristic function by an equaliser). – David Roberts Dec 7 '18 at 23:24

It seems that you've got factorization of maps covered, so let me address the question of why canonical quotient maps and canonical inclusions are "better".

Given a set $$X$$, in general there is a proper class of injections $$Y \to X$$. However, many of these are isomorphic, where injections $$i : Y \to X$$ and $$j : Z \to X$$ are isomorphic if there is an isomorphism $$k : Y \to Z$$ such that $$i = j \circ k$$. The isomorphism classes of injections into $$X$$ are the subobjects of $$X$$. In fact, there are only set-many subobjects of $$X$$ (in category-theoretic language, sets form a well-powered category). It is pesky to work with set-many proper equivalence classes, so we instead look for a set $$P(X)$$ of injections into $$X$$, one from each isomorphism class. We may additionally require some nice properties, for instance, if $$i : X \to Y$$ is in $$P(Y)$$ and $$j : Y \to Z$$ is in $$P(Y)$$, we would expect $$j \circ i : X \to Z$$ to be in $$P(Z)$$. One can come up with a wish list of such nice closure conditions, here's another one: if $$i : Y \to X$$ and $$j : Z \to X$$ are in $$P(X)$$, and there is (a unique) $$k : X \to Z$$ such that $$i = j \circ k$$, then $$k$$ is in $$P(Z)$$.

We know the answer, of course, just take $$P(X)$$ to be the canonical subset inclusions into $$X$$. This is not the only choice of such representative inclusions, but it's a pretty good one.

We may therefore say that the canonical inclusions of subsets are "better" because they are the canonical representatives of subobjects (equivalence classes of injections).

The answer for quotient maps and surjections is dual. Consider equivalence classes of surjections, quotiented by isomorphism. There are only set-many such classes, therefore sets form a well-copowered category. (Some people say "cowell-powered" but then why not call it "ill-powered"?) This time we look for a set $$Q(X)$$ of surjections from $$X$$, each representing one equivalence class of surjections from $$X$$. We may take $$Q(X)$$ to be the set of all canonical quotient maps $$X \to X/{\sim}$$, or just the set of all equivalence relations on $$X$$. Once again, canonical quotient maps are "better" because they are the distinguished representatives of isomorphism classes of surjections.

• "This is not the only choice of such representative inclusions, but it's a pretty good one.". Can you give an example of another one? In particular do you know one satisfying all the properties you mention, as well as all the further properties that we might think of once you've come up with one? It would be really cool if we could either classify the subset inclusions uniquely or prove that there is no chance of classifying them uniquely. – Kevin Buzzard Dec 8 '18 at 0:11
• For any set $S$ let $\bar{S} = \{\{x\} \mid x \in S\}$ and let $b_S : \bar{S} \to S$ be given by $b_S(\{x\}) = x$. Given $S \subseteq X$ let $i_S : S \to X$ be the canonical inclusion. Define $P(X) = \{ i_S \circ b_S : \bar{S} \to X \mid S \subseteq X\}$. Then I think we get representatives of injections that are closed under composition (because they're not composable). – Andrej Bauer Dec 8 '18 at 1:04
• @AndrejBauer At the end of your second paragraph, do you want the source of $k$ to be $Y$ and not $X$? – Santana Afton Dec 8 '18 at 4:03
• Is this bar example really closed under composition? I start with $Z$, I choose an actual subset $Y_0$, I get a corresponding map $Y\to Z$ in $P(Z)$ with $Y=\overline{Y_0}$, I choose a subset $X_0$ of $Y$, I get a map $X\to Y$ in $P(Y)$, but I don't think that $X\to Z$ will be in $P(Z)$ because I'll have to strip squiggly brackets twice, right? – Kevin Buzzard Dec 8 '18 at 8:05
• It would be a bit depressing (but perhaps not surprising) if there was some non-constructive "of course other choices for $P$ exist, just start off with a map from a set with one element to a set with two elements which isn't an inclusion and then extend by Zorn's Lemma somehow". – Kevin Buzzard Dec 8 '18 at 8:09

Are inclusions in some way better than arbitrary injections? Are maps to sets of equivalence classes somehow better than arbitrary quotients?

This is a simple-minded answer, but I would say yes because there is a proper class of distinct injections into $$Y$$ --- the injecting set $$X$$ can live anywhere in the set-theoretic universe --- whereas inclusions into $$Y$$ are effectively just subsets of $$Y$$. Under the natural notion of equivalence for injections, distinct subsets give inequivalent injections, so you could say that going from injections to inclusions is a matter of selecting one distinguished, canonical element from each equivalence class of injections.

I would say that the injections into $$Y$$ are classified by the subsets of $$Y$$, and similarly the quotients of $$X$$ are classified by the equivalence relations on $$X$$.

• I completely understand that I am choosing one element from each equivalence class of injections. What I am unsure about is whether it is "canonical" and indeed what "canonical" even means in this context. – Kevin Buzzard Dec 9 '18 at 1:33
• Ah, I see. I suppose "canonical" has a fairly straightforward informal meaning, but if you want a rigorous definition ... I don't know, it doesn't seem likely. – Nik Weaver Dec 9 '18 at 2:03
• What does your answer mean if you cannot give a rigorous definition of "canonical"? Taking this further -- what does my question mean? Is this mathematics at all? This is what I do not understand. I know what mathematics is supposed to be, and there are not supposed to be things which are open to discussion. – Kevin Buzzard Dec 9 '18 at 11:01
• @KevinBuzzard Since the category of sets is equivalent to its skeleton, this question is not 'mathematicial' (definable in any invariant way) without additional structure (as in Mike's answer and David's comment). If you are working with ZFC, you can promote the category of ZFC sets to an M-Category in a canonical way, and that is how you make it mathematical. – Harry Gindi Dec 9 '18 at 17:46
• And in Harry's comment, one can replace ZFC by any set theory in which is meaningful to define subsets $x\subseteq y$ as $\forall z, z\in x \Rightarrow z\in y$. – David Roberts Dec 9 '18 at 19:49

The nLab page you're looking for is called factorization systems. Here is my favorite one, which I think answers your question. In any category with finite limits and colimits, every morphism $$f : X \to Y$$ has a canonical factorization

$$X \to \text{coim}(f) \to \text{im}(f) \to Y$$

where $$\text{im}(f)$$, the regular image, is the equalizer of the cokernel pair of $$f$$ (this is the "nonabelian" version of "kernel of the cokernel") and $$\text{coim}(f)$$, the regular coimage, is the coequalizer of the kernel pair of $$f$$ (again, the "nonabelian" version of "cokernel of the kernel"). These two constructions are categorically dual and so, among other things, the coimage-image factorization of $$f$$ in the opposite category is the same sequence of maps but in the opposite order.

In $$\text{Set}$$, the coimage and image are both the image of a function in the usual sense, but computed in different ways, which I think match the distinction you're getting at. $$\text{coim}(f)$$ is computed, more or less, by constructing the equivalence relation on $$X$$ defined by $$x_1 \sim x_2 \Leftrightarrow f(x_1) = f(x_2)$$, then quotienting $$X$$ by it. $$\text{im}(f)$$ is computed in a categorically dual way, although it looks a little strange at first: by first constructing the pushout $$Y \sqcup_X Y$$, then isolating the subset of $$Y$$ of elements which are sent to the same element by both of the canonical maps $$Y \to Y \sqcup_X Y$$.

In particular, the factorization you want for an injection is the regular image factorization, and the factorization you want for a surjection is the regular coimage factorization, so they are in fact categorically dual. The full coimage-image factorization combines these.

It's a nontrivial theorem that the map $$\text{coim}(f) \to \text{im}(f)$$ is an isomorphism in $$\text{Set}$$. It's also an isomorphism in any abelian category and in $$\text{Grp}$$ (this is an abstract form of the first isomorphism theorem), but in general it's just both a monomorphism and an epimorphism. A very instructive example is $$\text{Top}$$, where $$\text{coim}(f)$$ is the set-theoretic image topologized as a quotient of $$X$$, and $$\text{im}(f)$$ is the set-theoretic image topologized as a subspace of $$Y$$. (Note that these coincide for compact Hausdorff spaces!)

• But these things like im and coim are I believe defined by category-theoretic properties and are hence only defined up to unique isomorphism. Aren't I trying to do something better than isolating the object up to unique isomorphism? I'm wondering if in Set there is some sort of canonical representative (and am still not sure about if there is one). – Kevin Buzzard Dec 8 '18 at 0:06
• @Kevin: yes, I'm eliding some philosophical points here that I think Andrej's answer tackles better, at least in $\text{Set}$. In particular I am really referring to a particular construction of the image and coimage rather than to anything which satisfies their universal properties, which is a sin I don't normally indulge in. My excuse is that I never just isolate myself to $\text{Set}$ if I can help it; morally the coimage is "the image as seen from $X$" and the image is "the image as seen from $Y$," as I think the example of $\text{Top}$ makes vividly clear, and so I think of them as... – Qiaochu Yuan Dec 8 '18 at 0:10
• ...conceptually distinct even though they happen to agree as universal constructions in $\text{Set}$. Said another way, I'm either talking about your state of knowledge before you learn that $\text{coim}(f) \to \text{im}(f)$ is an isomorphism in $\text{Set}$, or I'm reserving the right to replace $\text{Set}$ with another category in which that's false. If you really want to stick to $\text{Set}$ then Andrej's answer is probably more relevant than mine. – Qiaochu Yuan Dec 8 '18 at 0:12

Andrej's answer is a good one for explaining "what is special" about injections and quotients. In terms of formalizing the notion of "subset inclusion", David Roberts has already mentioned in a comment the notion of M-category, which could be used to represent "the category $$\mathrm{Set}$$ together with the information about which injections are inclusions" (or which surjections are quotients).

Another formalization which is specifically adapted to "inclusion-like" subcategories is called (appropriately enough) a system of inclusions (with enhancements that add adjectives such as "directed" and "structural"); it was introduced in this paper by Awodey, Butz, Simpson, and Streicher. One could presumably dualize this somehow to obtain a notion of "system of quotients". Note that a system of inclusions is a particular kind of M-category.

As has been noted, when the category $${\rm Set}$$ is treated "purely category-theoretically" it does not "notice" which injections are inclusions, i.e. this information does not transfer usefully across an equivalence of categories. An M-category is a way of defining a "category-theoretic" structure (namely, a certain kind of enriched category) that nevertheless can carry this sort of information.

• Thanks for the reference, I was aware of but failed to mention it. – Andrej Bauer Dec 9 '18 at 9:08
• However, the standard construction of quotients doesn't naively form an M-category, as the 'set of equivalence classes with a map to it' isn't transitive: one gets sets of sets of equivalence classes. Perhaps there is a way to fix this, but I didn't see it with a (small amount of) thinking. – David Roberts Dec 9 '18 at 19:52
• So "M-category" does not answer the question for surjections? – Kevin Buzzard Dec 9 '18 at 22:18
• @DavidRoberts Good point, I was too glib about that. I guess the dual notion of "system of quotients" would have to omit the composability if you want to include the usual notion of quotient set in ${\rm Set}$. However, it occurs to me that "quotients" of setOIDS do compose, so at least ${\rm Set}$ is equivalent to some category that has a system of quotients with composition. – Mike Shulman Dec 9 '18 at 22:47

"Are inclusions in some way better than arbitrary injections?"

No they are not.
Anything that you can say about the one, you can say about the other.

In particular: Given $$X$$, there is a set of inclusions into $$X$$. And there is a (large groupoid equivalent to a) set of injections into $$X$$. For all practical purposes these are the same thing. So they should be treated as the same thing.

Are quotient maps somehow better than arbitrary surjections?

Again no.
Same story.

The fact that we can talk about inclusions versus injections is an artefact of our set theoretic foundations of mathematics. It would be better to use a language that disallows us from asking whether two sets are equal, and only allows us to talk about isomorphisms between sets.
We largely already do this in practice. When we write $$\mathbb Z \subset \mathbb Q$$, we don't stop to explain that elements of $$\mathbb Q$$ are defined as pairs of elements of $$\mathbb Z$$, and we don't distinguish between $$\mathbb Z$$ and its image in $$\mathbb Q$$. We just write $$\mathbb Z \subset \mathbb Q$$.

Unfortunately, I'm not knowledgeable enough in foundational issues in order to make sense of the notion of "a language that disallows asking whether two sets are equal, and only allows to talk about isomorphisms". But I'm sure that such a thing exists (and that it can be tweaked so as to be exactly as powerful as ZFC).

• "a language that disallows asking whether two sets are equal, and only allows to talk about isomorphisms" One approach is FOLDS, by Makkai (cf ncatlab.org/nlab/show/FOLDS), and another approach was discussed by Bénabou projecteuclid.org/euclid.jsl/1183741771 – David Roberts Dec 12 '18 at 1:57
• Sounds like univalent foundations to me. – Nik Weaver Dec 12 '18 at 5:29
• "It would be better to use a language that disallows us from asking whether two sets are equal, and only allows us to talk about isomorphisms between sets." Better for who? I think that computer scientists using dependent type theory are well aware of the thorny issues surrounding equality, and I don't think they really have the notion of a subtype at all (at least not in such a way that a subtype of a subtype was syntactically or definitionally equal to the corresponding subtype). But they need equality -- it helps their algorithms. – Kevin Buzzard Dec 19 '18 at 15:32
• @Kevin Buzzard. "But they need equality -- it helps their algorithms." I would be interested if you could substantiate this claim by an example. (this is not just me being oppositional; I'm genuinely interested to know whether such a situation does occur) – André Henriques Dec 19 '18 at 18:45
• Sorry, I've only just seen this comment now. Over the last 18 months I've been learning about how to check mathematical proofs on a computer, and an issue people often run into is how to justify assertions which are mathematically trivial. Equality of types is a wonderful thing, because the recursor for equality enables you to do substitution (if $P(X)$ is true and $X=Y$ then $P(Y)$ is true). Isomorphism in dependent type theory is far harder to rewrite with. I think this is a big difference between dependent type theory and HOTT, however I am certainly not an expert. – Kevin Buzzard Jan 21 at 17:02