Section 6.3 Algebraic Proofs and Counterexamples
The proofs we did in the last section involved looking at elements in sets. We could translate statements about sets into logical statement such as “and”s, “or”s, and conditionals. This allowed us to prove many other properties of sets, such as DeMorgan’s Laws. But now that we have these properties, we can use them to prove new properties in a more algebraic way.
First we look at how to disprove statements involving sets. As we saw in
Section 4.1, we can disprove a statement with a counterexample.
To prove a statement is false, give a specific counterexample. This means defining specific sets for which the property fails. If you are trying to decide if a statement is true or false, you can experiment with small sets, or you can draw a Venn diagram. The Venn diagram itself is not a proof or a counterexample. But it can help you decide which you should be trying to find.
Example 6.3.1. Finding a Counterexample.
Prove or disprove \(\forall A, B, C,\) if \(A\nsubseteq B\) and \(B\nsubseteq C\text{,}\) then \(A\nsubseteq C\text{.}\)
This statement is false. Our counterexample should satisfy the negation of the statement: \(A\nsubseteq B, B\nsubseteq C\text{,}\) and \(A\subseteq C\text{.}\) Find small sets that satisfy the negation.
For example, we can try \(A=\{1, 2\}, B=\{4, 5\}, C=\{1, 2, 3\}\text{.}\) Then \(A\nsubseteq B, B\nsubseteq C\text{,}\) and \(A\subseteq C\text{.}\) Thus, we have a counterexample.
Advice for finding counterexamples:
Write the negation of the statement so you can make sure your sets satisfy the appropriate conditions.
Most counterexamples for the types of statements we see in this chapter can be found without needing to find “tricky” sets. So just try something, it will probably work.
You might need to be careful about whether your sets intersect or not.
If you need counterexamples that involve set complements, it is helpful to define a small universal set such as \(U=\{1, 2, 3, 4, 5, 6\}\text{.}\) Then if \(A=\{1, 2, 3\}\text{,}\) \(A^C=\{4, 5, 6\}\text{,}\) which is easier to work with than, say, all the integers except 1, 2, 3.
Now we want to be able to use the list of properties from the end of the previous section,
Summary of Set Identities, to prove statements algebraically. In this case, we do not need to use elements, but we can use properties such as the distributive property or DeMorgan’s Laws to rewrite our sets.
Example 6.3.2. Algebraic Set Theory Proof.
Prove \(A-(A\cap B)=A-B\) using properties of sets.
Proof.
\begin{align*}
A-(A\cap B) &= A\cap(A\cap B)^C \ \ \text{ Set Difference Law}\\
&= A\cap(A^C\cup B^C) \ \ \text{ DeMorgan's Law}\\
&= (A\cap A^C)\cup (A\cap B^C) \ \ \text{ Distributive Law}\\
&= \emptyset\cup (A\cap B^C) \ \ \text{ Complement Law}\\
&= A\cap B^C \ \ \text{ Identity Law}\\
&= A-B \ \ \text{ Set Difference Law}
\end{align*}
Activity 6.3.1.
Activity 6.3.2.
Prove or disprove for all sets \(A, B\) and \(C\text{,}\) \(A-(B-C)=(A-B)-C\text{.}\)
Hint.
To decide if a statement is true or false, draw a Venn diagram for each side of the equality. If the two diagrams are the same, provide a proof. If the two diagrams are different, provide a specific counterexample.
Activity 6.3.3.
Prove or disprove for all sets \(A, B\) and \(C\text{,}\) if \(A\subseteq B\) then \(A\cap(B\cap C)^{C}=\emptyset\text{.}\)
Hint.
It might be easier to define a small universal set for this one.
Recall the power set of a set \(A\text{,}\) \(\mathcal{P}(A)\), is the set of all subsets of \(A\text{.}\)
Example 6.3.3. Power Set Proof.
Prove for all sets \(A\) and \(B\text{,}\)
\begin{equation*}
\mathcal{P}(A\cap B)=\mathcal{P}(A)\cap \mathcal{P}(B)\text{.}
\end{equation*}
Proof.
Since we need to show two sets are equal we need to show both subsets. We should also note that elements of power sets are sets.
\((\subseteq)\text{:}\) Let \(C\in \mathcal{P}(A\cap B)\text{.}\) Then \(C\) must be a subset of \(A\cap B\text{.}\) Then \(C\subseteq A\) and \(C\subseteq B\text{.}\) This implies \(C\in \mathcal{P}(A)\) and \(C\in \mathcal{P}(B)\text{.}\) Thus, \(C\in\mathcal{P}(A)\cap\mathcal{P}(B)\text{.}\)
\((\supseteq)\text{:}\) Let \(C\in \mathcal{P}(A)\cap\mathcal{P}(B)\text{.}\) Then \(C\in \mathcal{P}(A)\) and \(C\in \mathcal{P}(B)\text{.}\) Then \(C\subseteq A\) and \(C\subseteq B\text{.}\) This implies \(C\) must be a subset of \(A\cap B\text{.}\) Thus, \(C\in\mathcal{P}(A\cap B)\text{.}\)
You might have noticed in this last proof that each of the subset proofs are really just the reverse of each other. If all the implications in our proof are really “if and only if” statements, then we can write the proof more succinctly as a single “if and only if” proof. We will show this technique in the next example. Be careful with if and only if proofs, though. Make sure that at each step both directions of the conditional are true. If you are unsure, you can always write you proof in two stages, as we did in the previous example. We generally use the symbol \(\Leftrightarrow\) to mean “if and only if” in proofs.
Example 6.3.4. Power Set Proof, Shortened.
Prove for all sets \(A, B\text{,}\) \(\mathcal{P}(A\cap B)=\mathcal{P}(A)\cap \mathcal{P}(B)\text{.}\)
Proof.
\begin{align*}
& C\in \mathcal{P}(A\cap B)\\
\Leftrightarrow & C\subseteq A\cap B\\
\Leftrightarrow & C\subseteq A \text{ and } C\subseteq B\\
\Leftrightarrow & C\in \mathcal{P}(A) \text{ and } C\in \mathcal{P}(B)\\
\Leftrightarrow & C\in\mathcal{P}(A)\cap\mathcal{P}(B).
\end{align*}
Since we are looking at the power set, we can prove a formula for counting the number of elements of a power set. In this proof we will revisit proof by induction. The number of elements in a set, \(S\text{,}\) is denoted \(|S|\).
Theorem 6.3.5.
If \(S\) has \(n\) elements, then \(\mathcal{P}(S)\) has \(2^n\) elements.
Proof.
We will prove this by induction on the number of elements, \(n\text{.}\)
Base step: Let \(n=0\text{.}\) Then since \(S\) has 0 elements, \(S=\emptyset\text{.}\) The only subset of the empty set is \(\emptyset\text{.}\) Thus, \(\mathcal{P}(S)=\{\emptyset\}\text{.}\) Hence, \(|\mathcal{P}(S)|=1\text{.}\) Since \(2^0=1\text{,}\) if \(n=0\text{,}\) \(\mathcal{P}(S)\) has \(2^n\) elements.
Induction step: Assume if a set \(S\) has \(k\) elements, then \(\mathcal{P}(S)\) has \(2^k\) elements.
Show if a set \(S\) has \(k+1\) elements, then \(\mathcal{P}(S)\) has \(2^{k+1}\) elements.
Proof of induction step: Assume \(|S|=k+1\text{.}\) Let \(b\in S\text{,}\) then \(S=A\cup \{b\}\) where \(A=S-\{b\}\text{,}\) the set of elements of \(S\) except \(b\text{.}\) Then \(A\) has \(k\) elements, so by the induction assumption, \(|\mathcal{P}(A)|=2^k\text{.}\)
Now consider the subsets of \(S\text{.}\) Each subset either contains \(b\) or it doesn’t. We know there are \(2^k\) subsets that do not contain \(b\text{.}\) We get all the subsets of \(S\) that do contain \(b\) by adding \(b\) to the sets that don’t contain \(b\text{.}\) Thus, there are the same number of subsets that do contain \(b\) as those that don’t. Hence, we have \(2^k\) subsets not containing \(b\) and \(2^k\) subsets containing \(b\text{.}\)
Therefore, \(S\) has \(2^k+2^k=2(2^k)=2^{k+1}\) subsets, hence \(\mathcal{P}(S)\) has \(2^{k+1}\) elements.
The next example demonstrates the proof of
Theorem 6.3.5 in a specific set.
Example 6.3.6. Counting the Number of Subsets.
Let
\(S=\{1, 2, 3\}\text{.}\) We can separate out the last element so, as in the proof of
Theorem 6.3.5,
\(b=3, A=\{1, 2\}\text{.}\)
We can look at the subsets of \(S\) that do not contain 3:
\begin{equation*}
\emptyset, \{1\}, \{2\}, \{1, 2\}.
\end{equation*}
Now add 3 to each of these sets:
\begin{equation*}
\{3\}, \{1, 3\}, \{2, 3\}, \{1, 2, 3\}.
\end{equation*}
You can check that we have all the possible subsets of \(S\text{.}\)
If we count up the sets, we have \(2^2\) subsets not containing 3, and \(2^2\) subsets containing 3. Which gives us \(2(2^2)=8=2^3\) subsets of \(S\text{.}\) Hence, \(|\mathcal{P}(S)|=2^3=8\text{.}\)
Reading Questions Check Your Understanding
Let \(A, B, C\) be sets and \(U\) be the universal set.
1.
True or false: If \(A\subseteq (B\cup C)\text{,}\) then \(A\subseteq B\) or \(A\subseteq C\text{.}\)
True.
-
False.
-
2.
True or false: If \(A\subseteq (B\cap C)\text{,}\) then \(A\subseteq B\) and \(A\subseteq C\text{.}\)
True.
-
False.
-
3.
Give a counterexample to disprove \(A\cap(B\cup C)=(A\cap B)\cup C\text{.}\)
4.
Give a counterexample to disprove \(A\cup \emptyset=\emptyset\text{.}\)
5.
Give a counterexample to disprove \(A\cup \emptyset\neq\emptyset\text{.}\)
6.
Give a counterexample to disprove \((A\cup B)^C=A^C\cup B^C\text{.}\)
7.
Give a counterexample to disprove \(B-A=A-B\text{.}\)
8.
Give a counterexample to disprove \(B\subseteq A\cup(B\cap C)\text{.}\)
9.
Exercises Exercises
1.
Find a counterexample to show the following statement is false:
For all sets \(A\text{,}\) \(B\text{,}\) and \(C\text{,}\) \((A\cap B)\cup C=A\cap (B\cup C)\text{.}\)
2.
Write a negation for the following statements. Indicate which is true, the statement or the negation. Justify your answer.
\(\forall\) sets \(S\text{,}\) \(\exists\) a set \(T\) such that \(S\cap T=\emptyset\text{.}\)
\(\exists\) a set \(S\) such that \(\forall\) sets \(T\text{,}\) \(S\cup T=\emptyset\text{.}\)
3.
Let \(S=\{a, b, c\}\) and for each integer \(i=0, 1, 2, 3,\) let \(S_i\) be the set of all subsets of \(S\) that have \(i\) elements. List the elements in \(S_0, S_1, S_2, S_3\text{.}\) Is \(\{S_0, S_1, S_2, S_3\}\) a partition of \({\cal P}(S)\text{?}\)
4.
Supply a reason for each step in the algebraic proof of the statement: For all sets \(A\text{,}\) \(B\text{,}\) and \(C\text{,}\)
\begin{equation*}
(A\cup B)\cap C=(A\cap C)\cup (B\cap C).
\end{equation*}
Proof: Suppose \(A\text{,}\) \(B\text{,}\) and \(C\) are sets. Then
| \((A\cup B)\cap C\) |
\(=C\cap(A\cup B)\) |
by ___ |
|
\(=(C\cap A)\cup (C\cap B)\) |
by ___ |
|
\(=(A\cap C)\cup (B\cap C)\) |
by ___ |
5.
Supply a reason for each step in the algebraic proof of the statement: For all sets \(A\text{,}\) \(B\text{,}\) and \(C\text{,}\)
\begin{equation*}
(A\cup B)- (C-A)=A\cup(B-C).
\end{equation*}
Proof: Suppose \(A\text{,}\) \(B\text{,}\) and \(C\) are sets. Then
| \((A\cup B)-(C-A)\) |
\(=(A\cup B)\cap(C-A)^C\) |
by ___ |
|
\(=(A\cup B)\cap(C\cap A^C)^C\) |
by ___ |
|
\(=(A\cup B)\cap (A^C\cap C)^C\) |
by ___ |
|
\(=(A\cup B)\cap ((A^C)^C\cup C^C)\) |
by ___ |
|
\(=(A\cup B)\cap (A\cup C^C)\) |
by ___ |
|
\(=A\cup( B\cap C^C)\) |
by ___ |
|
\(=A\cup( B- C)\) |
by ___ |
6.
Prove or disprove for all sets \(A\) and \(B\text{,}\) \(A\cap (A\cup B)=A\text{.}\)
7.
Prove or disprove for all sets \(A, B\) and \(C\text{,}\) \((A-B)\cap (C-B)=A-(B\cup C)\text{.}\)
8.
Prove or disprove for all sets \(A\) and \(B\text{,}\) if \(A\subseteq B\) then \(A\cap B^C=\emptyset\text{.}\)
9.
Prove or disprove for all sets \(A, B\) and \(C\text{,}\)
\begin{equation*}
A\cup (B-C)=(A\cup B)-(A\cup C).
\end{equation*}
10.
Prove or disprove for all sets \(A\) and \(B\text{,}\) if \(A\subseteq B\) then \({\cal P}(A)\subseteq {\cal P}(B)\text{.}\)
11.
Prove or disprove for all sets \(A\) and \(B\text{,}\) \({\cal P}(A\cup B)\subseteq {\cal P}(A)\cup{\cal P}(B)\text{.}\)
12.
Give an algebraic proof of the statement: For all sets \(A\) and \(B\text{,}\) \((A-B)\cup(A\cap B)=A\text{.}\)
13.
Give an algebraic proof of the statement: For all sets \(A\) and \(B\text{,}\) \((A-B)\cap(A\cap B)=\emptyset\text{.}\)
14.
Simplify the statement using algebraic properties: \((A-(A\cap B))\cap(B-(A\cap B))\text{.}\)
You have attempted
of
activities on this page.
