Categories from scratch

Background terminology

Observability

Each topic has two “groups” of things: things that can be observed from the “outside”, and things that appear (mostly) as black boxes from the outside but are “connected” between the things in the first group:

Grouping things together

Each topic provides a mechanism to plug the “black box” things together:

Composition semantics

Each topic has a notion of “good” compositions that “make sense”, and “bad” compositions that nonsensical and not expected to “work properly”:

To identify “good” from “bad” compositions, each topic places a large emphasis on the notion of interface:

Remarkably, users understand or conceptualize interfaces, despite the fact they are not always defined explicitly beforehand.

Neutral behaviors

Each topic has some instances of black box things that “do nothing”, ie have a neutral behavior:

The knowledge of whether a black box is neutral can be gained in either or three ways.

Either it is known to be neutral by construction, because the specification is available for scrutinity and can be proven to define a neutral behavior:

Or, the knowledge is provided externally, eg. by fiat:

Or, it is discovered: to find out whether a black box thing A is neutral, assuming an observer has access to a pre-existing, valid “observable thing” that can be fed to A, then the observer can deduce the behavior of A is “neutral” if the observable as a result of A’s activity is the same as the original observable:

Once a black box thing N is known to be neutral, then its composition “left” and “right” with another black box thing A can be assumed to have the same behavior as A on its own:

Associativity

When one composes three black box things A, B and C together (assuming the compositions are point-wise sensical), the order in which the composition is realized does not change the behavior:

Objects and morphisms

First, the observables are named objects. The black boxes things are named morphisms or arrows.

Modeling: be careful about equivalences

Categories are defined over mathematical sets of objects and morphisms. Sets are different from simple “collections” (or “bag”) of things from the real world: all their elements are distinct, according to some equivalence relation.

So in order to talk about categories over things from the real world, we must first choose how to define the mathematical sets. This choice is called a model and multiple models are possible for the same collection of things.

The most focus should be given to the set of morphisms. The set of objects is simply derived from it once the morphisms are properly identified. For example, in our pipes example, considering what happens to data streams. What does it mean for two processes to be equal or different?

We can choose for example “data stream equality”. By this standard, two processes that filter out lines containing the text “foo” over any data stream are the “same thing.” So “sed '/foo/d'” and “grep -v foo” are the same morphism.

If we choose this definition for morphisms, then the objects are not individual files (or time-particular datastreams over FIFOs), but rather entire classes of all possible data streams that compare equal to each other byte by byte. For example, a stream that delivers “helloworld” in one go is the same stream as another that delivers “hello” and then “world” 5 seconds later.

Another possible choice for a definition is “physical equality”. By this standard, two processes that run at different times or in different physical regions of the system are distinct, even if they perform the same task. So two processes run from the same command (eg cat) at different times end up as different morphisms in the set.

If we choose this definition, then the mathematical objects are not only data streams, but also where and when the bytes are physically encoded. So two streams that deliver “helloworld” in different places/times are distinct objects.

The rule of thumb while choosing a definition is the following: if one wants to talk about categories over sets of objects and morphisms that are already mathematically defined, then all is well. If one wants to use category theory over things that are not yet mathematical, be careful to explain clearly and explicitly how they are modeled using mathematical sets, and which equivalence relation is used.

For the next sections, we use the following definitions:

Arrow notation

The arrow notation describes a morphism: “\(A\rightarrow B\)” is a description for a morphism from object A to object B. The two sides of a morphism can be named “input” and “output”, but are usually named “source” and “target”.

There may be multiple morphisms between any two objects, so the arrow notation does not identify a particular morphism; instead, it can be seen as an “interface” or “type” for the set of all morphisms between the designated objects:

Composition

If two morphisms have the same intermediary object, it is possible to compose them together (cf. Composition semantics above). This is abstracted by an composition operator noted “\(\cdot\)“: given two compatible morphisms f and g, “\(g\cdot f\)” designates their composition, ie. \((g\cdot f)(x) = g(f(x))\).

By construction, if f can be described by \(A\rightarrow B\) and g by \(B\rightarrow C\), then \(g\cdot f\) can be described by \(A\rightarrow C\).

Composition is associative: for any f, g, h, \((f\cdot g)\cdot h = f \cdot (g\cdot h)\).

Identity

For any object, there must exist at least one morphism that keeps the object unchanged. Each such identity morphism for an object x is called “\(\text{id}_x\)” (sometimes also “\(\mathbf{1}_x\)”) and can be described as \(x\rightarrow x\); it must satisfy the following property: for every morphism \(f : A\rightarrow B\), \(\text{id}_{B}\cdot f = f = f\cdot\text{id}_A\).

So there must be at least as many identity morphisms as there are objects.

For categories defined by modeling over concrete things, it may be necessary to extend the mathematical set of morphisms with “theoretical” identity morphisms, when there are no concrete identities.

For example, it is not possible to build a concrete identity circuit: any one-to-one pairing of physical input and output connectors with direct wires between them is bound to introduce noise in the signal due to the physical distance. However, the mathematical set modeling circuits can be naturally extended to include “virtual” identity circuits that preserve signals unchanged.

Hopefully, with many categories the identity morphisms can be concretely constructed in the application domain:

Definition of a category

A category is an algebraic structure formed over:

• a (mathematical) set of objects,
• a (mathematical) set of morphisms over these objects containing at least one identity morphism for each object,
• an associative composition operator.

Unicity of the identity

Although the existence of identity morphisms is a prerequisite to form a category (axiomatic), it is possible to prove within category theory that each identity is unique.

You can do this as follows.

Suppose you have two morphisms \(\text{id1}_x\) and \(\text{id2}_x\) that preserve object x and satisfy the axiomatic identity properties:

1. for every \(f : y\rightarrow x\), \(\text{id1}_x\cdot f = \text{id2}_x\cdot f = f\); and
2. for every \(g : x\rightarrow y\), \(g\cdot\text{id1}_x = g\cdot\text{id2}_x = g\).

In equation #1, replace f by \(\text{id2}_x\), and you find that \(\text{id1}_x\cdot \text{id2}_x = \text{id2}_x\).

In equation #2, replace g by \(\text{id1}_x\), and you find that \(\text{id1}_x\cdot \text{id2}_x = \text{id1}_x\).

Since both left-hand sides are equal, you have proven that \(\text{id2}_x = \text{id1}_x\). \(\blacksquare\)

What this means in practice: if you can construct/define two morphisms in a category and prove they satisfy the identity laws, then you have proven they are the same morphism. In our examples, that means identity commands (pipes), compilers or circuits become interchangeable with regards to their properties in category theory. This can be used to simplify formulas that use complex morphisms into simpler ones.

Invertibility and isomorphisms

The general notion of invertibility for a morphism can be expressed purely in the vocabulary of category theory:

\(f : A\rightarrow B\) is invertible if there exists \(g : B\rightarrow A\) such that \(g\cdot f : \text{id}_{A}\) and \(f\cdot g : \text{id}_B\).

Invertible morphisms are also called isomorphisms.

By extension, two objects A and B are isomorphic if there exists at least one isomorphism described by \(A\rightarrow B\).

Duality

For any category \(C\), it is possible to define mathematically another category \(C^{op}\) where the source and target of every morphism are interchanged. This is called the “opposite category” or dual category of \(C\).

Duality is “invertible”: \((C^{op})^{op}\) is the same category as \(C\).

The dual category of a category \(C\) of concrete objects may be purely abstract, ie. without concrete representations for morphisms in the application domain of \(C\), for example if the morphisms in \(C\) are not invertible.

Nevertheless, duality serves an important purpose: say, you have demonstrated a property that holds within a category \(C\), which you can express within the language of category theory using a formula \(\sigma\) (some text string).

If you then replace all occurences of “source” by “target” and vice-versa in \(\sigma\), and all occurences of \(f\cdot g\) by \(g\cdot f\), you obtain a new formula \(\sigma^{op}\). By construction, this formula is true in \(C^{op}\). It is said to be the dual property of \(\sigma\). Conversely, if you know a property \(\sigma\) to be true in \(C^{op}\), then \(\sigma^{op}\) will be true in \(C\) as well.

Why this is useful: many important/useful results and properties of mathematics come in pairs that are expressed using “symmetric” formulas, which are dual in category theory. For example, monomorphisms and epimorphisms are morphisms for which different properties hold, but their definitions are dual. From this, if one can derive another unrelated property \(\phi\) that relies on the fact a morphism is monomorphic, then thanks to duality, automatically the dual property \(\phi^{op}\) is also proven over epimorphisms. Thanks to category theory, many pairs of results/theorems in algebra can be obtained with half the effort.

Functors

The observation that there are some common features between different categories intuitively brings the idea to transform one category into another, while preserving its structure.

For example, our category of “pipes” over Unix data streams can be transformed into a category of “networked services” over network data streams trivially, by attaching the program nc around each Unix processes.

Such a transformation of a category into another is called a functor. Generally, a functor F from a category C to a category D has the following properties:

• for each object x in C, F associates an object in D noted F(x);
• for each morphism \(f : x\rightarrow y\) in C, F associates a morphism in D that can be described by \(F(x)\rightarrow F(y)\), noted F(f);
• for every identity morphism \(h : x\rightarrow x\) in C, F(h) is an identity morphism for F(x) in D;
• for every pair of morphisms f and g in C, \(F(g\cdot f) = F(g)\cdot F(f)\) in D.

(This specific flavor of functors is called “covariant.” If F maps each arrow in C to an arrow with opposite direction in D, it is called “contravariant” instead. Covariant and contravariant functors are dual.)

Side property: Because of the properties of functors, the algebraic structure formed by 1) a set of categories 2) a set of functors over these categories 3) the identity functors that leave each category in set #1 unchanged, and 4) the natural generalization of composition, together, is itself a category.

Some follow-up concepts to read about

• Natural transformations: a constuction that transforms a functor into another functor, that respects the category structure of the functor transformations.
• Functor category: category where the objects are functors, and the morphisms are natural transformations between them.
• Categorical logic, especially used in computer science, focuses on semantic systems with a difference between syntax and semantics. To use categorical logic, one defines one category for syntax, one category for semantics, and phrases interpretation as a functor between them. An example application is proofs of behavior correctness, or “correct by construction” languages: by choosing an appropriate interpretation functor, proofs over the syntax category can be carried over transparently to the category of semantics.