\(\newcommand{\set}[1]{\{\, #1 \,\}}\)
Problem 1: The Other Side
In the reading exercise for today, you proved the left-to-right direction of De Morgan’s Law. To begin this lab, go ahead and prove the right-to-left direction:
Claim: \(\overline{A} \cap \overline{B} \subseteq \overline{A \cup B}\).
Problem 2: Pivots
In the previous lab, you were introduced to the notion of a set partition:
Definition (Partition): a partition of a set \(T\) is a pair of subsets, \(S_1\) and \(S_2\), of \(T\) that obeys the following properties:
- \(S_1 \cap S_2 = \emptyset\).
- \(S_1 \cup S_2 = T\).
Now let’s consider a proposition about this definition.
Claim (Pivots Determine Partitions): let \(a \in S\). Define \(T_1, T_2 \subseteq \mathcal{P}(S)\) as follows:
- \(T_1 = \mathcal{P}(S - \set{a})\).
- \(T_2 = \set{B \cup \set{a} \mid B \in \mathcal{P}(S - \set{a})}\).
\(T_1\) and \(T_2\) form a partition of \(\mathcal{P}(S)\) where \(a\) is its pivot.
Give an artificial example of a set \(S\). Identify a pivot element \(a\) drawn from \(S\) and list the contents of \(T_1\) and \(T_2\) for that choice of pivot. Explain in a sentence or two why your concrete sets \(T_1\) and \(T_2\) form a partition.
To prove this claim, we must show that for an arbitrary set \(S\) and choice of pivot \(a\) that:
- \(T_1 \cap T_2 = \emptyset\).
- \(T_1 \cup T_2 = \mathcal{P}(S)\).
(Note that our claim states that \(T_1\) and \(T_2\) are a partition for the power set of \(S\), not necessarily \(S\) itself.) We will leave the first proposition to prove as an optional exercise. Recall that the second proposition, as a set equality, really consists of two subset proofs due to double inclusion:
- \(T_1 \cup T_2 \subseteq \mathcal{P}(S)\), the left-to-right or “if” direction.
- \(\mathcal{P}(S) \subseteq T_1 \cup T_2\), the right-to-left or “only if” direction.
You will prove the left-to-right direction in the demonstration exercise for this week. As a warm-up for this, you will now prove the right-to-left direction to wrap up this lab!
Claim: \(\mathcal{P}(S) \subseteq T_1 \cup T_2\)
For this set inclusion proof, note that the only thing you can conclude from your initial premise that \(X \in \mathcal{P}(S)\) is that \(X \subseteq S\). To make progress you need to perform case analysis on the fact that the pivot \(a\) is either in \(X\) or it is not in \(X\). From there, you can choose which of \(T_1\) or \(T_2\) ought to be a member of and then proceed forward.
Also note that since \(X\) is a set, it’ll be difficult to reason about \(X\)’s relationship to \(T_1\) and \(T_2\). To work around this, at this point in the proof you should consider an arbitrary \(x \in X\) and try to show that \(x\) is also in \(T_1\) or \(T_2\). This will then imply that \(X\) is a subset of the appropriate partition.
Problem 3: Double the Practice Makes Perfect
Formally prove the following standard identities of sets:
- (Absorption) \(A \cup (A \cap B) = A\)
- (Distribution of Difference) \((A - B) - C = A - (B \cup C)\).