Set Theory
Basics
Definition 1 (Set). Set is a bucket that can hold objects or elements.
Example:
\[\begin{aligned} &S = \{1, 2, 3, 4, 5\} \quad\text{(S is a set of some numbers)} \\ &C = \{a, b, g, r, s\} \quad\text{(C is a set of some letters)} \end{aligned}\]Remark 1 (Set Membership). Given a set $S$ and an element $x$, $x$ can either be included in $S$ (denoted as $x \in S$), or excluded in $S$ (denoted as $x \not\in S$).
Example:
\[\begin{aligned} &3 \in S, \text{but}\ 8 \not\in S \\ &B \not\in C, \text{but}\ b \in S \end{aligned}\]Remark 2 (Set Construction). A set builder notation ${x : \text{
}\}$ can be used to construct sets more conveniently.
Example:
\[\begin{aligned} &N = \{x : x \in \mathbb{Z} \text{ and } 0 < x < 101\} \quad\text{$N$ is a set of all positive integers up to 101}\\ &E = \{x : x \in \mathbb{N} \text{ and } x \mod 2 = 0\} \quad\text{$E$ is a set of all even natural numbers}\\ \end{aligned}\]Definition 2 (Union of Sets). Union of sets $A = {a_1, a_2, \cdots}$ and $B = {b_1, b_2, \cdots}$ is another set containing all the elements of $A$ and $B$, i.e., $A \cup B = {a_1, a_2, a_3, \cdots, b_1, b_2, \cdots}$.
Example:
\[\begin{aligned} S \cup C = \{1, 2, 3, 4, 5, a, b, g, r, s\} \end{aligned}\]Definition 3 (Intersection of Sets). Intersection of sets $A$ and $B$ is another set containing all the common elements that appear both in $A$ and $B$, i.e., $A \cap B =$
Example:
\[\begin{aligned} S \cap C = \{\} \end{aligned}\]More About Sets
Definition 4 (Countability). A set $X$ is called countable (or denumerable) in case $X \precsim w$ and countably infinite in case $X \sim w$.
Definition 5. If $X$ and $Y$ are sets such that $X$ is equivalent to a subset of $Y$, we say $Y$ dominates $X$ or \(X \precsim Y\)
Remark 3. Strong domination vs weak domination