About this article
- This post is an alpha version of the first part of the intended article.
- People who are beginners in learning abstract math concepts have many misunderstandings about the definitions and early theorems of category theory.
- This article introduces a few basic concepts of category theory. It goes into detail in Purple Prose about the misunderstandings that can arise with each of the concepts. The article is not at all a complete introduction to categories.
- My blog post Introducing abstract topics describes some of the strategies needed in teaching a new abstract math concept.
- This article also introduces a few examples of categories that are primarily chosen to cause the reader to come up against some of those misunderstandings. The first example is completely abstract.
- Math students usually see categories after considerable exposure to abstract math, but students in computing science and other fields may see it without having much background in abstraction. I hope teachers in such courses will include explanations of the sort of misunderstandings mentioned in this article.
- Like all posts in Gyre&Gimble and all posts in abstractmath.org, this article is licensed under a Creative Commons Attribution-ShareAlike 2.5 License. If you are teaching a class involving category theory, feel free to hand it out, and to modify it (in which case you should include a link to this post).
- You could also use the article as a source of remarks you make in the class about the topics.
About categories
To be written.
Definition of category
A category is a type of Mathematical structure consisting of two types of data, whose relationships are entirely determined by some axioms. After the definition is complete, I will introduce several categories with a detailed discussion of each one, explaining how they fit the definition of category.
Axiom 1: Data
- A category consists of two types of data: objects and arrows.
- No object can be an arrow and no arrow can be an object.
Notes for Axiom 1
- An object of a category can be any kind of mathematical object. It does not have to be a set and it does not have to have elements.
- Arrows of a category are also called morphisms. You may be familiar with “homomorphisms”, “homeomorphisms” or “isomorphisms”, all of which are functions. This does not mean that a “morphism” in an arbitrary category is a function.
Axiom 2: Domain and codomain
- Each arrow has a domain and a codomain, each of which is an object of the category.
- The domain and the codomain of an arrow may or may not be the same object.
- Each arrow has only one domain and only one codomain.
Notes for Axiom 2
- If $f$ is an arrow with domain $A$ and codomain $B$, that fact is typically shown either by the notation “$f:A\to B$” or by a diagram like this:
- The notation “$f:A\to B$” is like that used for functions. This notation may be used in any category, but it does not imply that $f$ is a function or that $A$ and $B$ have elements.
- For such an arrow, the notation “$\text{dom}(f)$” refers to $A$ and “$\text{cod}(f)$” refers to $B$.
- For a given category $\mathsf{C}$, the collection of all the arrows with domain $A$ and codomain $B$ may be denoted by
- “$\text{Hom}(A,B)$” or
- “$\text{Hom}_\mathsf{C}(A,B)$” or
- “$\mathsf{C}(A,B)$”.
- Some newer books and articles in category theory use the name source for domain and target for codomain. This usage has the advantage that a newcomer to category theory will be less likely to think of an arrow as a function.
Axiom 3: Composition
- If $f$ and $g$ are arrows in a category for which $\text{cod}(f)=\text{dom}(g)$, as in this diagram:
then there is a unique arrow with domain $A$ and codomain $C$ called the composite of $f$ and $g$.
Notes for Axiom 3
- diagra
- An important metaphor for composition is: Every path of length 2 has exactly one composite.
- The unique arrow required by Axiom 3 may be denoted by “$g\circ f$” or “$gf$”. “$g\circ f$” is more explicit, but “$gf$” is much more commonly used by category theorists.
- Many constructions in categories may be shown by diagrams, like the one used just above.
- The diagram
is said to commute if $h=g\circ f$. The idea is that going along $f$ and then $g$ is the same as going along $h$.
- It is customary in some texts in category theory to indicate that a diagram commutes by putting a gyre in the middle:
- The concept of category is an abstraction of the idea of function, and the composition of arrows is an abstraction of the composition of functions. It uses the same notation, “$g\circ f$”. If $f$ and $g$ are set functions, then for an element $x$ in the domain of $f$, \[(g\circ f)(x)=g(f(x))\]
- But in arbitrary category, it may make no sense to evaluate an arrow $f$ at some element $x$; indeed, the domain of $f$ may not have elements at all, and then the statement “$(g\circ f)(x)=g(f(x))$” is meaningless.
Axiom 4: Identity arrows
- For each object $A$ of a category, there is a unique arrow denoted by $\textsf{id}_A$.
- $\textsf{dom}(\textsf{id}_A)=A$ and $\textsf{cod}(\textsf{id}_A)=A$.
- For any object $B$ and any arrow $f:B\to A$, the diagram
commutes.
- For any object $C$ and any arrow $g:A\to C$, the diagram
commutes.
Notes for Axiom 4
- The fact stated in Axiom 4(b) could be shown diagrammatically either as
or as
- Facts (c) and (d) can be written in algebraic notation: For any arrow $f$ going to $A$,\[\textsf{id}_A\circ f=f\]and for any arrow $g$ coming from $A$,\[g\circ \textsf{id}_A=g\]
Axiom 5: Associativity
- If $f$, $g$ and $h$ are arrows in a category for which $\text{cod}(f)=\text{dom}(g)$ and $\text{cod}(g)=\text{dom}(h)$, as in this diagram:
then there is a unique arrow $k$ with domain $A$ and codomain $C$ called the composite of $f$, $g$ and $h$.
- In the diagram below, the two triangles containing $k$ must both commute.
Notes for Axiom 5
- Axiom 5b requires that \[h\circ(g\circ f)=(h\circ g)\circ f\](which both equal $k$), which is the usual formula for associativity.
- Note that the top two triangles commute by Axiom 3.
- The associativity axiom means that we can get rid of parentheses and write \[k=h\circ f\circ g\]just as we do for addition and multiplication of numbers.
- In my opinion the notation using categorical diagrams communicates information much more clearly than algebraic notation does. In particular, you don’t have to remember the domains and codomains of the functions — they appear in the picture. I admit that diagrams take up much more space, but now that we read math stuff on a computer screen instead of on paper, space is free.
Examples of categories
For the first three examples, I will give a detailed explanation about how they fit the definition of category.
Example 1: MyFin
This first example is a small, finite category which I have named $\mathsf{MyFin}$ (my very own finite category). It is not at all an important category, but it has advantages as a first example.
- It’s small enough that you can see all the objects and arrows on the screen at once, but big enough not to be trivial.
- The objects and arrows have no properties other than being objects and arrows. (The other examples involve familiar math objects.)
- So in order to check that $\mathsf{MyFin}$ really obeys the axioms for a category, you can use only the skeletal information given here. As a result, you must really understand the axioms!
A correct proof will be based on axioms and theorems. The proof can be suggested by your intuitions, but intuitions are not enough. When working with $\mathsf{MyFin}$ you won’t have any intuitions!
A diagram for $\mathsf{MyFin}$
This diagram gives a partial description of $\mathsf{MyFin}$.
Now let’s see how to make the diagram above into a category.
Axiom 1
- The objects of $\mathsf{MyFin}$ are $A$, $B$, $C$ and $D$.
- The arrows are $f$, $g$, $h$, $j$, $k$, $r$, $s$, $u$, $v$, $w$ and $x$.
- You can regard the letters just listed as names of the objects and arrows. The point is that at this stage all you know about the objects and arrows are their names.
- If you prefer, you can think of the arrows as the actual arrows shown in the $\mathsf{MyFin}$ diagram.
- Our definition of $\mathsf{MyFin}$ is an abstract definition. You may have seen multiplication tables of groups given in terms of undefined letters. (If you haven’t, don’t worry.) Those are also abstract definitions.
- Most of our other definitions of categories involve math objects you actually know something about. They are like the definition of division, for example, where the math objects are integers.
Axiom 2
- The domains and codomains of the arrows are shown by the diagram above.
- For example, $\text{dom}(r)=A$ and $\text{cod}(r)=C$, and $\text{dom}(v)=\text{cod}(v)=B$.
Axiom 3
Showing the $\mathsf{MyFin}$ diagram does not completely define $\mathsf{MyFin}$. We must say what the composites of all the paths of length 2 are.
- In fact, most of them are forced, but two of them are not.
- We must have $g\circ f=r$ because $r$ is the only arrow possible for the composite, and Axiom 3 requires that every path of length 2 must have a composite.
- For the same reason, $h\circ g=s$.
- All the paths involving $u$, $v$, $w$ and $x$ are forced:
- (p1) $u\circ u=u$, $v\circ v=v$, $w\circ w=w$ and $x\circ x=x$.
- (p2) $f\circ u=f$, $r\circ u=r$, $j\circ u=j$ and $k\circ u=k$. You can see that, for example, $f\circ u=f$ by opening up the loop on $f$ like this:
There is only one arrow going from $A$ to $B$, namely$f$, so $f$ has to be the composite $f\circ u$.
- (p3) $v\circ f=f$, $g\circ v=g$ and $s\circ v=s$.
- (p4) $w\circ g=g$, $w\circ r=r$ and $h\circ w=h$.
- (p5) $x\circ h=h$, $x\circ s=s$, $x\circ j=j$ and $x\circ k=k$.
Definition: $s\circ f=h\circ r=j$.
If we had defined $s\circ f=h\circ r=k$ we would have a different category, although one that is “isomorphic” to $\mathsf{MyFin}$ (you have to define “isomorphic” or look it up.)
Axiom 4
- It is clear from the $\mathsf{MyFin}$ diagram that for each object there is just one arrow that has that object both as domain and as codomain, as required by Axiom 4a.
- The requirements in Axiom 4b and 4c are satisfied by statements (p1) through (p5).
Axiom 5
- Since we have already required both $(h\circ g)\circ f$ and $h\circ(g\circ f)$ to be $k$, composition is associative.
Example 2: Set
To be written.
This will be a very different example, because it involves known mathematical objects — sets and functions. But there are still issues, for example the fact that the inclusion of $\{1,2\}$ into $\{1,2,3\}$ and the identity map on $\{1,2\}$ are two different arows in the category of sets.
Example 3: IntegerDiv
To be written.
The objects are all the positive integers and there is an arrow from $m$ to $n$ if and only if $m$ divides $n$. So this example involves familiar objects and predicates, but the arrows are nevertheless not functions that take elements to elements. Integers don’t have elements. I would expect to show how the GCD of two integers is a limit.
References
- Category theory for programmers, Bartosz Milewski.
- A gentle introduction to category theory, Peter Smith.
- The list Category Theory in Logic Matters gives a pretty complete coverage of every introduction to category theory that is available online.
This work is licensed under a Creative Commons Attribution-ShareAlike 2.5 License.
Send to Kindle
The blending of graph and formula associates each point on the (blue) graph with the value of the formula at the number on the x-axis directly underneath the point.