3.1: Sets

At its essence, all of mathematics is built on set theory. In this chapter, we will introduce some of the basics of sets and their properties.

Definition 3.1. A set is a collection of objects called elements. If \(A\) is a set and \(x\) is an element of \(A\), we write \({x\in A}\). Otherwise, we write \({x\notin A}\). The set containing no elements is called the empty set, and is denoted by the symbol \({\emptyset}\). Any set that contains at least one element is referred to as a nonempty set.

If we think of a set as a box potentially containing some stuff, then the empty set is a box with nothing in it. One assumption we will make is that for any set \(A\), \(A\notin A\). The language associated to sets is specific. We will often define sets using the following notation, called set-builder notation: \[{S=\{x \in A\mid P(x)\}},\] where \(P(x)\) is some predicate statement involving \(x\). The first part “\(x \in A\)" denotes what type of \(x\) is being considered. The predicate to the right of the vertical bar (not to be confused with “divides") determines the condition(s) that each \(x\) must satisfy in order to be a member of the set. This notation is read as “The set of all \(x\) in \(A\) such that \(P(x)\)." As an example, the set \(\{x\in \mathbb{N}\mid x \mbox{ is even and }x\geq 8\}\) describes the collection of even natural numbers that are greater than or equal to 8.

There are a few sets that are commonly discussed in mathematics and have predefined symbols to denote them. We have already encountered the integers, natural numbers, and real numbers. Notice that our definition of the rational numbers uses set-builder notation.

• Natural Numbers: \({\mathbb{N}:= \{1,2,3,\ldots\}}\). Some books will include zero in the set of natural numbers, but we do not.
• Integers: \({\mathbb{Z} := \{0, \pm 1, \pm2, \pm 3, \ldots\}}\).
• Rational Numbers: \({\mathbb{Q} := \{a/b \mid a, b \in \mathbb{Z} \text{ and } b \neq 0\}}\).
• Real Numbers: \({\mathbb{R}}\) denotes the set of real numbers. We are taking for granted that you have some familiarity with this set.

Since the set of natural numbers consists of the positive integers, the natural numbers are sometimes denoted by \({\mathbb{Z}^+}\).

Problem 3.2. Unpack the meaning of each of the following sets and provide a description of the elements that each set contains.

1. \(A=\{x \in \mathbb{N} \mid x = 3k \mbox{ for some } k\in \mathbb{N} \}\)
2. \(B=\{t \in \mathbb{R} \mid t \leq 2 \mbox{ or } t\geq 7 \}\)
3. \(C=\{t \in \mathbb{Z} \mid t^2 \leq 2 \}\)
4. \(D=\{s \in \mathbb{Z} \mid -3<s\leq 5 \}\)
5. \(E=\{m \in \mathbb{R} \mid m = 1 - \frac{1}{n} \mbox{, where } n \in \mathbb{N} \}\)

Problem 3.3. Write each of the following sentences using set-builder notation.

1. [prob:set-builder examples a] The set of all real numbers less than \(-\sqrt{2}\).
2. [prob:set-builder examples b] The set of all real numbers greater than \(-12\) and less than or equal to 42.
3. The set of all even integers.

Parts (a) and (b) of Problem 3.3 are examples of intervals.

Definition 3.4. For \(a,b\in\mathbb{R}\) with \(a<b\), we define the following sets, referred to as intervals.

1. (a,b) := {x ∈ R | a<x<b}
2. [a,b] := {x ∈ R | a\(\leq\) x \(\leq\) b}
3. [a,b) := {x ∈ R | a \(\leq\) x< b}
4. (a,\(\infty\)) := {x ∈ R | a<x}
5. (- \(\infty\) ,b) := {x ∈ R | x<b}
6. (- \(\infty\) , \(\infty\) ) := R

We analogously define \({(a,b]}\), \({[a,\infty)}\), and \({(-\infty,b]}\). Intervals of the form \((a,b)\), \((-\infty,b)\), \((a,\infty)\), and \((-\infty,\infty)\) are called open intervals while \([a,b]\) is referred to as a closed interval. A bounded interval is any interval of the form \((a,b)\), \([a,b)\), \((a,b]\), and \([a,b]\). For bounded intervals, \(a\) and \(b\) are called the endpoints of the interval.

We will always assume that any time we write \((a,b), [a,b], (a,b]\), or \([a,b)\) that \(a<b\). We will see where the terminology of “open" and “closed" comes from in Section 5.2.

Problem 3.5. Give an example of each of the following.

1. An interval that is neither an open nor closed interval.
2. An infinite set that is not an interval.

Definition 3.5. If \(A\) and \(B\) are sets, then we say that \(A\) is a subset of \(B\), written \({A\subseteq B}\), provided that every element of \(A\) is an element of \(B\).

Problem 3.7. List all of the subsets of \(A=\{1,2,3\}\).

Every nonempty set always has two subsets. Notice that if \(A=\emptyset\), then Parts (a) and (b) of the next theorem say the same thing.

Theorem 3.8. Let \(A\) be a set. Then

1. \(A\subseteq A\), and
2. \(\emptyset \subseteq A\).

Observe that “\(A\subseteq B\)" is equivalent to “For all \(x\) (in the universe of discourse), if \(x\in A\), then \(x\in B\)." Since we know how to deal with “for all" statements and conditional propositions, we know how to go about proving \(A\subseteq B\). If \(A\) happens to be the empty set, then the statement “For all \(x\) (in the universe of discourse), if \(x\in A\), then \(x\in B\)" is vacuously true. This is in agreement with Theorem 3.8(b), which states that the empty set is always a subset of every set. In light of this, it is common to omit discussion of the case when \(A\) is the empty set when proving that \(A\) is s a subset of \(B\).

Problem 3.9. Suppose \(A\) and \(B\) are sets. Describe a skeleton proof for proving that \(A\subseteq B\).

Theorem 3.10. Suppose that \(A\), \(B\), and \(C\) are sets. If \(A\subseteq B\) and \(B\subseteq C\), then \(A\subseteq C\).

Definition 3.11. Two sets \(A\) and \(B\) are equal, denoted \({A=B}\), if the sets contain the same elements.

Since the next theorem is a biconditional proposition, you need to write two distinct subproofs, one for “\(A=B\) implies \(A \subseteq B\) and \(B \subseteq A\)", and another for “\(A \subseteq B\) and \(B \subseteq A\) implies \(A=B\)". Be sure to make it clear to the reader when you are proving each implication.

Theorem 3.12. Suppose that \(A\) and \(B\) are sets. Then \(A=B\) if and only if \(A \subseteq B\) and \(B \subseteq A\).

Note that if we want to prove \(A=B\), then we have to do two separate subproofs: one for \(A\subseteq B\) and one for \(B\subseteq A\). Be sure to make it clear to the reader where these subproofs begin and end. One approach is to label each subproof with “\((\subseteq)\)" and “\((\supseteq)\)" (including the parentheses), respectively.

Definition 3.13. If \(A\subseteq B\), then \(A\) is called a proper subset provided that \(A\neq B\). In this case, we may write \({A\subset B}\) or \({A\subsetneq B}\).

Note that some authors use \(\subset\) to mean \(\subseteq\), so some confusion could arise if you are not reading carefully.

Definition 3.14. Let \(A\) and \(B\) be sets in some universe of discourse \(U\).

1. The union of the sets \(A\) and \(B\) is \(A \cup B\) := {\(x\in U \mid x\in A \mbox{ or } x\in B \)}.
2. The intersection of the sets \(A\) and \(B\) is \(A \cap B \) := {\(x\in U \mid x\in A \mbox{ and } x\in B\) }.
3. The set difference of the sets \(A\) and \(B\) is \(A \setminus B\) := {\(x\in U \mid x\in A \mbox{ and } x\notin B \)}.
4. The complement of \(A\) (relative to \(U\)) is the set \(A^c\):= \( U \setminus A\) ={\( x \in U \mid x \notin A\)}.

Definition 3.15. If two sets \(A\) and \(B\) have the property that \(A \cap B = \emptyset\), then we say that \(A\) and \(B\) are disjoint sets.

Problem 3.16. Suppose that the universe of discourse is \(U=\{1,2,3,4,5,6,7,8,9,10\}\). Let \(A=\{1, 2, 3, 4, 5\}\), \(B=\{1, 3, 5\}\), and \(C=\{2, 4, 6, 8\}\). Find each of the following.

1. \(A \cap C\)
2. \(B \cap C\)
3. \(A \cup B\)
4. \(A\setminus B\)
5. \(B \setminus A\)
6. \(C \setminus B\)
7. \(B^c\)
8. \(A^c\)
9. \((A\cup B)^c\)
10. \(A^c\cap B^c\)

Problem 3.17. Suppose that the universe of discourse is \(U=\mathbb{R}\). Let \(A=[-3,-1)\), \(B=(-2.5,2)\), and \(C=(-2,0]\). Find each of the following.

1. \(A^c\)
2. \(A \cap C\)
3. \(A \cap B\)
4. \(A \cup B\)
5. \((A\cap B)^c\)
6. \((A\cup B)^c\)
7. \(A \setminus B\)
8. \(A\setminus (B \cup C)\)
9. \(B \setminus A\)

Problem 3.18. Suppose that the universe of discourse is \(U=\{x,y, z, \{y\}, \{x,z\}\}\). Let \(S=\{x,y,z\}\) and \(T=\{x,\{y\}\}\). Find each of the following.

1. \(S \cap T\)
2. \((S\cup T)^{c}\)
3. \(T\setminus S\)

Theorem 3.19. If \(A\) and \(B\) are sets such that \(A \subseteq B\), then \(B^c \subseteq A^c\).

Theorem 3.20. If \(A\) and \(B\) are sets, then \(A\setminus B = A \cap B^c\).

In Chapter 2, we encountered De Morgan’s Law (see Theorem 2.26 and Problem 2.27), which provided a method for negating compound propositions involving conjunctions and disjunctions. The next theorem provides a method for taking the complement of unions and intersections of sets. This result is also known as De Morgan’s Law. Do you see why?

Theorem 3.21. If \(A\) and \(B\) are sets, then

1. \((A \cup B)^c = A^c \cap B^c\), and
2. \((A \cap B)^c = A^c \cup B^c\).

The next theorem indicates how intersections and unions interact with each other.

Theorem 3.22. If \(A\), \(B\), and \(C\) are sets, then

1. \(A \cup(B\cap C) = (A\cup B)\cap (A\cup C)\), and
2. \(A\cap (B\cup C)= (A\cap B)\cup (A\cap C)\).

Problem 3.23. For each of the statements (a)–(d) on the left, find an equivalent symbolic proposition chosen from the list (i)–(v) on the right. Note that not every statement on the right will get used.

\(A \nsubseteq B\). \(A \cap B= \emptyset\). \((A \cup B)^{c} \neq \emptyset\). \((A \cap B)^{c} = \emptyset\).

\((\forall x)(x \in A \wedge x \in B)\) \((\forall x)(x \in A \implies x \notin B)\) \((\exists x)(x \notin A \wedge x \notin B)\) \((\exists x)(x \in A \vee x \in B)\) \((\exists x)(x \in A \wedge x\notin B)\)