# Disjoint union of sets

https://arbital.com/p/set_disjoint_union

by Patrick Stevens Aug 24 2016 updated Oct 23 2016

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

[summary: The disjoint union of two sets is just the union, but with the additional information that the two sets also don't have any elements in common. That is, we can use the phrase "disjoint union" to indicate that we've taken the union of two sets which have empty intersection. The phrase can also be used to indicate a very slightly different operation: "do something to the elements of each set to make sure they don't overlap, and then take the union".]

[summary(Technical): The phrase "disjoint union" is used to mean one of two slightly different operations on sets. It indicates either "just take the union, but also notice that we've been careful to ensure that the sets have empty intersection", or "perform a specific operation on each set to ensure that the resulting sets have empty intersection, and then take the union".]

The disjoint union of two sets is just the union, but with the additional information that the two sets also don't have any elements in common. That is, we can use the phrase "disjoint union" to indicate that we've taken the union of two sets which have empty intersection. The phrase can also be used to indicate a very slightly different operation: "do something to the elements of each set to make sure they don't overlap, and then take the union".

# Definition of the disjoint union

"Disjoint union" can mean one of two things:

• The simple union, together with the assertion that the two sets don't overlap;
• The operation "do something to the elements of each set to make sure they don't overlap, and then take the union".

(Mathematicians usually let context decide which of these meanings is intended.)

The disjoint union has the symbol $\sqcup$: so the disjoint union of sets $A$ and $B$ is $A \sqcup B$.

## The first definition

Let's look at $A = \{6,7\}$ and $B = \{8, 9\}$. These two sets don't overlap: no element of $A$ is in $B$, and no element of $B$ is in $A$. So we can announce that the union of $A$ and $B$ (that is, the set $\{6,7,8,9\}$) is in fact a disjoint union.

In this instance, writing $A \sqcup B = \{6,7,8,9\}$ is just giving the reader an extra little hint that $A$ and $B$ are disjoint; I could just have written $A \cup B$, and the formal meaning would be the same. For the purposes of the first definition, think of $\sqcup$ as $\cup$ but with a footnote reading "And, moreover, the union is disjoint".

As a non-example, we could not legitimately write $\{1,2\} \sqcup \{1,3\} = \{1,2,3\}$, even though $\{1,2\} \cup \{1,3\} = \{1,2,3\}$; this is because $1$ is in both of the sets we are unioning.

## The second definition

This is the more interesting definition, and it requires some fleshing out.

Let's think about $A = \{6,7\}$ and $B = \{6,8\}$ (so the two sets overlap). We want to massage these two sets so that they become disjoint, but are somehow "still recognisably $A$ and $B$".

There's a clever little trick we can do. We tag every member of $A$ with a little note saying "I'm in $A$", and every member of $B$ with a note saying "I'm in $B$". To turn this into something that fits into set theory, we tag an element $a$ of $A$ by putting it in an ordered pair with the number $1$: $(a, 1)$ is "$a$ with its tag". Then our massaged version of $A$ is the set $A'$ consisting of all the elements of $A$, but where we tag them first: $$A' = \{ (a, 1) : a \in A \}$$

Now, to tag the elements of $B$ in the same way, we should avoid using the tag $1$ because that means "I'm in $A$"; so we will use the number $2$ instead. Our massaged version of $B$ is the set $B'$ consisting of all the elements of $B$, but we tag them first as well: $$B' = \{ (b,2) : b \in B \}$$

Notice that $A$ bijects with $A'$ %%note: Indeed, a bijection from $A$ to $A'$ is the map $a \mapsto (a,1)$.%%, and $B$ bijects with $B'$, so we've got two sets which are "recognisably $A$ and $B$".

But magically $A'$ and $B'$ are disjoint, because everything in $A'$ is a tuple with second element equal to $1$, while everything in $B'$ is a tuple with second element equal to $2$.

We define the disjoint union of $A$ and $B$ to be $A' \sqcup B'$ (where $\sqcup$ now means the first definition: the ordinary union but where we have the extra information that the two sets are disjoint). That is, "make the sets $A$ and $B$ disjoint, and then take their union".

# Examples

## $A = \{6,7\}$, $B=\{6,8\}$

Take a specific example where $A = \{6,7\}$ and $B=\{6,8\}$. In this case, it only makes sense to use $\sqcup$ in the second sense, because $A$ and $B$ overlap (they both contain the element $6$).

Then $A' = \{ (6, 1), (7, 1) \}$ and $B' = \{ (6, 2), (8, 2) \}$, and the disjoint union is $$A \sqcup B = \{ (6,1), (7,1), (6,2), (8,2) \}$$

Notice that $A \cup B = \{ 6, 7, 8 \}$ has only three elements, because $6$ is in both $A$ and $B$ and that information has been lost on taking the union. On the other hand, the disjoint union $A \sqcup B$ has the required four elements because we've retained the information that the two $6$'s are "different": they appear as $(6,1)$ and $(6,2)$ respectively.

## $A = \{1,2\}$, $B = \{3,4\}$

In this example, the notation $A \sqcup B$ is slightly ambiguous, since $A$ and $B$ are disjoint already. Depending on context, it could either 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 usually be clear which of the two senses is meant; the former is more common in everyday maths, while the latter is usually intended in set theory.

## Exercise

What happens if $A = B = \{6,7\}$?

%%hidden(Show): Only the second definition 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 elements.%%

## $A = \mathbb{N}$, $B = \{ 1, 2, x \}$

Let $A$ be the set $\mathbb{N}$ of natural numbers including $0$, and let $B$ be the set $\{1,2,x\}$ containing two natural numbers and one symbol $x$ which is not a natural number.

Then $A \sqcup B$ only makes sense under the second definition; 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 notation $A \sqcup B$ is ambiguous; it could mean $\{ 0,1,2,\dots, x, y \}$, or it could mean $\{(0,1), (1,1), (2,1), \dots, (x,2), (y,2)\}$.

# Multiple operands

We can generalise the disjoint union so that we can write $A \sqcup B \sqcup C$ instead of just $A \sqcup B$.

To use the first definition, the generalisation is easy to formulate: it's just $A \cup B \cup C$, but with the extra information that $A$, $B$ and $C$ are pairwise disjoint (so there is nothing in any of their intersections: $A$ and $B$ are disjoint, $B$ and $C$ are disjoint, and $A$ and $C$ are disjoin).

To use the second definition, 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'$.

## Infinite unions

In fact, both definitions generalise even further, to unions over arbitrary sets. Indeed, in the first sense we can define $$\bigsqcup_{i \in I} A_i = \bigcup_{i \in I} A_i$$ together with the information that no pair of $A_i$ intersect.

In the second 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 example, $$\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 definitions?

The first definition is basically just a notational convenience: it saves a few words when saying "… and moreover the sets are pairwise disjoint".

The real meat of the idea is the second definition, which provides a way of forcing the sets to be disjoint. It's not necessarily the only way we could coherently define a disjoint union (since there's more than one way we could have tagged the sets; if nothing 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 \}$, swapping the tags). But it's the one we use by convention. Usually when we're using the second definition we don't much care exactly how we force the sets to be disjoint; we only care that there is such a way. (For comparison, there is [ordered_pair_formal_definitions more than one way] to define the ordered pair in the [ZF] set theory, but we almost never care really which exact definition we use; only that there is a definition that has the properties we want from it.)