Operations: Union, intersection, and complement of sets

Sets can be combined with each other in various ways. Sometimes this is used as a different way of defining sets, and sometimes it is an actual construction process where multiple sets serve as the input to some mechanism that returns a single set as the output. You’ll see many examples of both usages throughout the course. Before we discuss these operations, though, we have to introduce one special set that will help us illustrate how these operations work.

The empty set

As mentioned before, you can think of sets as a kind of strange container without internal order and without duplicates. Since containers can be empty, it isn’t too surprising that there is something called the empty set. The empty set is written \(\left \{ \right \}\), or more commonly \(\emptyset\).

The empty set contains nothing. There is no \(a\) such that \(a \in \emptyset\). At the same time, the empty set is not simply nothing because it is still a set. A set is not nothing, just like an empty container is not nothing.

The empty set may seem rather useless to you, but it actually has a very important role to play. Just like the introduction of \(0\) was a tremendous breakthrough that made arithmetic a lot more elegant and internally consistent, operations on sets would not be as well-behaved without the empty set. You will see some examples of that right away.

Union

Given two sets \(A\) and \(B\), their union \(A \cup B\) is the set that contains

• all elements of \(A\), and
• all elements of \(B\), and
• nothing else.

This means that the union of two sets is the result of taking everything that belongs to at least one set. Union builds bigger sets from smaller sets. This makes it something like the set counterpart of addition over numbers.

Union is associative, which means that \((A \cup B) \cup C = A \cup (B \cup C)\). This is just like \((5 + 4) + 3 = 5 + (4 + 3)\).

Union is also commutative. That is to say, the order of arguments does not matter: \(A \cup B = B \cup A\). This again mirrors addition, where \(5 + 3 = 3 + 5\). Also note that \(A \cup \emptyset = A\) for any set \(A\), just like \(n + 0 = n\) for any number \(n\).

Intersection

Intersection is the opposite of union in that it builds smaller sets rather than bigger ones.

Note that \(A \cap \emptyset = \emptyset\) no matter what the set \(A\) looks like. This is similar to how \(n \cdot 0 = 0\) irrespective of the value of \(n\). So intersection is akin to multiplication for sets. Like multiplication, intersection is associative, so that \((A \cap B) \cap C = A \cap (B \cap C)\). This mirrors the fact that \((5 \cdot 4) \cdot 2 = 5 \cdot (4 \cdot 2)\).

Intersection is also commutative, again just like multiplication: \(A \cap B = B \cap A\), and \(m \cdot n = n \cdot m\).

The one difference between intersection and multiplication seems to be that the former produces something smaller and the latter something bigger. But as we will learn later, this isn’t really all that important, and the two operations are indeed very close counterparts in an abstract sense.

(Relative) complement

Given the set-counterparts for \(+\) and \(\cdot\), you probably expect one for subtraction, too. It exists, indeed, and is called relative complement.

Given two sets \(A\) and \(B\), their relative complement is written \(A - B\) (sometimes \(A \setminus B\)). The complement of \(B\) relative to \(A\) contains all members of \(A\) that are not members of \(B\).

Relative complement is not associative in the general case.

That doesn’t mean that there are never cases where one can’t change the order of evaluation at all. For instance, \((\left \{ 0,1 \right \} - \left \{ 0 \right \}) - \left \{ 2 \right \} = \left \{ 1 \right \} = \left \{ 0,1 \right \} - (\left \{ 0 \right \} - \left \{ 2 \right \})\). But that is merely a coincidence. That relative complement is not associative mirrors subtraction for numbers, where \((5 - 2) - 3 = 0 \neq 6 = 5 - (2 -3)\).

Commutativity does not hold for relative complement either, as is shown by \(\left \{ 5 \right \} - \left \{ 5,4 \right \} = \emptyset \neq \left \{ 4 \right \} = \left \{ 5,4 \right \} - \left \{ 5 \right \}\).

Sometimes we may fix a specific set \(U\) such that every set we are interested in can only contain elements of \(U\). In this case, we call \(U\) our universe. Given a universe \(U\), we just \(\overline{B}\) for \(A - B\) and call it the complement of \(B\).

Pictures for set operations

If we represent the sets \(A\) and \(B\) as overlapping circles, then we can use shading to indicate what parts of \(A\) and or \(B\) are picked out by the respective operations.

Mnemonics for notation

Beginners tend to confuse \(\cap\) and \(\cup\). Here is a mnemonic: The term union starts with u, and \(\cup\) looks like a stylized U. By contrast, \(\cap\) looks like a bit like a stylized, minimalist A, and \(A \cap B\) contains all \(x\) that are members of \(A\) and \(B\).

Recap

• The union of \(A\) and \(B\) is the smallest set that contains every \(x\) such that \(x \in A\) or \(x \in B\) (or both).
• The intersection of \(A\) and \(B\) is the smallest set that contains every \(x\) such that \(x \in A\) and \(x \in B\).
• The relative complement of \(A\) and \(B\) (or equivalently, the complement of \(B\) relative to \(A\)) is the smallest set that contains every \(x\) such that \(x \in A\) and \(x \notin B\).
• Union and intersection are associative (order of evaluation doesn’t matter) and commutative (order of arguments doesn’t matter).
• Relative complement is neither associative nor commutative.
• The complement of \(B\), denoted \(\overline{B}\), is a shorthand for \(A - B\) when \(A\) is clear from context.