Skip to main content

Section 1.3 Set operations

The word “algebra” may make you recall a course where you had to solve equations and draw pictures. More broadly, “algebra” refers to the operations between mathematical objects. A high school algebra class teaches you to think about the way real numbers interact with each other and can be interacted with: addition, multiplication, exponentiation, the exponential function, etc. However, real numbers are not the only objects to enjoy operations and functions. In this chapter, we will learn about the algebra of sets.

Subsection 1.3.1 Union, intersection, difference

Definition 1.3.1.

Let \(A\) and \(B\) be sets. Their union is the set \(A \cup B\) of all elements that are in at least one of \(A\) or \(B\text{,}\) in set builder notation this is

\begin{equation*} A \cup B = \{\; x \; | \; x \in A \text{ or } x \in B \}. \end{equation*}

The above set-builder notation reads, “the union of \(A\) and \(B\) is the set of all elements \(x\) where either \(x\) is in \(A\) or \(x\) is in \(B\text{.}\)”

The union of two sets is pictured as two intertwining circles. Both circles are shaded, since the union contains anything in either set.
Figure 1.3.2.

The union of two sets is pictured as two intertwining circles. Both circles are shaded, since the union contains anything in either set.

The following example will calculate a couple of unions. In this example as well as many others, you are encouraged to try to come up with your own example after reading.

Consider the sets \(A = \{a,b,c,d\}\text{,}\) \(B=\{1,2,3\}\text{,}\) and \(C=\{a,2,c,3\}\text{.}\) Then,

\begin{equation*} A \cup C = \{a,b,c,d,2,3\} \end{equation*}

Notice that elements of a set aren't repeated: \(a\) can't be in the set “more than once”. As another example,

\begin{equation*} C \cup B = \{a,2,c,3,1\} \end{equation*}

Notice there is no difference between \(C \cup B\) and the set

\begin{equation*} B \cup C = \{1,2,3,a,c\} \end{equation*}

When the order of the objects in question doesn't matter, we say the operation commutes. So, the union commutes.

Definition 1.3.4.

Let \(A\) and \(B\) be sets. Their intersection is the set \(A \cap B\) of all elements that are in both \(A\) and \(B\text{,}\) in other words,

\begin{equation*} A \cap B = \{\; x \; | \; x \in A \text{ and } x \in B \}. \end{equation*}
Two sets are depicted as intertwining circles. Because the intersection is only the elements the two sets have in common, only the overlap between the two circles is shading, representing the intersection.
Figure 1.3.5.

Two sets are depicted as intertwining circles. Because the intersection is only the elements the two sets have in common, only the overlap between the two circles is shading, representing the intersection.

Consider once again the sets \(A = \{a,b,c,d\}\text{,}\) \(B=\{1,2,3\}\text{,}\) and \(C=\{a,2,c,3\}\text{.}\) This time we will calculate their intersections.

\begin{equation*} A \cap C = \{a,c\}, \end{equation*}

since these are the elements in both \(A\) and \(C\text{.}\)

\begin{equation*} B \cap C = \{2,3\} \end{equation*}

Because \(A\) and \(B\) have nothing in common,

\begin{equation*} A \cap B = \varnothing, \end{equation*}

the empty set.

Definition 1.3.7.

Let \(A\) and \(B\) be sets. The difference \(A-B\) is the set of all elements in \(A\) but not \(B\text{,}\) i.e.

\begin{equation*} A-B=\{ \; x \; | \; x \in A \text{ and } x \not\in B\}. \end{equation*}

Sometimes the difference of \(B\) from \(A\) is denoted \(A \setminus B\) instead.

Two sets are depicted as intertwining circles. The difference between them is represented as the shaded region of one circle outside the other. The second circle and the overlap are not shaded.
Figure 1.3.8.

Two sets are depicted as intertwining circles. The difference between them is represented as the shaded region of one circle outside the other. The second circle and the overlap are not shaded.

Let \(X = \{a,b,c,d,e\}\) and \(Y=\{b,d,f\}\text{.}\) Then

\begin{equation*} X-Y = \{a,c,e\} \end{equation*}

However,

\begin{equation*} Y-X = \{f\} \end{equation*}

Unlike union and intersection, difference is not commutative.

Often we work with sets in the context of a universal or ambient set, sometimes denoted \(\Omega\text{,}\) that all of our sets are assumed to be subsets of. This set is typically inferred from context. Here are some examples:

  • The sentence “Every number is odd or even” is true if the universal set is the integers \(\mathbb{Z}\text{,}\) but false if the universal set is the real numbers \(\mathbb{R}\text{.}\) If you are speaking to a novice, you should make the difference clear.

  • If a computer science student's advisor says “Everyone takes discrete math”, then the universal set is understood to be computer science students at that institution. If that were said to students in a general education course, or to someone who did not go to school, then the universal set would change, and the statement would likely no longer be true.

Definition 1.3.10.

Let \(A\) be a set contained in some universal set \(\Omega\text{.}\) The complement of \(A\) (relative to \(\Omega\)), denoted \(\overline{A}\text{,}\) is all the elements not in \(A\text{.}\) In other words, \(\overline{A}=\Omega-A\text{.}\)

The symbol \(\Omega\) is the Greek letter capital “omega”. Greek letters provide mathematicians with a convenient second alphabet, and we will see several Greek letters throughout this book.

Additionally, note that the complement is sometimes denoted \(A'\) or \(A^c\text{,}\) especially in statistics, where the “bar” notation is saved for an average.

Again let \(X = \{a,b,c,d,e\}\) and \(Y=\{b,d,f\}\text{.}\) This time, suppose the universal set is \(\Omega = \{a,b,c,d,e,f,g\}\text{.}\) Then

\begin{equation*} \overline{X} = \{f,g\} \end{equation*}

and

\begin{equation*} \overline{Y} = \{a,c,e,g\} \end{equation*}

Subsection 1.3.2 Products and functions

The first three operations we discussed are called binary operations since they involve two objects. The complement is unary, because we act on a single object. Here is another binary operation.

Definition 1.3.12.

Let \(A\) and \(B\) be sets. Their Cartesian product (sometimes just product) is the set

\begin{equation*} A\times B = \{(a,b)\;|\; a \in A \text{ and } b \in B\}. \end{equation*}

The elements of the product are called ordered pairs.

You are likely familiar with a classic Cartesian product.

Typically in an introductory algebra course students work with the Cartesian coordinate plane \(\mathbb{R}^2\text{.}\) This is the product of the real number line \(\mathbb{R}\) with itself:

\begin{equation*} \mathbb{R}^2 = \mathbb{R}\times \mathbb{R} = \{(x,y)\;|\;x,y \in \mathbb{R}\} \end{equation*}

For instance, the point \((-1,\pi)\) would be plotted \(1\) unit to the left of the origin, and approximately \(3.14\) units above it.

However, we can take products of any sets we like.

Let \(E=\{1,2,3\}\) and \(F=\{x,y,z\}\text{.}\) Then

\begin{equation*} E \times F = \{(1,x), (1,y), (1,z), (2,x), (2,y), (2,z), (3,x), (3,y), (3,z)\} \end{equation*}

The Cartesian product does not commute:

\begin{equation*} F \times E = \{(x,1), (x,2), (x,3), (y,1), (y,2), (y,3), (z,1), (z,2), (z,3)\} \end{equation*}

A word of caution. While sets are unordered, ordered pairs are not (hence the name). So even though \(\{1,z\}\) and \(\{z,1\}\) are the same set, \((1,z)\) and \((z,1)\) are not the same pair. This is why \(E \times F\) and \(F\times E\) are not the same set. You should adopt the rule of thumb that structures listed in \(\{\) curly braces \(\}\) are unordered, while structures listed in \((\) parentheses \()\) are ordered.

Nothing is stopping us from taking a product of a set with itself:

\begin{equation*} F^2 = F \times F = \{(x,x), (x,y), (x,z), (y,x), (y,y), (y,z), (z,x), (z,y), (z,z)\} \end{equation*}

A subset of the Cartesian product \(A \times B\) is called a relation between \(A\) and \(B\text{.}\) We will study relations in excruciating detail in Part IV of this book. However, a more specific type of relation is so ubiquitous in mathematics that it will appear several times between now and then, so we should mention it now.

Definition 1.3.15.

A function \(f:A\to B\) whose domain is the set \(A\) and whose codomain is the set \(B\) is a subset of \(A \times B\) where every element of \(A\) is paired with exactly one element of \(B\text{.}\) The range of \(f\) is the set \(f(A)\text{,}\) which consists of the elements \(b \in B\) for which there is a pair \((a,b) \in f\text{.}\) Finally, when \((a,b) \in f\text{,}\) we write \(f(a)=b\text{.}\)

It's a complicated definition, but you likely already know it: a function assigns every element of one set to exactly one element of a second set (maybe the same set). In an introductory algebra course you may have learned the vertical line test, which is a graphical way to verify the “every \(a\) gets one \(b\)” restriction.

One point of potential confusion to those who have seen the word “function” before is the difference between the codomain and the range. The codomain is the set of all possible outputs of the function. The range, on the other hand, is the set of actual inputs.

Let \(A = \{1,2,3\}\) and \(B=\{x,y,z\}\text{.}\) Consider the set

\begin{equation*} f = \{(1,y), (2,y), (3,x)\} \end{equation*}

We would say that \(f\) is a function whose domain is \(A\) and whose codomain is \(B\text{,}\) which we can say in one swing by writing \(f:A\to B\text{.}\) We write \(f(1)=y\text{,}\) \(f(2)=y\text{,}\) and \(f(3)=x\text{.}\) The range of the function is \(f(A) = \{x,y\}\text{,}\) since these are the only elements of \(B\) that \(f\) actually attains.

As a non-example, the relation

\begin{equation*} g = \{(1,x), (1,y), (2,z), (3,z)\} \end{equation*}

is not a function because the element \(1\) is mapped to both \(x\) and \(y\text{.}\) We say \(g\) is not well-defined.

Definition 1.3.17.

Let \(A\) and \(B\) be sets. The set of all functions between \(A\) and \(B\) is denoted \(B^A\) or \(Hom(A,B)\text{.}\)

The reason for the abbreviation \(Hom\) is because a certain special kind of function that many mathematicians are interested in is called a “homomorphism”.

Subsection 1.3.3 Cardinality

Definition 1.3.18.

Let \(A\) be a finite set. Then the cardinality of \(A\text{,}\) denoted \(|A|\text{,}\) is the number of elements contained in \(A\text{.}\)

Students tend to confuse the notation for cardinality with the notation for absolute value. They are similar for a reason! Like absolute value, cardinality suggests the “size” of a set. However, we only take the “absolute value” of a number, not a set.

The idea of cardinality can be extended to infinite sets as well, but that is generally difficult, and far beyond the scope of this book. We will stick to counting finite sets.

Let \(A = \{a,b,c,d\}\text{.}\) Then \(|A|=4\text{.}\)

Let

\begin{equation*} B = \{p\;|\;p \text{ is a prime number and }1 \le p \le 15\} \end{equation*}

In this case, \(|B|=6\) since \(B=\{2,3,5,7,11,13\}\text{.}\)

We can prove some useful formulas for finding the cardinalities of unions, products, functions, and power sets.

The set \(A \cup B\) contains all the elements that are in either \(A\) or \(B\text{,}\) so we start by adding the cardinalities of those sets. However, any element in \(A \cap B\) has been double-counted. To correct this mistake, we subtract \(|A \cap B|\text{.}\) Therefore,

\begin{equation*} |A \cup B| = |A| + |B| - |A \cap B| \end{equation*}

Let \(A = \{a,b,c,d\}\) and \(B=\{c,d,e\}\text{.}\) Then \(A \cup B = \{a,b,c,d,e\}\text{.}\) By inspection, \(|A \cup B|=5\text{.}\) We could also see this by using the formula

\begin{equation*} |A \cup B| = |A| + |B| - |A \cap B| = 4 + 3 - 2 = 5 \end{equation*}

To construct \(A \times B\text{,}\) every element of \(A\) is paired with every element of \(B\text{.}\) For each element of \(A\text{,}\) then, there are \(|B|\) total pairs. That means

\begin{equation*} |A \times B| = |B| + |B| + |B| + \cdots + |B| \end{equation*}

where the above sum consists of \(|A|\) terms. Therefore,

\begin{equation*} |A \times B| = |A||B| \end{equation*}

Let \(A = \{a,b,c,d\}\) and \(B=\{c,d,e\}\text{.}\) Then

\begin{align*} A \times B = \{ \amp (a,c), (a,d), (a,e), (b,c), (b,d), (b,e)\\ \amp (c,c), (c,d), (c,e), (d,c), (d,d), (d,e)\} \end{align*}

This set contains \(12\) elements, which we also know becuase \(|A||B| = 4 \times 3 = 12\text{.}\)

If you were wondering why the set of functions from \(A\) to \(B\) was called \(B^A\) and not \(A^B\text{,}\) hopefully this theorem answers your question. We will not provide a proof of this theorem just yet, and wait until Part III of the book.

We could shove off this proof until Part III as well, but if we take the previous theorem for granted, we can employ a cool argument where we construct functions between \(A\) and another set and count those functions.

Let \(A\) be a set and consider the set \(\{0,1\}\) of two elements. We will construct a function \(f:A \to \{0,1\}\text{.}\) The point is that there is a correspondence between the subsets of \(A\) (the elements of \(\mathscr{P}(A)\)) and such functions. Take a subset \(E \subseteq A\text{;}\) if \(a \in E\text{,}\) then we can say \(f(a)=1\text{;}\) and if \(a \not\in E\text{,}\) we can say \(f(a)=0\text{.}\) Likewise, we can go from functions to subsets. So, since there are \(2^{|A|}\) functions \(A \to \{0,1\}\text{,}\) there are also \(2^{|A|}\) subsets.

That proof may have been a little abstract. Consider the following example.

The power set of \(B = \{c,d,e\}\) is

\begin{equation*} \mathscr{P}(B) = \Big\{ \varnothing, \{c\}, \{d\}, \{e\}, \{c,d\}, \{c,e\}, \{d,e\}, \{c,d,e\}\} \end{equation*}

We can see for ourselves that \(|\mathscr{P}(B)|=8=2^3\text{.}\) To understand how each element of the power set can be viewed as a function \(f:B \to \{0,1\}\text{,}\) take the subset \(\{c,d\}\) as an example. Because \(c\) and \(d\) are both in the subset, we say \(f(c)=1\) and \(f(d)=1\text{.}\) On the other hand, \(f(e)=0\text{.}\)

For the two extreme examples, \(\varnothing\) corresponds to the function where \(f(x)=0\) for all \(x \in B\) and \(\{c,d,e\}\) corresponds to the function where \(f(x)=1\) for all \(x \in B\text{.}\)

If you enjoyed this proof and the example, you are going to love Part III. But for now, there's more to learn in Part I.