% If you are working from this template to just write up your own
% solutions, I'm trying to keep it simple for you and there are only a
% few places you need to edit. On line 43 there's a place where the
% phrase "YOUR NAME HERE" appears; change it to your actual
% name. Several places below there are places where the phrase "YOUR
% ANSWER HERE" appears, and directly below (or replacing) those lines
% are good places to put your answers.
%
% One important thing you need to do, however (due to the complicated
% way I use a single form to produce both the question sheets and
% solution writeups) is to make sure that you keep the word 'solution'
% in your filename, or else your answers won't be printed at all.
\documentclass[12pt]{article}
\usepackage[margin=0.7in,dvips]{geometry}
\usepackage{fancyhdr,lastpage}
\usepackage{amsmath,amsfonts,amsthm,amssymb}
\usepackage{tikz}
\usepackage{substr}
\usepackage{hyperref}
\IfSubStringInString{\detokenize{solution}}{\jobname}{%
% Solutions
\newcommand\qfill{}
\newcommand\qpage{}
\newcommand\qonly[1]{}
\newcommand\answer[1]{#1}
\newcommand\question[1]{{\em #1}}
\newcommand\rubric[1]{}
}
{%
% Question sheets
\newcommand\qfill{\vfill}
\newcommand\qpage{\newpage}
\newcommand\qonly[1]{#1}
\newcommand\answer[1]{}
\newcommand\question[1]{#1}
\newcommand\rubric[1]{}
}
\pagestyle{fancy}
\lhead{MATH 311-01}
\chead{Extra Credit Problem Set \answer{ solutions}}
\rhead{\answer{}}
\lfoot{}
\cfoot{Page \thepage\ of \pageref{LastPage}}
\rfoot{{\bf due April 25, 2017}}
\newtheorem{prop}{Proposition}
% The command below redefines \neg (the logical negation character)
% to be a big tilde, in line with the usage in the book. Comment it
% out if you prefer the more traditional negation symbol.
\renewcommand*{\neg}{\mathord{\sim}}
\begin{document}
\begin{enumerate}
\item \question{Prove that for sets $A$ and $B$, if $|A|\leq |B|$,
then $|\mathcal P(A)|\leq|\mathcal P(B)|$}
\answer{Note that this statement is not about arithmetic comparison
of set sizes, but about the existence of certain functions
relating sets. Here is a more direct framing of the statement to
be proven, and its proof.
\begin{prop}
For sets $A$ and $B$, if an injection from $A$ to $B$ exists,
then than injection from $\mathcal P(A)$ to $\mathcal P(B)$
exists.
\end{prop}
\begin{proof}
In accordance with our premise, let us assume the existence of
an injection $f:A\rightarrow B$. Now we may explicitly construct
a function $g:\mathcal P(A)\rightarrow \mathcal P(B)$ as such:
$g(S)=\{f(a):a\in S\}$ which is to say, he function $g$, applied
to an element $S$ of $\mathcal P(A)$ (i.e. $S$ is a subset of
$A$), invokes $f$ on each individual element of $S$ to produce a
set of elements of $B$ (i.e. a subset of $B$, or an element of
$\mathcal P(B)$). We shall show that $g$ is an injeciton by
way of contradiction.
Suppose, counterfactually, that there are $S,T\in\mathcal P(A)$
with $S\neq T$ but such that $g(S)=g(T)$. Since $S\neq T$, it
must be the case that either $S\not\subseteq T$ or
$T\not\subseteq S$; WLOG we may assume $S\not\subseteq T$. Thus
there is some $x\in S$ such that $x\notin T$. By the way we
constructed $g$, since $x\in S$, it follows that $f(x)\in
g(S)$. Since $g(S)=g(T)$, it then follows that $f(x)\in
g(T)$. Thus, by the definition of $g$, there must be some $y\in
T$ such that $f(y)=f(x)$. But since $x\notin T$, $y\neq x$,
violating injectivity of $f$ and leading to a contradiction.
\end{proof}
}
\item \question{Prove (or demonstrate with a suitable function or
functions) that the following equalities among cardinalities are
true; recall the interval notations $(a,b)=\{x\in\mathbb
R:a