Categories and SubThings

What’s a subset? That’s easy: if we have two sets A and B, A is a subset of B if every member of A is also a member of B.
What’s a subgroup? If we have two groups A and B, and the values in group A are a subset of the values in group B, then A is a subgroup of B.
For any kind of thing **X**, what does it mean to be a sub-X? Category theory gives us a way of answering that in a generic way. It’s a bit hard to grasp at first, so let’s start by looking at the basic construction in terms of sets and subsets.
The most generic way of defining subsets is using functions. Suppose we have a set, A. How can we define all of the subsets of A, *in terms of functions*?
We can take the set of all *injective* functions to A (an injective function from X to Y is a function that maps each member of X to a unique member of Y). Let’s call that set of injective functions **Inj**(A). Now, we can define equivalence classes over **Inj**(A), where two functions f : X → A and g : Y → A are equivalent if there is an isomorphism between X and Y.
The domain of each function in one of the equivalence classes in **Inj**(A) is a function isomorphic to a subset of A. So each equivalence class of injective functions defines a subset of A.
We can generalize that function-based definition to categories, so that it can define a sub-object of any kind of object that can be represented in a category.
Before we jump in, let me review one important definition from before; the monomorphism, or monic arrow.
>A *monic arrow* is an arrow f : a → b such that (∀ g1,
>g2: x → a) f º g1 = f º g2
>⇒ g1 = g2. (That is, if any two arrows composed with
>f in f º g end up at the same object only if they are the same.)
The monic arrow is the category theoretic version of an injective function.
Suppose we have a category C, and an object a ∈ Obj(C).
If there are are two monic arrows f : x → a and g : y → a, and
there is an arrow h such that g º h = f, then we say f ≤ g (read “f factors through g”). Now, we can take that “≤” relation, and use it to define an equivalence class of morphisms using f ≡ g ⇔ f ≤ g &land; g ≤ f.
What we wind up with using that equivalence relation is a set of equivalence classes of monomorphisms pointing at A. Each of those equivalence classes of morphisms defines a subobject of A. (Within the equivalence classes are objects which have isomorphisms, so the sources of those arrows are equivalent with respect to this relation.) A subobject of A is the sources of an arrow in one of those equivalence classes.

0 thoughts on “Categories and SubThings

  1. Torbjörn Larsson

    Even though I’m not sure what we are doing and why, some of these cathegory posts makes some sense. But there are always points that seems to suggest that I don’t get it.
    “The domain of each function in one of the equivalence classes in Inj(A) is a function isomorphic to a subset of A.”
    I take it we are looking at the functions of the equivalence classes and not the isomorphism between them. How and why is the domain of a function in an equivalence class a function here and not the usual set?

  2. Mark C. Chu-Carroll

    For the “why” part, I hope it will become clearer soon. CT has a lot of construction to it; but once you get that under your belt, you gain the ability to describe a lot of interesting things in simple ways. A lot of people have asked me to write about topology; some of the complicated ideas of topology can be described very easily using category theory.
    Anyway, to get to your specific question: the functional definition is creating a broader abstract definition of subset that’s equivalent from the viewpoint of abstract set theory.
    The members of the equivalence class are functions from some other set into A. So, suppose we have one of the equivalence classes of Inj(A). Let’s call it I1.
    Take any function f : B -> A ∈ I1. What the abstract definition says is that the set B is isomorphic to a subset of A.
    Further: let’s take this definition, and look at another equivalence class, I2. If there are injective functions from the domain of functions in I2 to the domain of functions in I1, then the members of I2 are also subsets of I1. If we define ≤ as the relation we just talked about between I1 and I2, so that I2 ≤ I1, then the ≤ relation actually defines the subset lattice from set theory.

  3. Torbjörn Larsson

    “What the abstract definition says is that the set B is isomorphic to a subset of A.”
    It still seems to me that you originially wanted to say “The domain of each function in one of the equivalence classes in Inj(A) is a *set* isomorphic to a subset of A.” since the set B, the domain of f, is the domain of a function in one of the equivalence classes?!
    Sorry, I’m still confused.

  4. Mark C. Chu-Carroll

    Sorry for the delay in answering; somehow, I managed to not notice this question until you pointed it out in the other thread.
    I’m not entirely sure what you’re confused about, so bear with me a bit.
    The idea of the indirect definition of subsets is that a subset is defined by a function – not by a simple set. In the indirect definition, a subset of a set A is a mapping from some other set onto members of A.
    The reason for that is: suppose we have a set B. In the abstract definition of subset, we do not require that B have exactly the same elements as A. What we require is that there be a clean mapping from specific members of B to specific members of A. So the functions in the equivalence class define subsets: they establish the isomorphism from elements of B to the subset of elements of A.
    Does that help?

  5. Daryl McCullough

    This category-theory concept of “subset” seems so completely different from the usual notion in naive set theory. In set theory, if you have a set A, and you have a formula Phi(x), then you can form a subset A’ = { x in A | Phi(x) }. I guess that the point of category theory is that you don’t really care whether something is a subset in the set-theoretic sense, you only care about whether you can interpret something as a subset.

  6. Mark C. Chu-Carroll

    The point of category theory is to dig down to the bare roots of the structural properties of mathematical systems. The set theoretic notion of a subset has a lot of “extra” structure to it: the set is a collection of items with a specific set of properties; the selector function for a subset has to have some specific properties; etc.
    Category theory is interested only in the *structural* part of what it means to be a sub-object. So just like we have a selector function in set theory (the Phi in your example), we have a selector arrow in category theory. And we define the properties that the sub-thing has to have – but only the structural ones, not the ones that rely on the semantics of what’s *inside* the objects.
    So it *does* have a very different concept from subset – it’s a much more general concept of a particular kind of structural relationship. But the set-theoretic subset relation *is* an instance of the category theoretic sub-object relation.

  7. Torbjörn Larsson

    Thank you for your patience!
    What was confusing me is that you say that the *domain of a function* (the domain set of the mappings you refer to) “is a *function*” instead of a set (or an equivalence class).
    Now I’m also confused when you say that both an individual mapping (“a subset is defined by a function”) and the equivalence class defines a subset (“the functions in the equivalence class define subsets”). I think you mean the later.
    Perhaps you use “function” as placeholder for “equivalence class”?

  8. Vincent Aravantinos

    Torbjörn (very late 😉 :
    Agreed with you.
    Furthermore, the new subsets should not be called that way : this introduces much confusion (+ this is ill typed : a CT set is the same as a classical set ; why a CT subset is functions whereas old subsets sill are sets ? pretty confusing…)


Leave a Reply