\documentclass[11pt]{article}
\usepackage{amsfonts}
\usepackage{amsthm}
\usepackage{amsmath}
\usepackage{multicol}
\usepackage{latexsym}
\usepackage{verbatim}
\usepackage[pdftex]{graphicx}
\usepackage{url}
\usepackage{mathrsfs}
\usepackage{hyperref}
\hypersetup{colorlinks=true}
\setlength{\oddsidemargin}{.25in}
\setlength{\evensidemargin}{.25in}
\setlength{\textwidth}{6in}
\setlength{\topmargin}{-0.4in}
\setlength{\textheight}{8.5in}

\input{preamble.tex}

\begin{document}

\homework{4: Cardinality}{Due Friday, Week 2}

Do \textbf{one} of the \textbf{three} problems below!

\begin{enumerate}

\item \begin{enumerate}
\item Can you make a bijection between $(0,1)$ and $[0,1]$?
\item We call a function $f$ \textbf{order-preserving} if whenever $x < y$, we have $f(x) < f(y)$.  Can you make an order-preserving bijection from $(0,1)$ to $[0,1]$?
\item  Can you make an order-preserving bijection from $\mathbb{N}$ to $\mathbb{Q}$?
\end{enumerate}
\item Given a set $A$, we say that a set $B$ is a \textbf{subset} of $A$ if every member of $B$ is also a member of $A$.  For example, if $A = \{w,x,y,z\}$ and $B = \{w,z\}$, then $B$ is a subset of $A$, because every member of $B$ is also a member of $A$.  Conversely, the set $C = \{x,y,z,\alpha\}$ is not a subset of $A$, because the element $\alpha$ is a member of $C$ and not a member of $A$.

A special set that bears mentioning is the \textbf{empty set}, denoted $\emptyset$.  This is the set that contains no elements.  

Given a set $A$, the \textbf{power set} of $A$, denoted $\mathcal{P}(A)$, is the collection of all of the subsets of $A$.  For example, the power set of $\{1,2,3\}$ is the set containing the following eight sets:
\begin{multicols}{3}
\begin{itemize}
\item $\emptyset$
\item $\{1\}$
\item $\{2\}$
\item $\{3\}$
\item $\{1,2\}$
\item $\{1,3\}$
\item $\{2,3\}$
\item $\{1,2,3\}$
\item[]
\end{itemize}
\end{multicols}
We write this as
\begin{align*}
\mathcal{P}(A) = \Bigg\{ \emptyset, \{1\}, \{2\}, \{3\}, \{1,2\}, \{1,3\}, \{2,3\}, \{1,2,3\} \Bigg\}.
\end{align*}
(It may seem weird for a set to contain other sets, but this is entirely valid!  Sets are just collections of objects, and those objects can be all sorts of strange things, including other sets.  If this bothers you, come and talk to me at office hours, or send me an email!)

Prove that for any set $A$, the cardinality of the power set of $A$, $|\mathcal{P}(A)|$ is greater than the cardinality of $A$, $|A|$.

\item Create an injection from $\mathcal{P}(\mathbb{N})$ to the real numbers $\mathbb{R}$.
\end{enumerate}
\end{document}