Sunday, August 2, 2009

A First Taste of Categories

Recall we had previously introduced a scaffolding for abstract mathematical thinking in an "object oriented" way. We muddled through with barely introducing the notion of categories and groupoids, we seek to remedy this situation by introducing the notion of categories.

We are inspired from several sources, which we'll cite now:

Definition 1 A "category" consists of:
  • a collection $Ob(C)$ of mathematical objects;
  • for any pair of objects $x,y$ we have a corresponding set $\hom(x,y)$ of morphisms from $x$ to $y$;
equipped with
  • for any object $x$ an identity morphism $1_{x}:x\to{x}$;
  • for any pair of morphisms $f:x\to{y}$ and $g:y\to{z}$ we have a morphism $g\circ{f}:x\to{z}$ called the composite of $f$ and $g$ (it's also denoted as $fg$ so it looks like multiplication);
such that
  • for any morphism $f:x\to{y}$ the left and right unit laws hold $1_{x}f=f=f1_{y}$
  • for any triple of morphisms $f:w\to{x}$, $g:x\to{y}$, $h:y\to{z}$, the associative law holds: $(fg)h=f(gh)$.

In other words, it's a cute collection of objects and morphisms. Note that when we read composition of morphisms $g\circ{f}$ it's read from right to left, i.e. "first do $f$, then do $g$".

In all honesty, I kind of thought of something along the lines of a category when I was studying graph theory. Consider a directed network - in other words, a diagram with dots and arrows connecting dots in a certain way. If we identify each dot with a mathematical object, and each arrow with a morphism, that's precisely a diagram (it's a functor embedding a network into a category to be precise, we'll revisit this idea again later).

We specifically have objects in a category be the same type of objects. That is to say, we cannot "mix and match" objects as we please. All the objects in the category are the same type, they're all groups, or monoids, or ... etc.

Grocery List of Examples

We can best exemplify the notion of categories in a grocery list of examples, as usual. We'll begin with very basic examples that are not too exciting, but useful later on.

0 is the "empty category" with no objects and no morphisms.

1 is the "singleton category" with one object $\{*\}$ and one identity morphism. This can be intuitively thought of as an object as a category.

2 is the category with two objects $\{a,b\}$ and one non-identity morphism $a\to{b}$. This can be intuitively thought of as a morphism as a category.

3 is the category with three objects $\{a,b,c\}$ and three non-identity morphism $a\to{b}$, $b\to{c}$, $c\to{a}$ arranged in a neat triangle.

$\downdownarrows$ is the category with two objects $\{a,b\}$ and two arrows $a\rightrightarrows b$.

We have more elaborate categories of interest which use more complicated mathematical objects. We can also make certain mathematical objects into a category, which we'll investigate presently.

Discrete categories. A category is called "discrete" when every morphism is an identity. This is basically just a set $X$ as a category (we just equip it with, for each $x\in X$, a corresponding morphism $1_{x}:x\to{x}$), and every discrete category is completely determined by its set of objects. So it really is just a set.

Monoid. We have a monoid considered as a category $C$ with a single object. In other words, it is completely determined by its morphisms. We can "equip" it with the composition of morphisms. By the property of left and right unit laws, and the condition of a single object, we see that there is an identity morphism corresponding to the notion of an identity element. By the associativity property, the composition of morphisms is an associative law of composition. This directly relates to the notion of a monoid as we specified in our previous entry on object oriented math.

Group. We have a group as a category when we have a monoid category with the extra property that each morphism is invertible.

Topology. We have a certain topology $\mathcal{T}$ over a set $X$ which consists of subsets of $X$ with certain nice properties (namely any intersection of finitely many elements of $\mathcal{T}$ are in $\mathcal{T}$, and any union of arbitrarily many elements of $\mathcal{T}$ are in $\mathcal{T}$). If we demand that the objects are the elements of $\mathcal{T}$ and the morphisms are inclusion mappings (or if we "reverse the direction of arrows", then the morphisms are restriction mappings).

Addendum (December 15, 2011 at 9:13 PM): I've written some notes on topology which really explains the peculiarity of the morphisms, see A Rapid Introduction to Topology.

Preorders. Consider a category $P$ in which, given objects $p,p^{\prime}$, there is at most one morphism $p\to{p^{\prime}}$. In any preorder, we can define a binary relation $\leq$ on the objects of $P$: we have $p\leq p^{\prime}$ if and only if there is a morphism $p\to{p^{\prime}}$. This binary relation is:

  • reflexive (there's always the identity morphism $p\to{p}$ in $P$);
  • transitive (because arrows can be composed).
So a preorder is a set of mathematical objects equipped with a reflexive and transitive binary relation.

Ordinal Numbers. We can think of each ordinal number $n$ as the linearly ordered set of all preceding ordinals $n=\{0,1,\ldots,n-1\}$ so in particular $0=\emptyset$ is the empty set, while $\omega=\{0,1,2,3,\ldots\}$ is the first infinite ordinal. Each $n$ is linearly ordered and hence is a preorder (a category).

$\Delta$ is the category with objects all finite ordinals and morphisms $f:m\to{n}$ all order-preserving functions ($i\leq{j}$ in $m$ implies $f(i)\leq f(j)$ in $n$). This category is sometimes called the "simplicial category".

Large Categories. When the collection of objects in a category is actually a set, we call the category "small". Otherwise it's "large". We have a list of our favorite large categories:

Set
objects: all small sets
morphisms: functions between them
remarks: in topology, $\mathbb{R}$ had all the nice properties; similarly, we'll find that Set has all the nice properties in category theory (in general).
Set*
objects: Pointed sets, i.e. all small sets with a base point
morphisms: base-point-preserving functions
Ens
objects: all sets
morphisms: functions within a variable set $V$
Cat
objects: small categories
morphisms: all functors between them (covered in next blog post)
Mon
objects: all small monoids
morphisms: all monoidal homomorphisms between them
Grp
objects: all small groups
morphisms: all group homomorphisms between them
Ab
objects: all small (additive) abelian groups
morphisms: all group homomorphisms between them
Rng
objects: all small rings (with units)
morphisms: ring homomorphisms (preserving unit) between them
CRng
objects: all small commutative rings (with units)
morphisms: ring homomorphisms between them
R-Mod
objects: all small left modules over the ring R
morphisms: corresponding linear maps
Mod-R
objects: small right R-modules
morphisms: corresponding linear maps
K-Mod
objects: small modules over the commutative ring K
morphisms: linear maps between them
Top
objects: small topological spaces
morphisms: continuous maps between them
Toph
objects: small topological spaces
morphisms: homotopy classes of maps
Top*
objects: small topological spaces with selected base point
morphisms: base-point preserving continuous maps between them
VectK
objects: vector spaces over a field K
morphisms: linear transformations between the vector spaces

No comments:

Post a Comment