Category Theory Illustrated - Categories

"prev

next"

From Sets to Categories

In this chapter, we will see some more set-theoretic constructs, but we will also introduce their category-theoretic counterparts in an effort to gently introduce the concept of a category itself.

When we are finished with that, we will try (and almost succeed) to define categories from scratch, without actually relying on set theory.

Products

In the previous chapter, we needed a way to construct a set whose elements are composite of the elements of some other sets e.g. when we discussed mathematical functions, we couldn’t define $+$ and $-$ because we could only formulate functions that take one argument. Similarly, when we introduced the primitive types in programming languages, like Char and Number, we mentioned that most of the types that we actually use are composite types. So how do we construct those?

So, consider a set $A$ (containing $a$’s) and a set $B$ (containing $B$’s)

We introduce a new set that combines those two sets into one, their product set.

The Cartesian product (or tuple) of sets $A$ and $B$ (denoted $A \times B$) is the set of ordered pairs that contain one element of the set $A$ and one element of the set $B$. Or formally speaking: $A \times B = { (a, b) }$ where $a ∈ A, b ∈ B$ ($∈$ means “is an element of”).

Task 1 : Why is this called a product? Hint: How many elements does it have?

Naturally, the product comes equipped with two functions, one for each property, which allow you to take a pair and extracts the value of the property,

For each set $C$, that is a product of $A$ and $B$, there are two functions $C \to A$ and $C \to B$, called the product’s projections that retrieve back its (the product’s) constituent values).

(in programming terms, we would dub these the “getters”)

Triple product

There are occasions where we want to combine not two, but three sets into a product (e.g. $A \times B \times C$). But we don’t need to define the concept of triple product separately: we can achieve it by combining the first and second one into a product and then combining their product with the third set, (so it will be $(A \times B) \times C$.

There is another way to make a triple product of three sets — combining the second and the third one and then combining the result with the first one (so $A \times (B \times C)$, but it doesn’t actually matter which one you use — if we view isomorphic sets as equal, the end results would be the same i.e.

The two ways of combining three sets into a triple product are isomorphic, $(A \times B) \times C \cong A \times (B \times C)$.

You might recognize this diagram from the section on functional composition. It means that the cartesian product operation is (like functional composition), associative.

Products as Objects

In the previous chapter, we established the correspondence of various concepts in programming languages and set theory — sets resemble types, and functions resemble methods/subroutines. This picture is made complete with products, that are like stripped-down classes (also called records or structs) — the sets that form the product correspond to the class’s properties (also called members) and the functions for accessing them are like what programmers call getter methods e.g. the famous example of object-oriented programming of a Person class with name and age fields is nothing more than a product of the set of strings, and the sets of numbers. And, as we showed, objects with more than two values can be expressed as compositions of nested products.

Using Products to define Numeric Operations

Products can also be used for expressing functions that take more than one argument (and this is indeed how multi-param functions are implemented in some languages, like the ones from the ML family). For example, “plus” is a function from the set of products of two numbers to the set of numbers, so, $+: \mathbb{Z} \times \mathbb{Z} → \mathbb{Z}$.

By the way, such functions (ones that take two objects of one type and return a third object of the same type) are called operations.

Defining products in terms of sets—Internal definition

A product is, as we said, a set of ordered pairs (formally speaking $A \times B ≠ B \times A$). So, to define a product we must define the concept of an ordered pair. So how can we do that?

Note that an ordered pair of elements is not just a set containing the two elements (that would be an unordered pair)

but it also contains information about which of those objects comes first and which one goes second in the pair—some mathematical operations (such as addition) don’t care about order, others (such as subtraction) do. And in programming, we have the ability to assign names to each property of an object, which accomplishes the same purpose—allows us to access a specific property of the object, not just any random property.

So, if an ordered pair isn’t a set, does that mean that we have to define it as a “primitive” type...