Skip to main content

Chapter 1 Sets

Every mathematics, science, and engineering course uses sets, the basic building blocks of mathematics, so we start here. It might seem that we should start with numbers. However, set theory is required to do a mathematically rigorous development of the numbers as well, so sets are the best starting point.

We won't define the words “element,” “set” and “universe.” Rather, we will rely on our intuition. We will consider a set to be a collection of elements coming from some universe \(\U\) of elements. For example, if we are talking about numbers, our universe might be the set of all real numbers or might be the set of all integers. If we are talking about animals, our universe might be all animals in the San Diego Zoo or it might be all animals on this planet.

Definition 1.2.

If \(\A\) and \(\B\) are sets and every element of \(\A\) is also in \(\B\text{,}\) then we say that \(\A\) is a subset of \(\B\) and write \(\A \subseteq \B\) .

Definition 1.5.

The set \(\R\) is the set of all real numbers.

Example 1.6.

Are the sets \(\dsp \A = \{ (x,y) \mid x\in \R \mbox{ and } x=\sqrt{y} \}\) and \(\dsp \B = \{ (x,y) \mid x\in \R \mbox{ and } x^2 = y \}\) the same sets? What are some elements of \(\A\text{?}\) Of \(\B\text{?}\)

Definition 1.7.

The empty set is the set having no members,

\begin{equation*} \emptyset = \{x \in \U \mid x \ne x\}\text{.} \end{equation*}

We can construct new sets from old using the Set Specification Axiom.

Definition 1.8.

Let \(\A\) and \(\B\) be sets. The intersection of \(\A\) and \(\B\) is the set

\begin{equation*} \A \cap \B = \{x \in \U \mid x \in \A \ \mbox{ and } \ x \in \B\}\text{.} \end{equation*}
Definition 1.9.

Let \(\A\) and \(\B\) be sets. The union of \(\A\) and \(\B\) is the set

\begin{equation*} \A \cup \B = \{x \in \U \mid x \in \A \ \mbox{ or } \ x \in \B\}\text{.} \end{equation*}
Definition 1.10.

Let \(\B\) be a set. The complement of \(\B\) is the set

\begin{equation*} \sim \B = \{x \in \U \mid x \not \in \B\}\text{.} \end{equation*}
Definition 1.11.

Let \(\A\) and \(\B\) be sets. The difference between \(\A\) and \(\B\) is the set

\begin{equation*} \A \sim \B = \A \cap (\sim \B)\text{.} \end{equation*}

The following illustrations are Venn diagrams for the sets just defined.

\begin{equation*} \A\cap \B \qquad\qquad\qquad \A\cup \B \qquad\qquad \A \sim \B \qquad\qquad \sim \B \end{equation*}

Different expressions might represent the same set as illustrated by the next example, which together with Problem 1.12 will show that

\begin{equation*} \A \cap (\B \cup \C) = (\A \cap \B) \cup (\A \cap \C)\text{.} \end{equation*}
Example 1.12.

For every choice of sets \(\A, \B\) and \(\C\text{,}\) \(\dsp \A \cap (\B \cup \C) \subseteq (\A \cap \B) \cup (\A \cap \C)\text{.}\)

For the remainder of this chapter we will assume that \(\A, \B\text{,}\) and \(\C\) are sets of elements from some universe \(\U\text{.}\)

Problem 1.13.

Show that \((\A \cap \B) \cup (\A \cap \C) \subseteq \A \cap (\B \cup \C)\text{.}\)

You are already familiar with operations on numbers such as addition, subtraction, multiplication, and division (\(+\text{,}\) \(-\text{,}\) \(*\text{,}\) \(\div\)). We have introduced the operations on sets such as intersection, union, and difference (\(\cap\text{,}\) \(\cup\text{,}\) and \(\sim\)). Soon, we will introduce more set operations, including ×, \(\oplus\) and \(\circ\text{.}\) All of these number and set operations are referred to as binary operations because each operation takes two inputs.

For the next few problems, illustrate each of the following identities with Venn Diagrams and write down a proof using the Set Equality Axiom.

Problem 1.14.

The Commutative Laws

  1. \(\displaystyle \A \cap \B = \B \cap \A\)

  2. \(\displaystyle \A \cup \B = \B \cup \A\)

Problem 1.15.

The Associative Laws

  1. \(\displaystyle \A \cap (\B \cap \C) = (\A \cap \B) \cap \C\)

  2. \(\displaystyle \A \cup (\B \cup \C) = (\A \cup \B) \cup \C\)

Problem 1.16.

Ask one question that you have after reading the introduction.

Problem 1.17.

The Distributive Laws

  1. \(\displaystyle \A \cup (\B \cap \C) = (\A \cup \B) \cap (\A \cup \C)\)

  2. \(\displaystyle \A \cap (\B \cup \C) = (\A \cap \B) \cup (\A \cap \C)\)

Problem 1.18.

The Absorption Laws

  1. \(\displaystyle \A \cup (\A \cap \B) = \A\)

  2. \(\displaystyle \A \cap (\A \cup \B) = \A\)

For the next problem, it is helpful to make the observation about the empty set that any statement starting with “If \(x \in \emptyset\text{,}\) then …” is a true statement. For example, the statement “If \(x \in \emptyset\text{,}\) then \(x\) is a seven-headed dog.” is a true statement. Why? Because the only way that statement could be false would be to have some value of \(x\) such that \(x \in \emptyset\) but \(x\) was not a seven-headed dog. But there is no such \(x\) since there is nothing in the empty set.

Problem 1.19.

The Identity Laws

  1. \(\displaystyle \A \cup \emptyset = \A\)

  2. \(\displaystyle \A \cap \U = \A\)

Problem 1.20.

The Inverse Laws

  1. \(\displaystyle \A \cup \sim \A = \U\)

  2. \(\displaystyle \A \cap \sim \A = \emptyset\)

Problem 1.21.

DeMorgan's Laws

  1. \(\displaystyle \sim(\A \cap \B) = \sim\A \cup \sim \B\)

  2. \(\displaystyle \sim(\A \cup \B) = \sim\A \cap \sim \B\)

Definition 1.22.

The symmetric difference between sets \(\A\) and \(\B\) is defined by

\begin{equation*} \A \oplus \B = (\A \cup \B) \sim (\A \cap \B)\text{.} \end{equation*}

We illustrate \(\A \oplus \B\) via a Venn diagram.

Problem 1.23.

\(\A \oplus \B = (\A \sim \B) \cup (\B \sim \A)\)

Example 1.24.

Does

\begin{equation*} \A \oplus (\B \cup \C) = (\A \oplus \B) \cup (\A \oplus \C) ? \end{equation*}

Restated, does \(\oplus\) distribute over \(\cup\text{?}\)

Problem 1.25.

\(\A \oplus (\B \oplus \C) = (\A \oplus \B) \oplus \C\)

It is likely that you “know” what an ordered pair is from previous courses, but unlikely that you have ever seen a precise definition. The next two problems make precise the notion of ordered pairs.

Problem 1.26.

Suppose that each of \(a\text{,}\) \(b\text{,}\) \(c\) and \(d\) is an element.

  1. Suppose \(\{a, b\} = \{c, d\}\text{.}\) Must it be true that \(a = c\) and \(b = d\) ?

  2. Suppose \(a = c\) and \(b = d\text{.}\) Must it be true that \(\{a, b\} = \{c, d\}\) ?

Definition 1.27.

If each of \(a\) and \(b\) is an element, then by the ordered pair \((a, b)\) we mean the set \(\{\{a\}, \{a, b\}\}\text{.}\) The elements \(a\) and \(b\) are known as the first and second coordinates of \((a,b)\text{,}\) respectively.

Problem 1.26 hinted at the property that we want from our new definition for ordered pairs. We want that \((a, b) = (c, d)\) if and only if \(a = c\) and \(b = d\text{.}\) The next problem allows you to show that our definition for ordered pairs, \((a, b) = \{ \{a\}, \{a, b\}\}\text{,}\) satisfies this property and therefore is a valid definition.

Problem 1.28.

Suppose each of \(a\text{,}\) \(b\text{,}\) \(c\) and \(d\) is an element. Use Definition 1.27 to prove the following two statements:

  1. If \((a, b) = (c, d)\text{,}\) then \(a = c\) and \(b = d\text{.}\)

  2. If \(a = c\) and \(b = d\text{,}\) then \((a, b) = (c, d)\text{.}\)

Definition 1.29.

If \(\A\) and \(\B\) are sets, the Cartesian product of \(\A\) and \(\B\text{,}\) denoted by \(\A\times \B\text{,}\) consists of all ordered pairs \((x,y)\) where \(x\in \A\) and \(y\in \B\text{.}\) Restated,

\begin{equation*} \A\times \B = \{\,(x,y) \mid x\in \A \mbox{ and } y\in \B\,\}\text{.} \end{equation*}
Problem 1.30.

Prove or give a counter-example:

\begin{equation*} \A\cap (\B\times \C) = (\A\cap \B) \times (\A\cap \C) \end{equation*}