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, logarithms, 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
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.
In the following example we 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.
Example 1.3.3.
Consider the sets \(A = \{a,b,c,d\}\text{,}\) \(B=\{1,2,3\}\text{,}\) and \(C=\{a,2,c,3\}\text{.}\) Then,
Notice that elements of a set aren't repeated: \(a\) can't be in the set “more than once”. As another example,
Note that there is no difference between \(C \cup B\) and the set
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,
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.
Example 1.3.6.
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.
since these are the elements in both \(A\) and \(C\text{.}\)
Because \(A\) and \(B\) have nothing in common,
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.
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.
Example 1.3.9.
Let \(X = \{a,b,c,d,e\}\) and \(Y=\{b,d,f\}\text{.}\) Then
However,
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\) (this is the capital Greek letter “Omega”), 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{.}\)
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.
Example 1.3.11.
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
and
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
The elements of the product are called ordered pairs.
You are likely familiar with a classic Cartesian product.
Example 1.3.13.
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:
For instance, the point \((-1,\pi)\) would be plotted \(1\) unit to the left of the origin, and approximately \(3.14\) units above it.
Graphs of functions that you remember from algebra, such as the graph of a parabola like
are subsets of the Cartesian plane.
However, we can take products of any sets we like.
Example 1.3.14.
Let \(E=\{1,2,3\}\) and \(F=\{x,y,z\}\text{.}\) Then
The Cartesian product does not commute:
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, like we did in the above example with the Cartesian plane. For instance:
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 outputs.
Example 1.3.16.
You are familiar with functions that produce outputs via numerical rules. Consider the function \(f:\mathbb{N}\to\mathbb{N}\) defined by the rule \(f(n) = -n^2\text{.}\) For instance, \(f(0) = 0\text{,}\) \(f(2) = -4\text{,}\) and \(f(17) = -289\text{.}\) The domain of this function is the set of the natural numbers, and so is the codomain. However, since the function will never produce a positive value, its range is the set of negative perfect squares
Example 1.3.17.
Let \(A = \{1,2,3\}\) and \(B=\{x,y,z\}\text{.}\) Consider the set
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.
Example 1.3.18.
As a non-example, the relation
is not a function because the element \(1\) is mapped to both \(x\) and \(y\text{.}\) We say \(g\) is not well-defined.
Subsection 1.3.3 Cardinality
Definition 1.3.19.
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.
Example 1.3.20.
Let \(A = \{a,b,c,d\}\text{.}\) Then \(|A|=4\text{.}\)
Let
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, and power sets.
Theorem 1.3.21. Inclusion-exclusion principle.
Let \(A\) and \(B\) be finite sets. Then,
Proof.
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,
Example 1.3.22.
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
Theorem 1.3.23.
Let \(A\) and \(B\) be finite sets. Then,
Proof.
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
where the above sum consists of \(|A|\) terms. Therefore,
Example 1.3.24.
Let \(A = \{a,b,c,d\}\) and \(B=\{c,d,e\}\text{.}\) Then
This set contains \(12\) elements, which we also know becuase \(|A||B| = 4 \times 3 = 12\text{.}\)
Theorem 1.3.25.
Let \(A\) be a finite set. Then,
A proof of this theorem is provided in the appendix to Part I. Additionally, since Part III is all about counting, we'll revisit the theorem there as well. But for now, you're done with your first chapter of this book!
A crucial part of any mathematics text is the exercises, which follow this paragraph. Exercises test that you understood what you've read and allow you to expand the boundaries of what you know. If you get stuck, go back to the examples in this chapter and see if anything looks familiar. You can also see if similar exercises have solutions. If all else fails, assuming that you are reading this book for a class, ask your instructor for help! What's important is that you don't give up. Getting stuck and struggling are vital parts of the learning process.