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)$.

#