Sunday, November 22, 2009

Haskell Annotations

I am starting to play around with the Haskell programming language, it is based off of category theory (well very loosely). There are a few questions I have for any Haskell gurus and category theory mathematicians, namely with regards to the existence of a terminal object in Hask (the category of Haskell data types and programs).

The underlying aim, I must confess, is to write up some abstract algebra in Haskell. For the scheme of things, I must give a reference:

  • Saunders Mac Lane, Categories for the Working Mathematician, Springer-Verlag (2000).
The question I want to answer is this: to what extent can we use Haskell to model abstract algebra in a universal algebraic manner?

First let us review some concepts from category theory (and a little Haskell), then we will dive into my rambling questions.

Review Of Category Theory

To repent for my sins, I will review category theory first before launching into my twisted approach to Haskell.

Let us review two propositions, the first from chapter III "Universals and Limits, section 5 "Categories with Finite Products":

Proposition. If a category C has a terminal object T and a product diagram AA×BB for any objects A,BC, then C has all finite products.

For an introduction to category theory in Haskell syntax, the reader is referred to:

There are a few reservations I have about those series of blog posts, for example in Part I the author states "In Haskell, a terminal object may be a phantom type: data T since T is containing only the element undefined." There is a different way to present the terminal object, it's the unit object ().

In fact, now that I think of it, the unit object () as the terminal object is more in line with category theory than the phantom type. If we refer to part II, we have the product correspond to (A,B). If we use Mac Lane's insight:

In particular, C has a product of no objects, which is simply a terminal object T in C, as well as a product for any two objects.
Source: Saunders Mac Lane, Categories for the Working Mathematician
Chapter III Universals and Limits, Section 5 "Categories with Finite Products".

It would follow that the terminal object would correspond to the unit object. Well, to be strict, it would be (,) which is isomorphic to ().

We use Mac Lane's other insight about monoids and groups from Chapter III, section 6 "Groups in Categories", which boils down to this: a monoid in C is a triple (C, μ:C×CC, η:TC) where T is the terminal object of C, μ is multiplication, and η is the "identity element" of C.

Using the jargon of "stuff, structure, and properties", we have the stuff be C an object of a category, the structure be two morphisms μ and η, and the properties be diagrams.

A group in C is a monoid (C, μ, η) together with a morphism ζ:CC which makes a diagram commute (intuitively it sends each element of C to its (right) inverse).

Now for something slightly different: if we take the product of two objects A and B in Hask to be (A,B), then Hask is closed under finite products.

Conjecture. The category Hask is closed under finite products.

Haskell Question

Now, we have precisely enough knowledge to consider the questions relevant to abstract algebraic Haskell programming.

Naively, I would want to say that in Haskell typeclasses are structure-types. That is, we can write

TerminalObject :: ()

class Monoid C where
    mu :: C -> C -> C
    eta :: TerminalObject -> C

However, we cannot specify anything about the implementation of class Monoid. It is frustratingly close, we have the stuff C, we have the structure, but alas no properties!

Question 1: Is there any way around this or am I doomed? More precisely, is there any way to specify behavior without specifying implementation?

Now, consider the following additional code snippet:

class (Monoid C) => Group C where
    zeta :: C -> C

Question 2: Can I specify the behavior of zeta without specifying implementation, while assuming that mu and eta have been implemented already?

Haskell is so frustratingly close to being a good language, but it fails at some of these key things.

Saturday, September 26, 2009

School Starts!

Just a small update, for those that are interested in me rambling some more on category theory. Sadly school has started. So I need to focus on that.

So I will be posting irregularly henceforth, don't expect regular updates, etc. etc. etc.

But when time allows, I shall resume writing some notes.

Thursday, August 27, 2009

Morphisms of...Morphisms? A First Look at Slice Categories

So to basically summarize the pattern that we have been using: we introduced mathematical objects, then some generalized notion of mappings between objects which we called "morphisms". We then collected a bunch of objects and morphisms together such that a bunch of nice properties were true, and we called it a category.

A category "is-a" mathematical object, so we figured out what morphisms between categories were: functors, or mathematical procedures. We then said "Hey, a functor 'is-a' mathematical object, what's a morphism between them?" It turns out it's a natural transformation.

But a morphism is-a mathematical object. So what's a "morphism" between morphisms? Is this a "meaningful" question? (It is, but first some references!)

  • Saunders Mac Lane, Categories for the Working Mathematician, Chapter II.6 "Comma Categories"
  • The Catsters, Youtube Lecture Series "Slice and Comma Categories", 1, 2

(We hope that the reader can see the pattern here, in category theory we started out with remarkably simple, almost comical, premises. We have objects, and we have morphisms. We group all objects of the same sort together into a category. But we can apply this powerful notion of a morphism to any object, and everything in math "is-a" mathematical object. We can then ask, for each object, what's the morphism of this thing? What's a morphism of this morphism? And so on...)

Category of Objects Under and Over a Specific Object

Now, to discuss morphisms between objects, we need to demand that they are the "same sort" of objects. How to do this? Well, we can demand that the morphisms are from one fixed object or dually they go to one fixed object.

More precisely, let bC be a fixed object, we can construct "the category of objects under $b$" denoted by $(b\downarrow\mathbf{C})$. Basically the objects are ordered pairs $\langle f,c\rangle$ consisting of morphisms from $b$ and the target of the morphism, and the morphisms are morphisms of the target $h:\langle f,c\rangle\to\langle f',c'\rangle$...well, this doodle should summarize things nicely:

Composition of morphisms is given by composition of these triangles. More precisely, the composition of the morphisms in the base of the triangle. To be formal, lets give the full definition:

Definition 1. Let C be a category, bC be some element. Then a "category of objects under b" consists of
  1. (Objects) the collection of ordered pairs ⟨f,c⟩ where $f:b\to{c}$ is a morphism in C, and cC is an object;
  2. (Morphisms) the morphisms are h: ⟨f,c⟩ → ⟨f',c'⟩
such that the following diagram specifies this

Consider any one point set $*$, and any other set $X$. The function $*\to{X}$ is a single element of $X$. The category of objects under $*$ consist of objects $\langle *\to{X},X\rangle$ which is a selected element of $X$, and the set $X$. This is precisely Set*, the first part of the ordered pair (the morphism) is the "base point", the second part of the ordered pair is the set itself.

Now, as alluded to earlier, we can reverse the direction of the arrows by "duality". This ends up letting us consider morphisms with the same target.

That is, if we have a category C and an object aC, then we can construct a category with the objects being ⟨c,f⟩ where f : ca is a morphism.

The morphisms in this category would be "morphisms of morphisms". More precisely, it would make the following diagram (on the right) commute:

As we reversed the direction of the arrows, we should probably distinguish this sort of category of objects over a from the category of objects under b. We denote it by (Ca), compared to (bC) for objects under b.

Formally, this is summarized in the following definition:

Definition 2. Let C be a category, aC be some element. Then a "category of objects over a" denoted by (Ca) consists of
  1. (Objects) the collection of ordered pairs ⟨f,c⟩ where $f:c\to{a}$ is a morphism in C, and cC is an object;
  2. (Morphisms) the morphisms are h: ⟨f,c⟩ → ⟨f',c'⟩
such that the following summarizes the category:

Observe that this is just the same as the category of objects under b, except we have the arrows be reversed.

We should consider, to be kosher, what (Set*) is. The objects are ordered pairs, as before, consisting of ⟨X → *,*⟩ where the first component of the ordered pair is unique. There is always a map in Set from X to a singleton *, it's very boring though -- it's the constant map. It's a unique map too (this is kind of trivial, where else could it map stuff to? There's only one choice!).

The morphisms are really just morphisms between the sets.

Lets think for a second: for each object XSet there is a unique object ⟨X → *,*⟩ in (Set*); and for each morphism fhomSet(X,Y) there is a corresponding morphism in (Set*).

Since there is a unique one-to-one correspondence between objects and between morphisms in the two categories, we can represent this by a functor which is invertible. What does this mean? It's an isomorphism...i.e. (Set*) is isomorphic to Set!!!

Remark: Notation

Apparently Mac Lane uses two notations. One is what we've seen. The other is writing C/c for (C ↓ c), and (one assumes) c/C for (c ↓ C). Just be warned there are two different notations (apparently).

[More to follow...apologies to those who would've liked more, duty calls at my job]

Wednesday, August 19, 2009

Emacs Latex Macros

Oftentimes I write LaTeX notes in the emacs editor, and I often do it on an Asus EEE PC 900 HA. Unfortunately, the keyboard is rather small, and my hands rather large, which leads to some complications. To make things worse, the "\" key is as wide as a fingernail's width (which is a nightmare for LaTeX coding!).

Fortunately there is a solution with Emacs: macros! I've written up a few macros that simplifies my life. First I have an texHelp.el file in my ~/.emacs.d/ directory which consists of the following stuff:

;; macro to help me write stuff
(defun write (mystring)
  (insert-string mystring)

;; starts the document class
(defun docclass ()
  (write "\\documentclass{amsart}"))

;; use a package
(defun use-package (package)
  (write (concat

;; all the packages of interest
(defun my-packages ()
  (use-package "url")
  (use-package "manfnt")
  (use-package "amsthm")
  (use-package "amsmath")
  (use-package "amsthm")
  (use-package "amssymb")
  (use-package "amsfonts")
  (use-package "amscd")
  (use-package "graphicx")
  (write "\\DeclareGraphicsRule{*}{mps}{*}{}")
  (use-package "mathrsfs")

;; amsthm package configuration
(defun thm-style ()
  (write "\\theoremstyle{definition}")
  (write "\\newtheorem{defn}{Definition}")
  (write "\\newtheorem{thm}{Theorem}")
  (write "\\newtheorem{rmk}{Remark}")
  (write "\\newtheorem{lem}{Lemma}")
  (write "\\newtheorem{cor}{Corollary}")
  (write "\\newtheorem{ex}{Example}")
  (write "\\newtheorem{nonex}[ex]{NON-Example}")
  (write "\\newtheorem{prop}{Proposition}")
  (write "\\newtheorem{sch}{Scholium}")
  (write "\\newtheorem{axm}{Axiom}")
  (write "\\newtheorem*{prob}{Problem}")

;; number equations within the section
(defun eqn-numbering ()
  (write "\\numberwithin{equation}{section}")

;; my custom defined macros
(defun macros ()
  ;; code snipped out ;;

(defun doc-stuff ()
  (write "\\title[]{}")
  (write (concat "\\date{" (format-time-string "%B %d, %Y") "}"))
  (write (concat "\\email{" user-email-address "}"))
  (write (concat "\\author{" user-full-name "}"))
  (write "\\begin{document}")
  (write "\\maketitle")
  (write "\\end{document}"))

;; call this function when starting a new LaTeX document
(defun start-tex ()
  (previous-line 5))

I only need to create the directory (usually I have a ~/notebk directory, and subdirectories ordered in the way arXiv is ordered, so I usually create sub-sub-directories of ~/notebk/*), then create the file with C-x C-f path and start TeXnical stuff with M-x start-tex (remember that M-x means "Alt-x").

This does not solve the problem of the tex macros, I would still have to write "\begin{equation}...\end{equation". Woah is me!

Fortunately Emacs macros comes to the rescue yet again! I have another file, ~/.emacs.d/texMacros.el which consists of the helper functions:

;; for subequations
(defun subeqn()
  (insert "\\begin{subequations}\n")
  (insert "\\begin{align}\n")
  (insert "\n")
  (insert "\\end{align}\n")
  (insert "\\end{subequations}")
  (previous-line 2))

;; for equations
(defun eqn()
  (insert "\\begin{equation}%\\label{eq:}\n")
  (insert "\n")
  (insert "\\end{equation}")
  (previous-line 1))

;; all the amsthm environment
(defun thm()
  (insert "\\begin{thm}%\\label{thm:}\n")
  (insert "\n")
  (insert "\\end{thm}\n")
  (insert "\\begin{proof}\n\n")
  (insert "\\end{proof}")
  (previous-line 4))
(defun defn()
  (insert "\\begin{defn}%\\label{defn:}\n")
  (insert "\n")
  (insert "\\end{defn}")
  (previous-line 1))
(defun cor()
  (insert "\\begin{cor}%\\label{cor:}\n")
  (insert "\n")
  (insert "\\end{cor}")
  (previous-line 1))
(defun lem()
  (insert "\\begin{lem}%\\label{lem:}\n")
  (insert "\n")
  (insert "\\end{lem}")
  (previous-line 1))
(defun rmk()
  (insert "\\begin{rmk}\n")
  (insert "\n")
  (insert "\\end{rmk}")
  (previous-line 1))
(defun prop()
  (insert "\\begin{prop}%\\label{prop:}\n")
  (insert "\n")
  (insert "\\end{prop}")
  (previous-line 1))
(defun ex()
  (insert "\\begin{ex}\n")
  (insert "\n")
  (insert "\\end{ex}")
  (previous-line 1))
(defun nonex()
  (insert "\\begin{nonex}\n")
  (insert "\n")
  (insert "\\end{nonex}")
  (previous-line 1))

;; lists macros
(defun enumerate()
  (insert "\\begin{enumerate}\n")
  (insert "\\item \n")
  (insert "\\end{enumerate}")
  (previous-line 1))
(defun itemize()
  (insert "\\begin{itemize}\n")
  (insert "\\item \n")
  (insert "\\end{itemize}")
  (previous-line 1))
(defun item()
  (insert "\\item "))

;; proofs, from the amsthm package
(defun pf()
  (insert "\\begin{proof}\n")
  (insert "\n")
  (insert "\\end{proof}")
  (previous-line 1))
(defun axm()
  (insert "\\begin{axm}%\\label{axm:}\n")
  (insert "\n")
  (insert "\\end{axm}")
  (previous-line 1))
(defun prob()
  (insert "\\begin{prob}\n")
  (insert "\n")
  (insert "\\end{prob}")
  (previous-line 1))

;; reference to an equation
(defun eqref()
  (insert "\\eqref{}")
  (backward-char 1))
(defun pmatrix()
  (insert "\\begin{pmatrix}\n")
  (insert "\n")
  (insert "\\end{pmatrix}")
  (previous-line 1))
(defun diagram()
  (insert "\\begin{figure}[H]\n")
  (insert "\\includegraphics{}\n")
  (insert "\\end{figure}")
  (previous-line 2)
  (forward-char 23))
(defun fig()
(defun figure()
(defun src()
  (insert "\\begin{Verbatim}[fontsize=\\footnotesize,frame=lines,numbers=left,numbersep=3pt,firstnumber=]\n")
  (insert "\n")
  (insert "\\end{Verbatim}")
  (previous-line 2)
  (forward-char 77))
(defun quotation()
  (insert "\\begin{quote}\n")
  (insert "\n")
  (insert "\\end{quote}")
  (previous-line 1))

And shazam! I'm off to the races, avoiding usage of the "\" key with only a handful of exceptions.

If one wants to have a bunch of keybindings for these functions, one can use the following in their ~/.emacs file:

;; load texMacros when doing LaTeX stuff
(load "~/.emacs.d/texHelp.el")
(load-file "~/.emacs.d/texMacros.el")  ; load these LaTeX preferences
(defun my-LaTeX-startup ()
  (local-unset-key "\C-c\C-e")
  (local-set-key "\C-c\C-e" 'eqn)
  (local-unset-key "\C-c\C-s")
  (local-set-key "\C-c\C-s" 'subeqn)
  (local-unset-key "\C-c\C-t")
  (local-set-key "\C-c\C-t" 'thm)
  (local-unset-key "\C-c\C-d")
  (local-set-key "\C-c\C-d" 'defn)
  (local-unset-key "\C-c\C-r")
  (local-set-key "\C-c\C-r" 'rmk)
  (local-unset-key "\C-c\C-l")
  (local-set-key "\C-c\C-l" 'lem)
  (local-unset-key "\C-c\C-k")
  (local-set-key "\C-c\C-k" 'cor)
  (local-unset-key "\C-c\C-p")
  (local-set-key "\C-c\C-p" 'prop)
  (local-unset-key "\C-c\C-x")
  (local-set-key "\C-c\C-x" 'ex)
  (local-unset-key "\C-c\C-n")
  (local-set-key "\C-c\C-n" 'nonex))
(add-hook 'LaTeX-mode-hook 'my-LaTeX-startup)
(add-hook 'latex-mode-hook 'my-LaTeX-startup)
(add-hook 'TeX-mode-hook 'my-LaTeX-startup)

Of course, one is more than welcome to change the keybindings to their own preference!

Addendum: Making the Definition Macro Better!

Recall for our object oriented approach, we have a mathematical object consist of "stuff" equipped with some "structure" such that a bunch of "properties" hold. We can modify the definition environment to simplify this format. In ~/.emacs.d/texMacros.el, change the (defun defn() ...) lines to be:

(defun defn()
  (insert "\\begin{defn}%\\label{defn:}\n")
  (insert "A \\textbf{} consists of\n")
  (insert "\\begin{enumerate}\n\\item\n\\end{enumerate}")
  (insert "\n equipped with\n")
  (insert "\\begin{enumerate}\n\\item\n\\end{enumerate}")
  (insert "\n such that\n")  
  (insert "\\begin{enumerate}\n\\item\n\\end{enumerate}")
  (insert "\n\\end{defn}")
  (previous-line 10))

You're set to start defining objects left and right!

Thursday, August 13, 2009

LaTeX Macros...

So here are some LaTeX3 macros I've found or written that are pretty useful. This post covers the following packages I've written/patched together:

  • Bourbaki inspired dangerous bend environments
  • Macros for underbrackets and overbrackets, similar to underbrace and overbrace
  • Misner, Thorne, and Wheeler type equations
  • Exercises and Answers in the style of the TeXbook
  • Style like the TeXbook in LaTeX macros

Addendum (9:30 AM (PST) 15 December 2011): I have modified the danger.sty code, and it is now more robust. For more macros, see my Notebk's wiki page for others and documentation.

Dangerous Bends!

Bourbaki used Dangerous Bend symbols to indicate some tricky reasoning. Knuth used this too in his TeX book, among other places.

I too use it in my notes...but I use it as an environment. It's safer this way ;) At any rate the code is contained a file danger.sty, reproduced below:

\ProvidesPackage{danger}[2009/08/06 Danger and Double Danger Environments]

% or if manfnt is unavailable, uncomment the next two lines
%\def\dbend{{\manual\char127}} % dangerous bend sign

% This macro header is what controls the ``dangerous bend''
% paragraph

% Danger, Will Robinson!
  \hbox to0pt{\hskip-\hangindent\dbend\hfill}\small\ignorespaces}%

% Danger! Danger!
  \hbox to0pt{\hskip-\hangindent\dbend\kern2pt\dbend\hfill}\small\ignorespaces}%

The above code is just literally cut/paste from Knuth's TeXbook macros. On the other hand, in LaTeX a better implementation might be:

\def\dbend{{\manual\char127}} % dangerous bend sign

% Danger, Will Robinson!
  \hbox to0pt{\hskip-\hangindent\dbend\hfill}\small\ignorespaces}%

% Danger! Danger!
  \hbox to0pt{\hskip-\hangindent\dbend\kern2pt\dbend\hfill}\small\ignorespaces}%

Underbrackets and Overbrackets

In math mode, you can use underbrace and overbrace, but there are no corresponding brackets macros. This is sad, because I'm more fond of brackets than I am of braces.

So I fiddled around and pieced together the brackets.sty file:

\ProvidesPackage{brackets}[2009/08/06 Overbracket and Underbracket racket]

\def\overbracket{\@ifnextchar [ {\@overbracket} {\@overbracket
\def\@overbracket[#1]{\@ifnextchar [ {\@over@bracket[#1]}
\def\@over@bracket[#1][#2]#3{%\message {Overbracket: #1,#2,#3}
\mathop {\vbox {\m@th \ialign {##\crcr \noalign {\kern 3\p@
\nointerlineskip }\downbracketfill {#1}{#2}
                              \crcr \noalign {\kern 3\p@ }
                              \crcr  $!\hfil$ \displaystyle {#3}\hfil $%
                              \crcr} }}\limits}
\def\downbracketfill#1#2{$!\m@th$ \setbox \z@ \hbox {$!\braceld$$}
                  \leaders \vrule \@height #1 \@depth \z@ \hfill
                  \leaders \vrule \@height #1 \@depth \z@ \hfill
\def\downbracketend#1#2{\vrule depth #2 width #1\relax}

  \@ifnextchar[{\@underbracket}{\@underbracket [\@bracketheight]}%
\def\@under@bracket[#1][#2]#3{%\message {Underbracket: #1,#2,#3}
 \mathop{\vtop{\m@th \ialign {##\crcr $!\hfil$ \displaystyle {#3}\hfil $!$%
 \crcr \noalign {\kern 3\p@ \nointerlineskip }\upbracketfill {#1}{#2}
       \crcr \noalign {\kern 3\p@ }}}}\limits}
\def\upbracketfill#1#2{$!\m@th$ \setbox \z@ \hbox {$!$\braceld$!$}
                    \leaders \vrule \@height #1 \@depth \z@ \hfill
                    \leaders \vrule \@height #1 \@depth \z@ \hfill \bracketend
\def\bracketend#1#2{\vrule height #2 width #1\relax}

% Makes limits on sums and integrals pretty
\def\clap#1{\hbox to 0pt{\hss#1\hss}}

The other part of the code, which % Makes limits pretty, allows stuff to be written on top of the sum's limits. It's taken from Voss's math mode notes.

Equations with Misner, Thorne and Wheeler type Arrows

This is going to be a bit harder to explain (it's one of those "You have to have seen it to understand what I'm talking about" type situations). So look at page 139, equation 5.15a for example. Note the arrows pointing to the terms in the equation? Yeah, I'd like to do that in LaTeX, but how?

Unfortunately you have to use the picture environment (or, at least, that's the only way I know how to do it!). Consider the following example document:



{\catcode`p=12 \catcode`t=12 \gdef\cm#1pt{#1cm}}
{\catcode`p=12 \catcode`t=12 \gdef\dimensionless#1pt{#1}}


\begin{picture}(\expandafter\dimensionless\the\textwidthcm, 2.5)(0,0)
  \put(5,1.5){$\displaystyle Z[0]=\underbracket[0.25pt]{\int ~\mathcal{D}\phi\;\;\; }
Woah what is eq \eqref{eq:four} again? Don't forget the text width is \the\textwidth ~or 
equivalently \expandafter\cm\the\textwidthcm ~or 

This produces the following text:

The only disadvantage is that for each equation you want to do, you have to do this by hand.

Exercises and Answers Macros From The TeXbook

\ProvidesPackage{exercises}[2009/08/06 LaTeX version of exercise macros from the TeXbook]
% Options: number within either the chapter or the part
%          default is to number the exercises/answers via sections



\newcommand{\upd@teCtr}{\ifnum \value{sectionCtr}=\value{section}%
\newcommand{\upd@teCtr}{\ifnum \value{sectionCtr}=\value{chapter}
\newcommand{\upd@teCtr}{\ifnum \value{sectionCtr}=\value{part}%
\newcommand{\upd@teCtr}{\ifnum \value{sectionCtr}=\value{section}%

% Exercise Environment
% well, to make it an environment, one would instead do the following:
% \newenviornment{exercise}{\medbreak\upd@teCtr%
%  \noindent\llap{\mantriangleright\kern.15em}% triangle in margin
%  \small{\textbf{EXERCISE \thesection.\arabic{exno}}}\\%
%  \noindent}{}
% that is, stuff the command into an environment
  \noindent\llap{\mantriangleright\kern.15em}% triangle in margin
  \small{\textbf{EXERCISE \thesection.\arabic{exno}}}\\%
  \noindent\llap{\mantriangleright\kern.15em}% triangle in margin
  \small{\textbf{EXERCISE \arabic{sectionCtr}.\arabic{exno}}}\\%
\newcommand{\dangerexercise}{\dbend \dexercise}
\newcommand{\ddangerexercise}{\dbend\dbend \dexercise}

% formatting macro
    \hbox to\parindent{\bf\hss(Answer to #1.#2)\enspace}\ignorespaces}
    \hbox to \parindent{\bf\hss #1.#2.\enspace}\ignorespaces}

% Answers Command
\if@dump % if we are dumping the answers directly where they're placed
  \def\ans{} % ans is defined as nothing
  \newcommand{\answer}[1]{\par\medbreak % \answer simply
      \ansno\arabic{sectionCtr}.\arabic{exno}: \\% prints directly
      #1} % out when it's called 
  \newcommand{\dumpanswers}{} % \dumpanswers is empty
\else % else we are dumping it into a file
  \immediate\openout\ans=answers % file for answers to exercises
    \immediate\write\ans{ \detokenize{#1}}}

One could easily turn the exercises command into an environment, but it'd be trickier to turn the \answer command into an environment. The \answer spits out all the answers to a file answers.tex which can be included at the end of the main document.

To write the answers, one should call the \dumpanswers command in its own section/chapter. It does everything necessary to include the answers in the document.

The Poor Man's TeXbook Style

\ProvidesPackage{TeXbook}[2009/08/06 Poor man's \TeX{}book style for \LaTeX]

% the following is the TeXbook's exact specifications
% textwidth=30pc,inner=6pc,marginparwidth=8pc,marginparsep=1cm]{geometry}
% the following is OUR preferred specifications!
\abovedisplayskip=6pt plus 3pt minus 1pt
\belowdisplayskip=6pt plus 3pt minus 1pt
\abovedisplayshortskip=0pt plus 3pt
\belowdisplayshortskip=4pt plus 3pt




This has a decent sized margin, the header is also slightly extended. It's really just a poor man's TeXbook style file, using the exact specifications from the manmac.tex macros file that is freely available from CTAN.

Note that the style file is not exactly as the TeXbook specifies, I thought the \headsep was too large. The textwidth and placement from the inner margin are the same, the marginparwidth is slightly larger so one can write annotations in the margins (I love using \marginpar).

I'm writing up some notes on slice and comma categories, as well as adjoint functors, so sit tight while I polish them up in the next couple of days...

Tuesday, August 11, 2009

Coproducts (but not Products!)

We introduced the notion of products as a sort of categorification of the "Cartesian Product". The product of $c_1$ and $c_2$ is an object $p$ equipped with projection morphisms $\pi_1:p\to{c_1}$ and $\pi_2:p\to{c_2}$ such that some diagram commutes.

We also introduced the duality principle, which allows us to "reverse the arrows" in diagrams to get some "dual" notion. So now we would like to use the duality principle to find the dual notion of a product, or the "co-product". First some references:

  • The Catsters, "Products and Coproducts" Lectures: 2, 3, 4
  • Saunders Mac Lane, Categories for the Working Mathematician Graduate Texts in Mathematics (vol 5) Springer-Verlag, Second Edition (1998);
  • Jiri Adámek, Horst Herrlich, George E. Strecker Abstract and Concrete Categories: The Joy of Cats freely available online (2004)
  • Serge Lang Algebra Springer-Verlag, Third Edition (2000)

We set up our diagram by reversing the arrows for the product. That is, in some category C, we have objects $c_1,c_2\in\mathbf{C}$, the product is an object $p$ such that given any object $d\in\mathbf{C}$ with morphisms $f:d\to{c_1}$, $g:d\to{c_2}$, then there exists a morphism $h:d\to{p}$ such that the following diagram commutes:

      &                &      d        &                &      \\
      &\ldTo^{f}       & \dDashto_{!h} & \rdTo^{g}      &      \\
c_{1} & \lTo_{\pi_{1}} & p             & \rTo_{\pi_{2}} & c_{2}

Now we "turn the arrows around". We denote the coproduct of $c_1$ with $c_2$ as an object $c_1\sqcup\displaystyle{c_2}$. We want this object to be equipped with two morphisms, but they should be dual to the projection morphisms. Huh? They should have the codomain and the domain switched, so $i:c_1\to c_1\sqcup\displaystyle{c_2}$ and $j:c_2\to c_1\sqcup\displaystyle{c_2}$. We call these morphisms "injections" or "insertion maps" of the coproduct (although they are not required to be injective functions).

Now putting the diagram on its head, we end up with the following property that coproducts must satisfy: for each $d$ with morphisms $f:c_1\to{d}$ and $g:c_2\to{d}$, there exists a unique morphism $h:c_1\sqcup\displaystyle{c_2\to{d}}$ such that the following diagram commutes:

So to summarize what we've figured, lets write the formal definition of the coproduct:

Definition 1. Let C be some category and $c_{1},c_{2}\in\mathbf{C}$, the "Coproduct of $c_1$ with $c_2$" consists of
  • an object $c_{1}\sqcup\displaystyle{c_{2}\in\mathbf{C}}$
equipped with
  • a pair of morphisms $i:c_{1}\to c_{1}\sqcup\displaystyle{c_{2}}$ and $j:c_{2}\to c_{1} \sqcup\displaystyle{c_{2}}$ called "insertions"
such that
  • for any $d\in\mathbf{C}$ and pair of morphisms $f:c_1\to{d}$ and $g:c_2\to{d}$, there exists a unique morphism $\textstyle h:c_1\sqcup\displaystyle{c_2\to{d}}$ such that the following diagram commutes:

So the motivation for this construction was based off of the "dual" to the product, but we don't really know intuitively what this is (I mean, we want an intuition other than "it's related 'somehow' to the product"). What to do? We do what category theorists love to do in this situation: doodle!

We work in Set and set up the following problem:

We have only specified the sets $c_1,c_2,d$ and the morphisms $f$ and $g$. We want to figure out what $c_1\sqcup\displaystyle{c_{2}}$ is. We can use "universality", the fact that there is a unique morphism $h:c_1\sqcup\displaystyle{c_{2}\to{d}}$ which satisfies a commutativity property.

What can we deduce about $h$? Well, we see that since the image $g(c_2)$ is all of $d$, we need $h$ to map the image of $j(c_2)$ in $c_{1}\sqcup\displaystyle{c_{2}}$ to all of $d$. So in other words, we need at least two distinct elements in our coproduct. We can doodle at least part of what we know it could be:

On the other hand, since we also have to take into account $c_1$, we need to consider how this would affect the coproduct object. We see that all elements of $c_1$ are mapped to a single element of $d$, which implies our solution would be the following diagram:

Now what's going on? We see that since we chose a rather bad map $c_{1}\to{d}$, a constant map (it maps everything to a single element of $d$), we have a rather hard time getting an intuition about the situation, but we can still deduce something. It appears that $h$ is injective, which means that the coproduct would behave sort of like a disjoint union.

But, to play the Devil's advocate, how do we know this diagram is even the right one to describe our object $c_1\sqcup{c_2}$? Couldn't the following diagram also work:

Well, yes, this diagram also works, but it uniquely factors through our previous diagram. Or in other words, we can doodle an "intermediate step" using green:

Now, we can do this for any other guesses at what $c_{1}\sqcup{c_{2}}$ might be, which tells us that there is a unique object which all our guesses "factor" through. This unique object is precisely our $c_{1}\sqcup{c_{2}}$.

Drawing Internal Diagrams

We introduced the internal diagram, but if one wants to draw such internal diagrams in LaTeX...well, LaTeX isn't known for its powerful drawing capabilities, so it seems like we are out of luck. Right? Wrong.

We can use other software (e.g. Metapost or Asymptote) to draw them. Metapost is old-school, based off of Knuth's Metafont...except Metapost produces .eps files. Asymptote is more "new-school", modeling itself off of C++. If one is new to all of this, asymptote may be easier to learn (it wasn't for me, I prefer metapost for 2d drawing). For example, in asymptote the following code generates the diagram:

pair midpoint(pair XXX, pair YYY)
 real a,b;
 a = (XXX.x + YYY.x)/2;
 b = (XXX.y + YYY.y)/2;
 return (a,b);
//real u = 14.1732284; // the number of "size points" in 0.5 centimeters 
dotfactor=8; // changes the size of a dot
real u = 14; // (u=72)==(u=1 inch);
pair z[]; // all the points we are working with
pair c1; // select points we are making red
pair c2;

// this draws one "factor" of $!$P$!$
c1 = (0*u,0*u);

// this draws the other "factor" of $!$P$!$
c2 = (13*u,0*u);

// this draws $!$P$!$

// this draws $!$D$!$
// draws $!$\<f, g\>$!$
draw((7*u,5*u)--(7*u,0*u),linetype("8 8"),EndArrow);
label("$!$\langle f,g\rangle$!$",(7*u,2.5*u),E);

// draw the morphisms f and g
z[0] =(6.5*u,5.25*u);
z[1] = c1;
//z[1] = (0*u,2*u);
draw (z[0]--z[1], EndArrow);
label("$!$f$!$", midpoint(z[0],z[1]),NW);
z[2] = (7.5*u,5.25*u);
z[3] = c2;
//z[3] = (13.5*u,1*u);
draw (z[2]--z[3], EndArrow);
label("$!$g$!$", midpoint(z[2],z[3]),NE);

// draw projections
z[4] =(6.5*u,-0.5*u);
z[5] = c1;
//z[5] =(1*u,0);
draw (z[4]--z[5], EndArrow);
label("$!$\pi_{1}$!$", midpoint(z[4],z[5]),S);
z[6] =(7.5*u,-0.5*u);
z[7] = c2;
//z[7] =(12*u,0);
draw (z[6]--z[7], EndArrow);
label("$!$\pi_{2}$!$", midpoint(z[6],z[7]),S);

// Redraw the red circles

We can translate this into a png that we can use on our blog by running on the command line (in the Ubuntu distro of Linux at least) convert -density 150 img.eps -flatten img.png which converts the file img.eps to png, the "-flatten" option makes the background white as opposed to translucent, the "-density 150" makes the png image have certain geometry (otherwise our picture ends up too small). Once we've done this, we can use our png image on our blog...huzzah!

So why did I use Asymptote for this image? Because Metapost is kind of "fudgy" with its labels, it uses TeX to translate the labels when we are "compiling" the TeX code. We can force Metapost to use Postscript fonts by making the first line of our Metapost file: prologues:=1;. It usually isn't too good in comparison to Asymptote's output, which is why I use it for blogging purposes.

Setting up a Table of Contents for Blogger...

In case anyone is really interested in setting up their own "table of contents" widget, let me set up the instructions on how exactly I did it.

First I introduced the "spoiler widget" code. What this "spoiler widget" means is when you click on the "Mathematics (Click Me!)" or "Programming (Click Me!)" entries of the table of contents, it expands into a more elaborate table of contents indexing the blog entries. The following is such a widget:

Example Spoiler

We need to modify the html code, so go to the "Layout" tab, and click on the "edit HTML" tab. See the following screen shot for details:

Find the line of code ]]></b:skin>, which is where the css code ends. We need to add the following lines right before it and after it:

background: #E8E8E8;
border: 1px dotted #000;
border-left: 4px solid #8394B2;
color: #000;
margin: 8px auto 0 auto;
padding: 3px;

background: #E8E8E8;
border: 1px dotted #000;
border-left: 4px solid #8394B2;
border-top: 0;
color: #000;
padding: 4px;
margin: 0 auto 8px auto;

<script language='JavaScript' type='text/javascript'>
function openClose(id) {
var obj = "";

if(document.getElementById) obj = document.getElementById(id).style;
else if(document.all) obj = document.all[id];
else if(document.layers) obj = document.layers[id];
else return 1;

if(obj.display == "") obj.display = "none";
else if(obj.display != "none") obj.display = "none";
else obj.display = "block";

This allows you to set up the spoilers. Once you've added this, all you need to do is use the following html code to generate spoilers:

<div class="spoilertop" onclick="openClose('EXWIDGETID')">
  <strong>Example Spoiler (Title)</strong>
  <div id="EXWIDGETID" style="display: none;" class="spoilermain">
    This is an example of the text contained in the widget. 
    Blah blah blah. Huzzah, it works!

The EXWIDGETID is the ID of the spoiler, it must be unique (i.e. you can't use the same ID twice). The <strong>Example Spoiler (Title)</strong> is the title of the spoiler, and the text This is an example of the text contained in the widget. Blah blah blah. Huzzah, it works! is the text that will be "spoiled".

To set up a table of contents, one can do the following:

Example Table of Contents

Which is precisely just the following code:

<div class="spoilertop" onclick="openClose('EXINDX')">
  <span style="font-weight: bold;">Example Table of Contents</span>
<div id="EXINDX" style="display: none;" class="spoilermain">
      <div class="spoilertop" onclick="openClose('EXINDX2')">
        <span style="font-weight: bold;">
          Example Of Nested table of Contents
      <div id="EXINDX2" style="display: none;" class="spoilermain">
          <li>Subentry One</li>
          <li>Subentry Two</li>
    <li>Entry One</li>
    <li>Entry Two</li>
    <li>Entry Three</li>
    <li>Entry Four</li>
One can make the entries links followed by a brief explanation if one so desires, or another spoiler "sub-index", like I do with my table of contents. You can see the example code has its "subindex" example code.

Friday, August 7, 2009

More Object Orientedness

Recall we previously introduced the notion of "object oriented mathematics" by defining a "Mathematical Object", then insisted that every definition in mathematics defines a mathematical object (in the sense that everything defined in math is-a mathematical object). We then proceeded to introduce a lot of category theoretic concepts, like morphisms as generalized structure-preserving maps from one object to another, categories as a sort of directed network whose nodes are mathematical objects and whose edges are morphisms, functors as a morphism of categories, natural transformations as morphisms of functors, and so forth. Now wouldn't it be lovely if this all tied together "somehow"?

The recommended reading this time is a little light, since I don't really know of any good references on this material (perhaps some needs to be written!). Therefore I am going to include material on "stuff, structure, and properties":

The Basic Algorithm

What we are going to do is pretty algorithmic. We are going to show all our work deriving this algorithm, so lets start by guessing at what it could be. The "obvious" approach (at least to me) is to use the following dictionary:

Category Theory Our "Object Oriented" Scheme
Objects of a Category Stuff
Morphisms Structure
Commutative Diagrams Properties

This "seems" like a good idea, so lets try it out on groups and see what we need to "forget" a group "into" a monoid.

Example: A Group

We are going to test our algorithm now by setting up a category to describe the notion of a group, and we are going to see how it behaves when we "forget" the inversion operator.

So we basically have our stuff be represented by the set of objects $\{G^{k}|k\in\mathbb{N}\}$ where $G^{0}$ = 1, and $G^{k}=G\times(\cdots)\times{G}$ ($k$ times). For our purposes with a group, we only need $k=0,1,2,3$, anything else is overkill.

Our structure consists of: the multiplication operator $m:G\times{G}\to{G}$; the identity element $e:\mathbf{1}\to{G}$; and the inversion operator $i:G\to{G}$.

The properties we want our group to satisfy are associativity of multiplication, which is equivalent to demanding the following diagram commutes:

G\times{G}\times{G}    && \rTo^{m\times{\pi_{2}} && G\times{G} \\
\dTo^{\pi_{0}\times m} &&                         && \dTo_{m}   \\
G\times{G}             && \rTo_{m}               && G
\end{diagram} and various properties of the identity and the inverse summarized by the demand the following diagrams commute (respectively):

G\times\mathbf{1} & \rTo^{1_{G}\times{e}} & G\times{G} & \lTo^{e\times1_{G}} & \mathbf{1}\times{G} && G         &\rTo^{(1_{G},i)}&G\times{G}&\lTo^{(i,1_{G})}& G\\
                  & \rdTo_{\pi_{0}}       & \dTo_{m}   & \ldTo_{\pi_{1}}     &                     && \dTo^{!_G}&                &\dTo_{m}  &                & \dTo_{!_{G}}\\
                  &                       &    G       &                     &                     && \mathbf{1}&\rTo_{e}        &G         &\lTo_{e}        & \mathbf{1}

We should probably see how to "demote" our category theoretic description of a group, from a category to a mere object in Grp. To do so first consider what a group homomorphism amounts to. It maps the identity to the identity, and preserves multiplication. This sounds a lot like a functor.

If we just insist that $F$ (our group homomorphism) maps $G$ to $F(G)=H$ some other group, and $e$ to $F(e):\mathbf{1}\to{H}$, $m$ to $F(m):H\times{H}\to{H}$, and maps inverses to inverses so $i$ to $F(i):H\to{H}$, then all the properties of the group are preserved since functors preserve composition of morphisms (and thus they preserve commutative diagrams!).

So in a sense, what we are doing is "promoting" the objects of Grp to categories, then - for consistency - the morphisms are "promoted" to functors. To summarize the relation between the "instance" of a group we've constructed and the category of groups, consider the following table:

Grp Instance
Object Category
Morphisms Functors
Functors Functors Again?

What would the "forgetful functor" $U:$ GrpSet look like in this scheme? Well, it would be a sort of "2-functor" that would be, one assumes, "2-faithful".

Forgetting A Group "Into" A Monoid

We want to "forget" the group into a monoid, what do we mean by this? Well a group "is-a" monoid equipped with an inversion operator such that a diagram commutes. We want to forget the inversion structure and consequently the properties it satisfies.

The "stupid simple" answer is fairly obvious: the "2-functor" from our "2-Grp" to "2-Mon" would be an embedding. Why? Because the inversion operator is just a homomorphism which maps $x$ to $x^{-1}$, and $e$ to $e^{-1}=e$. This requires "promoting" the inversion morphism to be an inversion functor, which is an illegal maneuver. So this "stupid simple" way to "forget" a group into a monoid can't work.

Perhaps we should just map the inversion operator to the identity morphism on $G$, that is $1_{G}$? This means that it is no longer faithful it's instead full...but it has the added bonus that it works.

It seems that this approach to describing "stuff, structure, and properties" was not in mind when Baez wrote:

There are various amounts of forgetfulness that [a functor] p can have:

  • p forgets nothing if it is an equivalence of categories, i.e. faithful, full, and essentially surjective. For example the identity functor AbAb forgets nothing.
  • p forgets at most properties if it is faithful and full. E.g. AbGrp, which forgets the property of being abelian, but a homomorphism of abelian groups is just a homomorphism between groups that happen to be abelian.
  • p forgets at most structure if it is faithful. E.g. the forgetful functor from groups to sets, AbSet, forgets the structure of being an abelian group, but it’s still faithful.
  • p forgets at most stuff if it is arbitrary. E.g. Set2Set, where we just throw out the second set, is not even faithful.

Source: Lectures on n-Categories and Cohomology

(Author's Note: I have modified the quote so it uses the conventions of this blog (e.g. Sets became Set, etc.) and - as usual - the category names have been made into links.)

So our current endeavor would require:

  1. a way to translate our category theory description of a particular mathematical object into an object of a corresponding category (denoted for brevity as Obj);
  2. a way to translate an object of Obj into our category theory description of the particular mathematical object.
It does seem circuitous, doesn't it? But it will explicitly demonstrate how forgetfulness works in our description of mathematical objects! One objection might be that this is assuming that the quote from Dr Baez is indeed correct; if Dr Baez is correct, we will verify it independently. Otherwise we won't forget things correctly.

So to describe our predicament using diagrams (as category theorists love doing), we basically are demanding the following commutes:

 \mathbf{Obj} &   \rTo^{U}         & \mathbf{Ob}\\
 \uInto       &                    & \dTo\\
 \mathbf{O}   & \rDashto_{forget!} & \mathbf{N}
\end{diagram} We embed the object of interest O into the category of corresponding objects Obj. We then "forget" something U:ObjOb (the category of slightly forgotten objects conveniently lacks the "j"). Then we recover the object as a category N, then assert there has to be a functor forget! which makes the diagram commute.

We see, however, that each morphism here is a functor, so our ability to forget a group G "into" a monoid should use a functor...but we should ultimately want to take a functor to a morphism, according to our table. It seems there is no way to construct such a functor forget! as we desire with the tools available at our disposal. We will have to revisit the issue of forgetfulness later on.

A 2-Category Description of A 1-Category Problem

I have been thinking about this problem we have, and the solution I think is this: we are using the language of 2-categories to describe a 1-category problem. It gives us extra information about groups, but it makes the problem a bit extra hard since the intuition we want to use doesn't apply here. First a reference...

Specifically Dr Baez writes:

What's a monoidal category, exactly?  Roughly it's a category with some
sort of "tensor product" and "unit object".  But we can precisely define
the so-called "strict" monoidal categories as follows: they are simply
2-categories with one object.  (Turn to "week80" for a definition of
2-categories.)   A 2-category has objects, morphisms, and 2-morphisms,
but if there is only one object, we can do the following relabelling

              2-morphisms ---------> morphisms
              morphisms   ---------> objects
              object      --------->  

Namely, we can forget about the object, call the morphisms "objects",
and call the 2-morphisms "morphisms".  But since all the new "objects"
were really morphisms from the original single object to itself, they
can all be composed, or "tensored".  That's why we get a category with
"tensor product", and similarly, a "unit object".   

So, just as a category with one object is just a monoid, a 2-category
with one object is a monoidal category!  This is one instance of a trick
that I sketched many more cases of in "week74".
Source: John Baez, Week 83
This Weeks Finds.

This gives me hope that we didn't screw up too badly! We're just ahead of the curve! Unfortunately, I'll need to cover a bit more category theory before I can make any more meaningful progress in this direction. I'm just afraid that I might have accidentally wandered into the wilderness of 3-categories... After reviewing a bit more about category theory, I believe now that I have wandered into the wilderness of topos!

Tuesday, August 4, 2009

Equivalence of Categories

We are going to start considering a hierarchy of "sameness". This is the strength of category theory really. At the top, the strongest notion of being the same is, I guess, the identity morphism. It says two things are identical. Next comes isomorphism. Then...what? First recommended reading:

And now down to business...

A Weaker Form of "Sameness"

We have that two categories $C,D$ are "isomorphic" if and only if there exists a functor $F:C\to{D}$ which is an isomorphism. We have the intuition that the categories are not identical but they are still "the same" in a sense.

Recall that our functor $F:C\to{D}$ is an isomorphism if and only if there exists a two-sided inverse functor $F^{-1}$. That is to say, $F^{-1}\circ{F}=1_{C}$ and $F\circ{F^{-1}}=1_{D}$. Note that these equations are "properties", so they're either true or false.

We want to "take it up a notch" and make them natural isomorphisms since $F^{-1}\circ{F}$, $F\circ{F^{-1}}$, $1_{C}$, and $1_{D}$ here are all functors. The only way to relate them all together is to use natural transformations, i.e. morphisms of functors!

Why is this "better"? (Well to interject, it's neither better nor's just different; kind of like apples and oranges, which is better? Well, they're different, we can't really compare them...) It's more appealing since we have more freedom with natural isomorphisms than strict equalities.

This programme of replacing boring equations with exciting isomorphisms is precisely the notion of "categorification". For a good introduction, see:

  • John Baez and James Dolan From Finite Sets to Feynman Diagrams arXiv:math/0004133 (2000)
In all seriousness, this procedure of categorification really is quite fascinating and - even if one knows nothing about Feynman diagrams - the paper is a good read.

Now, to reiterate the little explanation that was given, we will summarize it in our definition:

Definition 1. An "equivalence of categories" $C$ and $D$ consists of
  • a functor $F:C\to{D}$
such that
  • it has a "weak inverse", i.e. a functor $G:D\to{C}$ such that there exists some natural isomorphisms $\alpha:G\circ{F}\cong1_{C}$ and $\beta:1_{D}\cong F\circ{G}$.

The "orientation" of the natural isomorphisms may look odd at first, but when we get to adjoint functors it will become much clearer why this orientation is chosen.

The notion of equivalence is (hopefully) seen now as a "clearly" weaker form of "sameness". All it really says is that the composition of the functors $F\circ{G}$ is "the same as" (isomorphic to) the identity functor $1_{D}$, but how it is the same is given some freedom. We can specify some whacky relation $\beta_{d}$ for each $d\in{D}$ relating $(F\circ{G})(d)$ to $d$. It can be anything we want, even beyond our wildest dreams -- provided that $\beta_{d}$ is an isomorphism.

Similarly $G\circ{F}$ is isomorphic to $1_{C}$. It's the same as the identity, but this "sameness" is given some freedom in the sense that it "merely" has to be invertible. Of course the demand $G\circ{F}=1_{c}$ is an acceptable one, it's trivially isomorphic. But trivialities are boring.

That's precisely why we have equivalences, to avoid boredom ;)

Monday, August 3, 2009

Duality Principle

There is a powerful tool we have at our disposal and we never even knew about it: we can reverse the direction of the arrows. At first this is not too powerful, or so it should seem. (When I first read about it, I grunted and said "So what?" Its power becomes apparent later on...) First some citations:

  • Saunders Mac Lane, Categories for the Working Mathematician Graduate Texts in Mathematics (vol 5) Springer-Verlag, Second Edition (1998);
  • Jiri Adámek, Horst Herrlich, George E. Strecker Abstract and Concrete Categories: The Joy of Cats freely available online (2004)
  • Serge Lang Algebra Springer-Verlag, Third Edition (2000)
  • Duality entry in nLab wiki

We begin by introducing the notion of a dual category:

Definition 1. The "dual Category to $A$" (denoted $A^{op}$) consists of
  • a collection of objects $Ob(A)$, and
  • for each pair of objects $x,y\in OB(A)$ the set $\hom_{A^{op}}(x,y)=\hom_{A}(y,x)$.
equipped with the structure of a category such that it satisfies the properties of a category.

All the structure and properties of a dual category are "inherited" from a category in the obvious way (i.e. "by reversing the arrows").

We indicate dual objects in general by use of the prefix "co-", e.g. codomain of a co-morphism. When we reverse the direction of a morphism $f:x\to{y}$, we get $f^{op}:y\to{x}$ where $f^{op}$ is dual to $f$ and $y$ is the codomain.

When we have some property $\mathcal{P}$, we can find its dual $\mathcal{P}^{op}$. In general, the dual of a dual of a property is "the same" as the original $(\mathcal{P}^{op})^{op}\cong\mathcal{P}$.

We will now concern ourselves with the algorithm to finding the dual of a property about objects by example. Consider the property about objects $x\in{A}$:

  • $\mathcal{P}_{A}(x)$: for any $A$-object $a$ there exists exactly one $A$-morphism $f:a\to{x}$
Step 1: in $\mathcal{P}_{A}(x)$ replace all occurrences of $A$ by $A^{op}$, giving us
  • $\mathcal{P}_{A^{op}}(x)$: for any $A^{op}$-object $a$ there exists exactly one $A^{op}$-morphism $f:a\to{x}$
Step 2: we "translate it into the logically equivalent statement". This is just translatting the $A^{op}$ stuff into $A$ stuff, more explicitly:
  • $\mathcal{P}^{op}_{A}(x)$: for any $A$-object $a$ there exists exactly one $A$-morphism $f:x\to{a}$.
That concludes our algorithm for properties concerning objects in a category $A$.

There is a similar algorithm for properties of morphisms of $A$. Consider the following property of morphisms $f:x\to{y}$ in $A$:

  • $\mathcal{Q}_{A}(f)$: there exists an $A$-morphism $g:y\to{x}$ with $g\circ{f}:x\to{x}$ be the identity $g\circ{f}=1_{x}$.
Step 1: replace all occurrences of $A$ with $A^{op}$ giving us the following:
  • $\mathcal{Q}_{A^{op}}(f)$: there exists an $A^{op}$-morphism $g:y\to{x}$ with $g\circ{f}:x\to{x}$ be the identity $g\circ{f}=1_{x}$.
Step 2: we "translate into the logically equivalent", i.e. replace $A^{op}$ with the equivalent statements involving $A$:
  • $\mathcal{Q}^{op}_{A}(f)$: there exists an $A$-morphism $g:x\to{y}$ with $f\circ{g}:y\to{y}$ be the identity $f\circ{g}=1_{y}$.

These algorithms allow us to introduce one of the most foundational concepts in category theory:

Duality Principle for Categories. Whenever a property $\mathcal{P}$ holds for all categories, then the property $\mathcal{P}^{op}$ holds for all categories.

Products (but not Coproducts yet)

First some references:

  • The Catsters, Lectures on Products and Coproducts 1, 2, 3, 4
  • Saunders Mac Lane, Categories for the Working Mathematician Graduate Texts in Mathematics (vol 5) Springer-Verlag, Second Edition (1998);
  • Jiri Adámek, Horst Herrlich, George E. Strecker Abstract and Concrete Categories: The Joy of Cats freely available online (2004)
  • Serge Lang Algebra Springer-Verlag, Third Edition (2000)

We want to introduce the notion of "products" into category theory, or (equivalently) we want to categorify the notion of a product. We expect it to be such that when we work in Set we should recover the familiar Cartesian product, since that's what our intuition is based off of.

Where to start? Well, we know that with two sets $S_{1},S_{2}$ we can take their product $S_{1}\times{S_{2}}$. We can take their "projection", i.e. there are functions $\pi_{1}:S_{1}\times{S_{2}}\to{S_{1}}$ and $\pi_{2}:S_{1}\times{S_{2}}\to{S_{2}}$ which do the obvious things: they select out the first and second sets (respectively).

To generalize this notion to categories in general, we expect for some category $C$ and objects $c_{1},c_{2}\in{C}$ that their product is an object $p\in{C}$ such that we have two morphisms $\pi_{1}:p\to{c_{1}}$ and $\pi_{2}:p\to{c_{2}}$. But so what? There are probably a million such morphisms, how can pick some pair of morphisms out?

Good question, the answer is relatively intriguing. We select any third object $d\in{C}$ and demand that for every pair of morphisms $f:d\to{c_{1}}$ and $g:d\to{c_{2}}$, there needs to exist a unique function $h$ which makes the following diagram commute:

      &                &      d        &                &      \\
      &\ldTo^{f}       & \dDashto_{!h} & \rdTo^{g}      &      \\
c_{1} & \lTo_{\pi_{1}} & p             & \rTo_{\pi_{2}} & c_{2}
\end{diagram} The dashed arrow indicates we assert that morphism exists, usually we have the exclamation mark "!" involved to emphasize this fact. We have chosen the product to aptly be the object labeled by $p$. Lets give the formal definition:

Definition 1. The "product of $c_{1},c_{2}$" consists of
  • a mathematical object $p$
equipped with
  • a morphism $\pi_{1}:p\to{c_{1}}$;
  • a morphism $\pi_{2}:p\to{c_{2}}$;
such that
  • for any object $d\in{C}$ and pair of morphisms $f:d\to{c_{1}}$ and $g:d\to{c_{2}}$, there exists a corresponding morphism $h:d\to{p}$ such that the following diagram commutes:

      &                &      d        &                &      \\
      &\ldTo^{f}       & \dDashto_{!h} & \rdTo^{g}      &      \\
c_{1} & \lTo_{\pi_{1}} & p             & \rTo_{\pi_{2}} & c_{2}

Products of Categories

We have introduced the product for arbitrary mathematical objects, and being clever mathematicians we can say "Ah a category is-a mathematical object!" So we can get to our motivation for this section: the product of categories.

Here the notation is kind of more relaxed. We consider the product of categories $B$, $C$ to be denoted by $B\times{C}$. The objects are products of objects, and the morphisms are products of morphisms. More explicitly, for any $b,b^{\prime}\in{B}$ and $c,c^{\prime}\in{C}$ and morphisms $f:b\to{b^{\prime}}$, $g:c\to{c^{\prime}}$, the objects of $B\times{C}$ are $(b,c)$, $(b^{\prime},c^{\prime})$ and the morphisms $(f,g):(b,c)\to{}(b^{\prime},c^{\prime})$. We can intuitively think that things behave componentwise.

To emphasize this notion of "componentwise-thinking", consider the following scenario for our product category: we have objects $(b,c)$, $(b^{\prime},c^{\prime})$, and $(b^{\prime\prime},c^{\prime\prime})$. We have morphisms $(f,g):(b,c)\to(b^{\prime},c^{\prime})$ and $(f^{\prime},g^{\prime}):(b^{\prime},c^{\prime})\to(b^{\prime\prime},c^{\prime\prime})$. We can compose these two morphisms "in the obvious way", i.e. $(f,g)\circ(f^{\prime},g^{\prime})=(f\circ{f^{\prime}},g\circ{g^{\prime}})$.

Now, we need projection functors for our particular situation. That is, "projection morphisms" for our product category. It's even more intuitive in our notation what they do. If we have $B\xleftarrow{P}B\times{C}\xrightarrow{Q}C$, we have these projection functors be defined by $P(f,g)=f$ and $Q(f,g)=g$ on morphisms and similarly on object $P(b,c)=b$ and $Q(b,c)=c$.

These projection functors have to satisfy a similar property as the projection morphisms, which is what we expect to happen. More explicitly, for some category $D$ and two functors $B\xleftarrow{R}D\xrightarrow{T}C$ we demand that there is a unique functor $F:D\to{B\times{C}}$ such that the following diagram commutes:

      &                &      d        &                &      \\
      &\ldTo^{f}       & \dDashto_{!h} & \rdTo^{g}      &      \\
c_{1} & \lTo_{\pi_{1}} & p             & \rTo_{\pi_{2}} & c_{2}

This probably shouldn't be too surprising, it's what we expect to find if we just follow our nose.

Example: Products in "Set"

This is all rather complicated, so lets first examine what products of two sets means. To be more precise, what we mean is "The product of two objects in Set is what?"

Let $P$ be the product of $C_1$, $C_2$. Let $f:\mathbf{1}\to{C_{1}}$, $g:\mathbf{1}\to{C_{2}}$. How do these functions behave? This picks out a single element of $C_1$, $C_2$ (respectively). We can identify these morphisms as "the same as" the elements. Now the product idea makes the following diagram commute:

(Such a diagram is called an "internal diagram" since it shows the guts of the object, the dots are the elements of the sets, the arrows are morphisms in Set. Category theorists love doodling these sort of diagrams, it is really enlightening when inspecting a definition in category theory.)

What this means is that $\pi_{1}\circ\langle f,g\rangle=f$ (or the morphism $\mathbf{1}\to{P}$ followed by $\pi_{1}$ is completely equivalent to $f$) and $\pi_{2}\circ\langle f,g\rangle=g$ ($\mathbf{1}\to{P}$ then $P\to{C_{2}}$ is the same as $g$). But this morphism $\langle f,g\rangle$ picks out a single element of $P$, since its domain is 1.

So what do we imagine an element of $P$ ought to be? It should be such that it can be projected into two components. This hints that the elements of $P$ are ordered pairs $(c_1,d_2)$ where $c_1\in{C_{1}}$ and $d_{2}\in{C_{2}}$.

How can we say this? Well, there are 3 elements in $C_1$ and 2 elements in $C_2$. This means that there are 2 distinct morphisms $\mathbf{1}\to{C_{2}}$ and 3 distinct morphisms in $\mathbf{1}\to{C_{1}}$. How many distinct pairs of morphisms can we pick out? There are $2\times3=6$ different ways to pick out pairs of arrows $\mathbf{1}\to{C_{1}}$ and $\mathbf{1}\to{C_{2}}$, and so 6 unique corresponding arrows from $\mathbf{1}\to{P}$. This is the number of possible ordered pairs of elements $(c_1,d_2)$. For another possible pair of arrows we could have picked, consider the following internal diagram:

For each point $f:\mathbf{1}\to{C_{1}}$, there is a corresponding pair of points $g:\mathbf{1}\to{C_{2}}$. There are 3 distinct such $f$ arrows, and each distinct arrow has two corresponding $g$ arrows, yielding 6 distinct arrows $\mathbf{1}\to{P}$. Just as for each $c_{i}\in{C_{1}}$ there is a corresponding pair of elements $d_{1},d_{2}\in{C_{2}}$; so we can write 6 possible ordered pairs $(c_i,d_j)$ where $i=1,2,3$, $j=1,2$. This seems to be exactly what we are doing with our product, which is hinted by the $\mathbf{1}\to{P}$ morphism...

Summary: from our internal diagrams, we can deduce that the product of elements of Set amounts to the Cartesian products of those sets.

Natural Question: Morphisms of Functors?

By now I hope the reader sees the waltz that goes on here: we introduced objects, then asked about mappings between them. We introduced categories, and morphisms between them (functors). We now ask "Well, what about functors, can we have morphisms between them?"

(The very clever reader who asks "Wait, what about morphisms of morphisms?" We may get to this, it's basically the notion of comma categories, or slice categories. If I recall correctly, the two are the same. We'll get into it some more before covering the notion of universal arrows.)

The recommended reading this time includes some Youtube lectures by the Catsters:

Now there are many different ways to present natural transformations, because it's not so simple as it seems. We introduced functors in two ways: as a way to encode a mathematical process, and as a generalization of assigning information to each object of the domain. We have thus two different ways to present morphisms of functors.

Homotopy Analogy

How can we have a mapping of one process to another? This intuition is hard to grasp, personally I want to jump all over the idea of homotopy deformation. But recall a homotopy deformation takes two paths $\gamma_{1},\gamma_{2}:I\to\mathbb{C}$ where $I$ is an interval, and deforms one into the other. More precisely:


The problem is that we need some category theoretic analog to: the product $\times$ and the unit interval. I'll cheat and give the answer: we have some notion of the product of categories, and the category theoretic interval is our beloved 2. We set up the diagram describing the product category $C\times\mathbf{2}$:

C\times{1} &\qquad&\qquad& x       &\rTo^{(f,1)} & y\\
           &\qquad&\qquad& \uTo    &             & \uTo\\
C\times{0} &\qquad&\qquad& x       &\rTo_{(f,0)} & y

We treat the objects of this category as an ordered pair $(0,x)$ and $(1,x)$. For all practical purposes, $C\times\mathbf{2}$ behaves like two copies of $C$: $C\times{0}$ and $C\times{1}$. We have arrows joining the first to the second, as we have demonstrated in our diagram.

Here the functors $T_{0},T_{1}:C\to{C\times\mathbf{2}}$ ("bottom" and "top", respectively) are defined for each arrow $f$ of $C$ by $T_{0}(f)=(f,0)$ and $T_{1}(f)=(f,1)$.

Let $\downarrow$ denote the unique non-identity arrow $0\to{1}$ in 2. We can define a transformation between $T_0,T_1:C\to{C\times\mathbf{2}}$ by

$\mu:T_{0}\to{T_{1}},\quad \mu(c)=(c,\downarrow)$

for any object $c$. It maps "bottom" to "top" and is clearly "natural". This $\mu$ mapping is the skeleton of the "homotopy deformation" of processes. It's specifically something called a "universal natural transformation" from $C$. (Remark: the term "universal" means that we factor everything through it. We'll show what this means.)

Let $S,T:C\to{B}$ be functors. There is a unique functor $F:C\times\mathbf{2}\to B$ with $(F\circ{}\mu):C\to{B}$ identified as the "homotopy deformation" of $S\Rightarrow{T}$. (Notation: for our "homotopy deformation" of processes, we denote it with a special arrow $\Rightarrow{}$.)

Now what exactly is going on here? We basically identify acting on the "top" with $F$ as being "the same" as acting on $C$ by $S$; and we similarly identify acting on the "bottom" with $F$ as being "the same" as acting on $C$ by $T$. Now the question arises: what about acting on $(c,\downarrow)$? How does this behave?

$F$ acts on $(c,\downarrow)$ in precisely the homotopic way we envisioned. It "deforms" the "top" into the "bottom". Such a deformation is usually dubbed a "natural transformation" and denoted by the special arrow $S\Rightarrow{T}$. Note that the domain and codomain of natural transformations are functors. Specifically functors which have the same domain and codomain.

We see explicitly, for $f:c\to{c^{\prime}}$,

  1. $F(f,0)=S(f)$,
  2. $F(f,1)=T(f)$,
  3. $F(f,\downarrow)=T(f)\circ[(F\circ\mu)(c)]=[(F\circ\mu)(c^{\prime})]\circ S(f)$.
This is precisely the behavior describing a natural transformation $(F\circ\mu)$.

The reader interested in this "homotopy" presentation of natural transformations can refer to

  • The Catsters "Natural transformations 1" Youtube lecture (2007)
  • Saunders Mac Lane, Categories for the Working Mathematician Graduate Texts in Mathematics (vol 5) Springer-Verlag, Second Edition (1998); specifically the end of the section on products of categories (page 39 of my copy)
Sadly I haven't seen any other material on this presentation of natural transformations in this "homotopic way".

Morphisms of (Pre-)Sheaves

We have presented functors with the notion of generalizing vector fields to categories previously. A functor (presheaf really) "assigns" to each object of its domain some information, a mathematical object in the codomain, in a "consistent way".

The question that presents itself now is: we have assigned information in one way $S:C\to{B}$ and in another way $T:C\to{B}$. Is there a way to relate these two assignments?

Now there is a weakness with this motivation, consider the following situation: we have a vector and we can obtain a scalar (its norm). If we have the functor $S:C\to\mathbf{Vect}$ (where Vect is the category of vector spaces with morphisms be linear transformations) and $T:C\to\mathbf{Set}$, a "morphism" of these functors $\|\cdot\|:S\Rightarrow{T}$ done "in the obvious way" isn't a natural transformation. Why not? Because the codomains of $S$ and $T$ are different! But turning a vector into a scalar via the norm is really quite a natural thing to do!

But that's the wrong way to think of "naturally transforming $S$ into $T$". What we should instead do is consider the following situation, let $S,T:C\to\mathbf{Vect}$. They assign to each object of $C$ a vector space. Each morphism of $C$ becomes a linear transformation. However, the linear transformations are projections onto subspaces. This is the only way we could get the restriction morphism demand of the presheaf functor to work out.

The natural transformation then is subject to the condition that this morphism-of-sheaves is compatible with restrictions. In other words, we restrict then change the method of assigning information is the same as changing the method of assigning information then restricting. This is the same as demanding the following commutes:

G(u)             && \rTo^{\varphi_{u}} && F(u) \\
\dTo^{res_{v,u}} &&                    && \dTo_{res_{v,u}}\\
G(v)             &&\rTo_{\varphi_{v}}  && F(v)

In the immortal infallible words of wikipedia:

Heuristically speaking, a morphism of sheaves is analogous to a function between them. However, because sheaves contain data relative to every open set of a topological space, a morphism of sheaves is defined as a collection of functions, one for each open set, which satisfy a compatibility condition.

The interested reader can peruse a variety of references on the material:

Formal Considerations

We've given two approaches motivating the notion of natural transformations (or "morphisms of functors"). We should, being good mathematicians, define what a natural transformation is precisely.

Definition 1. Given two functors $F,G:C\to{D}$, a "Natural Transformation" $\tau:F\Rightarrow{G}$ consists of
  • a function $\tau$ mapping each object $x\in{C}$ to a morphism $\tau_{x}:F(x)\to{G(x)}$
such that
  • for any morphism $f:x\to{y}$ in $C$, the following diagram commutes:
F(x)             && \rTo^{F(f)} && F(y) \\
\dTo^{\tau_{x}}  &&             && \dTo_{\tau_{y}}\\
G(x)             &&\rTo_{G(f)}  && G(y)

(Note the notation: we use $\Rightarrow$ instead of $\to$ to indicate we're working with a natural transformation!)

What this effectively does is it "compares" (well, "relates") two different ways of assigning information in a "natural way". This is what both the homotopy approach and presheaf approach tells us, just in a more intuitive way.

Since a natural transformation "is-a" morphism (sort of), we can have an isomorphism. But we don't call it just that. We give it the adjective "natural" to indicate it's really a natural transformation with an "inverse". More precisely:

Definition 2. Let $F,G:C\to{D}$ be functors, a "natural isomorphism" consists of
  • a natural transformation $\alpha:F\Rightarrow{G}$
equipped with
  • a unique natural transformation $\beta:G\Rightarrow{F}$
such that
  • $\beta\circ\alpha=1_{F}$ and $\alpha\circ\beta=1_{G}$.

It's not uncommon to see this written as $\alpha:F\cong{G}$.

We Can "Compose" Natural Transformations With Functors

It's important to make a note here that I haven't really seen in e.g. Mac Lane's Categories for the Working Mathematician, but it's used all the time. We can "compose" natural transformations with functors "in the obvious way".

The only place that I have actually seen explicitly spell this out, shockingly enough, is Wikipedia(!):

If η : F ⇒ G is a natural transformation between functors F, G : C → D, and H : D → E is another functor, then we can form the natural transformation Hη : H∘F ⇒ H∘G by defining

$ (H \eta)_X = H_{\eta_X}. $

If on the other hand K : B → C is a functor, the natural transformation ηK : F∘K ⇒ G∘K is defined by

$ (\eta K)_X = \eta_{K(X)}.\, $
Source: Wikipedia, Natural Transformations.