\(\newcommand{\set}[1]{\{\, #1 \,\}}\)

In our discussion of mathematical literacy, we talked about the need to experiment with the definitions in a piece of mathematical prose to truly understand what they mean. We used real-world examples with mathematical logic to leverage our intuition in understanding the meaning of various logical connectives. Sets give us a formal way of using another kind of example, the artificial example, to explore definitions. An artificial example is a small-scale, abstract example, carefully designed to help us answer specific questions about a mathematical definition, usually a corner case.

In this lab, we’ll explore the fundamental definitions and operations of sets with an eye towards using artificial examples to aid in this exploration.

Problem 1: Foundations

In the course, we observe that set theory allows us to model data and mathematical logic allows us to describe properties about that data. We first studied logic and then set theory, but this might feel backwards! How could we discuss the properties of objects that we have not yet defined? It turns out we do this in programming quite often! For example, in the Java programming language, we can use interfaces to define how an object ought to behave without defining an implementation for that object.

In set theory, we can realize this principle by taking as the sole primitive definition of sets the notion of set inclusion, \(x \in S\), as a logic proposition. We can then view all other set definitions as shorthand for logical propositions whose atomic propositions are statements of set inclusions.

For each of the following definitions of sets, express that set as a logical proposition involving set inclusion atomic propositions, e.g., \(1 \in S ∧ 2 \in S\). The variables in each part are independent of the other parts of this problem.

1. \(S = \set{1, 2, 3}\).
2. \(S = (\set{1, 2, 4, 5} \cap \set{3, 4, 5}) \cup \set{4, 8}\).
3. \(U = \set{ x \mid x \in \mathbb{N}, x \bmod 3 \equiv 1}\). (Note: \(x \bmod 3 \equiv 1\) is standard number theory notation for expressing the idea that the remainder of \(x \div 3\) is \(1\).)
4. \(U = \set{ (x, y, z) \mid x, y \in \mathbb{R}, x + y = z }\).
5. \(U = \overline{S_1} \cup S_2\).
6. \(U = 𝒫(S_1 - S_2)\).

Problem 2: 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 and 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\), \(|S_1 ∪ S_2| = |S_1| + |S_2|\).

   (Recall that \(|S|\) 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 3: Trickiness

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

1. Give an artificial example of a partition.
2. 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.
3. 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 a piece.

Problem 4: 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:

Problem 5: Pivots

In the previous lab, you were introduced to the notion of a set partition:

Now let’s consider a proposition about this definition.

1. 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.

2. 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 6: Double the Practice Makes Perfect (Optional)

Formally prove the following standard identities of sets:

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