Paolo Perrone gives a nice, succinct motivation for monads in the introduction to his article on probability and monads.
… a monad is like a consistent way of extending spaces to include generalized elements of a specific kind.
He develops this idea briefly, and links to his dissertation where he gives a longer exposition (pages 8–14).
Related post: Monads are hard because …
Curry-Howard-Lambek is a set of correspondences between logic, programming, and category theory. You may have heard of the slogan proofs-as-programs or propositions-as-types. These refer to the Curry-Howard correspondence between mathematical proofs and programs. Lambek’s name is appended to the Curry-Howard correspondence to represent connections to category theory.
The term Curry-Howard isomorphism is often used but is an overstatement. Logic and programming are not isomorphic, nor is either isomorphic to category theory.
You’ll also hear the term computational trinitarianism. That may be appropriate because logic, programming, and category theory share common attributes without being identical.
The relations between logic, programming, and categories are more than analogies, but less than isomorphisms.
There are formal correspondences between parts of each theory. And aside from these rigorous connections, there is also a heuristic that something interesting in one area is likely to have an interesting counterpart in the other areas. In that sense Curry-Howard-Lambek is similar to the Langlands program relating number theory and geometry, a set of theorems and conjectures as well as a sort of philosophy.
My first math classes used the terms one to one and onto to describe functions. These Germanic names have largely been replaced with their French equivalents injective and surjective.
Monic and epic are the category theory analogs of injective and surjective respectively. This post will define these terms and show how they play out in several contexts. In some categories these new terms correspond exactly to their traditional counterparts, but in others they do not.
A function f from a set A to a set B is injective (one-to-one) if different points on A go to different points in B. That is, f(x) = f(y) only if x = y.
The function f is surjective (onto) if everything in B is covered. That is, for every b in B, there is some a in A such that f(a) = b.
A function is bijective if it is both injective and surjective.
How would we generalize these definitions to category theory? This is not obvious because the rules of category theory don’t let us peek inside objects and talk about elements. Everything has to be characterized in terms of objects and morphisms.
It turns out that the categorical way to view things is to focus on when composition can be cancelled out, either on the left or on the right.
A morphism f from an object X to an object Y is an epimorphism if for any other object Z, and any pair of morphisms g1 and g2 from Y to Z, if g1 f = g2 f then g1 = g2. Instead of saying f is an epimorphism, some authors would say f is epic or f is an epi.
If a morphism f is epic, we can cancel it out on the right.
(Unfortunately it is conventional to write function composition from right to left, like splicing in a little bit of Hebrew inside English prose. In the diagram above, f is on the left, and composition proceeds from left to right. But when we write the composition of functions we write from right to left, e.g. gf. When we say we can cancel out f on the right, we mean the right of the expression gf, not on the right of a commutative diagram!)
Monomorphism is the dual concept to epimorphism.
A morphism f from an object X to an object Y is an monomorphism if for any other object Z, and any pair of morphisms g1 and g2 from Z to X, if f g1 = f g2 then g1 = g2. Instead of saying f is a monomorphism, some authors would say f is monic or f is a mono.
If a morphism f is monic, we can cancel it out on the left, in the sense of fg as explained above.
In any category, an iso is epic and monic. That is, an isomorphism is always an epimorphism and a monomorphism. The converse holds in some categories but not in others.
In the category of sets, a function f from X to Y is an epimorphism iff (if an only if) it is surjective.
Also in the category of sets, a function is a monomorphism iff it is injective.
Groups are similar in that a group homomorphism is an epimorphism iff it surjective, and a monomorphism iff it is injective.
Recall that a monoid is like a group, except you don’t necessarily have inverses. That is, you have an associative operation and an identity element.
Let N be the non-negative integers with addition and let Z be the integers. Let f be the inclusion map that takes N into Z. Then f is injective and a monomorphism. It is not surjective, but it is an epimorphism because homomorphism from the integers to another monoid is determined by its values on the positive integers. Its range leaves out half the codomain, but we can still cancel it out on the right.
So here we have a function that is epic and monic, but not an isomorphism.
A ring homomorphism is a monomorphism iff it is injective. But as with monoids, a ring homomorphism can be an epimorphism without being surjective.
For example, consider the inclusion map from the integers to the rationals. A ring homomorphism is determined by its values on integers, so the inclusion map is an epimorphism even though it is not surjective.
Incidentally, homomorphism between fields is monic.
Currying is a simple but useful idea. (It’s named after logician Haskell Curry [1] and has nothing to do with spicy cuisine.) If you have a function of two variables, you can think of it as a function of one variable that returns a function of one variable. So starting with a function f(x, y), we can think of this as a function that takes a number x and returns a function f(x, -) of y. The dash is a placeholder as in this recent post.
If you’ve taken calculus then you saw this in the context of Fubini’s theorem:
To integrate the function of two variables f(x, y), you can temporarily fix y and integrate the remaining function of x. This gives you a number, the value of an integral, for each y, so it’s a function of y. Integrate that function, and you have the value of the original function of two variables.
The first time you see this you may think it’s a definition, but it’s not. You can define the integral on the left directly, and it will equal the result of the two nested integrations on the right. Or at least the two sides will often be equal. The conditions on Fubini’s theorem tell you exactly when the two sides are equal.
A more sophisticated version of the same trick occurs in partial differential equations. If you have an evolution equation, a PDE for a function on one time variable and several space variables, you can think of it as an ODE via currying. For each time value t, you get a function of the spatial variables. So you can think of your solution as a path in a space of functions. The spatial derivatives specify an operator on that space of functions.
(I’m glossing over details here because spelling everything out would take a lot of writing, and might obscure the big idea, which relevant for this post. If you’d like the full story, you can see, for example, my graduate advisor’s book. It was out of print when I studied it, but now it’s a cheap Dover paperback.)
In the Haskell programming language (also named after Haskell Curry) you get currying for free. In fact, there’s no other way to express a function of two variables. For example, suppose you want to implement the function f(x, y) = x² + y.
Prelude> f x y = x**2 + y
Then Haskell thinks of this as a function of one variable (i.e. x), that returns a function of one variable (i.e. f(x, -)) which itself returns a number (i.e. f(x, y)). You can see this by asking the REPL for the type of f:
Prelude> :info f
f :: Floating a => a -> a -> a
Technically, Haskell, just like lambda calculus, only has functions of one variable. You could create a product datatype consisting of a pair of variables and have your function take that as an argument, but it’s still a function on one variable, though that variable is not atomic.
The way you’d formalize currying in category theory is to say that the following is a natural isomorphism:
For more on what Hom means, see this post.
[1] In concordance with Stigler’s law of eponymy, currying was not introduced by Curry but Gottlob Frege. It was then developed by Moses Schönfinkel and developed further by Haskell Curry.
Given two objects A and B, Hom(A, B) is simply the set of functions between A and B. From this humble start, things get more interesting quickly.
To make the above definition precise, we need to say what kinds of objects and what kinds of functions we’re talking about. That is, we specify a category C that the object belong to, and the functions are the morphisms of that category [1]. For example, in the context of groups, Hom(A, B) would be the set of group homomorphisms [2] between A and B, but in the context of continuous groups (Lie groups), we would restrict Hom(A, B) to be continuous group homomorphisms.
To emphasize that Hom refers to a set of morphisms in a particular category, sometimes you’ll see the name of the category as a subscript, as in HomC(A, B). Sometimes you’ll see the name of the category as a replacement for Hom as in C(A, B). You may also see the name of the category in square braces as in [C](A, B).
So far Hom has been a set, but you’ll also see Hom as a functor. This is where the notation takes a little more interpretation. You may see a capital H with objects as superscripts or subscripts:
You may also see a lower case h instead. And I’ll use the name of the category instead of “Hom” just to throw that variation in too.
I’ll explain what these mean and give a mnemonic for remembering which is which.
The dash in Hom(A, -) and Hom(-, A) means “insert your object here.” That is, Hom(A, –) takes an object B and maps it to the set of morphisms Hom(A, B), and Hom(-, A) takes an object B to Hom(B, A).
So Hom(A, -) and Hom(-, A) each take an object in the category C to a set of morphims, i.e. an element in the category Set. But that’s only half of what it takes to be a functor. A functor not only maps objects in one category to objects in another category, it also maps morphisms in one category to morphisms in the other. (And it does so in a way that the interactions between the maps of objects and morphisms interact coherently.)
Where do the morphisms come in? We’ve established what HA and HA do to objects, but what do they do to morphisms?
Suppose we have a morphism f: X → Y in the category C and a function g in Hom(A, X) to Hom(A, Y)? For each g in Hom(A, X), the composition fg is an element of Hom(A, Y).
Next suppose f: Y → X (note the reversed order) and a function g in Hom(X, A). Now the composition gf is an element of Hom(Y, A). Note that before we applied f after g, but here we pre-compose with f, i.e. apply f before g.
Aside from the notation, what’s going on is very simple. If you have a function from A to X and a function from X to Y, then the composition of the two is a function from A to Y. Similarly, if you have a function from Y to X and a function from X to A, the composition is a function from Y to A.
Note that HA is a covariant functor, but HA is a contravariant. More on covariant vs contravariant below.
How can you keep HA and HA straight? It’s common to use superscript notation YX to indicate the set of functions from the superscript object X to the base object Y. You may have seen this before even if you don’t think you have.
The notation Y² denotes the product of Y with it self, such as R² for the plane, i.e. pairs of real numbers. A pair of things in Y is a function from a two-element set to Y. You could think of (y1, y2) as the result of mapping the set (1, 2) into Y.
You may also have seen the notation 2X for the power set of X, i.e. the set of all subsets of X. You could think of the power set of X being the set of maps from X to the Boolean values (true, false) where an element x is mapped to true if and only if x is in that particular subset.
The notation using H or h with a superscript A stands for Hom(A, -), i.e. morphisms out of A, which is consistent with the usage described above. And so the other is the other, i.e. a subscript A stands for Hom(-, A), i.e morphisms into A.
(Unfortunately, some authors use the opposite of the convention used here, which blows the whole mnemonic away. But the convention used here is most common.)
We’re close to being able to state one of the most important theorems in category theory, the Yoneda lemma. (Lemmas often turn out to be more useful and better known than the theorem they were first used to prove.) So while we’re in the neighborhood, we’ll take a look.
A corollary of the Yoneda lemma says
The meaning of “Hom” is different on the left and right because we’re looking at morphisms between different kinds of objects. On the right we have sets of morphisms in our category C as above. The left side takes more explanation.
What kind of things are HA and HB? They are functors from C to Set. The class of functors between two categories forms a category itself. The functors are the objects in this new category, and natural transformations are the morphisms. So Hom in this context is the set of natural transformations between the two functors.
What kind of things are HA and HB? They are contravariant functors from C to Set, and contravariant functors also form a category. However, contemporary category theory doesn’t like to speak of contravariant functors, preferring to only work with covariant functors, and leaving the term “covariant” implicit. So rather than saying HA and HB are contravariant functors on C, most contemporary writers would say they are (covariant) functors on a new category Cop, where “op” stands for opposite. That is, Cop is a category with all the same objects as C, but with all the arrows turned around. Every morphism from A to B in C corresponds to a morphism from B to A in Cop.
[1] Morphisms are a generalization of functions. Often morphisms are functions, but they might not be. But still, they have to be things that compose like functions.
[2] The name Hom is a shortened from of “homomorphism.” Different areas of math have different names for structure-preserving functions, and category theory wanted to have one name for them all. It used “Hom” as an allusion to what structure-preserving functions are called in group theory. Similarly, “morphism” is also a shorted form of “homomorphism.” I suppose the goal was to use names reminiscent of group theory, but different enough to remind the reader that the category theory counterparts are distinct.
Incidentally, “homomorphism” comes from the Greek roots meaning “similar” and “shape.” A homomorphism is a function between similar objects (objects in the same category) that preserves structure (shape).
The Moore-Penrose pseudoinverse of a matrix is a way of coming up with something like an inverse for a matrix that doesn’t have an inverse. If a matrix does have an inverse, then the pseudoinverse is in fact the inverse. The Moore-Penrose pseudoinverse is also called a generalized inverse for this reason: it’s not just like an inverse, it actually is an inverse when that’s possible.
Given an m by n matrix A, the Moore-Penrose pseudoinverse A+ is the unique n by m matrix satisfying four conditions:
The first equation says that AA+ is a left identity for A, and A+A is a identity for A.
The second equation says A+A is a left identity for A+, and A A+ is a right identity for A+.
The third and fourth equations say that A A+ and A+A are Hermitian.
If A is invertible, A A+ and A+A are both the identity matrix. Otherwise A A+ and A+A act an awful lot like the identity, as much as you could expect, maybe a little more than you’d expect.
Update: See this post for the relationship between the singular value decomposition and pseudoinverses, and how to compute both in Python and Mathematica.
John Baez recently wrote that a Galois connection, a kind of categorical adjunction, is
“the best approximation to reversing a computation that can’t be reversed.”
That sounds like a pseudoinverse! And the first two equations defining a pseudoinverse look a lot like things you’ll see in the context of adjunctions, so the pseudoinverse must be an adjunction, right?
The question was raised on MathOverflow and Michal R. Przybylek answered
I do not think the concept of Moore-Penrose Inverse and the concept of categorical adjunction have much in common (except they both try to generalise the concept of inverse) …
and gives several reasons why. (Emphasis added.)
Too bad. It would have made a good connection. Applied mathematicians are likely to be familiar with Moore-Penrose pseudoinverses but not categorical adjoints. And pure mathematicians, depending on their interests, may be more familiar with adjoint functors than matrix pseudoinverses.
So what about John Baez’ comment? His comment was expository (and very helpful) but not meant to be rigorous. To make it rigorous you’d have to be rigorous about what you mean by “best approximation” etc. And when you define your terms carefully, in the language of category theory, you get adjoints. This means that the Moore-Penrose inverse, despite its many nice properties [1], doesn’t mesh well with categorical definitions. It’s not the best approximate inverse from a categorical perspective because it doesn’t compose well, and category theory values composition above all else. The Moore-Penrose pseudoinverse may be the best approximate inverse from some perspectives, but not from a categorical perspective.
Przybylek explains
… adjunctions compose … but Moore-Penrose pseudoinverses—generally—do not. … pseudoinverses are not stable under isomorphisms, thus are not categorical.
That’s the gist of his final point. Now let me fill in and expand slightly part of what I cut out.
If f: A → B is left adjoint to f+: B → A and g: B → C is left adjoint to g+: C → B then the composition gf: A → C is left adjoint to the composition f+g+: C → A, but Moore-Penrose pseudoinverses do not compose this way in general.
This turns out to be an interesting example, but not of what I first expected. Rather than the pseudoinverse of a matrix being an example of an adjoint, it is an example of something that despite having convenient properties does not compose well from a categorical perspective.
[1] The book Matrix Mathematics devotes about 40 pages to stating theorems about the Moore-Penrose pseudoinverse.
Categorical data analysis could mean a couple different things. One is analyzing data that falls into unordered categories (e.g. red, green, and blue) rather than numerical values (e.g. height in centimeters).
Another is using category theory to assist with the analysis of data. Here “category” means something more sophisticated than a list of items you might choose from in a drop-down menu. Instead we’re talking about applied category theory.
So we have ((categorical data) analysis) and (categorical (data analysis)), i.e. analyzing categorical data and categorically analyzing data. The former is far, far more common.
I ran across Alan Agresti’s classic book the other day in a used book store. The image below if from the third (2012) edition. The book store had the 1st (1990) edition with a more austere cover.
I bought Agresti’s book because it’s a good reference to have. But I was a little disappointed. My first thought was that someone has written a book on category theory and statistics, which is not the case, as far as I know.
The main reference for category theory and statistics is Peter McCullagh’s 2002 paper What is a statistical model? That paper raised a lot of interesting ideas, but the statistics community did not take McCullagh’s bait.
Maybe this just wasn’t a fruitful idea. I suspect it is a fruitful idea, but the number of people available to develop it, conversant in both statistics and category theory, is very small. I’ve seen category theory used in mathematical modeling more generally, but not in statistics per se.
At its most basic, category theory asks you to be explicit about the domain and range (codomain) of functions. It would be very helpful if statisticians merely did this. Statistical notation is notoriously bad at revealing where a function goes from and to, or even when a function is a function. Just 0th level category theory, defining categories, would be useful. Maybe it would be useful to go on to identifying limits or adjoints, but simply being explicit about “from” and “to” would be a good start.
Category theory is far too abstract to completely carry out a statistical analysis. But it can prompt you to ask questions that check whether your model has any inconsistencies you hadn’t noticed. The idea of a “categorical error” doesn’t differ that much moving from its philosophical meaning under Aristotle to its mathematical meaning under MacLane. Nor does the idea of something being “natural.” One of the primary motivations for creating category theory was to come up with a rigorous definition of what it means for something in math to be “natural.”
From Paul Phillips:
I see adjoint functors.
How often do you see them?
All the time. They’re everywhere. pic.twitter.com/6PkGJ9wP4A
— Paul Phillips (@contrarivariant) May 27, 2017
Mashup of Saunders Mac Lane’s quip “Adjoint functors arise everywhere” and Haley Joel Osment’s famous line from Sixth Sense.
Related: Applied category theory
The ladder of abstractions in category theory starts with categories, then functors, then natural transformations. Unfortunately, natural transformations don’t seem very natural when you first see the definition. This is ironic since the original motivation for developing category theory was to formalize the intuitive notion of a transformation being “natural.” Historically, functors were defined in order to define natural transformations, and categories were defined in order to define functors, just the opposite of the order in which they are introduced now.
A category is a collection of objects and arrows between objects. Usually these “arrows” are functions, but in general they don’t have to be.
A functor maps a category to another category. Since a category consists of objects and arrows, a functor maps objects to objects and arrows to arrows.
A natural transformation maps functors to functors. Sounds reasonable, but what does that mean?
You can think of a functor as a way to create a picture of one category inside another. Suppose you have some category and pick out two objects in that category, A and B, and suppose there is an arrow f between A and B. Then a functor F would take A and B and give you objects FA and FB in another category, and an arrow Ff between FA and FB. You could do the same with another functor G. So the objects A and B and the arrow between them in the first category have counterparts under the functors F and G in the new category as in the two diagrams below.
A natural transformation α between F and G is something that connects these two diagrams into one diagram that commutes.
The natural transformation α is a collection of arrows in the new category, one for every object in the original category. So we have an arrow αA for the object A and another arrow αB for the object B. These arrows are called the components of α at A and B respectively.
Note that the components of α depend on the objects A and B but not on the arrow f. If f represents any other arrow from A to B in the original category, the same arrows αA and αB fill in the diagram.
Natural transformations are meant to capture the idea that a transformation is “natural” in the sense of not depending on any arbitrary choices. If a transformation does depend on arbitrary choices, the arrows αA and αB would not be reusable but would have to change when f changes.
The next post will discuss the canonical examples of natural and unnatural transformations.
The following quote gives a good description of the value of abstract mathematics. The quote speaks specifically of “universal algebra,” but consistent with the spirit of the quote you could generalize it to other areas of mathematics, especially areas such as category theory.
Universal algebra is the study of features common to familiar algebraic systems … [It] places the algebraic notions in their proper setting; it often reveals connexions between seemingly different concepts and helps to systemize one’s thoughts. … [T]his approach does not usually solve the whole problem for us, but only tidies up a mass of rather trivial detail, allowing us to concentrate our powers on the hard core of the problem.
Emphasis added. Source: Universal Algebra by P. M. Cohn
Related: Applied category theory
