\(\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.

- \(S = \set{1, 2, 3}\).
- \(S = (\set{1, 2, 4, 5} \cap \set{3, 4, 5}) \cup \set{4, 8}\).
- \(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\).) - \(U = \set{ (x, y, z) \mid x, y \in \mathbb{R}, x + y = z }\).
- \(U = \overline{S_1} \cup S_2\).
- \(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.

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.)Is the empty set, \(∅\), the subset of any set? What about itself?

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?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?

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:

**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:

- \(S_1 \cap S_2 = ∅\).
- \(S_1 \cup S_2 = T\).

- Give an
*artificial*example of a partition. *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.- 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:

**Claim**: \(\overline{A} \cap
\overline{B} \subseteq \overline{A \cup B}\).

# Problem 5: Pivots

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

**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:

- \(S_1 \cap S_2 = \emptyset\).
- \(S_1 \cup S_2 = T\).

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 - \set{a})\).
- \(T_2 = \set{B \cup \set{a} \mid B \in \mathcal{P}(S - \set{a})}\).

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

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

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