# Set Theory

## What is a Set?

“A set is an unordered collection of distinct objects.” –Wikipedia

Why unordered?

Why distinct?

## Outline

1. Notation
2. Set Operations
3. Proofs
5. Philosophy (Outside Syllabus)
6. Cardinality (Outside Syllabus)

# Notation

## Basic Notation

$A = \{1, 2, 3\}$ $\{1, 2, 3\} \subset \{1, 2, 3, 4\}$ $\{1, 2, 3\} \subseteq \{1, 2, 3\}$ $2 \in \{1, 2, 3\}$ $4 \notin \{1, 2, 3\}$

## Special Sets

\begin{aligned} \emptyset &= \{\} \\ \mathbb{N} &= \{0, 1, 2, 3, 4, \dots\} \\ \mathbb{Z} &= \{\dots, -4, -3, -2, -1, 0, 1, 2, 3, 4, \dots\} \\ \mathbb{Q} &= \text{Fractions} \\ \mathbb{R} &= \text{Real Numbers} \\ \mathbb{C} &= \text{Complex Numbers} \\ \end{aligned}

## Set-Builder Notation

$S := \{x^2 : x \in \mathbb{N}\}$

## Exercises

Compute each of the following sets.
Note that $$\land$$ denotes “and” and $$\lor$$ denotes “or.”
1. $$\{x : \frac{x}{2} \in \mathbb{Z}\}$$ = $$\{\dotsc, -4, -2, 0, 2, 4, \dotsc\}$$
2. $$\{\sqrt{x} : x \in \mathbb{N} \land x < 5\}$$ = $$\{0, 1, \sqrt{2}, \sqrt{3}, 2\}$$
3. $$\{x^3 : x \in [1, 3]\}$$ = $$[1, 27]$$

Determine whether each statement is true or false.
1. $$2018 \in \{x + y\sqrt{2} : x, y \in \mathbb{Z}\}$$ — True
2. $$\mathbb{Q} = \{\frac{x}{y} : x, y \in \mathbb{N}\}$$ — False

# Set Operations

## Notation

$A^\complement = \bar{A} = A'$ $U = \mathbb{U}$ $A \vartriangle B = A \ominus B = A \oplus B$

## Review

Label each statement as true or false.
A statement is true if it holds for every set $$A$$ and $$B$$.
1. $$A \cup B = B \cup A$$ — True
2. $$A = (A^\complement)^\complement$$ — True
3. $$A \cup B = \{x : x \in A \lor x \in B\}$$ — True
4. $$A \cup A^\complement = U$$ — True
5. $$A \subset A \cup B$$ — False
6. $$(A \cup B)^\complement = A^\complement \cap B^\complement$$ — True

# Proofs

## Subset Proofs

To prove $$A \subseteq B$$:
1. If $$A = \emptyset$$, we are done. Otherwise, state that $$A \neq \emptyset$$.
2. Take an arbitrary $$x \in A$$.
3. Prove that $$x \in B$$.
4. Since $$x$$ is arbitrary, we know that every element in $$A$$ is also in $$B$$.

## Example

For any sets $$A$$ and $$B$$, prove that $$A \subseteq \{x : x \in A \lor x \in B\}$$.
1. Note that $$A$$ is nonempty.
2. Therefore, we can take an arbitrary $$a \in A$$.
3. Since $$a \in A$$, we know $$a$$ satisfies the contition $$x \in A \lor x \in B$$.
4. Therefore, we have $$a \in \{x : x \in A \lor x \in B\}$$.
5. Since $$a$$ was arbitrary, we know that $$A \subseteq \{x : x \in A \lor x \in B\}$$.

## Equality Proofs

We say that $$A = B$$ iff $$A \subseteq B$$ and $$B \subseteq A$$.

Therefore, to prove $$A = B$$:
1. Prove $$A \subseteq B$$.
2. Prove $$B \subseteq A$$.

## Exercises

1. Prove that $$\mathbb{Z} \subseteq \mathbb{Q}$$.
2. Prove that $$\{x : x \equiv 3\,\text{(mod 15)}\} \subseteq \{x : x \equiv 3\,\text{(mod 5)}\}$$.
3. Prove that $$\{x^2 : x \in [1, 2]\} = [1, 4]$$.
4. Prove that $$\{\sqrt{x} : x \in \mathbb{R}^+\} = \mathbb{R}^+$$.
5. Prove that $$A \cup A^\complement = U$$.

## De Morgan's Laws

$(A \cup B)^\complement = A^\complement \cap B^\complement$

$(A \cap B)^\complement = A^\complement \cup B^\complement$

$(A \cup B)^\complement = \{x : \neg(x \in A \lor x \in B)\}$ $A^\complement \cap B^\complement = \{x : \neg (x \in A) \land \neg (x \in B)\}$

## Exercise

Prove that $$(A \cap B)^\complement \subseteq A^\complement \cup B^\complement$$.

#### Hints

To prove $$x \in E \cup F$$, prove that at least one of $$x \in E$$ or $$x \in F$$ is true.
If $$x \notin E \cap F$$, then either $$x \notin E$$ or $$x \notin F$$.

## Solution

1. Assume $$(A \cap B)^\complement \neq \emptyset$$.
2. Therefore, take an arbitrary $$x \in (A \cap B)^\complement$$.
3. We know that $$x \notin A \cap B$$.
4. Therefore, either $$x \notin A$$ or $$x \notin B$$.
5. Thus, we have $$x \in A^\complement$$ or $$x \in B^\complement$$.
6. Finally, we know $$x \in A^\complement \cup B^\complement$$.

## Distributive Laws

$A \cup (B \cap C) = (A \cup B) \cap (A \cup C)$ $A \cap (B \cup C) = (A \cap B) \cup (A \cap C)$

## Exercise

Prove that $$A \cup (B \cap C) \subseteq (A \cup B) \cap (A \cup C)$$.

#### Hints

To prove $$x \in E \cap F$$, you must prove $$x \in E$$ and $$x \in F$$.
You will need to consider two cases in the proof.

## Solution

1. Assume $$A \cup (B \cap C) \neq \emptyset$$.
2. Therefore, take an arbitrary $$x \in A \cup (B \cap C)$$.
3. We know that either $$x \in A$$ or $$x \in B \cap C$$.
4. From here, we will need to consider two cases.

#### Case 1

In the first case, we know $$x \in A$$.
1. It follows that $$x \in A \cup B$$ and $$x \in A \cup C$$.
2. Therefore, we have $$x \in (A \cup B) \cap (A \cup C)$$ and we are done.

#### Case 2

In the second case, we know $$x \in B \cap C$$.
1. Therefore, we know $$x \in B$$ and $$x \in C$$.
2. It follows that $$x \in (A \cup B)$$ and $$x \in (A \cup C)$$.
3. Therefore, we have $$x \in (A \cup B) \cap (A \cup C)$$ and we are done.

# Philosophy

### Explicit Perspective

$A = \{1, 2, 3\}$

### Implicit Perspective

$1 \in A$ $2 \in A$ $3 \in A$ $4 \notin A$ $5 \notin A$ $\vdots$

## Unordered

$A = \{1, 2, 3\} \qquad B = \{1, 3, 2\}$ $A \stackrel{?}{=} B$

 $1 \in A$ $2 \in A$ $3 \in A$ $4 \notin A$ $5 \notin A$ $\vdots$ $1 \in B$ $2 \in B$ $3 \in B$ $4 \notin B$ $5 \notin B$ $\vdots$

## Distinct

$A = \{1, 2, 3\} \qquad B = \{1, 2, 2, 3\}$ $A \stackrel{?}{=} B$

 $1 \in A$ $2 \in A$ $3 \in A$ $4 \notin A$ $5 \notin A$ $\vdots$ $1 \in B$ $2 \in B$ $3 \in B$ $4 \notin B$ $5 \notin B$ $\vdots$

## Set Equality

$\{1, 2, 3\} = \{1, 2, 2, 3\}$ These sets contain the “same elements.”
What do we mean?

Suppose we had a set of everything; call it $$U$$. We would then go through every element $$x \in U$$ and check to see that $$x$$ is either in both sets or neither.

## Definition of Set Equality

The problem is that for $$U$$ to contain everything, we need $$U \in U$$.

To avoid this problem, we only need to check whether every element $$x \in A$$ is also in $$B$$, and vice-versa. $\boxed{A = B \iff A \subseteq B \land B \subseteq A}$

# Cardinality

What is the cardinality of a set? $\lvert\{1, 2, 3\}\rvert = 3$

$\{1, 2, 3\} = \{1, 2, 2, 3\}$

$\lvert\{1, 2, 2, 3\}\rvert = 3?$