Section3.1Sets

An underlying idea of mathematics is the concept of a collection of objects or a set.

Definition3.1.1.

A set is a collection of distinct objects, which are called the elements of the set. We will use capital letters to denote sets, for example $a\text{,}$ $B\text{,}$ $S\text{,}$ $T\text{,}$ etc. If $x$ is an element of a set $S\text{,}$ we use the notation $x \in S\text{.}$ As is frequently done in mathematics, if $x$ is not an element of a set $S\text{,}$ we denote this by $x \notin S\text{.}$ Two sets, $A$ and $B\text{,}$ are equal (denoted $A = B$) if and only if they have precisely the same elements.

Definition3.1.2.

A set which is comprised of some (or all) of the elements of $\mathbb U\text{,}$ some universal set, is called a subset of $\mathbb U$ and is denoted $S \subseteq \mathbb U\text{.}$ If $A \subseteq \mathbb U$ and $B \subseteq \mathbb U\text{,}$ we further state that $A$ is a subset of $B\text{,}$ denoted $A \subseteq B$ or $A \subseteq B\text{,}$ if each element of $A$ is also an element of $B\text{.}$ Moreover, if $A \subseteq B$ but $A \neq B\text{,}$ we say that $A$ is a proper subset of $B$ and write $A \subsetneq B\text{.}$

Let $\mathbb U = \{a, b, c, \ldots, z\}\text{,}$ $S = \{ a, b, s, u \}\text{,}$ $T = \{a, u\}\text{,}$ and $W = \{ b,d \}\text{.}$ The $S \subseteq \mathbb U\text{,}$ $T \subseteq \mathbb U\text{,}$ $W \subseteq \mathbb U\text{,}$ and $T \subseteq S\text{.}$ However, $W \not\subseteq S\text{,}$ $W \not\subseteq T\text{,}$ $T \not\subseteq W\text{,}$ and $S \not\subseteq W\text{.}$ We read $W \not\subseteq S$ as “$W$ is not a subset of $S\text{.}$” In addition, $S \subset \mathbb U\text{,}$ $T \subset \mathbb U\text{,}$ $W \subset \mathbb U\text{,}$ and $T \subset S\text{.}$

When referring to the definition of subset, you should note that to prove $A \subseteq B\text{,}$ one would naturally consider an arbitrary element $x$ of $A$ and prove that $x \in B\text{.}$ In other words, we must prove the conditional statement “If $x \in A\text{,}$ then $x \in B\text{.}$”

Without entering into a philosophical argument, we define $\emptyset$ to be the set with no elements, called the empty set, the void set, or the null set. This set is extremely useful and should be understood carefully.

By definition of subset, we must show each element in $\emptyset$ is also an element of $A$ (or $\mathbb U\text{,}$ if we are proving $\emptyset \subseteq \mathbb U$); however, since there are no elements in to check, the definition is satisfied.

Let us consider the proof above logically. Recall that $A \subseteq B$ is a conditional statement (if $x \in A\text{,}$ then $x \in B$). So we need to examine “If $x \in \emptyset\text{,}$ then $x \in A\text{.}$” But $\emptyset$ has no elements, so $x \in \emptyset$ is false, meaning the conditional is true.

The next definition introduces several basic ways of combining sets which are used throughout mathematics.

Definition3.1.6.

Let $\mathbb U$ be the universal set with $A$ and $B$ subsets of $\mathbb U\text{.}$ Then

• $A \cup B = \{ x \in \mathbb U \mid x \in A \text{ or } x \in B \}\text{,}$ which is called $A$ union $B\text{.}$
• $A \cap B = \{ x \in \mathbb U \mid x \in A \text{ and } x \in B \}\text{,}$ which is called $A$ intersect $B\text{.}$
• $\overline{A} = \{ x \in \mathbb U \mid x \notin A \}\text{,}$ which is called the complement of $A\text{.}$
• $A \setminus B = \{ x \in \mathbb U \mid x \in A \text{ or } x \notin B \}\text{,}$ which is read $A$ minus $B\text{.}$
• $A$ and $B$ are set to be disjoint if $A \cap B = \emptyset\text{.}$

While not sufficient for proof, Venn diagrams can be useful in visualizing these concepts (Figure 3.1.7–3.1.10).

TAKS CONNECTION.

How might a student apply the concept of set intersections to answer the following question taken from the 2006 Texas Assessment of Knowledge and Skills (TAKS) Grade 5 Mathematics test?

The Venn diagram below is used to classify counting numbers according to a set of rules.

Which one of the following numbers belongs in the region of the diagram marked by the question mark?

• A. 45
• B. 50
• C. 60
• D. 65
Definition3.1.11.

If $A$ is a set, then the power set of $A$ is the set $\mathcal P(A) = \{ B \mid B \subseteq A \}\text{.}$

If $A = \{ 1,2\}\text{,}$ then $\mathcal P(A) = \{ \emptyset, \{1 \}, \{2\}, A\}\text{.}$ If $B = \{ a, b, c \}\text{,}$ then $\mathcal P(B) = \{ \emptyset, \{ a \}, \{ b \}, \{ c \}, \{ a, b \}, \{ a, c \}, \{ b, c \}, B \}\text{.}$

Definition3.1.13.

If $A$ and $B$ are sets, then $A \times B = \{ (a, b) \mid a \in A \text{ and } b \in B \}$ is called the Cartesian product or the cross product of $A$ and $B\text{.}$

If $A = \{ 1,2\}$ and $B = \{ a, b, c \}\text{,}$ then $A \times B = \{ (1, a), (1, b), (1, c), (2, a), (2, b), (2, c)\}\text{.}$

We will prove (3) in Fact 3.1.15. That is, we will show $A \setminus B \subseteq A\text{.}$

Proof: Let $x \in A \setminus B\text{.}$ Then $x \in A$ but $x \notin B\text{.}$ By the definition of a subset $A \setminus B \subseteq A\text{.}$ That is, “if $x \in A \setminus B\text{,}$ then $x \in A \text{.}$”

We will prove (7) in Fact 3.1.15. That is, we will show $A \cup B = B \cup A\text{.}$

Proof: Let $x \in A \cup B\text{.}$ Then $x \in A$ or $x \in B$ by the definition of $A \cup B\text{.}$ Hence, $x \in B$ or $x \in A\text{.}$ By the definition of union $x \in B \cup A\text{.}$ We have argued by direct proof that “$x \in A \cup B\text{,}$ then $x \in B \cup A\text{.}$” Thus, $A \cup B \subseteq B \cup A\text{.}$ By reversing the proof, we can show that $B \cup A \subseteq A \cup B\text{.}$ Therefore, $A \cup B = B \cup A$

We will prove (16) in Fact 3.1.15. That is, we will show $\overline{A \cap B} = \overline{A} \cup \overline{B}\text{.}$

Proof: To show $\overline{A \cap B} = \overline{A} \cup \overline{B}\text{,}$ we again use the method of double inclusion. Let $x \in \overline{A \cap B}\text{.}$ Then $x \notin A \cap B\text{.}$ Recalling the definition of intersection, we notice that the statement $x \notin A \cap B$ parallels the logic statement $\negate( p \wedge q)\text{.}$ DeMorgan's Laws for logic tell us that $[\negate( p \wedge q)] \leftrightarrow [\negate p \; \vee \negate q]\text{.}$ So we now have $x \notin A$ or $x \notin B\text{;}$ hence, $x \in \overline{A}$ or $x \in \overline{B}\text{.}$ Thus, by definition of union, $x \in A \cup B\text{.}$ Consequently, $\overline{A \cap B} \subseteq \overline{A} \cup \overline{B}\text{.}$

To see that $\overline{A} \cup \overline{B} \subseteq \overline{A \cap B}$ let $y \in \overline{A} \cup \overline{B}\text{.}$ Then $y \in \overline{A}$ or $y \in \overline{B}\text{,}$ which means that $y \notin A$ or $y \notin B\text{.}$ Arguing as above, we have $y \notin A \cap B\text{.}$ Thus, $y \in \overline{A \cap B}\text{,}$ and $\overline{A} \cup \overline{B} \subseteq \overline{A \cap B}\text{.}$

As indicated, the proofs of the other parts of this fact are left as exercises.

Subsection3.1.1Historical Note

Unlike most areas of mathematics, which arise as a result of the cumulative efforts of many mathematicians, sometimes over several generations, set theory is the creation of a single individual. Georg Ferdinand Ludwig Phillip Cantor (27 June 1806–18 March 1871) was a German mathematician, born in Russia. Use internet and/or library resources to research his major contributions to the area of set theory, specifically the concept of cardinality and Cantor's Theorem.

Exercises3.1.2Exercises

1.

Let $\mathbb U = \{1, 2, \ldots 10 \}\text{,}$ $A = \{ 1, 2, 3, 4, 5 \}\text{,}$ $B = \{ 2, 3, 5 \}\text{,}$ $D = \{ 1, 3, 5, 7, 9 \}\text{,}$ and $E = \{ 2, 4, 6, 8, 10 \}\text{.}$ Label each of the statements below as True or False and explain.

1. $D$ and $E$ are disjoint.
2. $A \subseteq E\text{.}$
3. $B \subset A\text{.}$
4. $A \subset \mathbb U\text{.}$
5. $(A \cap D) \subset A\text{.}$
6. $(A \cup E) \subset \mathbb U\text{.}$
7. $(D \cup E) \subset \mathbb U\text{.}$
8. $(D \cup E) = \mathbb U\text{.}$
9. $6 \in D\text{.}$
10. $\{ 8 \} \in E\text{.}$
11. $\emptyset \subseteq B\text{.}$
12. $\{ 2, 3 \} \subseteq B\text{.}$
13. $5 \subseteq B\text{.}$
14. $\emptyset \subseteq \emptyset\text{.}$
15. $\overline{D} = E\text{.}$
16. $\overline{B \cup D} \subseteq E\text{.}$
2.

Using the sets in Exercise 3.1.2.1, find:

1. $\displaystyle \overline{B}$
2. $\displaystyle D \setminus A$
3. $\displaystyle \overline{D} \cap \overline{A}$
4. $\displaystyle \overline{D \cup A}$
5. $\displaystyle E \cap (B \cup D)$
6. $\displaystyle \overline{A} \cap (B \setminus D)$
7. $\displaystyle \overline{D \cap E}$
8. $\displaystyle \overline{D \setminus E}$
13.

Prove the second half of Part (13) in Fact 3.1.15

For each of the following problems, assume $A\text{,}$ $B\text{,}$ $C\text{,}$ and $D$ are subsets of some universal set $\mathbb U\text{.}$ In problems Exercise 3.1.2.21–3.1.2.33, prove that the statements are true.

21.

If $C \subseteq A$ or $C \subseteq B\text{,}$ then $C \subseteq A \cup B\text{.}$

22.

If $A \subseteq C$ and $B \subseteq C\text{,}$ then $A \cap B \subseteq C\text{.}$

23.

$A \setminus A = \emptyset\text{.}$

24.

$A \setminus (A \setminus B) \subseteq B\text{.}$

25.

If $A$ or $B$ are disjoint, then $B \subseteq \overline{A}\text{.}$

26.

If $A \subseteq C$ and $B \subseteq D\text{,}$ then $A \setminus D \subseteq C \setminus B\text{.}$

27.

$A \setminus (B \setminus C) = A \cap (\overline{B} \cup C)\text{.}$

28.

$(A \setminus B) \setminus C = A \setminus (B \cup C )\text{.}$

29.

$A \setminus (B \cup C) = (A \setminus B) \cap (A \setminus C)\text{.}$

30.

$A \subseteq B$ if and only if $A \cap B = A\text{.}$

31.

$A \subseteq B$ if and only if $A \cup B = B\text{.}$

32.

$B \subseteq A$ if and only if $A \cup \overline{B} = \mathbb U\text{.}$

33.

If $A \subseteq B$ and $C \subseteq D\text{,}$ then

1. $A \cup C \subseteq B \cup D$ and
2. $A \cap C \subseteq B \cap D\text{.}$
34.

Prove or disprove:

1. If $A \cup B = A \cup C\text{,}$ then $B = C\text{.}$
2. If $A \cap B = A \cap C\text{,}$ then $B = C\text{.}$
35.

Define $A \bigtriangleup B = (A \setminus B) \cup (B \setminus A)\text{.}$ Prove or disprove:

1. $A \bigtriangleup B = B \bigtriangleup A\text{.}$
2. $A \bigtriangleup (B \bigtriangleup C) = (A \bigtriangleup B) \bigtriangleup C\text{.}$
3. $A \bigtriangleup \emptyset = A\text{.}$
4. $A \bigtriangleup A = \emptyset\text{.}$
5. $A \bigtriangleup B = (A \cup B) \setminus (A \cap B)\text{.}$
6. $A \cap (B \bigtriangleup C) = (A \cap B) \bigtriangleup (A \cap C)\text{.}$
7. $A \cup (B \bigtriangleup C) = (A \cup B) \bigtriangleup (A \cup C)\text{.}$
8. $A \cap B = \emptyset$ if and only if $A \bigtriangleup B = A \cup B\text{.}$
36.

Draw Venn diagrams to illustrate various parts of Fact 3.1.15.

37.

For sets $A = \{1,2, 3, 4, 5\}\text{,}$ $B = \{ 3, 5, 7, 9\}\text{,}$ and $C = \{a, b \}\text{,}$ find:

1. $\mathcal P(C)\text{.}$
2. $A \times C\text{.}$
3. $C \times (A \cap B)\text{.}$
4. $(C \times A) \cap (C \times B)\text{.}$
38.

Prove or disprove: If $A, B \in \mathcal P(S)\text{,}$ then $A \cup B \in \mathcal P(S)\text{.}$

39.

Prove or disprove: If $A, B \in \mathcal P(S)\text{,}$ then $A \cap B \in \mathcal P(S)\text{.}$

40.

Is it true that $A \times \emptyset = \emptyset \times A = \emptyset\text{?}$ Justify your thinking.