# 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$$).

## $$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.