Universal property of the product

product_universal_property.json

https://arbital.com/p/product_universal_property

by Patrick Stevens Aug 25 2016 updated Oct 7 2016

The product can be defined in a very general way, applicable to the natural numbers, to sets, to algebraic structures, and so on.

[summary: We can define the general notion of "product" to coincide with the product of natural numbers and with the Set product, by means of a Universal property that the product has. Specifically, the product of objects $~$A$~$ and $~$B$~$ is an object denoted $~$A \times B$~$ together with maps $~$\pi_A : A \times B \to A$~$ and $~$\pi_B: A \times B \to B$~$, such that for every object $~$X$~$ and every pair of maps $~$f_A: X \to A$~$ and $~$f_B: X \to B$~$, there is a unique map $~$\gamma: X \to A \times B$~$ such that $~$\pi_A \circ \gamma = f_A$~$ and $~$\pi_B \circ \gamma = f_B$~$.]

[summary(Technical): The product of objects $~$A$~$ and $~$B$~$ is a certain tuple $~$(P, \pi_A, \pi_B)$~$, where $~$\pi_A$~$ is an arrow $~$P \to A$~$ and $~$\pi_B$~$ is an arrow $~$P \to B$~$. We require the product to satisfy the following Universal property: for every object $~$X$~$ and every pair of arrows $~$f: X \to A, g: X \to B$~$, there must be a unique factorisation $~$\gamma: X \to P$~$ satisfying $~$\pi_A \gamma = f$~$ and $~$\pi_B \gamma = g$~$.]

Just as we can define the Empty set by means of a Universal property (like this, in fact), so we can define the general notion of a "product" by referring not to what is in the product, but instead to how the product interacts with other objects.

Motivation

The motivating example here is the product of two sets.

Remember, the product of two sets $~$A$~$ and $~$B$~$ consists of all ordered pairs, the first element from $~$A$~$ and the second element from $~$B$~$. Category theory likes to think about maps involving an object rather than elements of an object, though, so we'd like a way of thinking about the product using only maps.

What maps can we find? Well, there's an easy way to produce an element of $~$A$~$ given an element of $~$A \times B$~$: namely, "take the first coordinate". Concretely, if we are given $~$(a,b) \in A \times B$~$, we output $~$a$~$. And similarly, we can take the second coordinate to get an element of $~$B$~$.

So we have two maps, one which we will denote $~$\pi_A: A \times B \to A$~$, and one denoted $~$\pi_B : A \times B \to B$~$. %%note: We use the Greek letter $~$\pi$~$ to stand for the word "[projection_map projection]", because the operation "take a coordinate" is often called "projection".%%

Now, this is certainly not enough to characterise the product. For one thing, there is a map from the Empty set to every other set (proof), so if all we knew about the product was that it had a map to $~$A$~$ and a map to $~$B$~$, then we might deduce that the empty set was a perfectly good product of $~$A$~$ and $~$B$~$. That's definitely not something we want our definition of "product" to mean: that the empty set is the product of every pair of sets! So we're going to have to find something else to add to our putative definition.

What else do we know about the product? To try for a universal property, we're going to want to talk about all the maps involving the product. It turns out that the correct fact to note is that a map $~$f$~$ from any set $~$X$~$ to $~$A \times B$~$ may be defined exactly by the first coordinate and the second coordinate of the result. Concretely, if we know $~$\pi_A(f(x))$~$ and $~$\pi_B(f(x))$~$, then we know $~$f(x)$~$: it's just $~$\langle \pi_A(f(x)), \pi_B(f(x)) \rangle$~$. %%note: I've used $~$\langle \text{angled brackets}\rangle$~$ to indicate the ordered pair here, just because otherwise there are confusingly many round brackets.%%

Another way of stating the universal property of the product is that maps $~$h : A \to B \times C$~$ are naturally in bijection with pairs of maps $~$f : A \to B$~$, $~$g : A \to C$~$. That is, a generalized element (of shape $~$A$~$) of $~$B \times C$~$ is a pair consisting of a generalized element (of the same shape) of $~$B$~$ and a generalized element of $~$C$~$; this is the same as the usual description of the product in sets, but now since we use generalized elements instead of elements it makes sense in any category. Under this correspondence, $~$h$~$ being the identity on $~$B \times C$~$ corresponds to $~$f$~$ being the projection $~$B \times C \to B$~$ and $~$g$~$ being the projection $~$B \times C \to C$~$. On the other hand, if $~$h$~$ corresponds to $~$f$~$ and $~$g$~$ via this bijection, we have $~$h = \langle f, g\rangle$~$. Naturality of the isomorphism turns out to imply that $~$\pi_{B} \langle f, g \rangle = f$~$ and $~$\pi_C \langle f, g \rangle = g$~$, as well as $~$\langle \pi_{B}, \pi_{C} \rangle = \text{id}$~$.

[todo: I think this is pretty good motivation, but it's at the cost of introducing the other version of the universal property. There's a general yoga of going between a universal property as in "representing or corepresenting a functor" and a universal property as in "being an initial or terminal object in some category", but I don't know where is a good place to discuss that.]

The universal property

From the above, we can extract the following universal property, which really does define the product (up to Isomorphism):

Given objects $~$A$~$ and $~$B$~$, we define the product to be the following collection of three objects, if it exists: $$~$A \times B \\ \pi_A: A \times B \to A \\ \pi_B : A \times B \to B$~$$ with the requirement that for every object $~$X$~$ and every pair of maps $~$f_A: X \to A, f_B: X \to B$~$, there is a unique map $~$f: X \to A \times B$~$ such that $~$\pi_A \circ f = f_A$~$ and $~$\pi_B \circ f = f_B$~$.

If you're anything like me, you're probably a bit lost at this point. Trust me that once you've set up the right structures in your mind, the property is quite simple. At the moment it probably feels more like I've given you a sentence in Swahili, and I've just told you it doesn't mean anything difficult.

Category theory contains lots of things like this, where it takes a lot of words to write them out and some time to get your head around them properly. %%note: In this particular instance, one unavoidable annoyance is that the object $~$X$~$ isn't really playing any interesting role other than "domain of an arbitrary function", but we have to include the words "for every object $~$X$~$" because otherwise the definitions of $~$f_A$~$ and $~$f_B$~$ don't make sense. %% One learns category theory by gradually getting used to examples and pictures; in particular, the idea of the commutative diagram is an extremely powerful tool for improving understanding.

The following "commutative diagram" (really just a picture showing the objects involved and how they interact) defines the product.

Product universal property

The dashed arrow indicates "the presence of all the other arrows forces this arrow to exist uniquely"; and the diagram is said to commute, which means that if we follow any chain of arrows round the diagram, we'll get the same answer. Here, "the diagram commutes" %%note: That is, "the diagram is a commutative diagram".%% is exactly expressing $~$\pi_A \circ f = f_A$~$ (following one of the triangles round) and $~$\pi_B \circ f = f_B$~$ (following the other triangle). And the dashed-ness of the line is exactly expressing the words "there is a unique map $~$f: X \to A \times B$~$".

We'll see several examples now, some related to each other and some not. Hopefully in working through these, you will pick up what the property means; and maybe you will start to get a feel for some underlying intuitions.

Example: finite sets

(This discussion works just as well in the category of all sets, not just the finite ones, but finite sets are much easier to understand than general sets.)

The motivation above took some properties of the set-product, and turned them into a new general definition. So we should hope that when we take the new general definition and bring it back into the world of sets, we recover the original set-product we started with. That is indeed the case.

Let $~$A$~$ and $~$B$~$ be finite sets; we want to see what $~$A \otimes B$~$ %%note: Because $~$\times$~$ already has a meaning in set theory, we'll use $~$\otimes$~$ to distinguish this new concept. Of course, the aim of this section is to show that $~$\otimes$~$ is actually the same as our usual $~$\times$~$. %% is (using the universal-property definition), if it exists.

Well, it would be the finite set $~$A \otimes B$~$ (whatever that might be), together with two maps $~$\pi_A: A \otimes B \to A$~$ and $~$\pi_B: A \otimes B \to B$~$, such that:

For every finite set $~$X$~$ and every pair of maps $~$f_A: X \to A, f_B: X \to B$~$, there is a unique map $~$f: X \to A \otimes B$~$ such that $~$\pi_A \circ f = f_A$~$ and $~$\pi_B \circ f = f_B$~$.

Let's try and identify what set this universal property describes %%note: If such a set exists. (Spoiler: it does.)%%. The property is very general, talking about the entire "universe" of finite sets, so to get a grasp of it, it should help to specialise to some simple sets $~$X$~$.

You might like to work out for yourself why letting $~$X = \emptyset$~$ doesn't tell us anything about $~$A \otimes B$~$.

But a much more enlightening choice of $~$X$~$ arises if we take $~$X = \{ 1 \}$~$. In that case, a map from $~$X$~$ to $~$A$~$ is just identifying a specific element of $~$A$~$, so for example we may refer to $~$f_A: X \to A$~$ as a "choice of element of $~$A$~$". Indeed, if $~$g: \{1\} \to A$~$, then we have an element $~$g(1)$~$ in $~$A$~$, because there's no choice about which element of the domain we use: there's only the element $~$1$~$, so the only possible output of $~$g$~$ is the element $~$g(1)$~$ of $~$A$~$.

Specialising to this instance of $~$X$~$, then, the universal property requires that:

For every pair of choices of element, $~$f_A: \{ 1 \} \to A$~$ and $~$f_B : \{ 1 \} \to B$~$, there is a unique choice of element $~$f: \{1\} \to A \otimes B$~$ such that $~$\pi_A \circ f = f_A$~$ and $~$\pi_B \circ f = f_B$~$.

(What does it mean to compose a function with a choice of element? Well, $~$\pi_A \circ f$~$ is a function from $~$\{1\}$~$ to $~$A$~$, so it's also just a choice of element of $~$A$~$; it's basically just $~$\pi_A$~$ applied to the choice-of-element embodied by $~$f$~$.)

More familiarly stated:

For every pair of elements $~$a \in A$~$ and $~$b \in B$~$, there is a unique element $~$x \in A \otimes B$~$ such that $~$\pi_A(x) = a$~$ and $~$\pi_B(x) = b$~$.

That's just saying "$~$A \otimes B$~$ consists of objects which $~$\pi_A$~$ and $~$\pi_B$~$ allow us to interpret as ordered pairs"! Specifically, it's saying that for every ordered pair of objects in $~$A \times B$~$, we can find a unique element of $~$A \otimes B$~$ which gets interpreted by $~$\pi_A$~$ and $~$\pi_B$~$ as having the same components as that ordered pair.

Example: natural numbers

To give you an idea of where we're aiming for, in this section, we're going to use the fact that a Partially ordered set may be viewed as a category, by letting there be a single arrow $~$a \to b$~$ if and only if $~$a \leq b$~$ in the poset. That is, instead of maps $~$f: A \to B$~$, we have "facts that $~$A \leq B$~$ in the poset" which we interpret as "arrows from $~$A$~$ to $~$B$~$"; there is only ever at most one fact that $~$A \leq B$~$, so there is only ever at most one arrow from $~$A$~$ to $~$B$~$.

We'll examine what the category-theoretic product means in this category, and hopefully this should help indicate how versatile the "universal property" idea is.

Specific poset: "less than"

Let us work in a specific poset: $~$\mathbb{N}$~$ the natural numbers, ordered by the usual "less than". For example, $~$1$~$ is less than or equal to every number except $~$0$~$, so there is an arrow from $~$1$~$ to every number except $~$0$~$. There is an arrow from $~$2$~$ to every number bigger than or equal to $~$2$~$, and so on. There is an arrow from $~$0$~$ to every number.

The universal property of the category-theoretic product %%note: I'll emphasise "category-theoretic" in this section, because it will turn out that in this context, "product" doesn't mean "usual product of natural numbers".%% here is:

Given natural numbers $~$m$~$ and $~$n$~$, we define the category-theoretic product $~$\otimes$~$ %%note: Because $~$\times$~$ already has a meaning in the naturals, we'll use $~$\otimes$~$ to distinguish this new concept.%% to be the following collection of three objects, if it exists:

We also have the requirement that for every natural number $~$x$~$ and every instance of the fact that $~$x \leq m, x \leq n$~$ %%note: Such an instance corresponds to the pair of maps $~$f_A: X \to A$~$ and $~$f_B: X \to B$~$.%%, there is a unique instance of the fact that $~$x \leq m \otimes n$~$. %%note: This corresponds to the map $~$f: X \to A \times B$~$. In fact we can omit "unique", because in a poset, there is never more than one arrow between any two given objects; in this context, there is only one way to express $~$x \leq m \otimes n$~$.%%

You might want to spend a little time convincing yourself that the requirement in the posets case is the same as the requirement in the general category-theoretic case. Indeed, we can omit the "compositions" part entirely. For example, half of the compositions part reads "$~$\pi_A \circ f = f_A$~$"; when translated into poset language, that is "the instance of the fact that $~$m \otimes n \leq m$~$, together with the instance of the fact that $~$x \leq m \otimes n$~$, yields the instance of the fact that $~$x \leq m$~$". But this is immediate anyway because posets already let us deduce that $~$A \leq C$~$ from $~$A \leq B$~$ and $~$B \leq C$~$.

To summarise, then, we define $~$m \otimes n$~$, if it exists, to be the natural number which is less than or equal to $~$m$~$ and to $~$n$~$, such that for every natural $~$x$~$ with $~$x \leq m, x \leq n$~$, we have $~$x \leq m \otimes n$~$.

If you think about this for a few minutes, you might work out that this is just referring to the minimum of $~$m$~$ and $~$n$~$. So we have defined the minimum of two natural numbers in a category-theoretic "universal properties" way: it's the category-theoretic product in this particular poset.

Notice, by the way, that in this case, the category-theoretic product (i.e. the minimum) does always exist. Remember, the universal property comes with a caveat: it defines the product to be a certain triple of $~$(A \times B, \pi_A, \pi_B)$~$, if those three things exist. It's by no means a given that the triple always does exist; but in this particular instance, with the natural numbers under the "less than" relation, it so happens that it does always exist. For every pair $~$m, n$~$ of naturals, there is a triple $~$(m \otimes n, \pi_m, \pi_n)$~$ satisfying the universal property: namely, letting $~$m \otimes n$~$ be the minimum of $~$m$~$ and $~$n$~$, and letting $~$\pi_m$~$ and $~$\pi_n$~$ be "instances of the facts that $~$m \otimes n \leq m$~$ and $~$m \otimes n \leq n$~$" respectively.

Specific example: divisibility

Let's now use the poset which is given by the nonzero naturals $~$\mathbb{N}^{\geq 1}$~$ but using the order relation of divisibility: $~$a \mid b$~$ if and only if $~$a$~$ divides $~$b$~$. For example, $~$1$~$ divides every nonzero natural so there is an arrow $~$1 \to n$~$ for every $~$n$~$; there are arrows $~$2 \to n$~$ for every even positive natural $~$n$~$, and so on.

We'll give the product definition again:

Given natural numbers $~$m$~$ and $~$n$~$, we define the category-theoretic product $~$\otimes$~$ to be the following collection of three objects, if it exists:

We also have the requirement that for every natural number $~$x$~$ such that $~$x \mid m, x \mid n$~$, it is the case that $~$x \mid m \otimes n$~$.

Again, a few minutes of pondering might lead you to discover that this is referring to the Greatest common divisor, and again it so happens that it always exists.

Moral things to notice about the above examples

Working in a poset, the nature of the category-theoretic product as some kind of "optimiser" is a bit clearer. It is the "optimal" object such that certain conditions hold.

In fact this is true in general posets: the category-theoretic product of $~$X$~$ and $~$Y$~$ in a poset is the [-greatest_lower_bound] of $~$X$~$ and $~$Y$~$ in the poset.

The property characterises the product up to isomorphism

This is what makes our new definition really make sense: this theorem tells us that our construction really does pick out a specific object. The proof appears on a different page; it follows a similar pattern to the "maps" way of proving that the empty set is uniquely characterised by its universal property.

If we can show that some easy-to-specify property (such as the universal property of the product) characterises things uniquely or up to isomorphism, we can be pretty hopeful that the property is worth thinking more about. While the product's universal property is wordy, it has a simple diagram which defines it; the property itself is not very complicated, and the main difficulty is in understanding the background.

Why is the product interesting?

Why should we care about having this object defined by the universal property? Well, if we stop defining things by their internal properties (for instance, if we stop defining the product of sets $~$A$~$ and $~$B$~$ as the collection of ordered pairs) and use a universal property instead, we get a definition which doesn't care about internal properties. It's immediately applicable to other situations. If we make sure that, in proving things about the product, we only use the universal property (or things that can be derived from the universal property), we'll instantly get theorems that are true not just for set-products but also for more general situations. Category theory, and its beginnings in the idea of the universal property, is in some ways the art of finding where in mathematics we're just doing the same things in a slightly different way, and seeing if we can show why they're actually the same rather than merely looking similar.

Ultimately, this viewpoint shows us that the following ideas are "basically the same" (and it doesn't matter if you don't know what some of these mean):

I personally took algebraic geometry and didn't understand a word of it, including about the Segre embedding. The lecturer didn't tell me at the time that the Segre embedding is a product, so I just went on thinking it was incomprehensible. But now I know that the Segre embedding is "just" a product. That immediately tells me that in some deep moral sense it's "not too difficult": even though algebraic geometry is fiendishly hard, the Segre embedding is not at its heart one of the really difficult bits, and if I chose to learn it properly, I wouldn't need to do too much mental gymnastics to understand it.