Universal property of the disjoint union

Where could we start if we were look­ing for a nice “easy” uni­ver­sal prop­erty de­scribing the union of sets?

The first thing to no­tice is that uni­ver­sal prop­er­ties only iden­tify ob­jects up to iso­mor­phism, but there’s a sense in which the union is not well-defined up to iso­mor­phism: it is pos­si­ble to find sets \(A\) and \(B\), and sets \(A'\) and \(B'\), with \(A\) iso­mor­phic to \(A'\) and \(B\) iso­mor­phic to \(B'\), but where \(A \cup B\) is not iso­mor­phic to \(A' \cup B'\). noteIn this case, when we’re talk­ing about sets, an iso­mor­phism is just a bi­jec­tion.

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

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

So by re­plac­ing \(A\) with the iso­mor­phic \(X\), and \(B\) with the iso­mor­phic \(Y\), we have ob­tained \(\{1,2\}\) which is not iso­mor­phic to \(\{1\} = A \cup B\). <div><div>

So it’s not ob­vi­ous whether the union could even in prin­ci­ple be defined by a uni­ver­sal prop­erty.noteAc­tu­ally it is pos­si­ble.

But we can make our job eas­ier by tak­ing the next best thing: the dis­joint union \(A \sqcup B\), which is well-defined up to iso­mor­phism in the above sense: the defi­ni­tion of \(A \sqcup B\) is con­structed so that even if \(A\) and \(B\) over­lap, the in­ter­sec­tion still doesn’t get treated any differ­ently.

Be­fore read­ing this, you should make sure you grasp the dis­joint union of sets well enough to know the differ­ence be­tween 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 dis­joint 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 el­e­ment of \(A\) with the la­bel \(1\), and tag each el­e­ment of \(B\) with the la­bel \(2\); then take the union of the tagged sets”.

The im­por­tant fact about the dis­joint 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 dis­joint union a fairly ac­cessible idea to bring un­der the um­brella of cat­e­gory the­ory, and it also means we are jus­tified in us­ing a con­ven­tion that sim­plifies a lot of the no­ta­tion: we will as­sume from now on that \(A\) and \(B\) are dis­joint. (Since we only care about them up to iso­mor­phism, this is fine to do: we can re­place \(A\) and \(B\) with some dis­joint pair of sets of the same size if nec­es­sary, to en­sure that they are dis­joint.)

Univer­sal prop­erty of dis­joint union

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

There are cer­tainly two maps \(A \to A \sqcup B\) and \(B \to A \sqcup B\): namely, the in­clu­sions \(i_A : a \mapsto a\) and \(i_B : b \mapsto b\). But that’s not enough to pin down the dis­joint union pre­cisely, be­cause those maps ex­ist not just to \(A \sqcup B\) but also to any su­per­set of \(A \sqcup B\). noteIf this is not ob­vi­ous, stop and think for a cou­ple of min­utes about the case \(A = \{ 1 \}\), \(B = \{ 2 \}\), \(A \sqcup B = \{1,2\}\), and the su­per­set \(\{1,2,3\}\) of \(A \sqcup B\). So we need to find some way to limit our­selves to \(A \sqcup B\).

The key limit­ing fact about the dis­joint union is that any map from the dis­joint union can be ex­pressed in terms of two other maps (one from \(A\) and one from \(B\)), and vice versa. The fol­low­ing dis­cus­sion shows us how.

  • If we know \(f: A \sqcup B \to X\), then we know the re­stric­tion maps \(f \big|_A : A \to X\) noteThis is defined by \(f \big|_A (a) = f(a)\); that is, it is the func­tion we ob­tain by “re­strict­ing” \(f\) so that its do­main 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 con­struct a map \(f: A \sqcup B \to X\) which is ”\(\alpha\) and \(\beta\) glued to­gether”. For­mally, the map is defined as \(f(x) = \alpha(x)\) if \(x \in A\), and \(f(x) = \beta(x)\) if \(x \in B\).

The rea­son this pins down the dis­joint union ex­actly (up to iso­mor­phism) is be­cause the dis­joint union is the only set which leaves us with no choice about how we con­struct \(f\) from \(\alpha\) and \(\beta\):

  • We rule out strict sub­sets of \(A \sqcup B\) be­cause we use the fact that ev­ery el­e­ment of \(A\) is in \(A \sqcup B\) and ev­ery el­e­ment of \(B\) is in \(A \sqcup B\), to en­sure that the re­stric­tion maps make sense.

  • We rule out strict su­per­sets of \(A \sqcup B\) be­cause we use the fact that any el­e­ment in \(A \sqcup B\) is ei­ther in \(A\) or it is in \(B\) noteIf we re­placed \(A \sqcup B\) by any strict su­per­set, this stops be­ing true: by pass­ing to a su­per­set, we in­tro­duce an el­e­ment which is nei­ther in \(A\) nor in \(B\)., to en­sure that \(f\) is defined ev­ery­where on its do­main. More­over, we use the fact that ev­ery el­e­ment of \(A \sqcup B\) is in ex­actly one of \(A\) or \(B\), be­cause if \(x\) is in both \(A\) and \(B\), then we can’t gen­er­ally de­cide whether we should define \(f(x)\) by \(\alpha(x)\) or \(\beta(x)\).

The property

One who is well-versed in cat­e­gory the­ory and uni­ver­sal prop­er­ties would be able to take the above dis­cus­sion and con­dense it into the fol­low­ing state­ment, which is the uni­ver­sal prop­erty of the dis­joint union:

Given sets \(A\) and \(B\), we define the dis­joint union to be the fol­low­ing col­lec­tion of three ob­jects:

$$\text{A set labelled }\ A \sqcup B \\ i_A : A \to A \sqcup B \\ i_B : B \to A \sqcup B$$
with the re­quire­ment that for ev­ery set \(X\) and ev­ery 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 pic­ture, so I’m host­ing it in­stead. Disjoint union universal property

Aside: re­la­tion to the product

Re­call the uni­ver­sal prop­erty of the product:

Given ob­jects \(A\) and \(B\), we define the product to be the fol­low­ing col­lec­tion of three ob­jects, if it ex­ists:

$$A \times B \\ \pi_A: A \times B \to A \\ \pi_B : A \times B \to B$$
with the re­quire­ment that for ev­ery ob­ject \(X\) and ev­ery 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\).

No­tice that this is just the same as the uni­ver­sal prop­erty of the dis­joint union, but we have re­versed the do­main and codomain of ev­ery func­tion, and we have cor­re­spond­ingly re­versed any func­tion com­po­si­tions. This shows us that the product and the dis­joint union are, in some sense, “two sides of the same coin”. If you re­mem­ber the uni­ver­sal prop­erty of the empty set, we saw that the empty set’s uni­ver­sal prop­erty also had a “flip side”, and this flipped prop­erty char­ac­ter­ises the one-el­e­ment sets. So in the same sense, the empty set and the one-point sets are “two sides of the same coin”. This is an in­stance of the con­cept of du­al­ity, and it turns up all over the place.

Examples

{1} ⊔ {2}

Let’s think about the very first ex­am­ple that came from the top of the page: the dis­joint union of \(A=\{1\}\) and \(B=\{2\}\). (This is, of course, \(\{1,2\}\), but we’ll try and tie the uni­ver­sal prop­erty point of view in with the el­e­ments point of view.)

The defi­ni­tion be­comes:

The dis­joint union of \(\{1\}\) and \(\{2\}\) is the fol­low­ing col­lec­tion of three ob­jects:

$$\text{A set labelled } \{1\} \sqcup \{2\} \\ i_A : \{1\} \to \{1\} \sqcup \{2\} \\ i_B : \{2\} \to \{1\} \sqcup \{2\}$$
with the re­quire­ment that for ev­ery set \(X\) and ev­ery 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 com­pli­cated, but re­mem­ber from when we dis­cussed the product that a map \(f_A: \{1\} \to X\) is pre­cisely pick­ing out a sin­gle el­e­ment of \(X\): namely \(f_A(1)\). To ev­ery el­e­ment of \(X\), there is ex­actly one such map; and for ev­ery map \(\{1\} \to X\), there is ex­actly one el­e­ment of \(X\) it picks out. (Of course, the same rea­son­ing goes through with \(B\) as well: \(f_B\) is just pick­ing out an el­e­ment of \(X\), too.)

Also, \(i_A\) and \(i_B\) are just pick­ing out sin­gle el­e­ments of \(A \sqcup B\), though we are cur­rently pre­tend­ing that we don’t know what \(A \sqcup B\) is yet.

So we can rewrite this talk of maps in terms of el­e­ments, to make it eas­ier for us to un­der­stand this defi­ni­tion in the spe­cific case that \(A\) and \(B\) have just one el­e­ment each:

The dis­joint union of \(\{1\}\) and \(\{2\}\) is the fol­low­ing col­lec­tion of three ob­jects:

$$\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 re­quire­ment that for ev­ery set \(X\) and ev­ery pair of el­e­ments \(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, be­cause \(f\) acts differ­ently on them (if we take \(X = \{x,y\}\) where \(x \not = y\), for in­stance). But also if there were any \(z\) in \(\{1\} \sqcup \{2\}\) other than \(i_A\) and \(i_B\), then for any at­tempt at our unique \(f: A \sqcup B \to X\), we would be able to make a differ­ent \(f\) by just chang­ing where \(z\) is sent to.

So \(A \sqcup B\) is pre­cisely the set \(\{i_A, i_B\}\); and this has de­ter­mined it up to iso­mor­phism as “the set with two el­e­ments”.

Aside: cardinality

No­tice that the dis­joint union of “the set with one el­e­ment” and “the set with one el­e­ment” yields “the set with two el­e­ments”. It’s ac­tu­ally true for gen­eral finite sets that the dis­joint union of “the set with \(m\) el­e­ments” with “the set with \(n\) el­e­ments” yields “the set with \(m+n\) el­e­ments”; a few min­utes’ thought should be enough to con­vince you of this, but it is an ex­cel­lent ex­er­cise for you to do this from the cat­e­gory-the­o­retic uni­ver­sal prop­er­ties view­point as well as from the (much eas­ier) el­e­ments view­point. We will touch on this con­nec­tion be­tween “dis­joint union” and “ad­di­tion” a bit more later.

The empty set

What is the dis­joint union of the empty set with it­self? (Of course, it’s just the empty set, but let’s pre­tend we don’t know that.) The ad­van­tage of this ex­am­ple is that we already know a lot about the uni­ver­sal prop­erty of the empty set, so it’s a good test­ing ground to see if we can do this with­out think­ing about el­e­ments at all.

Re­call that the empty set is defined as fol­lows:

The empty set \(\emptyset\) is the unique set such that for ev­ery set \(X\), there is pre­cisely one func­tion \(\emptyset \to X\).

The dis­joint union of \(\emptyset\) with it­self would be defined as fol­lows (where I’ve stuck to us­ing \(A\) and \(B\) in cer­tain places, be­cause oth­er­wise the whole thing just fills up with the \(\emptyset\) sym­bol):

The fol­low­ing col­lec­tion of three ob­jects:

$$\text{A set labelled }\ A \sqcup B \\ i_A : \emptyset \to A \sqcup B \\ i_B : \emptyset \to A \sqcup B$$
with the re­quire­ment that for ev­ery set \(X\) and ev­ery 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 ev­ery set \(X\) there is a unique map \(!_X: \emptyset \to X\) noteIn gen­eral, the ex­cla­ma­tion mark \(!\) is used for a uniquely-defined map., we can re­place our talk of \(f_A\) and \(f_B\) by just the same \(!_X\):

The fol­low­ing col­lec­tion of three ob­jects:

$$\text{A set labelled }\ A \sqcup B \\ i_A : \emptyset \to A \sqcup B \\ i_B : \emptyset \to A \sqcup B$$
with the re­quire­ment that for ev­ery 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})\).

More­over, we know that \(i_A\) and \(i_B\) are also uniquely defined, be­cause there is only one map \(\emptyset \to A \sqcup B\) (no mat­ter what \(A \sqcup B\) might end up be­ing); so we can re­move them from the defi­ni­tion be­cause they’re forced to ex­ist any­way. They’re both just \(!_{A \sqcup B}\).

The set

$$A \sqcup B$$
with the re­quire­ment that for ev­ery set \(X\), there is a unique map \(f: A \sqcup B \to X\) such that \(f \circ (!_{A \sqcup B}) = (!_X)\).

A di­a­gram is in or­der.

Universal property of the disjoint union of the empty set with itself

The uni­ver­sal prop­erty is pre­cisely say­ing that for ev­ery 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)\) what­ever \(f\) is. In­deed, \(f \circ (!_{A \sqcup B})\) is a map from \(\emptyset \to X\), and \(!_X\) is the only such map. So we can drop that con­di­tion from the re­quire­ments, be­cause it au­to­mat­i­cally holds!

There­fore the dis­joint union is:

The set

$$A \sqcup B$$
with the re­quire­ment that for ev­ery set \(X\), there is a unique map \(f: A \sqcup B \to X\).

Do you recog­nise that defi­ni­tion? It’s just the uni­ver­sal prop­erty of the empty set!

So \(A \sqcup B\) is the empty set in this ex­am­ple.

More gen­eral concept

We saw ear­lier that the dis­joint union is char­ac­ter­ised by the “re­verse” (or “dual”) of the uni­ver­sal prop­erty of the product. In a more gen­eral cat­e­gory, we say that some­thing which satis­fies this prop­erty is a co­product. notePrepend­ing “co” to some­thing means “re­verse the maps”.

In gen­eral, the co­product of ob­jects \(A\) and \(B\) is writ­ten not as \(A \sqcup B\) (which is spe­cific to the cat­e­gory of sets), but as \(A + B\). Among other things, the co­product unifies the ideas of ad­di­tion of in­te­gers, least up­per bounds in posets, dis­joint union of sets, least com­mon mul­ti­ple of nat­u­rals, di­rect sum of vec­tor spaces, and free product of groups; all of these are co­prod­ucts in their re­spec­tive cat­e­gories.

Parents:

  • Disjoint union of sets

    One of the most ba­sic ways we have of join­ing two sets to­gether.

    • Set

      An un­ordered col­lec­tion of dis­tinct ob­jects.

  • Universal property

    A uni­ver­sal prop­erty is a way of defin­ing an ob­ject based purely on how it in­ter­acts with other ob­jects, rather than by any in­ter­nal prop­erty of the ob­ject it­self.