Skip to main content

Section 5.2 Proving Set Relationships

Beginning Activity Beginning Activity 1: Working with Two Specific Sets
A4US

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\text{.}\) Are all of these integers even?

2.

Use the roster method to specify the sets \(S\) and \(T\text{.}\) (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\text{.}\) (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\text{,}\) we need to prove that for each integer \(x\text{,}\) if \(x \in S\text{,}\) then \(x \in T\)

Complete the know-show table in Table 5.11 for the proposition that \(S\) is a subset of \(T\text{.}\)

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\text{.}\)) The key is that we have to prove something about all elements in \(\Z\text{.}\) We can then add something to the forward process by choosing an arbitrary element from the set \(S\text{.}\) (This is done in Step \(P1\text{.}\)) This does not mean that we can choose a specific element of \(S\text{.}\) Rather, we must give the arbitrary element a name and use only the properties it has by being a member of the set \(S\text{.}\) In this case, the element is a multiple of 6.

Table 5.11. Know-show table for Beginning Activity 1
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\text{.}\) Choose an arbitrary element
of \(S\text{.}\)
\(P2\) \(\left( {\exists m \in \mathbb{Z}} \right) \left( {x = 6m} \right)\) Definition of “multiple”
\(\vdots\) \(\vdots\) \(\vdots\)
\(Q2\) \(x\) is an element of \(T\text{.}\) \(x\) is even
\(Q1\) \(\left( \forall x \in \Z \right) \left[ \left( x \in S \right) \to \left( x \in T \right) \right]\) Step \(P1\) and Step \(Q2\)
\(Q\) \(S \subseteq T\text{.}\) Definition of “subset”
Step Show Reason

Beginning Activity Beginning Activity 2: Working with Venn Diagrams
A4US

1.

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

2.

Draw a general Venn diagram for two sets, \(A\) and \(B\text{.}\) 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\text{.}\) 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.

Subsection The Choose-an-Element Method

The method of proof we will use in this section can be called the choose-an-element 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:
Let S be the set of all integers that are multiples of 6, and let T be the set of all even integers. Then S is a subset of T.
In Beginning Activity 1, we worked on a know-show table for this proposition. The key was that in the backward process, we encountered the following statement:
Each element of \(S\) is an element of \(T\) or, more precisely, if \(x \in S\text{,}\) then \(x \in T\text{.}\)

In this case, the “element” is an integer, the “given property” is that it is an element of \(S\text{,}\) and the “something that happens” is that the element is also an element of \(T\text{.}\) One way to approach this is to create a list of all elements with the given property and verify that for each one, the “something happens.” When the list is short, this may be a reasonable approach. However, as in this case, when the list is infinite (or even just plain long), this approach is not practical.

We overcome this difficulty by using the choose-an-element method, where we choose an arbitrary element with the given property. So in this case, we choose an integer \(x\) that is a multiple of 6. We cannot use a specific multiple of 6 (such as 12 or 24), but rather the only thing we can assume is that the integer satisfies the property that it is a multiple of 6. This is the key part of this method.

Whenever we choose an arbitrary element with a given property, we are not selecting a specific element. Rather, the only thing we can assume about the element is the given property.
It is important to realize that once we have chosen the arbitrary element, we have added information to the forward process. So in the know-show table for this proposition, we added the statement, “Let \(x \in S\)” to the forward process. Following is a completed proof of this proposition following the outline of the know-show table from Beginning Activity 1.

Proof.

Let \(S\) be the set of all integers that are multiples of 6, and let \(T\) be the set of all even integers. We will show that \(S\) is a subset of \(T\) by showing that if an integer \(x\) is an element of \(S\text{,}\) then it is also an element of \(T\text{.}\)

Let \(x \in S\text{.}\) (Note: The use of the word “let” is often an indication that the we are choosing an arbitrary element.) This means that \(x\) is a multiple of 6. Therefore, there exists an integer \(m\) such that

\begin{equation*} x = 6m\text{.} \end{equation*}

Since \(6 = 2 \cdot 3\text{,}\) this equation can be written in the form

\begin{equation*} x = 2( {3m})\text{.} \end{equation*}

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\text{,}\) then \(x\) is an element of \(T\text{,}\) and hence that \(S \subseteq T\text{.}\)

Having proved that \(S\) is a subset of \(T\text{,}\) we can now ask if \(S\) is actually equal to \(T\text{.}\) 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\text{.}\) 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\text{.}\)

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.

Progress Check 5.13. Subsets and Set Equality.

Let \(A = \left\{ x \in \mathbb{Z} \mid x \text{ is a multiple of 9 } \right\}\) and let \(B = \left\{ x \in \mathbb{Z} \mid x \text{ is a multiple of 3 } \right\}\text{.}\)

(a)

Is the set \(A\) a subset of \(B\text{?}\) Justify your conclusion.

Solution.

The set \(A\) is a subset of \(B\text{.}\) To prove this, we let \(x \in A\text{.}\) Then there exists an integer \(m\) such that \(x = 9m\text{,}\) which can be written as

\begin{equation*} x = 3 \left( 3m \right)\!\text{.} \end{equation*}

Since \(3m \in \Z\text{,}\) the last equation proves that \(x\) is a multiple of 3 and so \(x \in B\text{.}\) Therefore, \(A \subseteq B\text{.}\)

(b)

Is the set \(A\) equal to the set \(B\text{?}\) Justify your conclusion.

Solution.

The set \(A\) is not equal to the set \(B\text{.}\) We note that \(3 \in B\) but \(3 \notin A\text{.}\) Therefore, \(B \not \subseteq A\) and, hence, \(A \ne B\text{.}\)

Progress Check 5.14. Using the Choose-an-Element Method.

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

(a)

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

(b)

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\text{.}\) Choose an arbitrary element
of \(B^c\text{.}\)
\(P2\) If \(x \in A\text{,}\) then \(x \in B\text{.}\) Definition of “subset”
\(\vdots\) \(\vdots\) \(\vdots\)
\(Q1\) If \(x \in B^c\text{,}\) then \(x \in A^c\text{.}\)
\(Q\) \(B^c \subseteq A^c\) Definition of “subset”
Step Show Reason

Solution.

Step Know Reason
\(P\) \(A \subseteq B\) Hypothesis
\(P1\) Let \(x \in B^c\text{.}\) Choose an arbitrary element
of \(B^c\text{.}\)
\(P2\) If \(x \in A\text{,}\) then \(x \in B\text{.}\) Definition of “subset”
\(P3\) If \(x \notin B\text{,}\) then \(x \notin A\text{.}\) Contrapositive
\(P4\) If \(x \in B^c\text{,}\) then \(x \in A^c\text{.}\) Step \(P3\) and definition
of “complement”
\(Q2\) The element \(x\) is in \(A^c\text{.}\) Steps \(P1\) and \(P4\)
\(Q1\) Every element of \(B^c\) is an element of \(A^c\text{.}\) The choose-an-element
method with Steps \(P1\) and \(Q2\)
\(Q\) \(B^c \subseteq A^c\) Definition of “subset”

Subsection Proving Set Equality

One way to prove that two sets are equal is to use Theorem 5.4 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.4 states that \(A = B\) if and only if \(A \subseteq B\text{ and } B \subseteq A\text{.}\)

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

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)\text{.}\)

First, let \(x \in A - (A - B)\text{.}\) This means that

\begin{equation*} x \in A\text{ and } x \notin (A - B)\text{.} \end{equation*}

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

\begin{equation*} x \in A \text{ and } x \in B\text{.} \end{equation*}

This means that \(x \in A \cap B\text{,}\) and hence we have proved that \(A - (A - B) \subseteq A \cap B\text{.}\) Now choose \(y \in A \cap B\text{.}\) This means that

\begin{equation*} y \in A\text{ and } y \in B\text{.} \end{equation*}

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\text{.}\) Since we have proved that \(y \in B\text{,}\) we conclude that \(y \notin (A - B)\text{,}\) and hence, we have established that \(y \in A\) and \(y \notin (A - B)\text{.}\) This proves that if \(y \in A \cap B\text{,}\) then \(y \in A - (A - B)\) and hence, \(A \cap B \subseteq A - (A - B)\text{.}\)

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

Progress Check 5.17. 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.

Solution.
Proof.

Let \(A\) and \(B\) be subsets of some universal set. We will prove that \(A - B = A \cap B^c\) by proving that each set is a subset of the other set. We will first prove that \(A - B \subseteq A \cap B^c\text{.}\) Let \(x \in A - B\text{.}\) We then know that \(x \in A\) and \(x \notin B\text{.}\) However, \(x \notin B\) implies that \(x \in B^c\text{.}\) Hence, \(x \in A\) and \(x \in B^c\text{,}\) which means that \(x \in A \cap B^c\text{.}\) This proves that \(A - B \subseteq A \cap B^c\text{.}\)

To prove that \(A \cap B^c \subseteq A - B\text{,}\) we let \(y \in A \cap B^c\text{.}\) This means that \(y \in A\) and \(y \in B^c\text{,}\) and hence, \(y \in A\) and \(y \notin B\text{.}\) Therefore, \(y \in A - B\) and this proves that \(A \cap B^c \subseteq A - B\text{.}\) Since we have proved that each set is a subset of the other set, we have proved that \(A - B = A \cap B^c\text{.}\)

Subsection 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\text{.}\) The sets \(A\) and \(B\) are said to be disjoint provided that \(A \cap B = \emptyset\text{.}\)

For example, the Venn diagram in Figure 5.19 shows two sets \(A\) and \(B\) with \(A \subseteq B\text{.}\) The shaded region is the region that represents \(B^c\text{.}\)

A Venn diagram for the set A, which is a subset of B, which is itself a subset of the universal set U. The area outside of B is shaded.
Figure 5.19. Venn Diagram with \(A \subseteq B\)

From the Venn diagram, it appears that \(A \cap B^c = \emptyset\text{.}\) This means that \(A\) and \(B^c\) are disjoint. The preceding example suggests that the following proposition is true:

If \(A \subseteq B\text{,}\) then \(A \cap B^c = \emptyset\text{.}\)
If we would like to prove this proposition, a reasonable “backward question” is, “How do we prove that a set \(\left( \text{ namely } A \cap B^c \right)\) is equal to the empty set?”

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:

If \(P\text{,}\) then \(T = \emptyset\text{.}\)
If we choose to prove the contrapositive or use a proof by contradiction, we will assume that \(T \ne \emptyset\text{.}\) These methods can be outlined as follows:

  • The contrapositive of “If \(P\text{,}\) then \(T = \emptyset\)” is, “If \(T \ne \emptyset\text{,}\) then \(\mynot P\text{.}\)” So in this case, we would assume \(T \ne \emptyset\) and try to prove \(\mynot P\text{.}\)

  • Using a proof by contradiction, we would assume \(P\) and assume that \(T \ne \emptyset\text{.}\) From these two assumptions, we would attempt to derive a contradiction.

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

Proof.

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

If \(A \cap B^c \ne \emptyset\text{,}\) then \(A \not \subseteq B\text{.}\)
So assume that \(A \cap B^c \ne \emptyset\text{.}\) We will prove that \(A \not \subseteq B\) by proving that there must exist an element \(x\) such that \(x \in A\) and \(x \notin B\text{.}\)

Since \(A \cap B^c \ne \emptyset\text{,}\) there exists an element \(x\) that is in \(A \cap B^c\text{.}\) This means that

\begin{equation*} x \in A\text{ and } x \in B^c\text{.} \end{equation*}

Now, the fact that \(x \in B^c\) means that \(x \notin B\text{.}\) Hence, we can conclude that

\begin{equation*} x \in A\text{ and } x \notin B\text{.} \end{equation*}

This means that \(A \not \subseteq B\text{,}\) and hence, we have proved that if \(A \cap B^c \ne \emptyset\text{,}\) then \(A \not \subseteq B\text{,}\) and therefore, we have proved that if \(A \subseteq B\text{,}\) then \(A \cap B^c = \emptyset\text{.}\)

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

Progress Check 5.21. Proving Two Sets Are Disjoint.

Proof: 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.

\begin{equation*} A = \{ x \in \Z \mid x \equiv 3 \pmod 12 \} \text{ and } B = \{ y \in \Z \mid y \equiv 2 \pmod 8 \}\text{.} \end{equation*}
Solution.
Proof.

Let \(A = \{ x \in \Z \mid x \equiv 3 \pmod 12 \}\) and \(B = \{ y \in \Z \mid y \equiv 2 \pmod 8 \}\text{.}\) We will use a proof by contradiction to prove that \(A \cap B = \emptyset\text{.}\) So we assume that \(A \cap B \ne \emptyset\) and let \(x \in A \cap B\text{.}\) We can then conclude that \(x \equiv 3 \pmod 12\) and that \(y \equiv 2 \pmod 8\text{.}\) This means that there exist integers \(m\) and \(n\) such that

\begin{equation*} x = 3 + 12m \text{ and } x = 2 + 8n\text{.} \end{equation*}

By equating these two expressions for \(x\text{,}\) we obtain \(3 + 12m = 2 + 8n\text{,}\) and this equation can be rewritten as \(1 = 8n - 12m\text{.}\) This is a contradiction since 1 is an odd integer and \(8n - 12m\) is an even integer. We have therefore proved that \(A \cap B = \emptyset\text{.}\)

Subsection A Final Comment

We have used the choose-an-element method to prove Proposition 5.12, Proposition 5.16, and Proposition 5.20. 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.

Exercises Exercises

1.

Let \(A = \left\{ {\left. {x \in \mathbb{R}} \right| x^2 \lt 4} \right\}\) and let \(B = \left\{ {x \in \mathbb{R}\left. \right| x \lt 2} \right\}\text{.}\)

(a)

Is \(A \subseteq B\text{?}\) Justify your conclusion with a proof or a counterexample.

Answer.

The set \(A\) is a subset of \(B\text{.}\) To prove this, we let \(x \in A\text{.}\) Then \(- 2 \lt x \lt 2\text{.}\) Since \(x \lt 2\text{,}\) we conclude that \(x \in B\) and hence, we have proved that \(A\) is a subset of \(B\text{.}\)

(b)

Is \(B \subseteq A\text{?}\) Justify your conclusion with a proof or a counterexample.

Answer.

The set \(B\) is not a subset of \(A\text{.}\) There are many examples of a real number that is in \(B\) but not in \(A\text{.}\) For example, \(-3\) is in \(A\text{,}\) but \(-3\) is not in \(B\text{.}\)

2.

Let \(A\text{,}\) \(B\text{,}\) and \(C\) be subsets of a universal set \(U\text{.}\)

(a)

Draw a Venn diagram with \(A \subseteq B\) and \(B \subseteq C\text{.}\) Does it appear that \(A \subseteq C\text{?}\)

(b)

Prove the following proposition:

If \(A \subseteq B\) 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\text{.}\) Then we should choose an arbitrary element of \(A\text{.}\)

3.

Let \(A = \{ x \in \mathbb{Z} \mid x \equiv 7 \pmod 8 \}\) and \(B = \{ x \in \mathbb{Z} \mid x \equiv 3 \pmod 4 \}\text{.}\)

(a)

List at least five different elements of the set \(A\) and at least five elements of the set \(B\text{.}\)

Answer.

\(A = \{ \ldots, -9, -1, 7, 15, 23, \ldots \}\) and \(B = \{ \ldots, -9, -5, -1, 3, 7, 11, 15, \ldots \}\text{.}\)

(b)

Is \(A \subseteq B\text{?}\) Justify your conclusion with a proof or a counterexample.

Answer.

To prove that \(A \subseteq B\text{,}\) let \(x \in A\text{.}\) Then, \(x \equiv 7 \pmod 8\) and so, \(8 \mid \left( x - 7 \right)\text{.}\) This means that there exists an integer \(m\) such that \(x - 7 = 8m\text{.}\) By adding 4 to both sides of this equation, we see that \(x - 3 = 8m + 4\text{,}\) or \(x - 3 = 4 \left( 2m + 1 \right)\text{.}\) From this, we conclude that \(4 \mid \left( x - 3 \right)\) and that \(x \equiv 3 \pmod 4\text{.}\) Hence, \(x \in B\text{.}\)

(c)

Is \(B \subseteq A\text{?}\) Justify your conclusion with a proof or a counterexample.

Answer.

\(B \not \subseteq A\text{.}\) For example, \(3 \in B\) and \(3 \notin A\text{.}\)

4.

Let \(C = \{ x \in \mathbb{Z} \mid x \equiv 7 \pmod {9} \}\) and \(D = \{ x \in \mathbb{Z} \mid x \equiv 1 \pmod {3} \}\text{.}\)

(a)

List at least five different elements of the set \(C\) and at least five elements of the set \(D\text{.}\)

(b)

Is \(C \subseteq D\text{?}\) Justify your conclusion with a proof or a counterexample.

(c)

Is \(D \subseteq C\text{?}\) Justify your conclusion with a proof or a counterexample.

5.

In each case, determine if \(A \subseteq B\text{,}\) \(B \subseteq A\text{,}\) \(A = B\text{,}\) or \(A \cap B = \emptyset\) or none of these.

(a)

\(A = \left\{ x \in \Z \mid x \equiv 2 \pmod 3 \right\}\) and \(B = \left\{ y \in \Z \mid 6 \text{ divides } (2y - 4) \right\}\text{.}\)

Answer.

We will prove that \(A = B\text{.}\) Notice that if \(x \in A\text{,}\) then there exists an integer \(m\) such that \(x - 2 = 3m\text{.}\) We can use this equation to see that \(2x - 4 = 6m\) and so 6 divides \((2x - 4)\text{.}\) Therefore, \(x \in B\) and hence, \(A \subseteq B\text{.}\) Conversely, if \(y \in B\text{,}\) then there exists an integer \(m\) such that \(2y - 4 = 6m\text{.}\) Hence, \(y - 2 = 3m\text{,}\) which implies that \(y \equiv 2 \pmod 83\) and \(y \in A\text{.}\) Therefore, \(B \subseteq A\text{.}\)

(b)

\(A = \left\{ x \in \Z \mid x \equiv 3 \pmod 4 \right\}\) and \(B = \left\{ y \in \Z \mid 3 \text{ divides } (y - 2) \right\}\text{.}\)

(c)

\(A = \left\{ x \in \Z \mid x \equiv 1 \pmod 5 \right\}\) and \(B = \left\{ y \in \Z \mid y \equiv 7 \pmod 10 \right\}\text{.}\)

Answer.

\(A \cap B = \emptyset\text{.}\) To prove this, we will use a proof by contradiction and assume that \(A \cap B \ne \emptyset\text{.}\) So there exists an \(x\) in \(A \cap B\text{.}\) We can then conclude that there exist integers \(m\) and \(n\) such that \(x - 1 = 5m\) and \(x - y = 10n\text{.}\) So \(x = 5m + 1\) and \(x = 10n + 7\text{.}\) We then see that

\begin{align*} 5m + 1 \amp = 10n + 7\\ 5(m - 2n) \amp = 6 \end{align*}

The last equation implies that 5 divides 6, and this is a contradiction.

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 \(x \left( x - 2 \right) \lt 0\text{,}\) then we can conclude that either (1) \(x \lt 0\) and \(x - 2 > 0\) or (2) \(x > 0\) and \(x - 2 \lt 0\text{.}\) However, in the first case, we must have \(x \lt 0\) and \(x > 2\text{,}\) and this is impossible. Therefore, we conclude that \(x > 0\) and \(x - 2 \lt 0\text{,}\) which means that \(0 \lt x \lt 2\text{.}\)

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

(a)

\(\left\{x \in \R \mid x^2 - 3x - 10 \lt 0 \right\} = \left\{ x \in \R \mid -2 \lt x \lt 5 \right\}\)

(b)

\(\left\{x \in \R \mid x^2 - 5x + 6 \lt 0 \right\} = \left\{ x \in \R \mid 2 \lt x \lt 3 \right\}\)

(c)

\(\left\{ x \in \R \mid x^2 \geq 4 \right\} = \left\{ x \in \R \mid x \leq -2 \right\} \cup \left\{ x \in \R \mid x \geq 2 \right\}\)

7.

Let \(A\) and \(B\) be subsets of some universal set \(U\text{.}\) Prove each of the following:

(a)

\(A \cap B \subseteq A\)

Answer.

Let \(x \in A \cap B\text{.}\) Then, \(x \in A\) and \(x \in B\text{.}\) This proves that if \(x \in A \cap B\text{,}\) then \(x \in A\text{,}\) and hence, \(A \cap B \subseteq A\text{.}\)

(b)

\(A \subseteq A \cup B\)

Answer.

Let \(x \in A\text{.}\) Then, the statement “\(x \in A\) or \(x \in B\)” is true. Hence, \(A \subseteq A \cup B\text{.}\)

(c)

\(A \cap A = A\)

(d)

\(A \cup A = A\)

(e)

\(A \cap \emptyset = \emptyset\)

Answer.

By Theorem 5.3, \(\emptyset \subseteq A \cap \emptyset\text{.}\) By Part (a), \(A \cap \emptyset \subseteq \emptyset\text{.}\) Therefore, \(A \cap \emptyset = \emptyset\text{.}\)

(f)

\(A \cup \emptyset = A\)

8.

Let \(A\) and \(B\) be subsets of some universal set \(U\text{.}\) From Proposition 5.15, we know that if \(A \subseteq B\text{,}\) then \(B^c \subseteq A^c\text{.}\) Now prove the following proposition:

For all sets \(A\) and \(B\) that are subsets of some universal set \(U\text{,}\) \(A \subseteq B\) if and only if \(B^c \subseteq A^c\text{.}\)

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\text{,}\) the sets \(A \cap B\) and \(A - B\) are disjoint.

10.

Complete the proof of Proposition 5.20 by proving the following conditional statement:

Let \(A\) and \(B\) be subsets of some universal set. If \(A \cap B^c = \emptyset\text{,}\) then \(A \subseteq B\) .

Hint.

Start with, “Let \(x \in A\text{.}\)” Then use the assumption that \(A \cap B^c = \emptyset\) to prove that \(x\) must be in \(B\text{.}\)

11.

Let \(A\text{,}\) \(B\text{,}\) \(C\text{,}\) and \(D\) be subsets of some universal set \(U\text{.}\) Are the following propositions true or false? Justify your conclusions.

(a)

If \(A \subseteq B\) and \(C \subseteq D\) and \(A\) and \(C\) are disjoint, then \(B\) and \(D\) are disjoint.

(b)

If \(A \subseteq B\) and \(C \subseteq D\) and \(B\) and \(D\) are disjoint, then \(A\) and \(C\) are disjoint.

12.

Let \(A\text{,}\) \(B\text{,}\) and \(C\) be subsets of a universal set \(U\text{.}\) Prove:

(a)

If \(A \subseteq B\text{,}\) then \(A \cap C \subseteq B \cap C\text{.}\)

Answer.

Let \(x \in A \cap C\text{.}\) Then \(x \in A\) and \(x \in C\text{.}\) Since we are assuming that \(A \subseteq B\text{,}\) we see that \(x \in B\) and \(x \in C\text{.}\) This proves that \(A \cap C \subseteq B \cap C\text{.}\)

(b)

If \(A \subseteq B\text{,}\) then \(A \cup C \subseteq B \cup C\text{.}\)

13.

Let \(A\text{,}\) \(B\text{,}\) and \(C\) be subsets of a universal set \(U\text{.}\) Are the following propositions true or false? Justify your conclusions.

(a)

If \(A \cap C \subseteq B \cap C\text{,}\) then \(A \subseteq B\text{.}\)

(b)

If \(A \cup C \subseteq B \cup C\text{,}\) then \(A \subseteq B\text{.}\)

(c)

If \(A \cup C = B \cup C\text{,}\) then \(A = B\text{.}\)

(d)

If \(A \cap C = B \cap C\text{,}\) then \(A = B\text{.}\)

(e)

If \(A \cup C = B \cup C\) and \(A \cap C = B \cap C\text{,}\) then \(A = B\text{.}\)

14.

Prove the following proposition:

For all sets \(A\text{,}\) \(B\text{,}\) 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\text{,}\) then \(B = C\text{.}\)

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.

(b)

For all subsets \(A\) and \(B\) of some universal set \(U\text{,}\) \(A \subseteq B\) if and only if \(A \cup B = B\text{.}\)

Answer.

To prove “If \(A \subseteq B\text{,}\) then \(A \cup B = B\text{,}\)” first note that if \(x \in B\text{,}\) then \(x \in A \cup B\) and, hence, \(B \subseteq A \cup B\text{.}\) Now let \(x \in A \cup B\) and note that since \(A \subseteq B\text{,}\) if \(x \in A\text{,}\) then \(x \in B\text{.}\) Use this to argue that under the assumption that \(A \subseteq B\text{,}\) \(A \cup B \subseteq B\text{.}\) To prove “If \(A \cup B = B\text{,}\) then \(A \subseteq B\text{,}\)” start with, Let \(x \in A\) and use this assumption to prove that \(x\) must be an element of \(B\text{.}\)

(c)

For all subsets \(A\) and \(B\) of some universal set \(U\text{,}\) \(A \subseteq B\) if and only if \(A \cap B = A\text{.}\)

(d)

For all subsets \(A\text{,}\) \(B\text{,}\) and \(C\) of some universal set \(U\text{,}\) \(A \subseteq B \cup C\) if and only if \(A \subseteq B\) or \(A \subseteq C\text{.}\)

(e)

For all subsets \(A\text{,}\) \(B\text{,}\) and \(C\) of some universal set \(U\text{,}\) \(A \subseteq B \cap C\) if and only if \(A \subseteq B\) and \(A \subseteq C\text{.}\)

16.

Let \(S\text{,}\) \(T\text{,}\) \(X\text{,}\) and \(Y\) be subsets of some universal set. Assume that

  1. \(S \cup T \subseteq X \cup Y\text{;}\)

  2. \(S \cap T = \emptyset\text{;}\) and

  3. \(X \subseteq S\text{.}\)

(a)

Using assumption (i), what conclusion(s) can be made if it is known that \(a \in T\text{?}\)

(b)

Using assumption (ii), what conclusion(s) can be made if it is known that \(a \in T\text{?}\)

(c)

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.

(a)
Proposition

Let \(A\text{,}\) \(B\text{,}\) and \(C\) be subsets of some universal set. If \(A \not \subseteq B\) and \(B \not \subseteq C\text{,}\) then \(A \not \subseteq C\text{.}\)

Proof

We assume that \(A\text{,}\) \(B\text{,}\) and \(C\) are subsets of some universal set and that \(A \not \subseteq B\) and \(B \not \subseteq C\text{.}\) 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\text{.}\) Therefore, \(x \in A\) and \(x \notin C\text{,}\) and we have proved that \(A \not \subseteq C\text{.}\)

(b)
Proposition

Let \(A\text{,}\) \(B\text{,}\) and \(C\) be subsets of some universal set. If \(A \cap B = A \cap C\text{,}\) then \(B = C\text{.}\)

Proof

We assume that \(A \cap B = A \cap C\) and will prove that \(B = C\text{.}\) We will first prove that \(B \subseteq C\text{.}\)

So let \(x \in B\text{.}\) If \(x \in A\text{,}\) then \(x \in A \cap B\text{,}\) and hence, \(x \in A \cap C\text{.}\) From this we can conclude that \(x \in C\text{.}\) If \(x \notin A\text{,}\) then \(x \notin A \cap B\text{,}\) and hence, \(x \notin A \cap C\text{.}\) However, since \(x \notin A\text{,}\) we may conclude that \(x \in C\text{.}\) Therefore, \(B \subseteq C\text{.}\)

The proof that \(C \subseteq B\) may be done in a similar manner. Hence, \(B = C\text{.}\)

(c)
Proposition

Let \(A\text{,}\) \(B\text{,}\) and \(C\) be subsets of some universal set. If \(A \not \subseteq B\) and \(B \subseteq C\text{,}\) then \(A \not \subseteq C\text{.}\)

Proof

Assume that \(A \not \subseteq B\) and \(B \subseteq C\text{.}\) Since \(A \not \subseteq B\text{,}\) there exists an element \(x\) such that \(x \in A\) and \(x \notin B\text{.}\) Since \(B \subseteq C\text{,}\) we may conclude that \(x \notin C\text{.}\) Hence, \(x \in A\) and \(x \notin C\text{,}\) and we have proved that \(A \not \subseteq C\text{.}\)

Activity 30. 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.

(a)

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\text{,}\) \(b = 12\text{,}\) and \(t = 4\text{.}\) In this case, \(t \mid a\) and \(t \mid b\text{.}\) In each of the following cases, determine the value of \(\left(ax + by \right)\) and determine if \(t\) divides \(\left(ax + by\right)\text{.}\)

(i)

\(x=1, y=1\)

(ii)

\(x=1, y=-1\)

(iii)

\(x=2, y=2\)

(iv)

\(x=2, y=-3\)

(v)

\(x=-2, y=3\)

(vi)

\(x=-2, y=-5\)

(b)

Repeat Task 30.a with \(a = 21\text{,}\) \(b = - 6\text{,}\) and \(t = 3\text{.}\)

Notice that the conclusion of the conditional statement in this proposition involves the universal quantifier. So in the backward process, we would have

\(Q\text{:}\) For all integers \(x\) and \(y\text{,}\) \(t\) divides \(ax + by\text{.}\)
The “elements” in this sentence are the integers \(x\) and \(y\text{.}\) In this case, these integers have no “given property” other than that they are integers. The “something that happens” is that \(t\) divides \(\left(ax + by\right)\text{.}\) This means that in the forward process, we can use the hypothesis of the proposition and choose integers \(x\) and \(y\text{.}\) That is, in the forward process, we could have
\(P\text{:}\) \(a\text{,}\) \(b\text{,}\) and \(t\) are integers with \(t \ne 0\text{,}\) \(t\) divides \(a\) and \(t\) divides \(b\text{.}\) \item \(P1\text{:}\) Let \(x \in \Z\) and let \(y \in \Z\text{.}\)

(c)

Complete the following proof of Proposition 5.22.

Proof.

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

So let \(x \in \Z\) and let \(y \in \Z\text{.}\) Since \(t\) divides \(a\text{,}\) there exists an integer \(m\) such that \(\ldots \text{.}\)