Demonstration Exercise 4

Problem 1: Set Equality

Prove the following common identity about sets:

Claim (Distribution of Union)

Problem 2: Partitions and Pivots, Revisited

Recall the definition of partitions and pivots from the lab:

Definition (Partition)

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

  1. .
  2. .

Claim (Pivots Determine Partitions)

Let . Define and as follows:

  • .
  • .

and form a partition of where 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 and defined in the claim form a partition. By the definition of partition, we must show that:

  1. .
  2. .

In the latter case, you needed to show that sets and 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 be a set and let . Define and as follows:

  • .
  • .

.

Now, prove the first proposition:

Lemma (Emptiness of Intersection)

Let be a set and let . Define and as follows:

  • .
  • .

.

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!)