What’s a Category anyway?
Not so long ago, I got very interested in Category theory. Understanding category theory better, makes you a better functional programmer, a better database designer, a better software engineer etc. I will try to convince you by showing you how it can be used in several fields of Mathematics & Computer Science.
In this series of blogs, I will define what a category is, what a Functor is, What are natural transformation and give you some examples of it. And gradually move towards more advanced topics like F-Algebra, Monoidal Category, Monads, etc.
But before we understand what a category is, we need to understand what a set is.
What is a Set?
To a category theorist, a set is nothing more than a sack/ bag/ collection of dots, and if two people are pointing to two dots in a set, one should be able to tell if they are pointing to the same dot or not.
Example-
In the above example we can see {A, B, C, D, E, F, G} are members of Set S. If someone points to A, and one point to B, we can tell if they are pointing to the same dot or not. This will be very familiar to Zermelo-Frenkel set theory that we study in high schools, but here’s where we make a distinction from it. To a category theorist the above set is same as {1, 2, 3, 4, 5, 6, 7} or {0, 1, 2, 3, 4, 5, 6} or {:), “Hello”, {1, 2, 3}, :(, A, B, C}, to him/her it’s just a collection of 7 dots, nothing more, nothing less.
Cartesian Product (x) between two Set A & B.
Cartesian Product between two Set A & B is defined as a set of all possible pairs between A & B. More precisely-
AxB = {(a, b), forall a in A and forall b in B}
Example-
A = {1, 2, 3}
B = {a, b}
AxB = {(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)}
BxA = {(a, 1), (b, 1), (a, 2), (b, 2), (a, 3), (b, 3)}Here you see distinction from Zermelo-Frenkel set theory, AxB is “same” as BxA (for all intended purposes). We will later make what “same” means more concrete.
One can visualize the above example as a matrix below-
Relation R between two Set A & B
A Relation R between two Set A & B is defined as any subset of AxB. For every element (a, b) in R, a is said to be in relationship with b and vice-versa.
Example-
A = {1, 2, 3}
B = {a, b}
AxB = {(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)}
R1 = {(1, a), (2, b), (3, a), (1, b)}
R2 = {(1, a), (2, a), (3, b), (1, b)}
...Function f from Set A to B
A Function f is a relation between two Set A & B such that forall a in A, there exists a unique element b in B. Another way of saying this is, forall a1, a2 in A iff a1 = a2, then f(a1) = f(a2).
The function f is sometimes denoted as-
f: A -> B
Example-
A = {1, 2, 3}
B = {a, b}
AxB = {(1, a), (1, b), (2, a), (2, b), (3, a), (3, b)}
f1 = {(1, a), (2, a), (3, b)}
f2 = {(1, b), (2, a), (3, a)}
...
Note that - {(1, a), (1, b), (2, b), (3, b)} is not a function because we have two different values for 1, and {(1, a), (2, b)} is not a function because we don't have any value in B for 3.What is a Category?
A Category C contains the following-
- A Set: Ob(C) whose members are called the objects in the Category C
- For every two members x, y ∈ Ob(C), there exists a Set: Ob(x, y) whose members are all the morphisms from objects x to y. Sometimes these are also called Hom-Set or Homo-morphisms, and sometimes also denoted as Hom𝒸(x, y)
Subjected to the following constraints-
- forall c in Ob(C), there exists a chosen (unique) morphism id𝒸 in C(c, c) called the identity morphism for object c.
- forall f in C(c1, c2) and g in C(c2, c3), there exists a unique morphism g.f in C(c1, c3), called the composition of morphism f and g and denoted as g . f (call it “g after f”)
Satisfying the following laws-
- Composition satisfies Left & Right Unital Laws: states that forall i, j in Ob(C), and forall morphism f in C(i, j), f . idᵢ = f = idⱼ . f
- Composition satisfies Associativity: states that forall i, j, k, l in Ob(C), and forall morphism f, g, h in Ob(i, j), Ob(j, k) and Ob(k, l) respectively, (h . g) . f = h. (g . f)
Some examples of Categories-
- Category of Sets: Objects are sets and morphisms are functions between sets. (If you are worried about Russell’s Paradox, that “is the Set of all Sets contained in itself?”, then you can refer to Grothendieck universe here.)
- Discrete Category: Objects are discrete dots, and the only morphisms are the identities on these dots. No morphisms exists between two distinct objects.
- Category Cat: Objects itself are Categories, sometimes referred to as “small” categories, and morphisms between them are Functors (I will describe what a functor is later in the series).
I haven’t yet shown you the things you can do with Category Theory yet, but you can see the definition of a Category is very straightforward and not that hard to wrap your heads around.
Category Theory is useful because of its simplicity so that it becomes very general and applicable to various fields of Mathematics & Computer Science. It’s the stem cell that can be modified to your respective field. It’s ubiquitous.
(Next- What does “same" mean? What is Isomorphism?)
References-
