Skip to main content
\(\newcommand{\identity}{\mathrm{id}} \newcommand{\notdivide}{{\not{\mid}}} \newcommand{\notsubset}{\not\subset} \newcommand{\lcm}{\operatorname{lcm}} \newcommand{\gf}{\operatorname{GF}} \newcommand{\inn}{\operatorname{Inn}} \newcommand{\aut}{\operatorname{Aut}} \newcommand{\Hom}{\operatorname{Hom}} \newcommand{\cis}{\operatorname{cis}} \newcommand{\chr}{\operatorname{char}} \newcommand{\Null}{\operatorname{Null}} \renewcommand{\vec}[1]{\mathbf{#1}} \newcommand{\lt}{ < } \newcommand{\gt}{ > } \newcommand{\amp}{ & } \)

Section4.1Methods of Proof for Sets

If \(A\), \(B\), and \(C\) are arbitrary sets, is it always true that \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\)? There are a variety of ways that we could attempt to prove that this distributive law for intersection over union is indeed true We start with a common “non-proof” and then work toward more acceptable methods.

Subsection4.1.1Examples and Counterexamples

We could, for example, let \(A = \{1, 2\}\), \(B = \{5, 8, 10\}\), and \(C = \{3, 2, 5\}\), and determine whether the distributive law is true for these values of \(A\), \(B\), and \(C\). In doing this we will have only determined that the distributive law is true for this one example. It does not prove the distributive law for all possible sets \(A\), \(B\), and \(C\) and hence is an invalid method of proof. However, trying a few examples has considerable merit insofar as it makes us more comfortable with the statement in question, and indeed if the statement is not true for the example, we have disproved the statement.

Definition4.1.1Counterexample

An example that disproves a statement is called a counterexample.

Example4.1.2Disproving distributivity of addition over multiplication

From basic algebra we learned that multiplication is distributive over addition. Is addition distributive over multiplication? That is, is \(a + (b \cdot c) = (a + b) \cdot (a + c)\) always true? If we choose the values \(a = 3\), \(b = 4\), and \(c = 1\), we find that \(3 + (4 \cdot 1) \neq (3 + 4)\cdot (3 + 1)\). Therefore, this set of values serves as a counterexample to a distributive law of addition over multiplication.

Subsection4.1.2Proof Using Venn Diagrams

In this method, we illustrate both sides of the statement via a Venn diagram and determine whether both Venn diagrams give us the same “picture,” For example, the left side of the distributive law is developed in Figure 4.1.3 and the right side in Figure 4.1.4. Note that the final results give you the same shaded area.

The advantage of this method is that it is relatively quick and mechanical. The disadvantage is that it is workable only if there are a small number of sets under consideration. In addition, it doesn't work very well in a static environment like a book or test paper. Venn diagrams tend to work well if you have a potentially dynamic environment like a blackboard or video.

Development of the left side of the distributive law for sets
Figure4.1.3Development of the left side of the distributive law for sets
Development of the right side of the distributive law for sets
Figure4.1.4Development of the right side of the distributive law for sets

Subsection4.1.3Proof using Set-membership Tables

Let \(A\) be a subset of a universal set \(U\) and let \(u\in U\). To use this method we note that exactly one of the following is true: \(u \in A\) or \(u\notin A\). Denote the situation where \(u \in A\) by 1 and that where \(u \notin A\) by 0. Working with two sets, \(A\) and \(B\), and if \(u \in U\), there are four possible outcomes of “where \(u\) can be.” What are they? The set-membership table for \(A \cup B\) is:

\(A\) \(B\) \(A \cup B\)
0 0 0
0 1 1
1 0 1
1 1 1
Table4.1.5Membership Table for \(A \cup B\)

This table illustrates that \(u\in A \cup B\) if and only if \(u\in A\) or \(u \in B\).

In order to prove the distributive law via a set-membership table, write out the table for each side of the set statement to be proved and note that if \(S\) and \(T\) are two columns in a table, then the set statement \(S\) is equal to the set statement \(T\) if and only if corresponding entries in each row are the same.

To prove \(A \cap (B \cup C) = (A \cap B) \cup (A \cap C)\), first note that the statement involves three sets, \(A\), \(B\), and \(C\), so there are \(2^3= 8\) possibilities for the membership of an element in the sets.

\(A\) \(B\) \(C\) \(B \cup C\) \(A \cap B\) \(A \cap C\) \(A \cap (B \cup C)\) \( (A \cap B) \cup (A \cap C)\)
0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0
0 1 0 1 0 0 0 0
0 1 1 1 0 0 0 0
1 0 0 0 0 0 0 0
1 0 1 1 0 1 1 1
1 1 0 1 1 0 1 1
1 1 1 1 1 1 1 1
Table4.1.6Membership table to prove the distributive law of intersection over union

Since each entry in Column 7 is the same as the corresponding entry in Column 8, we have shown that \(A\cap (B \cup C) = (A\cap B) \cup (A \cap C)\) for any sets \(A\), \(B\), and \(C\). The main advantage of this method is that it is mechanical. The main disadvantage is that it is reasonable to use only for a relatively small number of sets. If we are trying to prove a statement involving five sets, there are \(2^5 = 32\) rows, which would test anyone's patience doing the work by hand.

Subsection4.1.4Proof Using Definitions

This method involves using definitions and basic concepts to prove the given statement. This procedure forces one to learn, relearn, and understand basic definitions and concepts. It helps individuals to focus their attention on the main ideas of each topic and therefore is the most useful method of proof. One does not learn a topic by memorizing or occasionally glancing at core topics, but by using them in a variety of contexts. The word proof panics most people; however, everyone can become comfortable with proofs. Do not expect to prove every statement immediately. In fact, it is not our purpose to prove every theorem or fact encountered, only those that illustrate methods and/or basic concepts. Throughout the text we will focus in on main techniques of proofs. Let's illustrate by proving the distributive law.

Proof Technique 1. State or restate the theorem so you understand what is given (the hypothesis) and what you are trying to prove (the conclusion).

Proof

Proof Technique 2

  1. To prove that \(A\subseteq B\), we must show that if \(x \in A\), then \(x \in B\).

  2. To prove that \(A = B\), we must show:

    1. \(A\subseteq B\) and

    2. \(B \subseteq A\).

To further illustrate the Proof-by-Definition technique, let's prove the following theorem.

Proof

Subsection4.1.5Exercises for Section 4.1

1

Prove the following:

  1. Let \(A\), \(B\), and \(C\) be sets. If \(A\subseteq B\) and \(B\subseteq C\), then \(A\subseteq C\).

  2. Let \(A\) and \(B\) be sets. Then \(A - B= A\cap B^c\) .

  3. Let \(A,B, \textrm{ and } C\) be sets. If (\(A\subseteq B\) and \(A\subseteq C\)) then \(A\subseteq B\cap C\).

  4. Let \(A \textrm{ and } B\) be sets. \(A\subseteq B\) if and only if \(B^c\subseteq A^c\) .

  5. Let \(A,B, \textrm{ and } C\) be sets. If \(A\subseteq B\) then \(A\times C \subseteq B\times C\).

Answer
2

Write the converse of parts (a), (c), and (e) of Exercise 1 and prove or disprove them.

3

Disprove the following, assuming \(A, B, \textrm{ and } C\) are sets:

  1. \(A - B = B - A\).

  2. \(A\times B = B\times A\).

  3. \(A \cap B = A \cap C\) implies \(B = C\).

Answer
4

Let \(A, B, \textrm{ and } C\) be sets. Write the following in “if . . . then . . .” language and prove:

  1. \(x \in B\) is a sufficient condition for \(x \in A \cup B\).

  2. \(A \cap B\cap C = \emptyset\) is a necessary condition for \(A \cap B =\emptyset\).

  3. \(A \cup B = B\) is a necessary and sufficient condition for \(A\subseteq B\).

5

Prove by induction that if \(A\), \(B_1\) \(B_2\) , . . . , \(B_n\) are sets, \(n\geq 2\), then \(A\cap ( B_1 \cup B_2\cup \dots \cup B_n) = (A \cap B_1) \cup (A \cap B_2 ) \cup \dots \cup (A\cap B_n)\).

Solution