5 Set Theory

5.1 Sets and Operations on Sets

5.1.1 Beginning Activity 1 (Set Operations)

Before beginning this section, it would be a good idea to review sets and set notation, including the roster method and set builder notation, in Section 2.3.

In Section 2.1, we used logical operators (conjunction, disjunction, negation) to form new statements from existing statements. In a similar manner, there are several ways to create new sets from sets that have already been defined. In fact, we will form these new sets using the logical operators of conjunction (and), disjunction (or), and negation (not). For example, if the universal set is the set of natural numbers $\mathbb{N}$ and

$$A=\{1,2,3,4,5,6\}\text{ and }B=\{1,3,5,7,9\}$$

• The set consisting of all natural numbers that are in $A$ and are in $B$ is the set $\{1,3,5\}$;

• The set consisting of all natural numbers that are in $A$ or are in $B$ is the set $\{1,2,3,4,5,6,7,9\}$; and

• The set consisting of all natural numbers that are in $A$ and are not in $B$ is the set $\{2,4,6\}$.

These sets are examples of some of the most common set operations, which are given in the following definitions.

Definition. Let $A$ and $B$ be subsets of some universal set $U$. The intersection of $A$ and $B$, written $A\cap B$ and read "$A$ intersect $B$," is the set of all elements that are in both $A$ and $B$. That is,

$$A\cap B=\{x\in U\mid x\in A\text{ and }x\in B\}.$$

The union of $A$ and $B$, written $A\cup B$ and read "$A$ union $B$," is the set of all elements that are in $A$ or in $B$. That is,

$$A\cup B=\{x\in U\mid x\in A\text{ or }x\in B\}.$$

Definition. Let $A$ and $B$ be subsets of some universal set $U$. The set difference of $A$ and $B$, or relative complement of $B$ with respect to $A$, written $A-B$ and read "$A$ minus $B$" or "the complement of $B$ with respect to $A$," is the set of all elements in $A$ that are not in $B$. That is,

$$A-B=\{x\in U\mid x\in A\text{ and }x\notin B\}.$$

The complement of the set $A$, written $A^c$ and read "the complement of $A$," is the set of all elements of $U$ that are not in $A$. That is,

$$A^c=\{x\in U\mid x\notin A\}.$$

For the rest of this beginning activity, the universal set is $U=\{0,1,2,3,\mathrm{\dots },10\}$, and we will use the following subsets of $U$ :

$$A=\{0,1,2,3,9\}\text{ and }B=\{2,3,4,5,6\}.$$

So in this case, $A\cap B=\{x\in U\mid x\in A$ and $x\in B\}=\{2,3\}$. Use the roster method to specify each of the following subsets of $U$.

1. $A\cup B$

2. $A^c$

3. $B^c$

We can now use these sets to form even more sets. For example,

$$A\cap B^c=\{0,1,2,3,9\}\cap \{0,1,7,8,9,10\}=\{0,1,9\}$$

Use the roster method to specify each of the following subsets of $U$.

1. $A\cup B^c$

2. $A^c\cap B^c$

3. $A^c\cup B^c$

4. ${(A\cap B)}^c$

5.1.2 Beginning Activity 2 (Venn Diagrams for Two Sets)

In Beginning Activity 1, we worked with verbal and symbolic definitions of set operations. However, it is also helpful to have a visual representation of sets. Venn diagrams are used to represent sets by circles (or some other closed geometric shape) drawn inside a rectangle. The points inside the rectangle represent the universal set $U$, and the elements of a set are represented by the points inside the circle that represents the set. For example, Figure 5.1 is a Venn diagram showing two sets.

Figure 5.1: Venn Diagram for Two Sets

In Figure 5.1, the elements of $A$ are represented by the points inside the left circle, and the elements of $B$ are represented by the points inside the right circle. The four distinct regions in the diagram are numbered for reference purposes only. (The numbers do not represent elements in a set.) The following table describes the four regions in the diagram.

Region	Elements of $U$	Set
1	In $A$ and not in $B$	$A-B$
2	In $A$ and in $B$	$A\cap B$
3	In $B$ and not in $A$	$B-A$
4	Not in $A$ and not in $B$	$A^c\cap B^c$

We can use these regions to represent other sets. For example, the set $A\cup B$ is represented by regions 1, 2, and 3 or the shaded region in Figure 5.2.

Figure 5.2: Venn Diagram for $A\cup B$

Let $A$ and $B$ be subsets of a universal set $U$. For each of the following, draw a Venn diagram for two sets and shade the region that represent the specified set. In addition, describe the set using set builder notation.

1. $A^c$

2. $B^c$

3. $A^c\cup B$

4. $A^c\cup B^c$

5. ${(A\cap B)}^c$

6. $(A\cup B)-(A\cap B)$

5.1.3 Set Equality, Subsets, and Proper Subsets

In Section 2.3, we introduced some basic definitions used in set theory, what it means to say that two sets are equal and what it means to say that one set is a subset of another set. See the definitions from that section. We need one more definition.

Definition. Let $A$ and $B$ be two sets contained in some universal set $U$. The set $A$ is a proper subset of $B$ provided that $A\subseteq B$ and $A\ne B$. When $A$ is a proper subset of $B$, we write $A\subset B$.

One reason for the definition of proper subset is that each set is a subset of itself. That is,

$$\text{ If }A\text{ is a set, then }A\subseteq A\text{. }$$

However, sometimes we need to indicate that a set $X$ is a subset of $Y$ but $X\ne Y$. For example, if

$$X=\{1,2\}\text{ and }Y=\{0,1,2,3\},$$

then $X\subset Y$. We know that $X\subseteq Y$ since each element of $X$ is an element of $Y$, but $X\ne Y$ since $0\in Y$ and $0\notin X$. (Also, $3\in Y$ and $3\notin X$.) Notice that the notations $A\subset B$ and $A\subseteq B$ are used in a manner similar to inequality notation for numbers and $a\le b)$.

It is often very important to be able to describe precisely what it means to say that one set is not a subset of the other. In the preceding example, $Y$ is not a subset of $X$ since there exists an element of $Y$ (namely, 0) that is not in $X$.

In general, the subset relation is described with the use of a universal quantifier since $A\subseteq B$ means that for each element $x$ of $U$, if $x\in A$, then $x\in B$. So when we negate this, we use an existential quantifier as follows:

So we see that $A⊈B$ means that there exists an $x$ in $U$ such that $x\in A$ and $x\notin B$.

Notice that if $A=\mathrm{\varnothing }$, then the conditional statement, "For each $x\in U$, if $x\in \mathrm{\varnothing }$, then $x\in B$" must be true since the hypothesis will always be false. Another way to look at this is to consider the following statement:

$$\mathrm{\varnothing }⊈B\text{ means that there exists an }x\in \mathrm{\varnothing }\text{ such that }x\notin B.$$

However, this statement must be false since there does not exist an $x$ in $\mathrm{\varnothing }$. Since this is false, we must conclude that $\mathrm{\varnothing }\subseteq B$. Although the facts that $\mathrm{\varnothing }\subseteq B$ and $B\subseteq B$ may not seem very important, we will use these facts later, and hence we summarize them in Theorem 5.1.

Theorem 5.1. For any set $B,\mathrm{\varnothing }\subseteq B$ and $B\subseteq B$.

In Section 2.3, we also defined two sets to be equal when they have precisely the same elements. For example,

$$\{x\in ℝ\mid x^2=4\}=\{-2,2\}.$$

If the two sets $A$ and $B$ are equal, then it must be true that every element of $A$ is an element of $B$, that is, $A\subseteq B$, and it must be true that every element of $B$ is
an element of $A$, that is, $B\subseteq A$. Conversely, if $A\subseteq B$ and $B\subseteq A$, then $A$ and $B$ must have precisely the same elements. This gives us the following test for set equality:

Theorem 5.2. Let $A$ and $B$ be subsets of some universal set $U$. Then $A=B$ if and only if $A\subseteq B$ and $B\subseteq A$.

5.1.4 Progress Check 5.3 (Using Set Notation)

Let the universal set be $U=\{1,2,3,4,5,6\}$, and let

$$A=\{1,2,4\},B=\{1,2,3,5\},C=\{x\in U\mid x^2\le 2\}.$$

In each of the following, fill in the blank with one or more of the symbols $\subset$, $\subseteq ,=,\ne ,\in$, or $\notin$ so that the resulting statement is true. For each blank, include all symbols that result in a true statement. If none of these symbols makes a true statement, write nothing in the blank.

$A\underset{<span\; data-alttext="underline"\; style="border-bottom:\; 1px\; solid\; black;\; display:\; inline-block;\; width:\; 100px">\; </span>}{}B$

$5\underset{<span\; data-alttext="underline"\; style="border-bottom:\; 1px\; solid\; black;\; display:\; inline-block;\; width:\; 100px">\; </span>}{}B$

$A\underset{<span\; data-alttext="underline"\; style="border-bottom:\; 1px\; solid\; black;\; display:\; inline-block;\; width:\; 100px">\; </span>}{}C$

$\{1,2\}\underset{<span\; data-alttext="underline"\; style="border-bottom:\; 1px\; solid\; black;\; display:\; inline-block;\; width:\; 100px">\; </span>}{}A$

$6\underset{<span\; data-alttext="underline"\; style="border-bottom:\; 1px\; solid\; black;\; display:\; inline-block;\; width:\; 100px">\; </span>}{}A$

$\mathrm{\varnothing }\underset{<span\; data-alttext="underline"\; style="border-bottom:\; 1px\; solid\; black;\; display:\; inline-block;\; width:\; 100px">\; </span>}{}A$

$\{5\}\underset{<span\; data-alttext="underline"\; style="border-bottom:\; 1px\; solid\; black;\; display:\; inline-block;\; width:\; 100px">\; </span>}{}B$

$\{1,2\}\underset{<span\; data-alttext="underline"\; style="border-bottom:\; 1px\; solid\; black;\; display:\; inline-block;\; width:\; 100px">\; </span>}{}C$

$\{4,2,1\}\underset{<span\; data-alttext="underline"\; style="border-bottom:\; 1px\; solid\; black;\; display:\; inline-block;\; width:\; 100px">\; </span>}{}A$

$B\underset{<span\; data-alttext="underline"\; style="border-bottom:\; 1px\; solid\; black;\; display:\; inline-block;\; width:\; 100px">\; </span>}{}\mathrm{\varnothing }$

5.1.5 More about Venn Diagrams

In Beginning Activity 2, we learned how to use Venn diagrams as a visual representation for sets, set operations, and set relationships. In that activity, we restricted ourselves to using two sets. We can, of course, include more than two sets in a Venn diagram. Figure 5.3 shows a general Venn diagram for three sets (including a shaded region that corresponds to $A\cap C$).

In this diagram, there are eight distinct regions, and each region has a unique reference number. For example, the set $A$ is represented by the combination of regions 1, 2, 4, and 5, whereas the set $C$ is represented by the combination of regions 4,5,6, and 7. This means that the set $A\cap C$ is represented by the combination of regions 4 and 5. This is shown as the shaded region in Figure 5.3.

Finally, Venn diagrams can also be used to illustrate special relationships between sets. For example, if $A\subseteq B$, then the circle representing $A$ should be completely contained in the circle for $B$. So if $A\subseteq B$, and we know nothing about

Figure 5.3: Venn Diagram for $A\cap C$

Figure 5.4: Venn Diagram Showing $A\subseteq B$

any relationship between the set $C$ and the sets $A$ and $B$, we could use the Venn diagram shown in Figure 5.4.

5.1.6 Progress Check 5.4 (Using Venn Diagrams)

Let $A,B$, and $C$ be subsets of a universal set $U$.

1. For each of the following, draw a Venn diagram for three sets and shade the region(s) that represent the specified set.

   1. $(A\cap B)\cap C$

   2. $(A\cap B)\cup C$

   3. $\left(A^c\cup B\right)$

   4. $A^c\cap (B\cup C)$

2. Draw the most general Venn diagram showing $B\subseteq (A\cup C)$.

3. Draw the most general Venn diagram showing $A\subseteq \left(B^c\cup C\right)$.

5.1.7 The Power Set of a Set

The symbol $\in$ is used to describe a relationship between an element of the universal set and a subset of the universal set, and the symbol $\subseteq$ is used to describe a relationship between two subsets of the universal set. For example, the number 5 is an integer, and so it is appropriate to write $5\in \mathbb{Z}$. It is not appropriate, however, to write $5\subseteq \mathbb{Z}$ since 5 is not a set. It is important to distinguish between 5 and $\{5\}$. The difference is that 5 is an integer and $\{5\}$ is a set consisting of one element. Consequently, it is appropriate to write $\{5\}\subseteq \mathbb{Z}$, but it is not appropriate to write $\{5\}\in \mathbb{Z}$. The distinction between these two symbols (5 and $\{5\}$) is important when we discuss what is called the power set of a given set.

Definition. If $A$ is a subset of a universal set $U$, then the set whose members are all the subsets of $A$ is called the power set of $A$. We denote the power set of $A$ by $𝒫(A)$. Symbolically, we write

$$𝒫(A)=\{X\subseteq U\mid X\subseteq A\}$$

That is, $X\in 𝒫(A)$ if and only if $X\subseteq A$.

When dealing with the power set of $A$, we must always remember that $\mathrm{\varnothing }\subseteq A$ and $A\subseteq A$. For example, if $A=\{a,b\}$, then the subsets of $A$ are

$$\mathrm{\varnothing },\{a\},\{b\},\{a,b\}.$$ (1)

We can write this as

$$𝒫(A)=\{\mathrm{\varnothing },\{a\},\{b\},\{a,b\}\}.$$

Now let $B=\{a,b,c\}$. Notice that $B=A\cup \{c\}$. We can determine the subsets of $B$ by starting with the subsets of $A$ in (1). We can form the other subsets of $B$ by taking the union of each set in (1) with the set $\{c\}$. This gives us the following subsets of $B$.

$$\{c\},\{a,c\},\{b,c\},\{a,b,c\}.$$ (2)

So the subsets of $B$ are those sets in (1) combined with those sets in (2). That is, the subsets of $B$ are

$$\mathrm{\varnothing },\{a\},\{b\},\{a,b\},\{c\},\{a,c\},\{b,c\},\{a,b,c\},$$ (3)

which means that

$$𝒫(B)=\{\mathrm{\varnothing },\{a\},\{b\},\{a,b\},\{c\},\{a,c\},\{b,c\},\{a,b,c\}\}.$$

Notice that we could write

$$\{a,c\}\subseteq B\text{ or that }\{a,c\}\in 𝒫(B)$$

Also, notice that $A$ has two elements and $A$ has four subsets, and $B$ has three elements and $B$ has eight subsets. Now, let $n$ be a nonnegative integer. The following result can be proved using mathematical induction. (See Exercise 17.)

Theorem 5.5. Let $n$ be a nonnegative integer and let $T$ be a subset of some universal set. If the set $T$ has $n$ elements, then the set $T$ has $2^n$ subsets. That is, $𝒫(T)$ has $2^n$ elements.

5.1.8 The Cardinality of a Finite Set

In our discussion of the power set, we were concerned with the number of elements in a set. In fact, the number of elements in a finite set is a distinguishing characteristic of the set, so we give it the following name.

Definition. The number of elements in a finite set $A$ is called the cardinality of $A$ and is denoted by $\mathrm{card}(A)$.

For example, $\mathrm{card}(\mathrm{\varnothing })=0;\mathrm{card}(\{a,b\})=2;\mathrm{card}(𝒫(\{a,b\}))=4$.

Theoretical Note: There is a mathematical way to distinguish between finite and infinite sets, and there is a way to define the cardinality of an infinite set. We will not concern ourselves with this at this time. More about the cardinality of finite and infinite sets is discussed in Chapter 9.

5.1.9 Standard Number Systems

We can use set notation to specify and help describe our standard number systems. The starting point is the set of natural numbers, for which we use the roster method.

$$\mathbb{N}=\{1,2,3,4,\mathrm{\dots }\}$$

The integers consist of the natural numbers, the negatives of the natural numbers, and zero. If we let ${\mathbb{N}}^{-}=\{\mathrm{\dots },-4,-3,-2,-1\}$, then we can use set union and write

$$\mathbb{Z}={\mathbb{N}}^{-}\cup \{0\}\cup \mathbb{N}.$$

So we see that $\mathbb{N}\subseteq \mathbb{Z}$, and in fact, $\mathbb{N}\subset \mathbb{Z}$.
We need to use set builder notation for the set $\mathbb{Q}$ of all rational numbers, which consists of quotients of integers.

$$\mathbb{Q}=\left\{\frac{m}{n}\right|m,n\in \mathbb{Z}\text{ and }n\ne 0\}$$

Since any integer $n$ can be written as $n=\frac{n}{1}$, we see that $\mathbb{Z}\subseteq \mathbb{Q}$.
We do not yet have the tools to give a complete description of the real numbers. We will simply say that the real numbers consist of the rational numbers and the irrational numbers. In effect, the irrational numbers are the complement of the set of rational numbers $\mathbb{Q}$ in $ℝ$. So we can use the notation ${\mathbb{Q}}^c=\{x\in ℝ\mid x\notin \mathbb{Q}\}$ and write

$$ℝ=\mathbb{Q}\cup {\mathbb{Q}}^c\text{ and }\mathbb{Q}\cap {\mathbb{Q}}^c=\mathrm{\varnothing }.$$

A number system that we have not yet discussed is the set of complex numbers. The complex numbers, $ℂ$, consist of all numbers of the form $a+bi$, where $a,b\in ℝ$ and $i=\sqrt{-1}$ (or $i^2=-1$). That is,

$$ℂ=\{a+bi\mid a,b\in ℝ\text{ and }i=\sqrt{-1}\}.$$

We can add and multiply complex numbers as follows: If $a,b,c,d\in ℝ$, then

$(a+bi)+(c+di)$ $=(a+c)+(b+d)i,\text{ and}$

$(a+bi)(c+di)$ $=ac+adi+bci+bd{i}^2$

$=(ac-bd)+(ad+bc)i.$

5.1.10 Exercises for Section 5.1

1. $(\star )$ Assume the universal set is the set of real numbers. Let

   Respond to each of the following questions. In each case, explain your answer.

   1. Is the set $A$ equal to the set $B$?

   2. Is the set $A$ a subset of the set $B$?

   3. Is the set $C$ equal to the set $D$?

   4. Is the set $C$ a subset of the set $D$?

   5. Is the set $A$ a subset of the set $D$?

2. $(\star )$

   1. Explain why the set $\{a,b\}$ is equal to the set $\{b,a\}$.

   2. Explain why the set $\{a,b,b,a,c\}$ is equal to the set $\{b,c,a\}$.

3. $(\star )$ Assume that the universal set is the set of integers. Let

   In each of the following, fill in the blank with one or more of the symbols $\subset$, $\subseteq ,⊈,=,\ne ,\in$, or $\notin$ so that the resulting statement is true. For each blank, include all symbols that result in a true statement. If none of these symbols makes a true statement, write nothing in the blank.

   $A\underset{<span\; data-alttext="underline"\; style="border-bottom:\; 1px\; solid\; black;\; display:\; inline-block;\; width:\; 100px">\; </span>}{}B$

   $5\underset{<span\; data-alttext="underline"\; style="border-bottom:\; 1px\; solid\; black;\; display:\; inline-block;\; width:\; 100px">\; </span>}{}C$

   $A\underset{<span\; data-alttext="underline"\; style="border-bottom:\; 1px\; solid\; black;\; display:\; inline-block;\; width:\; 100px">\; </span>}{}C$

   $\{1,2\}\underset{<span\; data-alttext="underline"\; style="border-bottom:\; 1px\; solid\; black;\; display:\; inline-block;\; width:\; 100px">\; </span>}{}A$

   $4\underset{<span\; data-alttext="underline"\; style="border-bottom:\; 1px\; solid\; black;\; display:\; inline-block;\; width:\; 100px">\; </span>}{}B$

   $\mathrm{card}(A)\underset{<span\; data-alttext="underline"\; style="border-bottom:\; 1px\; solid\; black;\; display:\; inline-block;\; width:\; 100px">\; </span>}{}\mathrm{card}(D)$

   $A\underset{<span\; data-alttext="underline"\; style="border-bottom:\; 1px\; solid\; black;\; display:\; inline-block;\; width:\; 100px">\; </span>}{}𝒫(A)$

   $\mathrm{\varnothing }\underset{<span\; data-alttext="underline"\; style="border-bottom:\; 1px\; solid\; black;\; display:\; inline-block;\; width:\; 100px">\; </span>}{}A$

   $\{5\}\underset{<span\; data-alttext="underline"\; style="border-bottom:\; 1px\; solid\; black;\; display:\; inline-block;\; width:\; 100px">\; </span>}{}C$

   $\{1,2,\}\underset{<span\; data-alttext="underline"\; style="border-bottom:\; 1px\; solid\; black;\; display:\; inline-block;\; width:\; 100px">\; </span>}{}B$

   $\{3,2,1\}\underset{<span\; data-alttext="underline"\; style="border-bottom:\; 1px\; solid\; black;\; display:\; inline-block;\; width:\; 100px">\; </span>}{}D$

   $D\underset{<span\; data-alttext="underline"\; style="border-bottom:\; 1px\; solid\; black;\; display:\; inline-block;\; width:\; 100px">\; </span>}{}\mathrm{\varnothing }$

   $\mathrm{card}(A)\underset{<span\; data-alttext="underline"\; style="border-bottom:\; 1px\; solid\; black;\; display:\; inline-block;\; width:\; 100px">\; </span>}{}\mathrm{card}(D)$

   $A\underset{<span\; data-alttext="underline"\; style="border-bottom:\; 1px\; solid\; black;\; display:\; inline-block;\; width:\; 100px">\; </span>}{}𝒫(B)$

4. $(\star )$ Write all of the proper subset relations that are possible using the sets of numbers $\mathbb{N},\mathbb{Z},\mathbb{Q}$, and $ℝ$.

5. $(\star )$ For each statement, write a brief, clear explanation of why the statement is true or why it is false.

   1. The set $\{a,b\}$ is a subset of $\{a,c,d,e\}$.

   2. The set $\{-2,0,2\}$ is equal to $\{x\in \mathbb{Z}\mid x$ is even and .

   3. The empty set $\mathrm{\varnothing }$ is a subset of $\{1\}$.

   4. If $A=\{a,b\}$, then the set $\{a\}$ is a subset of $𝒫(A)$.

6. Use the definitions of set intersection, set union, and set difference to write useful negations of these definitions. That is, complete each of the following sentences

   1. $(\star )$ $x\notin A\cap B$ if and only if ….

   2. $x\notin A\cup B$ if and only if ….

   3. $x\notin A-B$ if and only if ….

7. $(\star )$ Let $U=\{1,2,3,4,5,6,7,8,9,10\}$, and let
   $A=\{3,4,5,6,7\}$,
   $B=\{1,5,7,9\}$,
   $C=\{3,6,9\}$,
   $D=\{2,4,6,8\}$.

   Use the roster method to list all of the elements of each of the following sets.

   1. $A\cap B$

   2. $A\cup B$

   3. ${(A\cup B)}^c$

   4. $A^c\cap B^c$

   5. $(A\cup B)\cap C$

   6. $A\cap C$

   7. $B\cap C$

   8. $(A\cap C)\cup (B\cap C)$

   9. $B\cap D$

   10. ${(B\cap D)}^c$

   11. $A-D$

   12. $B-D$

   13. $(A-D)\cup (B-D)$

   14. $(A\cup B)-D$

8. Let $U=\mathbb{N}$, and let
   $A=\{x\in \mathbb{N}\mid x\ge 7\}$,
   $B=\{x\in \mathbb{N}\mid x$ is odd $\}$,
   $C=\{x\in \mathbb{N}\mid x$ is a multiple of 3$\}$,
   $D=\{x\in \mathbb{N}\mid x$ is even $\}$.

   Use the roster method to list all of the elements of each of the following sets.

   1. $A\cap B$

   2. $A\cup B$

   3. ${(A\cup B)}^c$

   4. $A^c\cap B^c$

   5. $(A\cup B)\cap C$

   6. $(A\cap C)\cup (B\cap C)$

   7. $B\cap D$

   8. ${(B\cap D)}^c$

   9. $A-D$

   10. $B-D$

   11. $(A-D)\cup (B-D)$

   12. $(A\cup B)-D$

9. Let $P,Q,R$, and $S$ be subsets of a universal set $U$. Assume that $(P-Q)\subseteq (R\cap S)$.

   1. Complete the following sentence:

      For each $x\in U$, if $x\in (P-Q)$, then $\mathrm{\dots }$.

   2. $(\star )$ Write a useful negation of the statement in Part (9a).

   3. Write the contrapositive of the statement in Part (9a).

10. Let $U$ be the universal set. Consider the following statement:

    For all $A$ and $B$ that are subsets of $U$, if $A\subseteq B$, then $B^c\subseteq A^c$.

    1. $(\star )$ Identify three conditional statements in the given statement.

    2. Write the contrapositive of this statement.

    3. Write the negation of this statement.

11. Let $A,B$, and $C$ be subsets of some universal set $U$. Draw a Venn diagram for each of the following situations.

    1. $A\subseteq C$

    2. $A\cap B=\mathrm{\varnothing }$

    3. $A⊈B,B⊈A,C\subseteq A$, and $C⊈B$

    4. $A\subseteq B,C\subseteq B$, and $A\cap C=\mathrm{\varnothing }$

12. Let $A,B$, and $C$ be subsets of some universal set $U$. For each of the following, draw a general Venn diagram for the three sets and then shade the indicated region.

    1. $A\cap B$

    2. $A\cap C$

    3. $(A\cap B)\cup (A\cap C)$

    4. $B\cup C$

    5. $A\cap (B\cup C)$

    6. $(A\cap B)-C$

13. We can extend the idea of consecutive integers (See Exercise (10) in Section 3.5) to represent four consecutive integers as $m,m+1,m+2$, and $m+3$, where $m$ is an integer. There are other ways to represent four consecutive integers. For example, if $k\in \mathbb{Z}$, then $k-1,k,k+1$, and $k+2$ are four consecutive integers.

    1. Prove that for each $n\in \mathbb{Z},n$ is the sum of four consecutive integers if and only if $n\equiv 2(mod4)$.

    2. Use set builder notation or the roster method to specify the set of integers that are the sum of four consecutive integers.

    3. Specify the set of all natural numbers that can be written as the sum of four consecutive natural numbers.

    4. Prove that for each $n\in \mathbb{Z},n$ is the sum of eight consecutive integers if and only if $n\equiv 4(mod8)$.

    5. Use set builder notation or the roster method to specify the set of integers that are the sum of eight consecutive integers.

    6. Specify the set of all natural numbers can be written as the sum of eight consecutive natural numbers.

14. One of the properties of real numbers is the so-called Law of Trichotomy, which states that if $a,b\in ℝ$, then exactly one of the following is true:

    • ;

    • $a=b$;

    • $a>b$.

    Is the following proposition concerning sets true or false? Either provide a proof that it is true or a counterexample showing it is false.

    If $A$ and $B$ are subsets of some universal set, then exactly one of the following is true:

    • $A\subseteq B$;

    • $A=B$;

    • $B\subseteq A$.

5.1.11 Explorations and Activities

1. Intervals of Real Numbers. In previous mathematics courses, we have frequently used subsets of the real numbers called intervals. There are some common names and notations for intervals. These are given in the following table, where it is assumed that $a$ and $b$ are real numbers and .

Table 5.1: Common Notations for Intervals

Interval Notation	Set Notation	Name
$(a,b)=$		Open interval from $a$ to $b$
$[a,b]=$	$\{x\in ℝ\mid a\le x\le b\}$	Closed interval from $a$ to $b$
$[a,b)=$		Half-open interval
$(a,b]=$		Half-open interval
$(a,+\mathrm{\infty })=$	$\{x\in ℝ\mid x>a\}$	Open ray
$(-\mathrm{\infty },b)=$		Open ray
$[a,+\mathrm{\infty })=$	$\{x\in ℝ\mid x\ge a\}$	Closed ray
$(-\mathrm{\infty },b]=$	$\{x\in ℝ\mid x\le b\}$	Closed ray

1. Is $(a,b)$ a proper subset of $(a,b]$? Explain.

2. Is $[a,b]$ a subset of $(a,+\mathrm{\infty })$? Explain.

3. Use interval notation to describe

   1. the intersection of the interval [ $-3,7$ ] with the interval (5,9 ];

   2. the union of the interval $[-3,7]$ with the interval $(5,9]$;

   3. the set difference $[-3,7]-(5,9]$.

4. Write the set $\{x\in ℝ||x|\le 0.01\}$ using interval notation.

5. Write the set $\{x\in ℝ||x|>2\}$ as the union of two intervals.

1. More Work with Intervals. For this exercise, use the interval notation described in Exercise 15.

   1. Determine the intersection and union of $[2,5]$ and $[-1,+\mathrm{\infty })$.

   2. Determine the intersection and union of $[2,5]$ and $[3.4,+\mathrm{\infty })$.

   3. Determine the intersection and union of $[2,5]$ and $[7,+\mathrm{\infty })$.

      Now let $a,b$, and $c$ be real numbers with .

   4. Explain why the intersection of $[a,b]$ and $[c,+\mathrm{\infty })$ is either a closed interval, a set with one element, or the empty set.

   5. Explain why the union of $[a,b]$ and $[c,+\mathrm{\infty })$ is either a closed ray or the union of a closed interval and a closed ray.

2. Proof of Theorem 5.5. To help with the proof by induction of Theorem 5.5, we first prove the following lemma. (The idea for the proof of this lemma was illustrated with the discussion of power set.)

   Lemma 5.6. Let $A$ and $B$ be subsets of some universal set. If $A=B\cup \{x\}$, where $x\notin B$, then any subset of $A$ is either a subset of $B$ or a set of the form $C\cup \{x\}$, where $C$ is a subset of $B$.

   Proof. Let $A$ and $B$ be subsets of some universal set, and assume that $A=B\cup \{x\}$ where $x\notin B$. Let $Y$ be a subset of $A$. We need to show that $Y$ is a subset of $B$ or that $Y=C\cup \{x\}$, where $C$ is some subset of $B$. There are two cases to consider: (1) $x$ is not an element of $Y$, and (2) $x$ is an element of $Y$.

   Case 1: Assume that $x\notin Y$. Let $y\in Y$. Then $y\in A$ and $y\ne x$. Since

   $$A=B\cup \{x\},$$

   this means that $y$ must be in $B$. Therefore, $Y\subseteq B$.
   Case 2: Assume that $x\in Y$. In this case, let $C=Y-\{x\}$. Then every element of $C$ is an element of $B$. Hence, we can conclude that $C\subseteq B$ and that $Y=C\cup \{x\}$.

   Cases (1) and (2) show that if $Y\subseteq A$, then $Y\subseteq B$ or $Y=C\cup \{x\}$, where $C\subseteq B$. $\mathrm{\square }$

   To begin the induction proof of Theorem 5.5, for each nonnegative integer $n$, we let $P(n)$ be, "If a finite set has exactly $n$ elements, then that set has exactly $2^n$ subsets."

   1. Verify that $P(0)$ is true. (This is the basis step for the induction proof.)

   2. Verify that $P(1)$ and $P(2)$ are true.

   3. Now assume that $k$ is a nonnegative integer and assume that $P(k)$ is true. That is, assume that if a set has $k$ elements, then that set has $2^k$ subsets. (This is the inductive assumption for the induction proof.)

   Let $T$ be a subset of the universal set with $\mathrm{card}(T)=k+1$, and let $x\in T$. Then the set $B=T-\{x\}$ has $k$ elements.
   Now use the inductive assumption to determine how many subsets $B$ has. Then use Lemma 5.6 to prove that $T$ has twice as many subsets as $B$. This should help complete the inductive step for the induction proof.