Motivation: Sets are the modeling language of mathematics and
a fundamental skill.
Definitions
Definition 1: A set is a collection of unique objects.
Definition 2: A is defined as the subset of B (denoted by
$A \subset B$) iff $\{a : a \in A \text{ and } a \in B\}$.
Definition 3: The union of two sets $A \cup B$ is
defined as $A \cup B = \{x : x \in A \lor x \in B\}$.
Note that in maths, $=$ implies equivalence, not
assignment.
Definition 4: The intersection of two sets $A \cap B$ is
defined as $A \cap B = \{x : x \in A \land x \in B\}$.
Definition 5: The product of two sets $A, B$, denoted
$A \times B$ is the set of all ordered pairs ${a, b} : a \in A, b \in B$.
Definition 6: Let $A, B$ be sets, and $F \subset A
\times B$. We say $F$ is a function if and only if it satisfies the
following property: for each $a \in A$, there is a unique pair $(a, b) \in F$
(an input must have exactly one output). The set $A$ is called the
domain of F and $B$ is called the codomain of $F$. We
denote this with the arrow notation: $f: A \to B$.
Definition 7: Given a function $f: A \to B$, we define the image
of $f$ as the set $f(A) = \{f(a) : a \in A\}$. Alternatively,
$$\text{im } f = \{b \in B: \exists a \in A \text{ with } f(a) = b\}$$
Definition 8: Let $A, B$ be sets and $f: A \to B$ a
function. The preimage of $B$ under $f$ is defined as
$$f^{-1}(b) = \{a \in A: f(a) = b\}$$
Definition 9: A function $f: A \to B$ is called an
injection (it is injective) if $$\exists a, a' \in A, a \neq a':
f(a) \neq f(a')$$
Definition 10: A function $f: A \to B$ is called a
surjection (it is surjective) if $\forall b \in B, \exists a
\in A$ such that $f(a) = b$. A function is a bijection if it is
both surjective and injective.
Definition 11: Inverses are unique.
Theorems
Theorem 1: $\varnothing$ is a subset of all other sets. That is,
$\forall A \text{ where } A \text { is a set,} \varnothing \subset A$.
This theorem isn't in the book, but I wanted to prove it to myself
and to use it as a foundation for the other proofs.
Proof: There are no elements in $\varnothing$, therefore
all elements in $\varnothing$ are elements of any other set.
$\square$
Theorem 2: $A \cap B \subset A$
Proof: Let $C = A \cap B = \{x : x \in A \land x \in B\}$. By
definition 3, $\forall c \in C, c \in A$. Therefore $C \subset A$.
$\square$
Theorem 3: $A \subset A \cup B$
Proof: Let $C = A \cup B = \{x : x \in A \lor x \in B\}$. By
definition, $C$ contains every element in $A$ and therefore $A \subset C$.
$\square$
Theorem 4a: De Morgan's law for sets: $(A \cap B)^C = A^C \cup B^C$.
Proof: $A \cap B$ contains only the elements of $X$ in
both $A$ and $B$. Therefore, $(A \cap B)^C$ contains only the elements
of X that do not appear in both $A$ and $B$. That is,
$$(A \cap B)^C = \{x \in X: x \notin A \land x \notin B\}$$$A^C$ contains the elements of $X$ that don't appear in $A$; similarly,
$B^C$ contains the elements of $X$ that don't appear in $B$. Therefore,
$A^C \cup B^C$ contains the elements of $X$ that appear either in $A$,
$B$, or neither. That is,
$$A^C \cup B^C = \{x \in X: x \notin A \land x \notin B\}$$
These two definitions are equivalent, and therefore $(A \cap B)^C = A^C \cup B^C$.