Homework: Homework 4. Sets

Assigned

• February 17, 2026

Due

• February 20, 2026 10:00pm

Collaboration

You must work individually this assignment. Make sure you review and understand the policies on the syllabus before you discuss your work on this assignment with anyone.

Submitting

You will submit your compiled pdf on Gradescope. Everything must be typed in \(\Latex\)

Problem 1: Set Equality

Prove the following common identity about sets:

Claim (Distribution of Union) $S \cup (T \cap U) = (S \cup T) \cap (S \cup U)$

Problem 2: Partitions and Pivots, Revisited

Recall the definition of partitions and pivots from the lab:

A partition of a set $T$ is a pair of subsets, $S_1$ and $S_2$, of $T$ that obeys the following properties:

1. $S_1 \cap S_2 = ∅$.
2. $S_1 \cup S_2 = T$.

Claim (Pivots Determine Partitions) Let $a \in S$. Define $T_1$ and $T_2$ as follows:

• $T_1 = \mathcal{P}(S - ${$a$}).
• $T_2 = ${$B \cup ${$a$} $\mid B \in \mathcal{P}(S - ${$a$})}.

$T_1$ and $T_2$ form a partition of $\mathcal{P}(S)$ where $a$ is its pivot.

In lab, we explored this definition and proposition using examples. Additionally, we begun to show that this claim is correct. To do so, observe that we must show that the $T_1$ and $T_2$ defined in the claim form a partition. By the definition of partition, we must show that:

1. $T_1 \cap T_2 = \emptyset$.
2. $T_1 \cup T_2 = \mathcal{P}(S)$.

In the latter case, you needed to show that sets $T_1 \cup T_2$ and $T$ are subsets “in both directions,” of which, you showed the right-to-left direction in class. First, prove the right-to-left direction:

Lemma (Right-to-left Direction) Let $S$ be a set and let $a \in S$. Define $T_1$ and $T_2$ as follows:

• $T_1 = \mathcal{P}(S - ${$a$}).
• $T_2 = ${$B \cup ${$a$} $\mid B \in \mathcal{P}(S - ${$a$})}.

$T_1 \cup T_2 \subseteq \mathcal{P}(S)$.

Now, prove the first proposition:

Lemma (Emptiness of Intersection) Let $S$ be a set and let $a \in S$. Define $T_1$ and $T_2$ as follows:

• $T_1 = \mathcal{P}(S - ${$a$}).
• $T_2 = ${$B \cup ${$a$} $\mid B \in \mathcal{P}(S - ${$a$})}.

$T_1 \cap T_2 = \emptyset$.

Finally, put all three lemmas together—the lemmas from the lab and these two lemmas—to write a proof of the “Pivots Determine Partitions” claim.

(Hint: this final proof should be short since you already did all the work. You can simply cite these three lemma in your proof without replicating their steps!)