Sunday, August 2, 2009

Classification of Morphisms

We introduced the morphism but never really talked about the taxonomy of morphisms. That is, all the different properties a morphism can have. This post seeks to remedy the situation. As usual, the citations of interest:

  • Jiri Ad├ímek, Horst Herrlich, George E. Strecker Abstract and Concrete Categories: The Joy of Cats freely available online (2004)
  • Saunders Mac Lane, Categories for the Working Mathematician Graduate Texts in Mathematics (vol 5) Springer-Verlag, Second Edition (1998);

There are various different ways we can consider tackling the problem of presenting the various types of morphisms. We could consider it a generalization of functions, which we are familiar with. We could also consider it as straightforward generalization of algebraic properties, if we look at composition of morphisms as a law of composition. We could probably ingeniously come up with a million other different ways to approach the problem. (For an interesting note on generalizing one-to-one and onto, see:

it's a purely category theoretic investigation however!)

Consider the notion of being injective. It's basically a fancy Frenchman's way of saying "one-to-one", or $f(x)=f(y)$ implies $x=y$. One of the properties of note, which we should know from analysis, is that it has a left inverse, i.e. if $f$ is injective then there is a $g$ such that $g\circ{}f$ is the identity. We have special names for these things, we say $f$ is a "section" of $g$, and that $g$ is a "retraction" of $f$. This seems really handy having a left inverse, so lets insist that it has to be a desirable property for a morphism. This permits us to consider the first definition:

Definition 1. A "monomorphism" in a category $C$ consists of
  • a morphism $f:x\to{y}$
such that
  • for all morphisms $g_{1},g_{2}:z\to{x}$, if $f\circ{}g_{1}=f\circ{}g_{2}$ then it implies $g_{1}=g_{2}$.

Remember a monomorphism goes mono-a-mono, one-to-one. You'll never forget it again.

We'd like to similarly generalize the notion of surjectivity. That is, let $f:X\to{Y}$, for each $y\in{Y}$ there is at least one $x\in{X}$ such that $f(x)=y$. This is equivalent to saying $f$ has a right inverse (surprise!).

We can weaken this slightly to say for every $g_{1},g_{2}:Y\to{X}$, if $g_{1}\circ{}f=g_{2}\circ{}f$ then $g_{1}=g_{2}$. This "looks like" we can "compose on the right" by some "right-inverse" of $f$, but there are a few neurotic counter-examples to thinking like this (e.g. if we were working in 2 we could come up with a neurotic example of a our weaker-than-right-invertible function that isn't right-invertible). Lets try to formally define our generalization of surjectivity:

Definition 2. An "epimorphism" in a category $C$ consists of
  • a morphism $f:x\to{y}$ in $C$
such that
  • if $g_{1}\circ{}f=g_{2}\circ{}f$ (where $g_{1},g_{2}\in\hom(y,x)$), then $g_{1}=g_{2}$.

Now what do we have when we have something that is both injective and surjective? We have a bijection! It basically tells us that the domain and the codomain are "the same".

We generalize this notion to an "isomorphism". Here "isomorphism" has ancient Greek origin, "iso" meaning "equal" and "morphism" meaning "morphism" ;) Or more formally:

Definition 3. An "isomorphism" in a category $C$ consists of
  • a morphism $f:x\to{y}$ in $C$
such that
  • there is a unique $g:y\to{x}$ in $C$ satisfying $f\circ{g}=1_{y}$ and $g\circ{f}=1_{x}$.

Note that if $F:C\to{D}$ is an isomorphism, we say that $C$ is "isomorphic" to $D$. We denote this by $C\cong{D}$.

In other words, it has a two sided inverse. It's a fairly strong way to say that two objects are "the same". (Category theory has, as we'll see later on, a hierarchical structure of "sameness".)

There are a few more morphisms of note that are useful later on, but using our mathematical object algorithm of formatting definitions would be overkill on them. Simply they are:

  • an "endomorphism" $f:x\to{x}$ has the domain and codomain be the same;
  • an "automorphism" $f:x\to{x}$ is an isomorphism that's also an endomorphism.

I think that's enough for today...

No comments:

Post a Comment