# A Digression

13 Jul 2019

I’m not sure what this post set out to be. It ended up a digression on set theory vs. category theory.

In modern mathematics, there are two notions that might be truly called
foundational to all the work we do. These are *set theory* and *category theory.*
Both theories are living, evolving things with their specialists, constructions
and interesting problems, just like any other field of math,
but the core ideas are familiar and useful to nearly every mathematician.

A *set,* naively, is just a way to collect a bunch of objects (called *elements*)
together. Since a set only cares about membership or lack thereof, duplicate
elements are ignored. When we’re explicit about them, a set is typically
denoted as a list of elements (thought of as unordered), surrounded by curly braces.
So as sets, \(\{1,2,3,3,5\} = \{1,2,3,5\}\). A set comprises its elements, nothing more,
nothing less. Thus, maps or functions \(f\) between sets \(X\) and \(Y\) are just
assignments: to each element \(x\) in \(X\), we assign a (unique) element \(f(x)\)
of \(Y\).

Things, mathematical objects, whatever you can pin down in language, may be elements (or not) of sets. Sets may even be elements of other sets, although here is a source of worry. Bertrand Russell observed in 1901 that allowing this kind of willy-nilly calling things sets yields the mathematical equivalent of the following silly story: In a small village there is one barber. He shaves the beards of only those men who does not shave themselves. Who shaves the barber?

The question, of course, has no good answer. If the barber shaves himself, then he cannot, but then he must. The mathematical response to Russell’s realization was to retrench a bit, but it also paved the way for set theory to become an interesting field of research in its own right.

Set theory, thanks to work of Kurt Goedel and many others, has raised thorny,
even unsolvable, problems that mathematicians working in other fields would often
prefer to gloss over. One example is the following: If you have in front of you
a finite collection of sets, maybe think of them as baskets in the produce section,
you can obviously choose an element from each basket. This process is sometimes
called a *choice function.* If you imagine an infinitely long aisle at the grocery
store with baskets evenly spaced along it, you might agree that you can still
choose one element from each basket. Even though you won’t live to see it
through, it’s easy to describe a way to decide how to choose the next element;
each basket is eventually reached by you, even though you will never reach
every basket. This kind of infinity is *countably infinite,* like the numbers
we use for counting. But there are more kinds of infinity, and in those cases
it’s maybe not immediately clear that we should still be able to take an object from
each basket. The hypothesis that we *can* is called the *Axiom of Choice,* and it
turns out to be “independent” of the rest of the rules of set theory we commonly employ.
That is, the rest of set theory *can remain true* whatever position we wish to take on
the axiom of choice.

Category theory, (already touched on implicitly in The Category of Graphs) has
a somewhat similar history, although it arose later. Introduced by Samuel Eilenberg
and Saunders Mac Lane in their study of algebraic topology, it has since become
a central perspective in many areas of mathematics and also grown into a field
of interest in its own right. A category is a collection of objects and arrows.
Note that I did not say a *set.* This distinction is important theoretically
but in practice categorical and set-theoretic reasoning are typically
sufficiently different that this can be ignored. In category theory,
the sets themselves comprise a category, typically called **Set** with
objects sets and arrows functions between sets. This metaphor motivates
the definition: arrows have a *domain* and *codomain,* just as functions
between sets do. Arrows, like functions, may be *composed* (i.e.
“first add four, and then multiply by sixteen”), and the composition is
associative, but need not be commutative.

This general picture allows one to talk about several different, yet related,
situations together at once. Many common constructions in mathematics, including
“sum” and “product” may be phrased as a certain kind of “universal” construction
in the language of category theory. One such construction, the *free object,*
is particularly interesting within group theory. Originally I had meant to talk
about it in this post, but perhaps the next one.