\documentclass[ps, letterpaper]{cs121}
\usepackage{enumerate}
\begin{document}
\header{0}{Tuesday, September 10, 2013}{Friday, September 13, 2013}{20}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\noindent{\bf Note: This is our standard prologue. Problem set 0 counts 0 points, but you should complete it, and we will grade it and provide a solution set for your edification.}

\PART{Gabe}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem{2+2+2+2} Using set notation, give formal descriptions of the following sets:
\subproblem The set containing no elements.
\subproblem The set containing the empty string.
\subproblem The power set of a set $X$, denoted $\mathcal{P}(X)$, i.e., the set containing all subsets of $X$.
\subproblem The difference between two sets $X$ and $Y$, denoted $X\setminus Y$, i.e., the set containing all elements of $X$ that are not elements of $Y$.  

%%% Uncomment the lines below to add your solutions. Use the same format
%%% in all subsequent problems.

%%% \subsolution
    % your answer here
%%% \subsolution
    % your answer here
%%% \subsolution
    % your answer here
%%% \subsolution
    % your answer here

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\problem{10+10} Given a set $X$, we define the power set $\mathcal{P}(X)$ to be the set of all subsets of $X$. 
\subproblem Construct a bijection between $\mathcal{P}(X)$ and the set of functions from $X$ into the set $\{0,1\}$.
\subproblem Prove that for any finite set $X$, $|P(X)| = 2^{|X|}$. (Hint: use induction on $|X|$.)

\end{document}