Problem 1: Inclusion
Give formal proofs of the following claims:
Claim 1: \(A \cup (B \cap C) = (A \cup B) \cap (A \cup C)\).
Claim 2: \((A - B) \cap (A \cap B) = \emptyset\).
Problem 2: Partitions and Pivots, Revisited
In lab, we introduced the notion of a partition:
Definition (Partition): a partition of a set \(S\) is a pair of sets \(T_1, T_2\subseteq S\) such that:
- \(T_1 \cap T_2 = \emptyset\).
- \(T_1 \cup T_2 = S\).
As well as a pivot:
Claim (Pivots Determine Partitions): let \(S\) be a set and \(a \in S\). Then the sets:
- \(T_1 = \mathcal{P}(S - \{\, a \,\})\) and
- \(T_2 = \\{\, B \cup \{\, a \,\} \mid B \in \mathcal{P}(S - \{\, a \,\}) \,\\}\)
form a partition of \(\mathcal{P}(S)\) where \(a\) is its pivot.
First, formally prove the following useful fact about set inclusion and difference:
Claim (Preservation of Inclusion with Difference): For any values \(x\) and \(a\), if \(x \in S - \{\, a \,\}\) then \(x \in S\).
Use this fact to help you prove the left-to-right direction of the claim.
Claim (Pivot-partitions Are Complete \((\longrightarrow)\)): If \(T_1, T_2 \subseteq \mathcal{P}(S)\) are sets formed by choosing a pivot element \(a \in S\) as described above, then \(T_1 \cup T_2 \subseteq \mathcal{P}(S)\).