A Programmers Way of Thinking About Sets and Categories
The role of weakly and strongly typed variables in the foundations of math
A long time ago I asked a question about Category Theory over at math stack exchange that got a lot of fantastic answers and comments, but one answer by Carl Mummert struck me in particular, and it has completely changed the way I think about a lot of concepts in all branches of mathematics.
When I was an undergraduate and first learned about set theory it opened my eyes to the world of advanced mathematics, and when I first encountered category theorists saying bad things about set theory I felt very defensive. I had the very silly idea that I could prove that set theory is somehow “more fundamental” than category theory. When I first posted my question over at math stack exchange, I was hoping that I could finally find proof that set theory is required for the very formulation of category theory, and therefore is “more fundamental”. Whatever that means!
I realize now that Set Theory and Category Theory are just two different points of view for thinking about abstract concepts in a precise way. They are not mutually exclusive, but rather, both subjects play an important role in informing us about the foundations of mathematics.
Category theory is nice for the same reason that it’s nice to be able to write code in higher level languages like Java and not have to worry about the physics of semi-conductors, assembly language, or the inner workings of the virtual machine. It’s enough to know that someone else in the past worked it all out and everything checks out, and that there are experts who spend all of their time focusing on these subjects to optimize everything.
Set Theory and Java Script Objects
Very loosely speaking, set theory is “like an untyped programming language”, where we don’t care about the data type of our variables, everything is just a set. Set theory is the rigorous generalization of the naive concept of “a collection of objects”. By definition, the same element cannot appear twice in a set, and there is no apriori ordering. In Python, set is a data type which has these properties. We are going to sweep a very large number of issues under the rug and think about mathematical sets as java script objects for a moment. In set theory you can construct many sets, but what are the elements of these sets? Other sets of course! In set theory, everything is a set; just as in java script, at a certain level every variable is basically just an object.
In mathematics, as well as in programming, we deal with many different data structures. As opposed to languages which are compiled on a computer, mathematics is a language that is compiled by the human mind — and it is our own minds which must supply all of the warnings and error messages.
The problem of implementing a given data structure on a machine is completely irrelevant in pure math, and there are many data structures and data types which cannot exist on a computer. This explains why some questions that arise naturally in computer science, such as what is the maximum efficiency of a compression algorithm, can only be answered in the language of mathematics.
An example of a data structure that cannot exist on a computer is an uncountable set of elements such as the set of real numbers R. Floating point numbers are the best we can do, but they are merely a finite approximation to numbers that theoretically exist in a formal sense, and which contain an an infinite sequence of non-repeating digits after the decimal point.
Category Theory and Java
Category theory takes a different point of view towards the foundations of mathematics from set theory. According to this perspective, rather than treating sets as first class citizens we focus instead on mappings between two sets. For example, consider the following Java function:
int fn(int n) {
return 2 * n;
}
According to category theory, this function is a “mapping” which takes as input an integer and produces as output an even integer. In category theory, just like in java, all of our functions must have a return type and the data type of each parameter must be specified.
Once you have more than just a few functions acting on the same collection of sets, a very convenient and simple way to think about everything is to represent each set as a dot (or “vertex”), and each function as an arrow which points from its input set to its output set. This kind of data structure is called a directed graph, and it plays a fundamental role in category theory. The study of the graph data structure is called Graph Theory, it is a vast field with a wide range of deep and beautiful results.
Due to the foundational nature of Category Theory, and perhaps for other reasons as well, the graph data structure comes up over and over again in both pure and applied mathematics. It is no coincidence that it also plays such a prominent role in computer science and programming.
Number Theory and Casting
In Java, given an integer and a floating point number
int i = 2;
float p = 2.0f;
we cannot simply add these two numbers together and expect the compiler to return an integer, that would be an error. First we have to cast p to an integer:
int n = i + (int)p;
In category theory we don’t use the word “cast”, instead this is called the Natural Inclusion Map, but it’s the same thing.
There are two distinct branches of number theory which are deeply related by the casting operation between real (or complex) numbers and natural numbers, namely: analytic and elementary number theory.
Elementary number theory is the study of natural numbers without using a lot of advanced methods, and its a very hard subject. Elementary number theory poses many vexing questions and offers very little insight, but it can be fun to test ones cleverness against a challenging problem while being limited to only a small set of tools.
Analytic number theory is when the very powerful machinery of calculus and analysis are brought to bear on certain problems whose solution can be shown to also resolve questions which arise naturally in the elementary theory of numbers.
An interesting phenomenon is that there are multiple proofs of the same facts, by both elementary and analytic techniques, and the best of these proofs provide powerful methods that can be used to attack other problems. For example, Euler gave a shocking proof of the fact that there an infinite number of primes using an infinite product of geometric series, and this approach has been shown to be much better for obtaining other results, such as the Prime Number Theorem, than the original proof given by Euclid.
This phenomenon is similar to the way a new library or framework could make one or another tasks practical for the first time. However when writing a program, presumably you have some purpose for writing it that comes from the outside world. In pure mathematics our purpose is to discover eternal truths about certain abstract concepts (or “Categories) and to develop tools and methods that provide insight into the relationship between them.
tl;dr
The lack of typing in set theory is useful for many purposes, but it can cause an unnecessary amount of overhead for doing simple things which can be avoided by thinking about mathematical objects as strongly typed variables instead of sets; and the beauty of Category theory is that it provides a language for understanding a universal structure which is extremely fundamental, and which appears in a very large number of completely distinct mathematical systems.
