Class 19: Reviewing Infinities

# Comparing sets Recap:

**Definition.** Sets $A$ and $B$ have the same cardinality, denoted by $|A|=|B|$ if there is a bijection between $A$ and $B$.

**Definition.** Cardinality of $A$ is at least as big as cardinality of $B$, denoted by $|A|\geq |B|$ if and only if *either* of the following is true (they are equivalent).
\begin{enumerate}
\item There is a surjective function from $A$ to $B$.
\item There is a total injective function from $B$ to $A$.
\end{enumerate}

# Infinite Sets Recap

**Definition.** A set $C$ is *infinite* if and only if *either* of the following happens (they are all equivalnet).
\begin{enumerate}

\item Dedekind-infinite: There is a bijection between $C$ and a strict subset $B$ of $C$.

\item There is \emph{no} bijection between $C$ and any $\mathbb{N}_k$ for any natural number $ k \in \mathbb{N}$.

\item There exists a surjective function from $C$ to $\mathbb{N}$.

\item There exists a total injective function from $\mathbb{N}$ to $C$. \end{enumerate}

**Definition.** A set $C$ is *countable* if and only if there exists a
surjective function from $\mathbb{N}$ to $C$. (That is, $\le 1$ arrow
out from $\mathbb{N}$, $\ge 1$ arrow in to $C$.)

**Definition.** A set $C$ is *countably infinite* if and only if there
exists a bijection between $C$ and $\mathbb{N}$.

# Cantor’s Theorem

For **all** sets, $S$, $| pow(S) | > | S |$.

What does this mean for $| \mathbb{N} |$?

#

Show there is a bijection between $[0, 1]$ and $pow(\mathbb{N})$.

#

What is the cardinality of all the real numbers? Show a bijection between $[0, 1]$ and all real numbers. Hint, first show a bijection between $(0, 1)$ and real numbers, and then a bijection between $[0, 1]$ and $(0, 1)$.

#