# Categorial definition of subsets

I cannot see why this definition http://en.wikipedia.org/wiki/Subobject is equivalent to subsets in the category of sets. I am confused by the following facts,

1) the partial order is defined between morphism, and not objects (which are the sets in the category of sets), but the subset relation must hold between sets (i.e. objects)

2) why are there three objects involved, when for a subsetrelation just two sets are involved?

How does this defintion makes sense for example for $\{ 1 \} \subset \{ 1,2,3 \}$?

-
"In the category $\bf Sets$, a subobject of $A$ corresponds to a subset $B$ of $A$, or rather the collection of all maps from sets equipotent to $B$ with image exactly $B$. The subobject partial order of a set in $\bf Sets$ is just its subset lattice." (The Wikipedia link you provided, emphasis mine). – Asaf Karagila Feb 5 '13 at 22:01
Aside: $\leq$ is not a partial order on monomorphisms with codomain $A$: it is a preorder. The important distinction is that, usually, many different monomorphisms correspond to the same subobject. – Hurkyl Feb 6 '13 at 0:25
@Stefan The point is that those two definition aren't equivalent, but the definition of subobject is what comes closer to the notion of subset when you deal with categories. In practice is a way to extend the concept of substructure to categories which don't deal with sets. – Giorgio Mossa Feb 6 '13 at 10:00

I'll try to get the idea across. Instead of thinking of a subset $\{1\}\subseteq\{1,2,3\}$ as just the set $\{1\}$, try to emphasize the inclusion $\{1\}\hookrightarrow\{1,2,3\}$ in your head.

Why? From the categorical point of view, there is no real distinction between isomorphic sets (and in the category of sets, "isomorphic" means "of the same cardinality"). Indeed, $\{1\}$, $\{2\}$ and $\{\text{elephant}\}$ are all isomorphic as sets. This means that if you just define a subobject of $A$ to be an object that has a monomorphism to $A$, $\{\text{elephant}\}$ will be a subobject of $\{1,2,3\}$, as will $\{1\}$ and $\{2\}$.

Now you want to somehow distinguish $\{1\}$ and $\{2\}$ as being different subsets (and you're maybe tempted to try to come up with a definition in which $\{\text{elephant}\}$ is not a subset of $\{1,2,3\}$). You would want to say "$B$ is a subobject of $A$ if there is a monomorphism from $B$ to $A$ and the elements of $B$ really are in $A$". This is impossible in categorical terms, because "elements of" does not make sense in a category.

And let's face it, we don't really care about the names of the elements in all of our sets. If we want to give a new name (say $\text{elephant}$) to the element 1 of our sets, we can do so and nothing will explode. In this spirit, we don't really care whether the element in $\{1\}$ is actually called 1 and the element in $\{2\}$ is really called 2. What we care about is how the sets $\{1\}$ and $\{2\}$ have injections (monomorphisms) to $\{1,2,3\}$ (in this case, what the images of the morphisms are). This is what distinguishes $\{1\}\hookrightarrow\{1,2,3\}$ from $\{2\}\hookrightarrow\{1,2,3\}$: although $\{1\}$ and $\{2\}$ are isomorphic as sets (in this case even in a unique way), there is no isomorphism between them that will make the inclusion $\{1\}\hookrightarrow\{1,2,3\}$ correspond to the inclusion $\{2\}\hookrightarrow\{1,2,3\}$.

Now let's look at the injection $\{\text{elephant}\}\hookrightarrow\{1,2,3\}$ mapping $\text{elephant}$ to $2$. In the spirit of category theory, there is no difference between including $\text{elephant}$ into $\{1,2,3\}$ this way or the element $2$ in the usual way. And indeed, the inclusions $\{2\}\hookrightarrow\{1,2,3\}$ and $\{\text{elephant}\}\hookrightarrow\{1,2,3\}$ are equivalent for the equivalence relation explained on the Wikipedia article (there is an isomorphism between $\{2\}$ and $\{\text{elephant}\}$ making the triangle consisting of this isomorphism and the two inclusions commute -- in other words, if we suddenly rename $\text{elephant}$ to 2, then the inclusion $\{\text{elephant}\}\hookrightarrow\{1,2,3\}$ suddenly becomes the same as the inclusion $\{2\}\hookrightarrow\{1,2,3\}$).

Let me try to sum up the situation in a single sentence: we consider subsets of $A$ as (equivalence classes of) inclusions of any set into $A$, where we consider two inclusions to be the same if they have the same image (indeed, this is what the equivalence relation amounts to).

I find it hard to explain this, but I hope this is close enough to the heart of the matter to be useful. Let me just give you one confusing remark: one could inject $\{1\}$ into $\{1,2,3\}$ by mapping 1 to 2. In that case, we should regard this inclusion as the same subobject as the usual inclusion of $\{2\}$ into $\{1,2,3\}$ (meaning the two monomorphisms are equivalent).

-

When one starts to learn category theory one often learns how think about concepts, which one already knows (or claims to know) in a new, almost always more conceptual way. And one also learns that some notions, which are used all the time outside of category theory, don't really capture what is really going on.

For example, this is the case for the inclusion of sets. In any of the common axiomatizations of set theory it makes sense to ask if two sets $X,Y$ are contained in each other. This is just a property. But in some cases this is quite awkward: Is $42$ contained in $\pi_4(S^2)$? Probably no, but this depends on the precise definitions of these sets, and in any case the answer won't give us any insight about these two objects. With the von Neumann definition of natural numbers, we have $2 \subseteq 3$ (namely, $2=\{0,1\}$ and $3=\{0,1,2\}$). But again, is this a useful property? What is the reason for this inclusion? And is this reason unique at all? A set with three elements has three subsets with two elements. In other words, there are three injective maps $2 \to 3$, and no one can be preferred from the other. Thus, instead of saying that $2 \subseteq 3$ holds or holds not, it is more meaningful if some map $2 \to 3$ witnesses $2 \subseteq 3$. And this is exactly what happens in category theory. Similarily, it doesn't really make sense to ask if the set theoretic foundations guarantee that $\mathbb{Z} \subseteq \mathbb{Q}$. It is more meaningful to ask if a given map $\mathbb{Z} \to \mathbb{Q}$ provides a reason for us to write $\mathbb{Z} \subseteq \mathbb{Q}$. And of course we should also specify which structure this inclusion is refering to, for example it could refer to $\mathbb{Z}$ and $\mathbb{Q}$ as commutative rings. Then the map is required to be a homomorphism of commutative rings. Perhaps I over-emphasize these trivialities here, but students always ask themselves these questions which are well-defined from a set-theoretical point of view, but in reality have no meaning at all. And I wonder why this still happens.

Anyway, after this motivation it is easy to understand the definition of a subobject in an arbitrary category $C$. If $X,Y$ are objects of $C$, it doesn't make sense to ask if $X$ is a subobject of $Y$. Instead, one may ask which monomorphism $X \to Y$ provides a reason for this, and we remember it, i.e. it belongs to the data of the subobject! Moreover, two reasons $X \to Y$ and $X' \to Y$ are equivalent if there is an isomorphism $X \cong X'$ such that the obvious diagram commutes. An equivalence class with respect to this relation is called a subobject of $Y$.

If $C$ is the category of sets, then there is a bijection between the subsets of $Y$ and the subobjects of $Y$. Similar statements hold for categories of algebraic structures. This does not mean that we have found a more complicated definition of substructures; instead, we have found the correct one. Open an arbitrary book on galois theory and field extensions and replace everywhere "field extension" by "morphism of fields", it will make the subject a lot more transparent and understandable (if anyone is interested I can expand this).

-
Regarding the last paragraph, my Galois Theory lecturer tried that and was heavily criticised at the time... but now with hindsight it does make sense! – Zhen Lin Feb 6 '13 at 0:12
The correct one? That sounds mighty condescending... – Asaf Karagila Feb 6 '13 at 0:15
So is it right that categorically we cannot distinguish the statements $\{ 0, 1 \} \subseteq \{ 0, 1, 2 \}$, $\{ 1,2 \} \subseteq \{ 0, 1, 2 \}$ and $\{ 1,5 \} \subseteq \{ 0,1,2 \}$? – Stefan Feb 6 '13 at 11:13
@Stefan! It rather goes like $\{0,1\} = \{0,1\}\subseteq\{0,1,2\}$, $\ \{1,2\}\cong\{0,1\}\subseteq\{0,1,2\}\$ and $\ \{1,5\}\cong\{0,1\}\subseteq \{0,1,2\}$. Now each symbol of "$=$", "$\cong$", "$\subseteq$" represents a morphism, identity, isomorphism, inclusion, respectively, composed together yielding any monomorphism. The important thing is (the subobject wants to be) the range of this monomorphism. – Berci Feb 6 '13 at 11:23
These objects themselves are isomorphic in $\Bbb{Set}$, hence, categorially they are kind of indistinguishable, and can play the same role as any set of $2$ elements. That's why subobjects are rather morphisms than simple objects. An injection $f:\{a,b\}\to\{0,1,2\}$ represents its range, the subset $\{f(a),f(b)\}$ of $\{0,1,2\}$. Two such injections are isomorphic in ${\rm Sub}(\{0,1,2\})$ iff their range is the same. – Berci Feb 6 '13 at 11:34

Let $S$ be a set (for example $\{1,2,3\}$) then there is a category $\operatorname{Sub}(S)$ of subobjects of $S$. Its objects are "subsets of $S$" but these are actually isomorphism classes of sets with an injective (monic = injective in Set) map into S. Its morphisms are just maps that make the triangle into $S$ commute.

E.g. $\{6,3\}$ is a representative of an isomorphism class of subobjects of $S$ because $f(6) = 1$, $f(3) = 2$ gives us the object $(\{6,3\},f) \in \operatorname{Sub}(C)$.

Let $S' \subseteq S$ then clearly $(S',i)$ is a subobject of $S$, but the point here is that the up-to-isomorphismness of category theory comes through in the previous example.

-
2 monomorphisms (injective functions) belong to the same isomorphism class (i.e. determines the same 'subobject' of an object $C$) iff their range --within $C$-- is the same. But this 'range' (or 'image') notion is harder to catch in categorical terms, that's why this equivalence relation (being isomorphic in ${\rm Sub}(C)$) enters the picture. – Berci Feb 5 '13 at 22:05

1) the partial order is defined between morphisms, and not objects (which are the sets in the category of sets), but the subset relation must hold between sets (i.e. objects)

There is an unfortunate notational confusion here, which experienced category theorists untangle mentally, but it helps to spell out explicitly for beginners.

When we write $u : S \to A$, we mean that there is a morphism $\langle S, A, u \rangle$ in the collection $\textbf{Mor}_C$ of the category. In other words, the morphisms carry with them their own source and target objects (the $S$ and the $A$ in this case). So, as you can see, when we are defining a partial order on morphisms, the source objects $S$ are also involved. (Using triples $\langle S, A, u\rangle$ is one way of formalizing what morphisms are. There are also other ways, but they will get more complicated in this context.)

Since the partial order is being defined only between morphisms that lead into $A$, we can mentally erase the $A$ in the data, and regard the morphisms as just being pairs $\langle S, u\rangle$. So, we are saying $S$ is an object that "looks like" a subset of $A$, and $u$ is the way to interpret its elements as the elements of $A$.

So, $\langle S, u\rangle \leq \langle T, v\rangle$ means that $S$ and $T$ "look like" subsets of $A$, we have ways of interpreting their elements as those of $A$ and, further, there is also a monomorphism $w : S \to T$ which allows us to interpret the elements of $S$ as the elements of $T$ in a way that is consistent with $u$ and $v$.

Moreover, $\langle S, u\rangle \equiv \langle T, v\rangle$ means that $S$ and $T$ are isomorphic in a way that is consistent with the chosen interpretations $u$ and $v$.

2) why are there three objects involved, when for a subsetrelation just two sets are involved?

You want to think of the objects in a category as types rather than as sets. You can only talk about the equality of two elements within the same type. So, the normal set-theoretic locution $S \subseteq T \iff (\forall x.\, x \in S \to x \in T)$ is incoherent from a types point of view. It involves taking an element of type $S$ (viz., $x$) and talking about its equality with the elements of type $T$. A type-correct way of saying $S \subseteq T$ is $$\forall x : S.\, \exists y : T.\, u(x) =_A v(y)$$ In other words, to talk about $S$ being a subset of $T$, we need a larger set $A$, of which both $S$ and $T$ are part (intuitively), and we have ways of interpreting the elements of $S$ and $T$ as elements of $A$ (provided by the monomprhisms $u$ and $v$.) This is precisely what is meant by $\langle S, u\rangle \leq \langle T, v\rangle$.

-
see my comment at Martins post: "So is it right that categorically we cannot distinguish the statements $\{ 0, 1 \} \subseteq \{ 0, 1, 2 \}$, $\{ 1,2 \} \subseteq \{ 0, 1, 2 \}$ and $\{ 1,5 \} \subseteq \{ 0,1,2 \}$?" – Stefan Feb 6 '13 at 11:18
You cannot make a statement like $\{1,2\} \subseteq \{0,1,2\}$ categorically, let alone distinguish it from another. What you might say is that $\langle \{1,2\}, u\rangle$ is a subject of $\{0,1,2\}$ where $u$ is the injection of $\{1,2\}$ in $\{0,1,2\}$. But then neither $\langle \{0,1\},u \rangle$ nor $\langle\{1,5\},u\rangle$ is a subobject because $u$ doesn't type-check in those cases. – Uday Reddy Feb 7 '13 at 15:33
I think what you might need is a 10-minute exercise: Prove that, in category Set, the subobjects of $A$ (as clarified above) are one-to-one with the subsets of $A$. – Uday Reddy Feb 7 '13 at 17:56