Universal property of the disjoint union

Where could we start if we were looking for a nice “easy” universal property describing the union of sets?

The first thing to notice is that universal properties only identify objects up to isomorphism, but there’s a sense in which the union is not well-defined up to isomorphism: it is possible to find sets \(A\) and \(B\), and sets \(A'\) and \(B'\), with \(A\) isomorphic to \(A'\) and \(B\) isomorphic to \(B'\), but where \(A \cup B\) is not isomorphic to \(A' \cup B'\). noteIn this case, when we’re talking about sets, an isomorphism is just a bijection.

Consider \(A = \{ 1 \}\) and \(B = \{ 1 \}\). Then the union \(A \cup B\) is equal to \(\{1\}\).

On the other hand, consider \(X = \{1\}\) and \(Y = \{2\}\). Then the union \(X \cup Y = \{1,2\}\).

So by replacing \(A\) with the isomorphic \(X\), and \(B\) with the isomorphic \(Y\), we have obtained \(\{1,2\}\) which is not isomorphic to \(\{1\} = A \cup B\). <div><div>

So it’s not obvious whether the union could even in principle be defined by a universal property.noteActually it is possible.

But we can make our job easier by taking the next best thing: the disjoint union \(A \sqcup B\), which is well-defined up to isomorphism in the above sense: the definition of \(A \sqcup B\) is constructed so that even if \(A\) and \(B\) overlap, the intersection still doesn’t get treated any differently.

Before reading this, you should make sure you grasp the disjoint union of sets well enough to know the difference between the two sets \(\{ 2, 3, 5 \} \cup \{ 2, 6, 7 \}\) and \(\{ 2, 3, 5 \} \sqcup \{ 2, 6, 7 \}\).

Given sets \(A\) and \(B\), we define their disjoint union to be \(A \sqcup B = A' \cup B'\), where \(A' = \{ (a, 1) : a \in A \}\) and \(B' = \{ (b, 2) : b \in B \}\). That is, “tag each element of \(A\) with the label \(1\), and tag each element of \(B\) with the label \(2\); then take the union of the tagged sets”.

The important fact about the disjoint union here is that if \(A \cong A'\) and \(B \cong B'\), then \(A \sqcup B \cong A' \sqcup B'\). This is the fact that makes the disjoint union a fairly accessible idea to bring under the umbrella of category theory, and it also means we are justified in using a convention that simplifies a lot of the notation: we will assume from now on that \(A\) and \(B\) are disjoint. (Since we only care about them up to isomorphism, this is fine to do: we can replace \(A\) and \(B\) with some disjoint pair of sets of the same size if necessary, to ensure that they are disjoint.)

Universal property of disjoint union

How can we look at the disjoint union solely in terms of the maps to and from it? First of all, how can we look at the disjoint union at all in terms of those maps?

There are certainly two maps \(A \to A \sqcup B\) and \(B \to A \sqcup B\): namely, the inclusions \(i_A : a \mapsto a\) and \(i_B : b \mapsto b\). But that’s not enough to pin down the disjoint union precisely, because those maps exist not just to \(A \sqcup B\) but also to any superset of \(A \sqcup B\). noteIf this is not obvious, stop and think for a couple of minutes about the case \(A = \{ 1 \}\), \(B = \{ 2 \}\), \(A \sqcup B = \{1,2\}\), and the superset \(\{1,2,3\}\) of \(A \sqcup B\). So we need to find some way to limit ourselves to \(A \sqcup B\).

The key limiting fact about the disjoint union is that any map from the disjoint union can be expressed in terms of two other maps (one from \(A\) and one from \(B\)), and vice versa. The following discussion shows us how.

  • If we know \(f: A \sqcup B \to X\), then we know the restriction maps \(f \big|_A : A \to X\) noteThis is defined by \(f \big|_A (a) = f(a)\); that is, it is the function we obtain by “restricting” \(f\) so that its domain is \(A\) rather than the larger \(A \sqcup B\). and \(f \big|_B : B \to X\).

  • If we know two maps \(\alpha: A \to X\) and \(\beta: B \to X\), then we can uniquely construct a map \(f: A \sqcup B \to X\) which is “$\alpha$ and \(\beta\) glued together”. Formally, the map is defined as \(f(x) = \alpha(x)\) if \(x \in A\), and \(f(x) = \beta(x)\) if \(x \in B\).

The reason this pins down the disjoint union exactly (up to isomorphism) is because the disjoint union is the only set which leaves us with no choice about how we construct \(f\) from \(\alpha\) and \(\beta\):

  • We rule out strict subsets of \(A \sqcup B\) because we use the fact that every element of \(A\) is in \(A \sqcup B\) and every element of \(B\) is in \(A \sqcup B\), to ensure that the restriction maps make sense.

  • We rule out strict supersets of \(A \sqcup B\) because we use the fact that any element in \(A \sqcup B\) is either in \(A\) or it is in \(B\) noteIf we replaced \(A \sqcup B\) by any strict superset, this stops being true: by passing to a superset, we introduce an element which is neither in \(A\) nor in \(B\)., to ensure that \(f\) is defined everywhere on its domain. Moreover, we use the fact that every element of \(A \sqcup B\) is in exactly one of \(A\) or \(B\), because if \(x\) is in both \(A\) and \(B\), then we can’t generally decide whether we should define \(f(x)\) by \(\alpha(x)\) or \(\beta(x)\).

The property

One who is well-versed in category theory and universal properties would be able to take the above discussion and condense it into the following statement, which is the universal property of the disjoint union:

Given sets \(A\) and \(B\), we define the disjoint union to be the following collection of three objects: \($\text{A set labelled }\ A \sqcup B \\ i_A : A \to A \sqcup B \\ i_B : B \to A \sqcup B\)$ with the requirement that for every set \(X\) and every pair of maps \(f_A: A \to X\) and \(f_B: B \to X\), there is a unique map \(f: A \sqcup B \to X\) such that \(f \circ i_A = f_A\) and \(f \circ i_B = f_B\).

Imgur was down when I made this picture, so I’m hosting it instead.

Aside: relation to the product

Recall the universal property of the product:

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\).

Notice that this is just the same as the universal property of the disjoint union, but we have reversed the domain and codomain of every function, and we have correspondingly reversed any function compositions. This shows us that the product and the disjoint union are, in some sense, “two sides of the same coin”. If you remember the universal property of the empty set, we saw that the empty set’s universal property also had a “flip side”, and this flipped property characterises the one-element sets. So in the same sense, the empty set and the one-point sets are “two sides of the same coin”. This is an instance of the concept of duality, and it turns up all over the place.

Examples

{1} ⊔ {2}

Let’s think about the very first example that came from the top of the page: the disjoint union of \(A=\{1\}\) and \(B=\{2\}\). (This is, of course, \(\{1,2\}\), but we’ll try and tie the universal property point of view in with the elements point of view.)

The definition becomes:

The disjoint union of \(\{1\}\) and \(\{2\}\) is the following collection of three objects: \($\text{A set labelled } \{1\} \sqcup \{2\} \\ i_A : \{1\} \to \{1\} \sqcup \{2\} \\ i_B : \{2\} \to \{1\} \sqcup \{2\}\)$ with the requirement that for every set \(X\) and every pair of maps \(f_A: \{1\} \to X\) and \(f_B: \{2\} \to X\), there is a unique map \(f: A \sqcup B \to X\) such that \(f \circ i_A = f_A\) and \(f \circ i_B = f_B\).

This is still long and complicated, but remember from when we discussed the product that a map \(f_A: \{1\} \to X\) is precisely picking out a single element of \(X\): namely \(f_A(1)\). To every element of \(X\), there is exactly one such map; and for every map \(\{1\} \to X\), there is exactly one element of \(X\) it picks out. (Of course, the same reasoning goes through with \(B\) as well: \(f_B\) is just picking out an element of \(X\), too.)

Also, \(i_A\) and \(i_B\) are just picking out single elements of \(A \sqcup B\), though we are currently pretending that we don’t know what \(A \sqcup B\) is yet.

So we can rewrite this talk of maps in terms of elements, to make it easier for us to understand this definition in the specific case that \(A\) and \(B\) have just one element each:

The disjoint union of \(\{1\}\) and \(\{2\}\) is the following collection of three objects: \($\text{A set labelled }\ \{1\} \sqcup \{2\} \\ \text{An element } i_A \text{ of } \{1\} \sqcup \{2\} \\ \text{An element }i_B \text{ of } \{1\} \sqcup \{2\}\)$ with the requirement that for every set \(X\) and every pair of elements \(x \in X\) and \(y \in X\), there is a unique map \(f: A \sqcup B \to X\) such that \(f(i_A) = x\) and \(f(i_B) = y\).

From this, we can see that \(i_A\) and \(i_B\) can’t be the same, because \(f\) acts differently on them (if we take \(X = \{x,y\}\) where \(x \not = y\), for instance). But also if there were any \(z\) in \(\{1\} \sqcup \{2\}\) other than \(i_A\) and \(i_B\), then for any attempt at our unique \(f: A \sqcup B \to X\), we would be able to make a different \(f\) by just changing where \(z\) is sent to.

So \(A \sqcup B\) is precisely the set \(\{i_A, i_B\}\); and this has determined it up to isomorphism as “the set with two elements”.

Aside: cardinality

Notice that the disjoint union of “the set with one element” and “the set with one element” yields “the set with two elements”. It’s actually true for general finite sets that the disjoint union of “the set with \(m\) elements” with “the set with \(n\) elements” yields “the set with \(m+n\) elements”; a few minutes’ thought should be enough to convince you of this, but it is an excellent exercise for you to do this from the category-theoretic universal properties viewpoint as well as from the (much easier) elements viewpoint. We will touch on this connection between “disjoint union” and “addition” a bit more later.

The empty set

What is the disjoint union of the empty set with itself? (Of course, it’s just the empty set, but let’s pretend we don’t know that.) The advantage of this example is that we already know a lot about the universal property of the empty set, so it’s a good testing ground to see if we can do this without thinking about elements at all.

Recall that the empty set is defined as follows:

The empty set \(\emptyset\) is the unique set such that for every set \(X\), there is precisely one function \(\emptyset \to X\).

The disjoint union of \(\emptyset\) with itself would be defined as follows (where I’ve stuck to using \(A\) and \(B\) in certain places, because otherwise the whole thing just fills up with the \(\emptyset\) symbol):

The following collection of three objects: \($\text{A set labelled }\ A \sqcup B \\ i_A : \emptyset \to A \sqcup B \\ i_B : \emptyset \to A \sqcup B\)$ with the requirement that for every set \(X\) and every pair of maps \(f_A: \emptyset \to X\) and \(f_B: \emptyset \to X\), there is a unique map \(f: A \sqcup B \to X\) such that \(f \circ i_A = f_A\) and \(f \circ i_B = f_B\).

Now, since we know that for every set \(X\) there is a unique map \(!_X: \emptyset \to X\) noteIn general, the exclamation mark \(!\) is used for a uniquely-defined map., we can replace our talk of \(f_A\) and \(f_B\) by just the same \(!_X\):

The following collection of three objects: \($\text{A set labelled }\ A \sqcup B \\ i_A : \emptyset \to A \sqcup B \\ i_B : \emptyset \to A \sqcup B\)$ with the requirement that for every set \(X\), there is a unique map \(f: A \sqcup B \to X\) such that \(f \circ i_A = (!_{X})\) and \(f \circ i_B = (!_{X})\).

Moreover, we know that \(i_A\) and \(i_B\) are also uniquely defined, because there is only one map \(\emptyset \to A \sqcup B\) (no matter what \(A \sqcup B\) might end up being); so we can remove them from the definition because they’re forced to exist anyway. They’re both just \(!_{A \sqcup B}\).

The set \($A \sqcup B\)$ with the requirement that for every set \(X\), there is a unique map \(f: A \sqcup B \to X\) such that \(f \circ (!_{A \sqcup B}) = (!_X)\).

A diagram is in order.

The universal property is precisely saying that for every set \(X\), there is a unique map \(f: A \sqcup B \to X\) such that \(f \circ (!_{A \sqcup B})\) is the map \(!_X : \emptyset \to X\).

But since \(!_X\) is the only map from \(\emptyset \to X\), we have \(f \circ (!_{A \sqcup B}) = (!_X)\) whatever \(f\) is. Indeed, \(f \circ (!_{A \sqcup B})\) is a map from \(\emptyset \to X\), and \(!_X\) is the only such map. So we can drop that condition from the requirements, because it automatically holds!

Therefore the disjoint union is:

The set \($A \sqcup B\)$ with the requirement that for every set \(X\), there is a unique map \(f: A \sqcup B \to X\).

Do you recognise that definition? It’s just the universal property of the empty set!

So \(A \sqcup B\) is the empty set in this example.

More general concept

We saw earlier that the disjoint union is characterised by the “reverse” (or “dual”) of the universal property of the product. In a more general category, we say that something which satisfies this property is a coproduct. notePrepending “co” to something means “reverse the maps”.

In general, the coproduct of objects \(A\) and \(B\) is written not as \(A \sqcup B\) (which is specific to the category of sets), but as \(A + B\). Among other things, the coproduct unifies the ideas of addition of integers, least upper bounds in posets, disjoint union of sets, least common multiple of naturals, direct sum of vector spaces, and free product of groups; all of these are coproducts in their respective categories.

Parents:

  • Disjoint union of sets

    One of the most basic ways we have of joining two sets together.

  • Universal property

    A universal property is a way of defining an object based purely on how it interacts with other objects, rather than by any internal property of the object itself.