\documentclass[12pt]{article}
\usepackage{amssymb,amsmath,graphicx,hyperref}

\hypersetup{ pdfnewwindow=true, pdffitwindow=false }

\pagestyle{empty}
\begin{document}


There is a theorem called the Cantor-Schroeder-Bernstein Theorem which says that $A$ and $B$ have the same cardinality (by our class definition) if and only if there is a bijection between them. The theorem is annoyingly complicated to prove and not too edifying, so you can prove that to yourself on your own time. You are allowed to use that theorem for this problem set.

\begin{enumerate}

\item A set $S$ has $N$ distinct elements. How many distinct subsets are there? (Be sure to include $S$ and $\{ \}$.) Explain why your formula works.

\item The power set of $S$, written $P(S)$, is the set of subsets of $S$. Prove that the cardinality of $P(S)$ is strictly larger than the cardinality of $S$ when $S$ is finite.
 \item Consider the power set of the rational numbers, $ P(\mathbb{Q})$.
 \begin{enumerate}
 \item Show that $\mathbb{R}$ fits into $P(\mathbb{Q})$. (Hint: Each real number corresponds in some natural way to a set of rational numbers.)
 \item Use the last fact, and our previously established uncountability of the reals, to give a proof that $P(\mathbb{Q})$ does not fit into $\mathbb{Q}$, and therefore $P(\mathbb{Q})$ has larger cardinality than $\mathbb{Q}$
 \end{enumerate}

\item Prove that for any set $S$, the cardinality of $P(S)$ is always larger than the cardinality of $S$. (Hint: Suppose there is a bijection $\phi: S \to P(S)$. By using the spirit of diagonalization, construct a subset of $S$ in $P(S)$ that cannot be in the image of $\phi$.)

\item Compare the cardinalities of $\mathbb{C}$ and $\mathbb{R}$. Prove your answer.

\end{enumerate}


\end{document}