\documentclass{article}
\usepackage{amsmath,amssymb,amsthm,enumerate}
\usepackage{fullpage}
\usepackage{color}
\newcommand{\st}{{\text{\huge {.}}}\;}
\newcommand{\R}{\mathbb{R}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\PP}{\mathcal{P}}
\newcounter{theproblem} \setcounter{theproblem}{1}
\newenvironment{problem}[1][]
{\noindent{{\color{blue}\large\bf
\arabic{theproblem}. #1} \stepcounter{theproblem}\vspace{0.3cm}}\\}
{\vspace{0.5cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}\newpage}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\begin{document}
\noindent{\color{blue}{\Large\bf Homework 7 \hfill 21-127 Concepts of Math \hfill due 11.01.2012}\\
\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


% Assignment begins here! %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\noindent{\color{blue}\large\bf Name:} % WRITE YOUR NAME HERE
\vspace{0.3cm}\\
{\color{blue}\large\bf Andrew ID:} % WRITE YOUR ANDREW ID HERE
\vspace{0.3cm}\\
{\color{blue}\large\bf Section:} % WRITE YOUR RECITATION SECTION HERE
\vspace{0.3cm}\\
{\color{blue}\large\bf Collaborators:} % LIST ANYONE YOU WORKED WITH HERE
\vspace{0.3cm}\\
{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}

\begin{problem}[Surely, You (In)Jest! (10 pts)]
Consider the following claim:
\begin{quote}
Suppose $f:A\to B$ and $g:B\to C$ are functions. Suppose $g\circ f:A\to C$ is injective.\vspace{0.2cm}\\
Then $g$ is also injective.
\end{quote}
What is wrong with the following ``spoof'' of this claim?
\begin{quote}
Suppose $g\circ f$ is an injection. We want to show $g$ is an injection.\vspace{0.2cm}\\
Let $x,y\in B$ be given. Suppose $g(x)=g(y)$.\vspace{0.2cm}\\
We know $\exists a,b\in A$ such that $f(a)=x$ and $f(b)=y$.\vspace{0.2cm}\\
Since $g$ is a well-defined function, this means $g(f(a))=g(x)$ and $g(f(b))=g(y)$.\vspace{0.2cm}\\
Since $g\circ f$ is injective and $g(f(a))=g(f(b))$, this means $a=b$.\vspace{0.2cm}\\
Since $f$ is a well-defined function, then $f(a)=f(b)$.\vspace{0.2cm}\\
This means $x=y$. Thus, $g$ is injective.
\end{quote}

\noindent {\bf\color{blue}Bonus:} Find a counterexample that shows the claim's conclusion is incorrect.
\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\begin{problem}[Inverses On A Plane (20 pts)]
Let $a,b\in\R$ be arbitrary and fixed. Suppose $a^2+b^2\neq 0$.\vspace{0.2cm}\\
Consider the function $f:\R\times\R\to\R\times\R$ defined by
\[ \forall (x,y)\in\R\times\R\st\qquad f(x,y)=(ax-by,bx+ay)\]
Prove that $f$ is a bijection by finding its inverse and proving that inverse is correct.
\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\begin{problem}[Jections, Jections Everywhere (25 pts)]
Suppose $f:A\to B$ and $g:B\to C$ are functions.
\begin{enumerate}[{\bf\color{blue}(a)}]
\item Suppose $f$ and $g$ are surjections. Prove that $g\circ f:A\to C$ is also a surjection.
\item Suppose $f$ and $g$ are injections. Prove that $g\circ f:A\to C$ is also an injection.
\item Suppose $f$ and $g$ are bijections. Prove that $g\circ f:A\to C$ is also a bijection.
\end{enumerate}

\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\begin{problem}[Game: Set Match (20 pts)]
In this problem, you may cite the following facts that were stated and (possibly) proven in lecture:
\begin{itemize}
\item Fact $\alpha$\;: If $S$ and $T$ are finite sets and $S\cap T=\varnothing$, then $|S\cup T|=|S|+|T|$.\vspace{0.2cm}\\
(Use this in {\bf\color{blue}(a)} with $S=\text{Im}_f(A)$ and $T=B-S$.)
\item Fact $\beta$\;: If a function $h:S\to T$ is injective, then $|S|\leq |T|$.
\item Fact $\gamma$\;: If a function $h:S\to T$ is surjective, then $|S|\geq |T|$.
\item Fact $\delta$\;: If $S\subseteq T$, then $|S|\leq|T|$.
\end{itemize}
\begin{enumerate}[{\bf\color{blue}(a)}]
\item Let $A$ and $B$ be finite sets and suppose $|A|=|B|$. Suppose $f:A\to B$ is a function that is injective.\vspace{0.2cm}\\
Prove that $f$ must also necessarily be surjective by showing $\text{im}_f(A)=B$.
\item Let $m,n\in\N$ be given. Suppose $g:[m]\to[n]$ is a bijection. Prove that $m=n$.
\end{enumerate}
\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}
\begin{problem}[Two To The $n$, and Beyond! (25 pts)]
Let $k\in\N-\{1\}$ be given. Define
\[ S_1=\{X\in\PP(\,[k]\,)\mid k\notin X\}\]
and
\[ S_2=\{X\in\PP(\,[k]\,)\mid k\in X\}\]
\begin{enumerate}[{\bf\color{blue}(a)}]
\item Prove that the sets $S_1$ and $S_2$ form a partition of $\PP(\,[k]\,)$.
\item Define a function $f_1:S_1\to\PP(\,[k-1]\,)$ that is a bijection and prove that it is.
\item Define a function $f_2:S_2\to\PP(\,[k-1]\,)$ that is a bijection and prove that it is.
\item Use what you proved in {\bf\color{blue}(a)} and {\bf\color{blue}(b)} and {\bf\color{blue}(c)} to write an {\bf induction} proof that $\PP(\,[n]\,)$ has $2^n$ elements, for every $n\in\N$.\vspace{0.2cm}\\
Note: Because of the restriction $k\geq 2$ above, make $n=1$ your base case, use $n=k\geq 1$ in your Induction Hypothesis, and prove the claim for $n=k+1$ in the Induction Step.\vspace{0.2cm}\\
{\bf Hint:} You should definitely use Fact $\alpha$ from Problem \#3 \ldots
\end{enumerate}
\vspace{0.2cm}

{\color{blue}\noindent\rule{\linewidth}{0.03cm}\vspace{0.3cm}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% TYPE YOUR SOLUTION HERE
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{problem}

\end{document}