“Set theory”
Set $=$ Collection $=$ family.
{definable objects} True/ False.
ex) $A=\{-1,2,4,5\},-1 \in A . O \notin A$
ex) $B=\{x \mid P(x)\}$
ex) $C=\{1,2\}$
$P(C)=\{ \text{subsets in } C \}$.
Examples.
$\mathbb{N}=\{1,2,3,4,…\}$,
$\mathbb{Z}=\{0,1,2,3,4,…\}\cup \{-1,-2,-3,…\}$,
$ \mathbb{Q}=\left\{\frac{q}{p} \mid p_{1} q \in \mathbb{Z}, q \neq 0\right\}$,
$ \mathbb{R}=\{\text { real } \# s\}$,
$ \mathbb{C}=\{\text { Complex } \# s\}$
Exercise. Show that $\sqrt{2} \left(x^{2}=2, x>0\right)$ is not the rational number.
Definition. $X$ be an universal set. Let $A, B \subseteq X$, define
$A \cup B:=\{x \mid x \in A$ or $x \in B\}$.
$A \cap B:=\{x \mid x \in A$ and $x \in B\}$.
$A^{C}:=\{x \in X \quad \mid x \notin A\}$.
Definition. $A, B \subseteq X$.
$A=B \Leftrightarrow A \subseteq B$ and $B \subseteq A$
$\Leftrightarrow$ If $x \in B$ then $x \in B$, and if $y \in B$, then $y \in A$.
Proposition. Let A,B,C $\subseteq X$.
(a) $A \cap(B \cup C)=(A \cap B) \cup(A \cap C)$.
Proof. Need to show (NTS):
$A \cap(B \cup C) \subset(A \cap B) \cup(A \cap C)$
and $(A \cap B) \cup(A \cap C) C A \cap(B \cup C)$
$\Leftrightarrow$ If $x \in A \cap(B \cup C)$
$\Leftrightarrow x \in A$ and $(x \in B$ or $x \in C)$
$\Leftrightarrow(x \in A$ and $x \in B)$ or $(x \in A$ and $x \in C)$
$\Leftrightarrow x \in A \cap B$ or $x \in A \cap C$
$\Leftrightarrow x \in(A \cap B) \cup(A \cap C)$
(b) $A \cup(B \cap C)=(A \cup B) \cap(A \cup C)$
(c) $(A \cup B)^{C}=A^{C} \cap B^{C}$
(d) $(A \cap B)^{C}=A^{C} \cup B^{C}$
Definition. Given a set $A$, define
$P(A):=\{B \subset A\}$, the collection of subsets of $A$, called the power set of $A$.
Exercise. If $A$ has $n$ elements, then show that $P(A)$ has $2^{n}$ elements.
“Functions”
Given two sets $A, B$, $A \times B=\{(a, b) \mid a \in A, b \in B\}$.
Definition. Given “two sets $A, B$, we call $f: A \rightarrow B$ is a function, if we have ” $S_{f} \subseteq A \times B$ satisfying: for each $a \in A$, there exists $b \in B$ uniquely such that $(a, b) \in S_{f}$.
We call A the domain, B the codomain.
We call $Imf=\{b=f(a) \mid a \in A\}$ call the image (range) of f.
Proposition 2. Given $f : A \longrightarrow B$ a function, let $A_{1} A_{2} \subseteq A$.
1. $f\left(A_{1} \cup A_{2}\right):=\left\{f\left(x_{}\right) \mid x \in A_{1} \cup A_{2}\right\}=f\left(A_{1}\right) \cup f\left(A_{2}\right)$.
2. $f\left(A_{1} \cap A_{2}\right) \subseteq f\left(A_{1}\right) \cap f\left(A_{2}\right)$.
Proof. Exercise.
Definition. Given $f: A \rightarrow B$ a function.
Let $B_{1} \subset B$.
Define $f^{-1}\left(B_{1}\right):=\left\{x \in A \mid f(x) \in B_{1}\right\}$, called the inverse image of $f$ under $B_{1}$.
Proposition 3. Let $f: A \rightarrow B$ be a function, $B_{1}, B_{2} \subset B$.
(a) $f^{-1}\left(B_{1} \cup B_{2}\right)=f^{-1}\left(B_{1}\right) \cup f^{-1}\left(B_{2}\right)$.
(b) $f^{-1}\left(B_{1} \cap B_{2}\right)=f^{-1}\left(B_{1}\right) \cap f^{-1}\left(B_{2}\right)$.
(c) $f^{-1}\left(B_{1}{ }^{c}\right)=f^{-1}\left(B_{1}\right)^{c}$.
Proof. Exercise.