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