Disjoint union of sets

The dis­joint union of two sets is just the union, but with the ad­di­tional in­for­ma­tion that the two sets also don’t have any el­e­ments in com­mon. That is, we can use the phrase “dis­joint union” to in­di­cate that we’ve taken the union of two sets which have empty in­ter­sec­tion. The phrase can also be used to in­di­cate a very slightly differ­ent op­er­a­tion: “do some­thing to the el­e­ments of each set to make sure they don’t over­lap, and then take the union”.

Defi­ni­tion of the dis­joint union

“Disjoint union” can mean one of two things:

  • The sim­ple union, to­gether with the as­ser­tion that the two sets don’t over­lap;

  • The op­er­a­tion “do some­thing to the el­e­ments of each set to make sure they don’t over­lap, and then take the union”.

(Math­e­mat­i­ci­ans usu­ally let con­text de­cide which of these mean­ings is in­tended.)

The dis­joint union has the sym­bol \(\sqcup\): so the dis­joint union of sets \(A\) and \(B\) is \(A \sqcup B\).

The first definition

Let’s look at \(A = \{6,7\}\) and \(B = \{8, 9\}\). Th­ese two sets don’t over­lap: no el­e­ment of \(A\) is in \(B\), and no el­e­ment of \(B\) is in \(A\). So we can an­nounce that the union of \(A\) and \(B\) (that is, the set \(\{6,7,8,9\}\)) is in fact a dis­joint union.

In this in­stance, writ­ing \(A \sqcup B = \{6,7,8,9\}\) is just giv­ing the reader an ex­tra lit­tle hint that \(A\) and \(B\) are dis­joint; I could just have writ­ten \(A \cup B\), and the for­mal mean­ing would be the same. For the pur­poses of the first defi­ni­tion, think of \(\sqcup\) as \(\cup\) but with a foot­note read­ing “And, more­over, the union is dis­joint”.

As a non-ex­am­ple, we could not le­gi­t­i­mately write \(\{1,2\} \sqcup \{1,3\} = \{1,2,3\}\), even though \(\{1,2\} \cup \{1,3\} = \{1,2,3\}\); this is be­cause \(1\) is in both of the sets we are union­ing.

The sec­ond definition

This is the more in­ter­est­ing defi­ni­tion, and it re­quires some flesh­ing out.

Let’s think about \(A = \{6,7\}\) and \(B = \{6,8\}\) (so the two sets over­lap). We want to mas­sage these two sets so that they be­come dis­joint, but are some­how “still recog­nis­ably \(A\) and \(B\)”.

There’s a clever lit­tle trick we can do. We tag ev­ery mem­ber of \(A\) with a lit­tle note say­ing “I’m in \(A\)”, and ev­ery mem­ber of \(B\) with a note say­ing “I’m in \(B\)”. To turn this into some­thing that fits into set the­ory, we tag an el­e­ment \(a\) of \(A\) by putting it in an or­dered pair with the num­ber \(1\): \((a, 1)\) is ”\(a\) with its tag”. Then our mas­saged ver­sion of \(A\) is the set \(A'\) con­sist­ing of all the el­e­ments of \(A\), but where we tag them first:

$$A' = \{ (a, 1) : a \in A \}$$

Now, to tag the el­e­ments of \(B\) in the same way, we should avoid us­ing the tag \(1\) be­cause that means “I’m in \(A\)”; so we will use the num­ber \(2\) in­stead. Our mas­saged ver­sion of \(B\) is the set \(B'\) con­sist­ing of all the el­e­ments of \(B\), but we tag them first as well:

$$B' = \{ (b,2) : b \in B \}$$

No­tice that \(A\) bi­jects with \(A'\) noteIn­deed, a bi­jec­tion from \(A\) to \(A'\) is the map \(a \mapsto (a,1)\)., and \(B\) bi­jects with \(B'\), so we’ve got two sets which are “recog­nis­ably \(A\) and \(B\)”.

But mag­i­cally \(A'\) and \(B'\) are dis­joint, be­cause ev­ery­thing in \(A'\) is a tu­ple with sec­ond el­e­ment equal to \(1\), while ev­ery­thing in \(B'\) is a tu­ple with sec­ond el­e­ment equal to \(2\).

We define the dis­joint union of \(A\) and \(B\) to be \(A' \sqcup B'\) (where \(\sqcup\) now means the first defi­ni­tion: the or­di­nary union but where we have the ex­tra in­for­ma­tion that the two sets are dis­joint). That is, “make the sets \(A\) and \(B\) dis­joint, and then take their union”.

Examples

\(A = \{6,7\}\), \(B=\{6,8\}\)

Take a spe­cific ex­am­ple where \(A = \{6,7\}\) and \(B=\{6,8\}\). In this case, it only makes sense to use \(\sqcup\) in the sec­ond sense, be­cause \(A\) and \(B\) over­lap (they both con­tain the el­e­ment \(6\)).

Then \(A' = \{ (6, 1), (7, 1) \}\) and \(B' = \{ (6, 2), (8, 2) \}\), and the dis­joint union is

$$A \sqcup B = \{ (6,1), (7,1), (6,2), (8,2) \}$$

No­tice that \(A \cup B = \{ 6, 7, 8 \}\) has only three el­e­ments, be­cause \(6\) is in both \(A\) and \(B\) and that in­for­ma­tion has been lost on tak­ing the union. On the other hand, the dis­joint union \(A \sqcup B\) has the re­quired four el­e­ments be­cause we’ve re­tained the in­for­ma­tion that the two \(6\)’s are “differ­ent”: they ap­pear as \((6,1)\) and \((6,2)\) re­spec­tively.

\(A = \{1,2\}\), \(B = \{3,4\}\)

In this ex­am­ple, the no­ta­tion \(A \sqcup B\) is slightly am­bigu­ous, since \(A\) and \(B\) are dis­joint already. Depend­ing on con­text, it could ei­ther mean \(A \cup B = \{1,2,3,4\}\), or it could mean \(A' \cup B' = \{(1,1), (2,1), (3,2), (4,2) \}\) (where \(A' = \{(1,1), (2,1)\}\) and \(B' = \{(3,2), (4,2) \}\)). It will usu­ally be clear which of the two senses is meant; the former is more com­mon in ev­ery­day maths, while the lat­ter is usu­ally in­tended in set the­ory.

Exercise

What hap­pens if \(A = B = \{6,7\}\)?

Only the sec­ond defi­ni­tion makes sense.

Then \(A' = \{(6,1), (7,1)\}\) and \(B' = \{(6,2), (7,2)\}\), so

$$A \sqcup B = \{(6,1),(7,1),(6,2),(7,2)\}$$
which has four el­e­ments.<div><div>

\(A = \mathbb{N}\), \(B = \{ 1, 2, x \}\)

Let \(A\) be the set \(\mathbb{N}\) of nat­u­ral num­bers in­clud­ing \(0\), and let \(B\) be the set \(\{1,2,x\}\) con­tain­ing two nat­u­ral num­bers and one sym­bol \(x\) which is not a nat­u­ral num­ber.

Then \(A \sqcup B\) only makes sense un­der the sec­ond defi­ni­tion; it is the union of \(A' = \{ (0,1), (1,1), (2,1), (3,1), \dots\}\) and \(B' = \{(1,2), (2,2), (x,2)\}\), or

$$\{(0,1), (1,1),(2,1),(3,1), \dots, (1,2),(2,2),(x,2)\}$$

\(A = \mathbb{N}\), \(B = \{x, y\}\)

In this case, again the no­ta­tion \(A \sqcup B\) is am­bigu­ous; it could mean \(\{ 0,1,2,\dots, x, y \}\), or it could mean \(\{(0,1), (1,1), (2,1), \dots, (x,2), (y,2)\}\).

Mul­ti­ple operands

We can gen­er­al­ise the dis­joint union so that we can write \(A \sqcup B \sqcup C\) in­stead of just \(A \sqcup B\).

To use the first defi­ni­tion, the gen­er­al­i­sa­tion is easy to for­mu­late: it’s just \(A \cup B \cup C\), but with the ex­tra in­for­ma­tion that \(A\), \(B\) and \(C\) are pair­wise dis­joint (so there is noth­ing in any of their in­ter­sec­tions: \(A\) and \(B\) are dis­joint, \(B\) and \(C\) are dis­joint, and \(A\) and \(C\) are dis­join).

To use the sec­ond defi­ni­tion, we just tag each set again: let \(A' = \{(a, 1) : a \in A \}\), \(B' = \{ (b, 2) : b \in B \}\), and \(C' = \{ (c, 3) : c \in C \}\). Then \(A \sqcup B \sqcup C\) is defined to be \(A' \cup B' \cup C'\).

In­finite unions

In fact, both defi­ni­tions gen­er­al­ise even fur­ther, to unions over ar­bi­trary sets. In­deed, in the first sense we can define

$$\bigsqcup_{i \in I} A_i = \bigcup_{i \in I} A_i$$
to­gether with the in­for­ma­tion that no pair of \(A_i\) in­ter­sect.

In the sec­ond sense, we can define

$$\bigsqcup_{i \in I} A_i = \bigcup_{i \in I} A'_i$$
where \(A'_i = \{ (a, i) : a \in A_i \}\).

For ex­am­ple,

$$\bigsqcup_{n \in \mathbb{N}} \{0, 1,2,\dots,n\} = \{(0,0)\} \cup \{(0,1), (1,1) \} \cup \{ (0,2), (1,2), (2,2)\} \cup \dots = \{ (n, m) : n \leq m \}$$

Why are there two defi­ni­tions?

The first defi­ni­tion is ba­si­cally just a no­ta­tional con­ve­nience: it saves a few words when say­ing “… and more­over the sets are pair­wise dis­joint”.

The real meat of the idea is the sec­ond defi­ni­tion, which pro­vides a way of forc­ing the sets to be dis­joint. It’s not nec­es­sar­ily the only way we could co­her­ently define a dis­joint union (since there’s more than one way we could have tagged the sets; if noth­ing else, \(A \sqcup B\) could be defined the other way round, as \(A' \cup B'\) where \(A' = \{ (a, 2) : a \in A \}\) and \(B' = \{ (b,1) : b \in B \}\), swap­ping the tags). But it’s the one we use by con­ven­tion. Usu­ally when we’re us­ing the sec­ond defi­ni­tion we don’t much care ex­actly how we force the sets to be dis­joint; we only care that there is such a way. (For com­par­i­son, there is more than one way to define the or­dered pair in the ZF set the­ory, but we al­most never care re­ally which ex­act defi­ni­tion we use; only that there is a defi­ni­tion that has the prop­er­ties we want from it.)

Children:

Parents:

  • Set

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