5 Set Theory

5.2 Proving Set Relationships

5.2.1 Beginning Activity 1 (Working with Two Specific Sets)

Let $S$ be the set of all integers that are multiples of 6, and let $T$ be the set of all even integers.

1. List at least four different positive elements of $S$ and at least four different negative elements of $S$. Are all of these integers even?

2. Use the roster method to specify the sets $S$ and $T$. (See Section 2.3 for a review of the roster method.) Does there appear to be any relationship between these two sets? That is, does it appear that the sets are equal or that one set is a subset of the other set?

3. Use set builder notation to specify the sets $S$ and $T$. (See Section 2.3 for a review of the set builder notation.)

4. Using appropriate definitions, describe what it means to say that an integer $x$ is a multiple of 6 and what it means to say that an integer $y$ is even.

5. In order to prove that $S$ is a subset of $T$, we need to prove that for each integer $x$, if $x\in S$, then $x\in T$.

Complete the know-show table in Table 5.1 for the proposition that $S$ is a subset of $T$.

This table is in the form of a proof method called the choose-an-element method. This method is frequently used when we encounter a universal quantifier in a statement in the backward process. (In this case, this is Step $Q1$.) The key is that we have to prove something about all elements in $\mathbb{Z}$. We can then add something to the forward process by choosing an arbitrary element from the set $S$. (This is done in Step P1.) This does not mean that we can choose a specific element of $S$. Rather, we must give the arbitrary element a name and use only the properties it has by being a member of the set $S$. In this case, the element is a multiple of 6 .

Step	Know	Reason
$P$	$S$ is the set of all integers that are multiples of 6. $T$ is the set of all even integers.	Hypothesis
P1	Let $x\in S$.	Choose an arbitrary element of $S$.
P2	$(\exists m\in \mathbb{Z})(x=6m)$	Definition of "multiple"
$\mathrm{⋮}$	$\mathrm{⋮}$	$\mathrm{⋮}$
Q2	$x$ is an element of $T$.	$x$ is even
$Q1$	$(\forall x\in \mathbb{Z})[(x\in S)\to (x\in T)]$	Step $P1$ and Step Q2
$Q$	$S\subseteq T$.	Definition of "subset"
Step	Show	Reason

Table 5.1: Know-show table for Beginning Activity 1

5.2.2 Beginning Activity 2 (Working with Venn Diagrams)

1. Draw a Venn diagram for two sets, $A$ and $B$, with the assumption that $A$ is a subset of $B$. On this Venn diagram, lightly shade the area corresponding to $A^c$. Then, determine the region on the Venn diagram that corresponds to $B^c$. What appears to be the relationship between $A^c$ and $B^c$? Explain.

2. Draw a general Venn diagram for two sets, $A$ and $B$. First determine the region that corresponds to the set $A-B$ and then, on the Venn diagram, shade the region corresponding to $A-(A-B)$ and shade the region corresponding to $A\cap B$. What appears to be the relationship between these two sets? Explain.

In this section, we will learn how to prove certain relationships about sets. Two of the most basic types of relationships between sets are the equality relation and the subset relation. So if we are asked a question of the form, "How are the sets $A$ and $B$ related?", we can answer the question if we can prove that the two sets are equal or that one set is a subset of the other set. There are other ways to answer this, but we will concentrate on these two for now. This is similar to asking a question about how two real numbers are related. Two real numbers can be related by the fact that they are equal or by the fact that one number is less than the other number.

5.2.3 The Choose-an-Element Method

The method of proof we will use in this section can be called the choose-anelement method. This method was introduced in Beginning Activity 1. This method is frequently used when we encounter a universal quantifier in a statement in the backward process. This statement often has the form

For each element with a given property, something happens.

Since most statements with a universal quantifier can be expressed in the form of a conditional statement, this statement could have the following equivalent form:

If an element has a given property, then something happens.

We will illustrate this with the proposition from Beginning Activity 1. This proposition can be stated as follows:
there exists an integer $m$ such that

$$x=6m.$$

Since $6=2\cdot 3$, this equation can be written in the form

$$x=2(3m).$$

By closure properties of the integers, $3m$ is an integer. Hence, this last equation proves that $x$ must be even. Therefore, we have shown that if $x$ is an element of $S$, then $x$ is an element of $T$, and hence that $S\subseteq T$.

Having proved that $S$ is a subset of $T$, we can now ask if $S$ is actually equal to $T$. The work we did in Beginning Activity 1 can help us answer this question. In that activity, we should have found several elements that are in $T$ but not in $S$. For example, the integer 2 is in $T$ since 2 is even but $2\notin S$ since 2 is not a multiple of 6. Therefore, $S\ne T$ and we can also conclude that $S$ is a proper subset of $T$.

One reason we do this in a "two-step" process is that it is much easier to work with the subset relation than the proper subset relation. The subset relation is defined by a conditional statement and most of our work in mathematics deals with proving conditional statements. In addition, the proper subset relation is a conjunction of two statements ($S\subseteq T$ and $S\ne T$) and so it is natural to deal with the two parts of the conjunction separately.

5.2.4 Progress Check 5.8 (Subsets and Set Equality)

Let $A=\{x\in \mathbb{Z}\mid x$ is a multiple of 9$\}$ and let $B=\{x\in \mathbb{Z}\mid x$ is a multiple of 3$\}$.

1. Is the set $A$ a subset of $B$? Justify your conclusion.

2. Is the set $A$ equal to the set $B$? Justify your conclusion.

5.2.5 Progress Check 5.9 (Using the Choose-an-Element Method)

The Venn diagram in Beginning Activity 2 suggests that the following proposition is true.

Proposition 5.10. Let $A$ and $B$ be subsets of the universal set $U$. If $A\subseteq B$, then $B^c\subseteq A^c$.

1. The conclusion of the conditional statement is $B^c\subseteq A^c$. Explain why we should try the choose-an-element method to prove this proposition.

2. Complete the following know-show table for this proposition and explain exactly where the choose-an-element method is used.

Step	Know	Reason
$P$	$A\subseteq B$	Hypothesis
$P1$	Let $x\in B^c$.	Choose an arbitrary element of $B^c$.
P2	($\forall t\in U$)(If $t\in A$, then $t\in B$).	Definition of "subset"
$\mathrm{⋮}$	$\mathrm{⋮}$	$\mathrm{⋮}$
Q1	($\forall t\in U)$ (If $t\in B^c$, then $t\in A^c$).
$Q$	$B^c\subseteq A^c$	Definition of "subset"
Step	Show	Reason

5.2.6 Proving Set Equality

One way to prove that two sets are equal is to use Theorem 5.2 and prove each of the two sets is a subset of the other set. In particular, let $A$ and $B$ be subsets of some universal set. Theorem 5.2 states that $A=B$ if and only if $A\subseteq B$ and $B\subseteq A$.

In Beginning Activity 2, we created a Venn diagram that indicated that $A-(A-B)=A\cap B$. Following is a proof of this result. Notice where the choose-an-element method is used in each case.

Proposition 5.11. Let $A$ and $B$ be subsets of some universal set. Then $A-(A-B)=A\cap B$.

Proof. Let $A$ and $B$ be subsets of some universal set. We will prove that $A-(A-B)=A\cap B$ by proving that $A-(A-B)\subseteq A\cap B$ and that $A\cap B\subseteq A-(A-B)$.

First, let $x\in A-(A-B)$. This means that

$$x\in A\text{ and }x\notin (A-B).$$

We know that an element is in ($A-B$) if and only if it is in $A$ and not in $B$. Since $x\notin (A-B)$, we conclude that $x\notin A$ or $x\in B$. However, we also know that $x\in A$ and so we conclude that $x\in B$. This proves that

$$x\in A\text{ and }x\in B.$$

This means that $x\in A\cap B$, and hence we have proved that $A-(A-B)\subseteq A\cap B$.

Now choose $y\in A\cap B$. This means that

$$y\in A\text{ and }y\in B.$$

We note that $y\in (A-B)$ if and only if $y\in A$ and $y\notin B$ and hence, $y\notin (A-B)$ if and only if $y\notin A$ or $y\in B$. Since we have proved that $y\in B$, we conclude that $y\notin (A-B)$, and hence, we have established that $y\in A$ and $y\notin (A-B)$. This proves that if $y\in A\cap B$, then $y\in A-(A-B)$ and hence, $A\cap B\subseteq A-(A-B)$.

Since we have proved that $A-(A-B)\subseteq A\cap B$ and $A\cap B\subseteq A-(A-B)$, we conclude that $A-(A-B)=A\cap B$.

5.2.7 Progress Check 5.12 (Set Equality)

Prove the following proposition. To do so, prove each set is a subset of the other set by using the choose-an-element method.

Proposition 5.13. Let $A$ and $B$ be subsets of some universal set. Then $A-B=A\cap B^c$.

5.2.8 Disjoint Sets

Earlier in this section, we discussed the concept of set equality and the relation of one set being a subset of another set. There are other possible relationships between two sets; one is that the sets are disjoint. Basically, two sets are disjoint if and only if they have nothing in common. We express this formally in the following definition.

Definition. Let $A$ and $B$ be subsets of the universal set $U$. The sets $A$ and $B$ are said to be disjoint provided that $A\cap B=\mathrm{\varnothing }$.

For example, the Venn diagram in Figure 5.5 shows two sets $A$ and $B$ with $A\subseteq B$. The shaded region is the region that represents $B^c$. From the Venn diagram, it appears that $A\cap B^c=\mathrm{\varnothing }$. This means that $A$ and $B^c$ are disjoint. The preceding example suggests that the following proposition is true:

$$\text{ If }A\subseteq B\text{, then }A\cap B^c=\mathrm{\varnothing }\text{. }$$

If we would like to prove this proposition, a reasonable "backward question" is, "How do we prove that a set (namely $A\cap B^c$) is equal to the empty set?"

Figure 5.5: Venn Diagram with $A\subseteq B$

This question seems difficult to answer since how do we prove that a set is empty? This is an instance where proving the contrapositive or using a proof by contradiction could be reasonable approaches. To illustrate these methods, let us assume the proposition we are trying to prove is of the following form:

$$\text{ If }P\text{, then }T=\mathrm{\varnothing }\text{. }$$

If we choose to prove the contrapositive or use a proof by contradiction, we will assume that $T\ne \mathrm{\varnothing }$. These methods can be outlined as follows:

• The contrapositive of "If $P$, then $T=\mathrm{\varnothing }$" is, "If $T\ne \mathrm{\varnothing }$, then $\neg P$." So in this case, we would assume $T\ne \mathrm{\varnothing }$ and try to prove $\neg P$.

• Using a proof by contradiction, we would assume $P$ and assume that $T\ne \mathrm{\varnothing }$. From these two assumptions, we would attempt to derive a contradiction.

One advantage of these methods is that when we assume that $T\ne \mathrm{\varnothing }$, then we know that there exists an element in the set $T$. We can then use that element in the rest of the proof. We will prove one of the conditional statements for Proposition 5.14 by proving its contrapositive. The proof of the other conditional statement associated with Proposition 5.14 is Exercise (10).

Proposition 5.14. Let $A$ and $B$ be subsets of some universal set. Then $A\subseteq B$ if and only if $A\cap B^c=\mathrm{\varnothing }$.

Proof. Let $A$ and $B$ be subsets of some universal set. We will first prove that if $A\subseteq B$, then $A\cap B^c=\mathrm{\varnothing }$, by proving its contrapositive. That is, we will prove

$$\text{ If }A\cap B^c\ne \mathrm{\varnothing }\text{, then }A⊈B\text{. }$$

So assume that $A\cap B^c\ne \mathrm{\varnothing }$. We will prove that $A⊈B$ by proving that there must exist an element $x$ such that $x\in A$ and $x\notin B$.

Since $A\cap B^c\ne \mathrm{\varnothing }$, there exists an element $x$ that is in $A\cap B^c$. This means that

$$x\in A\text{ and }x\in B^c.$$

Now, the fact that $x\in B^c$ means that $x\notin B$. Hence, we can conclude that

$$x\in A\text{ and }x\notin B.$$

This means that $A⊈B$, and hence, we have proved that if $A\cap B^c\ne \mathrm{\varnothing }$, then $A⊈B$, and therefore, we have proved that if $A\subseteq B$, then $A\cap B^c=\mathrm{\varnothing }$.

The proof that if $A\cap B^c=\mathrm{\varnothing }$, then $A\subseteq B$ is Exercise (10).

5.2.9 Progress Check 5.15 (Proving Two Sets Are Disjoint)

It has been noted that it is often possible to prove that two sets are disjoint by using a proof by contradiction. In this case, we assume that the two sets are not disjoint and hence, their intersection is not empty. Use this method to prove that the following two sets are disjoint.

$$A=\{x\in \mathbb{Z}\mid x\equiv 3(mod12)\}\text{ and }B=\{y\in \mathbb{Z}\mid y\equiv 2(mod8)\}.$$

5.2.10 A Final Comment

We have used the choose-an-element method to prove Propositions 5.7, 5.11, and 5.14. Proofs involving sets that use this method are sometimes referred to as element-chasing proofs. This name is used since the basic method is to choose an arbitrary element from one set and "chase it" until you prove it must be in another set.

5.2.11 Exercises for Section 5.2

1. $(\star )$ Let and let .

   1. Is $A\subseteq B$? Justify your conclusion with a proof or a counterexample.

   2. Is $B\subseteq A$? Justify your conclusion with a proof or a counterexample.

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

   1. Draw a Venn diagram with $A\subseteq B$ and $B\subseteq C$. Does it appear that $A\subseteq C\mathrm{?}$

   2. Prove the following proposition:

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

      Note: This may seem like an obvious result. However, one of the reasons for this exercise is to provide practice at properly writing a proof that one set is a subset of another set. So we should start the proof by assuming that $A\subseteq B$ and $B\subseteq C$. Then we should choose an arbitrary element of $A$.

3. $(\star )$ Let $A=\{x\in \mathbb{Z}\mid x\equiv 7(mod8)\}$ and $B=\{x\in \mathbb{Z}\mid x\equiv 3(mod4)\}$.

   1. List at least five different elements of the set $A$ and at least five elements of the set $B$.

   2. Is $A\subseteq B$? Justify your conclusion with a proof or a counterexample.

   3. Is $B\subseteq A$? Justify your conclusion with a proof or a counterexample.

4. Let $C=\{x\in \mathbb{Z}\mid x\equiv 7(mod9)\}$ and $D=\{x\in \mathbb{Z}\mid x\equiv 1(mod3)\}$.

   1. List at least five different elements of the set $C$ and at least five elements of the set $D$.

   2. Is $C\subseteq D$? Justify your conclusion with a proof or a counterexample.

   3. Is $D\subseteq C$? Justify your conclusion with a proof or a counterexample.

5. In each case, determine if $A\subseteq B,B\subseteq A,A=B$, or $A\cap B=\mathrm{\varnothing }$ or none of these.

   1. $(\star )$ $A=\{x\in \mathbb{Z}\mid x\equiv 2(mod3)\}$ and $B=\{y\in \mathbb{Z}\mid 6$ divides $(2y-4)\}$.

   2. $A=\{x\in \mathbb{Z}\mid x\equiv 3(mod4)\}$ and $B=\{y\in \mathbb{Z}\mid 3$ divides $(y-2)\}$.

   3. $(\star )$ $A=\{x\in \mathbb{Z}\mid x\equiv 1(mod5)\}$ and $B=\{y\in \mathbb{Z}\mid y\equiv 7(mod10)\}$.

6. To prove the following set equalities, it may be necessary to use some of the properties of positive and negative real numbers. For example, it may be necessary to use the facts that:

   • The product of two real numbers is positive if and only if the two real numbers are either both positive or both negative.

   • The product of two real numbers is negative if and only if one of the two numbers is positive and the other is negative.

   For example, if , then we can conclude that either (1) and $x-2>0$ or (2) $x>0$ and . However, in the first case, we must have and $x>2$, and this is impossible. Therefore, we conclude that $x>0$ and , which means that .

   Use the choose-an-element method to prove each of the following:

   3. $\{x\in ℝ\mid x^2\ge 4\}=\{x\in ℝ\mid x\le -2\}\cup \{x\in ℝ\mid x\ge 2\}$

7. Let $A$ and $B$ be subsets of some universal set $U$. Prove each of the following:

   1. $(\star )$ $A\cap B\subseteq A$

   2. $A\cap A=A$ ${}_{}{}^{\star }($ e) $A\cap \mathrm{\varnothing }=\mathrm{\varnothing }$ $(\star )$

   3. $A\subseteq A\cup B$

   4. $A\cup A=A$

   5. $A\cup \mathrm{\varnothing }=A$

8. Let $A$ and $B$ be subsets of some universal set $U$. From Proposition 5.10, we know that if $A\subseteq B$, then $B^c\subseteq A^c$. Now prove the following proposition:

   For all sets $A$ and $B$ that are subsets of some universal set $U,A\subseteq B$ if and only if $B^c\subseteq A^c$.

9. Is the following proposition true or false? Justify your conclusion with a proof or a counterexample.

   For all sets $A$ and $B$ that are subsets of some universal set $U$, the sets $A\cap B$ and $A-B$ are disjoint.

10. $(\star )$ Complete the proof of Proposition 5.14 by proving the following conditional statement:

    Let $A$ and $B$ be subsets of some universal set. If $A\cap B^c=\mathrm{\varnothing }$, then $A\subseteq B$.

11. Let $A,B,C$, and $D$ be subsets of some universal set $U$. Are the following propositions true or false? Justify your conclusions.

    1. If $A\subseteq B$ and $C\subseteq D$ and $A$ and $C$ are disjoint, then $B$ and $D$ are disjoint.

    2. If $A\subseteq B$ and $C\subseteq D$ and $B$ and $D$ are disjoint, then $A$ and $C$ are disjoint.

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

    1. If $A\subseteq B$, then $A\cap C\subseteq B\cap C$.

    2. If $A\subseteq B$, then $A\cup C\subseteq B\cup C$.

13. Let $A,B$, and $C$ be subsets of a universal set $U$. Are the following propositions true or false? Justify your conclusions.

    1. If $A\cap C\subseteq B\cap C$, then $A\subseteq B$.

    2. If $A\cup C\subseteq B\cup C$, then $A\subseteq B$.

    3. If $A\cup C=B\cup C$, then $A=B$.

    4. If $A\cap C=B\cap C$, then $A=B$.

    5. If $A\cup C=B\cup C$ and $A\cap C=B\cap C$, then $A=B$.

14. Prove the following proposition:

    For all sets $A,B$, and $C$ that are subsets of some universal set, if $A\cap B=A\cap C$ and $A^c\cap B=A^c\cap C$, then $B=C$.

15. Are the following biconditional statements true or false? Justify your conclusion. If a biconditional statement is found to be false, you should clearly determine if one of the conditional statements within it is true and provide a proof of this conditional statement.

    1. $(\star )$ For all subsets $A$ and $B$ of some universal set $U,A\subseteq B$ if and only if $A\cap B^c=\mathrm{\varnothing }$.

    2. $(\star )$ For all subsets $A$ and $B$ of some universal set $U,A\subseteq B$ if and only if $A\cup B=B$.

    3. For all subsets $A$ and $B$ of some universal set $U,A\subseteq B$ if and only if $A\cap B=A$.

    4. For all subsets $A,B$, and $C$ of some universal set $U,A\subseteq B\cup C$ if and only if $A\subseteq B$ or $A\subseteq C$.

    5. For all subsets $A,B$, and $C$ of some universal set $U,A\subseteq B\cap C$ if and only if $A\subseteq B$ and $A\subseteq C$.

16. Let $S,T,X$, and $Y$ be subsets of some universal set. Assume that

    1. $S\cup T\subseteq X\cup Y$;

    2. $S\cap T=\mathrm{\varnothing }$; and

    3. $X\subseteq S$.

    1. Using assumption

    2. , what conclusion(s) can be made if it is known that $a\in T$?

    3. Using assumption (ii), what conclusion(s) can be made if it is known that $a\in T$?

    4. Using all three assumptions, either prove that $T\subseteq Y$ or explain why it is not possible to do so.

17. Evaluation of Proofs.

    See the instructions for Exercise (19) from Section 3.1.

    1. Let $A,B$, and $C$ be subsets of some universal set. If $A⊈B$ and $B⊈C$, then $A⊈C$.

       Proof. We assume that $A,B$, and $C$ are subsets of some universal set and that $A⊈B$ and $B⊈C$. This means that there exists an element $x$ in $A$ that is not in $B$ and there exists an element $x$ that is in $B$ and not in $C$. Therefore, $x\in A$ and $x\notin C$, and we have proved that $A⊈C$.

    2. Let $A,B$, and $C$ be subsets of some universal set. If $A\cap B=A\cap C$, then $B=C$.

       Proof. We assume that $A\cap B=A\cap C$ and will prove that $B=C$. We will first prove that $B\subseteq C$.

       So let $x\in B$. If $x\in A$, then $x\in A\cap B$, and hence, $x\in A\cap C$. From this we can conclude that $x\in C$. If $x\notin A$, then $x\notin A\cap B$, and hence, $x\notin A\cap C$. However, since $x\notin A$, we may conclude that $x\in C$. Therefore, $B\subseteq C$.
       The proof that $C\subseteq B$ may be done in a similar manner. Hence, $B=C$.

    3. Let $A,B$, and $C$ be subsets of some universal set. If $A⊈B$ and $B\subseteq C$, then $A⊈C$.

       Proof. Assume that $A⊈B$ and $B\subseteq C$. Since $A⊈B$, there exists an element $x$ such that $x\in A$ and $x\notin B$. Since $B\subseteq C$, we may conclude that $x\notin C$. Hence, $x\in A$ and $x\notin C$, and we have proved that $A⊈C$.

5.2.12 Explorations and Activities

1. Using the Choose-an-Element Method in a Different Setting. We have used the choose-an-element method to prove results about sets. This method, however, is a general proof technique and can be used in settings other than set theory. It is often used whenever we encounter a universal quantifier in a statement in the backward process. Consider the following proposition.

Proposition 5.16. Let $a,b$, and $t$ be integers with $t\ne 0$. If $t$ divides $a$ and $t$ divides $b$, then for all integers $x$ and $y,t$ divides $(ax+by)$.

1. Whenever we encounter a new proposition, it is a good idea to explore the proposition by looking at specific examples. For example, let $a=20,b=12$, and $t=4$. In this case, $t\mid a$ and $t\mid b$. In each of the following cases, determine the value of $(ax+by)$ and determine if $t$ divides $(ax+by)$.

   1. $x=1,y=1$

   2. $x=1,y=-1$

   3. $x=2,y=2$

   4. $x=2,y=-3$

   5. $x=-2,y=3$

   6. $x=-2,y=-5$

2. Repeat Part (18a) with $a=21,b=-6$, and $t=3$.

   Notice that the conclusion of the conditional statement in this proposition involves the universal quantifier. So in the backward process, we would have
   $Q:$ For all integers $x$ and $y,t$ divides $ax+by$.

   The "elements" in this sentence are the integers $x$ and $y$. In this case, these integers have no "given property" other than that they are integers. The "something that happens" is that $t$ divides $(ax+by)$. This means that in the forward process, we can use the hypothesis of the proposition and choose integers $x$ and $y$. That is, in the forward process, we could have
   $P:a,b$, and $t$ are integers with $t\ne 0,t$ divides $a$ and $t$ divides $b$.

   P1: Let $x\in \mathbb{Z}$ and let $y\in \mathbb{Z}$.

3. Complete the following proof of Proposition 5.16.

   Proof. Let $a,b$, and $t$ be integers with $t\ne 0$, and assume that $t$ divides $a$ and $t$ divides $b$. We will prove that for all integers $x$ and $y,t$ divides $(ax+by)$.

   So let $x\in \mathbb{Z}$ and let $y\in \mathbb{Z}$. Since $t$ divides $a$, there exists an integer $m$ such that ….