Lab: Artificial Examples and Sets

Problem 1: Corners

Artificial examples are a particularly useful device for exploring the corner cases of a mathematical definition. While our intuition allows us to explain the “common” scenarios, we sometimes do not have real-world examples that exercise corner cases. Furthermore, sometimes the corner cases behave precisely again our intuition, leading us to make incorrect assumptions about what a mathematical definition says.

In contrast, artificial examples allow us to create situations that are small enough to analyze directly using the definitions involved so that we can obtain a crisp, definitions-based understanding of what is going on. In short, we create small sets built from abstract values, e.g., $a$, $b$, and $c$, and then “run” our definitions on these sets and then observe the results. Ideally, the examples are constructed in such a way that we isolate our predicted behavior, so the example directly explains the situation. In programming, the analogy here is a minimally reproducing example or a “repro” that isolates buggy behavior in a program and is unlikely to produce other effects that might make analysis unnecessarily complicated.

For each of the following (intentionally vague) questions about the fundamental definitions of sets:

• Create one or more artificial examples that help you answer the question.
• Answer the question by generalizing your observations from your artificial examples. Explain your reasoning in a few sentences.

1. Is the following claim always true?

   Claim: for any sets $S_1$ and $S_2$, $\vert S_1 \cup S_2 \vert = \vert S_1\vert + \vert S_2\vert $.

   (Recall that $\vert S\vert$ is the size of $S$, i.e., the number of elements it contains.)

2. Is the empty set, $∅$, the subset of any set? What about itself?
3. When performing subtraction over numbers, we obtain negative numbers. We have set subtraction, $A - B$. Is there a resulting “negative” set we can obtain from set subtraction?
4. When performing multiplication of numbers, we know that multiplying any number by zero results in zero. The Cartesian Product, $A × B$, seems to behave similarly to numeric multiplication. Is there an analogous set in set theory for Cartesian Product?
5. Set subtraction and Cartesian Product are analogous to arithmetic subtraction and multiplication, respectively. Is there an arithmetic analog to the power set operation, $𝒫(S)$? If so, what is it? In particular, what is $𝒫(∅)$?

Problem 2: Trickiness

Artificial examples are also useful for gaining intuition about tricky definitions. Here is an example of such a definition:

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:

1. $S_1 \cap S_2 = ∅$.

2. $S_1 \cup S_2 = T$.

3. Give an artificial example of a partition.
4. Instantiate that artificial example to a real-world example. Use real-world objects in place of your abstract values. Try to choose a real-world domain where your intuitive notion of a “partition” would be relevant.
5. Using your examples as a guide, describe at a high-level what each of the two conditions of a partition is saying in a sentence or two each.

Problem 3: The Other Side

In a previous reading exercise, we proved the left-to-right direction of De Morgan’s Law. Go ahead and prove the right-to-left direction to demonstrate equivalence of the two set expressions.

Claim $\overline{A} \cap \overline{B} \subseteq \overline{A \cup B}$.

Problem 4: Pivoting to New Things

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 - ${$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.

1. Give an artificial example of a set $S$.
2. Identify a pivot element $a$ drawn from $S$ and list the contents of $T_1$ and $T_2$ for that choice of pivot.
3. Explain in a sentence or two why your concrete sets $T_1$ and $T_2$ form a partition according to this definition.

Now, to prove this claim, we must show that for an arbitrary set $S$ and choice of pivot $a$ that:

• $T_1 \cap T_2 = ∅$.
• $T_1 \cup T_2 = 𝒫(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’ll focus on the second proposition for this lab. Recall that, as a set equality, the proposition really consists of two subset proofs due to double inclusion:

• $T_1 \cup T_2 \subseteq 𝒫(S)$, the left-to-right or “if” direction.
• $𝒫(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!

Lemma (Left-to-right Direction) $𝒫(S) \subseteq T_1 \cup T_2$

This proof is a bit trickier than the other ones we’ve seen so far, primarily because of $\mathcal{P}(S)$. Here are some hints to help guide your proof development:

• For this set inclusion proof, note that the only thing you can conclude from your initial premise that $X \in 𝒫(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.

• 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, recall the definition of subset: $X \subseteq Y \equiv \forall x \in X \ldotp x \in X \rightarrow x \in Y$. 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 since the $x$ was arbitrary!

Problem 5: Double the Practice Makes Perfect (Optional)

Formally prove the following standard identities of sets. Recall that to prove a set equality, you must prove both directions of the equality.

1. (Absorption) $A \cup (A \cap B) = A$
2. (Distribution of Difference) $(A - B) - C = A - (B \cup C)$.