Sunday, August 2, 2009

Object Oriented Math: Some Category Theory

All the time in math we have definitions, we often can detect a recurring pattern in them. In fact, Dr Baez points this out in a number of places:

  • John Baez "Quantum Quandaries: A Category Theoretic Perspective", arXiv:quant-ph/0404040
  • John Baez and Derek Wise "Quantization and Categoriefication: Properties, Structures, 'n' Stuff!" Lecture Notes, 2004.
  • John Baez and Michael Shulman "Lectures on n-Categories and Cohomology", arXiv:math/0608420
  • John Baez and J Dolan "From Finite Sets to Feynman Diagrams", arXiv:math/0004133

(Addendum: I have been informed that James Dolan mentioned this earlier in sci.physics.research. For further reading see the following list:

Thank you.)

It is important to review the notion of "objects" for future use. My ambitions right now is to use this blog as a sort of "stream of consciousness notebook" for my mathematical physics studies. Definitions come up a lot, and category theory simplifies things many times. Lets define the notion of a mathematical object:

Definition 1 A "Mathematical Object" is defined by:
  1. specifying some underlying "stuff" (e.g. a set, several sets, etc.)
  2. equipping this "stuff" with some "structure" (e.g. functions, binary operators, collections of subsets, distinguished elements, etc.)
  3. such that certain "properties" hold (e.g. equations or inequalities, etc.).

Remark As pointed out by Baez and Wise, a property is a boolean type situation: it's either true or false, it can't be both. The equation $x+y=z$ either holds or it fails to hold, there's nothing in between.

Remark We can mix up the choice of structure with properties, and vice versa. It doesn't change much in the definition ("up to natural isomorphism").

We assert that every definition in mathematics defines one of the following: a mathematical object, "stuff", "structure", or a "property". If so, we can always present a definition in the same format as we've done for the mathematical object. We will, in this blog, always try to do so when possible.

A Grocery List of Examples

Now, in math, we need to make our notion of abstract definitions more intuitive and concrete by introducing examples. This basically involves browsing through the definitions in any old abstract math book, and reformulating them as definitions in an algorithmic way. We'll produce the results of our algorithmic rewriting of random definitions.

Definition 2 A "topology" $\mathcal{T}$ on some set $X$ consists of

  • a collection of subsets of $X$
such that
  • finite intersections of elements of $\mathcal{T}$ are also contained in $\mathcal{T}$;
  • arbitrary unions of elements of $\mathcal{T}$ are also contained in $\mathcal{T}$;
  • both $X\in\mathcal{T}$ and $\emptyset\in\mathcal{T}$.

Definition 3 A "Law of Composition" $f$ on $S$ is a mapping $f:S\times{S}\to{S}$. To put this in our algorithmic format, it consists of

  • a pair of sets $S\times{S}$ and $S$ (or $dom(f)$ and $cod(f)$ respectively)
equipped with
  • a set $f\subseteq(S\times{S})\times{S}$ (or more clearly $f\subseteq dom(f)\times cod(f)$)
such that
  • for each $(x\times{y})\in dom(f)$ there exists a corresponding $z\in cod(f)$ such that $(x\times{y},z)\in f$.
We usually denote the law of composition by $*,+,\times,\star$ or something similar. Because it is clumsy and hard to read $+(x,y)$ we will instead write $x+y$.

Definition 4 A "Monoid" $M$ consists of

  • a set $M$
equipped with
  • a law of composition $*:M\times{M}\to{M}$;
  • a unit element $e\in{M}$;
such that
  • the law of composition is associative, i.e. for every $x,y,z\in{M}$ we have $(x*y)*z=x*(y*z)$;
  • for every $x\in{M}$ we have $x*e=e*x=x$.

Now we can also define things in a clever way. That is, we can say that a group is a monoid with the extra property that every element is invertible. We can also rewrite the definition of the monoid adding the extra property that every element is invertible. In this sense, it's sort of analogous to a "macro expansion" in C programming. So consider the following two examples, which are two different definitions of the same thing in the way we just outlined:

Definition 5 A "Group" $G$ consists of

  • a set $G$
equipped with
  • a law of composition $*:G\times{G}\to{G}$;
  • a unit element $e\in{G}$;
  • an inversion operator $(-)^{-1}:G\to{G}$;
such that
  • the law of composition is associative, i.e. for every $x,y,z\in{G}$ we have $(x*y)*z=x*(y*z)$;
  • for every $x\in{G}$ we have $x*e=e*x=x$;
  • for every $x\in{G}$ there exists a corresponding unique element denoted $x^{-1}$ such that $x*x^{-1}=x^{-1}*x=e$.

Definition 6 A "Group" $G$ consists of

  • a monoid $G$
equipped with
  • an inversion operator $(-)^{-1}:G\to{G}$;
such that
  • for every $x\in{G}$ there exists a corresponding unique element denoted $x^{-1}$ such that $x*x^{-1}=x^{-1}*x=e$.

You can see the appeal in the latter approach, it takes up less space! It has the added bonus (or nightmarish drawback, depending on your point of view) that it sets up a sort of taxonomy of objects, in the same sense that inheritance in object oriented programming sets up a taxonomy of classes.

The Choice is Yours

You can check properties (they're true or false, as we previously remarked). You can choose structures from a set of possibilities. You can also choose stuff from a category of possibilities.

But we cannot do it willy-nilly, each step depends on the following ones. We can't demand properties hold for some structure we don't have, so once we choose our structure we are constrained to a subcategory of possibilities.

(If the reader is wondering "Gee whiz what's a category?" Don't worry, we'll get to it in the next exciting blog post.)

There is a dictionary available if the reader is a logician, namely:

Mathematical Logic Our Category Theoretic Scheme
Types ([2]) Stuff
Predicates ([2]) Structure
Axioms Properties

If one isn't a logician, but is still interested in this sort of categorical logic type thing, see:

Now revisiting a remark made earlier, there is some fudge factor in choosing structure and properties. For example, we have two definitions of a monoid:

a set $M$ equipped with
a law of composition $*:M\times{M}\to{M}$ and
an element $e\in{M}$
such that for all $x,y,z\in{M}$, $(x*y)*z=x*(y*z)$ and
a set $M$ equipped with
a law of composition $*:M\times{M}\to{M}$
such that (1) for all $x,y,z\in{M}$, $(x*y)*z=x*(y*z)$; and
(2) there exists an $e\in{M}$ such that $\forall y\in{M}$ satisfies $y*e=e*y=y$ (which automatically implies $e$ being unique).

These definitions give the same concept of a monoid, but they give different morphisms between monoids. This gives a different category of monoids.

As this is probably gibberish to the reader, lets explain some category theory. We have defined objects. We usually have some notions of "mapping" a given type of object to the same type of object. E.g. we have continuous functions map topological spaces to topological spaces, monoid homomorphisms map monoids to monoids, a linear transformation maps a vector space to a vector space, and so on. Can we generalize this notion of mapping for our objects?

Definition 7 A "morphism" between mathematical objects consists of
  • a map from stuff to corresponding stuff
such that
  • the structure is preserved.

In our consideration of two definitions of a monoid, we have two different morphisms - as previously stated. For the first definition, a morphism between monoids is:

  • a function $f:M\to{M^{\prime}}$
  • preserving the law of composition and identity: $f(x*y)=f(x)\star f(y)$ and $f(e)=e^{\prime}$.
for the second definition a morphism between monoids is:
  • a function $f:M\to{M^{\prime}}$
  • preserving multiplication $f(x*y)=f(x)\star f(y)$.
They're different but the same! Huh??

Observe the first type of morphism is contained in the second type, we just need to prove that the second type of morphism is actually the second. Observe for all $z\in{M}$ we have $e*z=z*e=z$ if and only if for all $y\in{M^{\prime}}$ we have $e* f^{-1}(y)=f^{-1}(y)=f^{-1}(y)*e$. This should not be too surprising since we've identified $f^{-1}(y)$ corresponds intuitively to $z$.

Now here's the subtle step: we apply $f$ to our second condition. That is, we have for all $y\in{M^{\prime}}$ we have $e* f^{-1}(y)=f^{-1}(y)=f^{-1}(y)*e$ if and only if for all $y\in{M^{\prime}}$ we have $f^{-1}(f(e)\star y)=f^{-1}(y)=f^{-1}(y\star f(e))$. All we did was apply $f^{-1}(f(-))$ to our current situation, which should effectively do nothing.

This means that the argument to the morphism $f^{-1}(-)$ must be the same. In other words we have for all $y\in{M^{\prime}}$ our desired situation $f(e)\star y = y = y\star f(e)$. This is true if and only if $f(e)=e^{\prime}$.

What does it all mean?! It means we have shown mathematically the second type of morphism is the same as the first.

Moral: whether we have something counted as structure or property doesn't affect the isomorphisms (invertible morphisms), so the groupoid (category with only isomorphisms) of mathematical objects is more robust than the category.

Similar reasoning can be made for stuff that can be reinterpreted as structure. We can always reinterpret properties as structure and structure as stuff, but not vice-versa!

Addendum (3 August 2009 at 4:44 PM)

I'd just like to remark that we have a clear cut hierarchy of properties, structure, and stuff, which can be put in terms of category theory:

{False,True} = the 0-category of all (-1)-categories.
Set = the 1-category of all (0)-categories.
Cat = the 2-category of all categories.

Where we have a (-1)-category be a truth value, a 0-category be a set, a 1-category be a category, and a 2-category as itself.

The important thing is that we have a pattern, which can be extended thanks to higher category theory. This is difficult to think about (and I haven't gotten to writing higher category theory notes!) so we'll end our addendum here.

Addendum 5 August 2009 at 7:41 PM

For some more on this, one might want to see

It discusses various aspects of "extra structure" in a category theoretic manner.

No comments:

Post a Comment