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