% 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<x<b\}$ and $[a,b]=\{x\in\mathbb R:a\leq x\leq b\}$.}

  \begin{enumerate}
  \item \question{$|(0,1)|=|[0,1]|$.}

    \answer{By the Cantor-Schr\"oder-Bernstein Theorem (and related
      results), we may demonstrate an equality of cardinality by using
      a pair of injections $f:(0,1)\rightarrow[0,1]$ and
      $g:[0,1]\rightarrow (0,1)$. There are two fairly simple
      functions which will suffice: $f(x)=x$ is a straightforward
      injection (not surjective, since no element of the domain is
      mapped to $0$ or $1$ by $f$). To define $g$, one simple example
      is $g(x)=\frac{x+1}3$, which will map $[0,1]$ injectively to the
      range $[\frac13,\frac23]$, which sits comfortably inside the
      open interval $(0,1)$.  }

  \item \question{$|(0,1)|=\mathbb R$.}

    \answer{A clever, elegant bijection which relegates the heavy
      lifting to trigonometry is a function $f:(0,1)\rightarrow\mathbb
      R$ given by $f(x)=\tan\left(\pi x-\frac\pi 2\right)$, which has
      an inverse $f^{-1}(y)=\frac{\arctan y}\pi+\frac12$ and is thus a
      bijection.
      
      You can also build more complicated piecewise functions
      involving reciprocals (noting that reciprocals of numbers close
      to 0 are mapped to very large-magnitude values), but doing so is
      difficult and would require breaking $(0,1)$ into three
      subsections to cover $(-\infty,-1)$, $[-1,1]$, and
      $(1,\infty)$. Here's an example of a function that would do
      that:
      \[g(x)=\left\{
        \begin{aligned}
          \frac1{3x}&\text{ if }0<x<\tfrac13\\
          6x-3&\text{ if }\frac13\leq x\leq \tfrac23\\
          \frac1{3(x-1)}&\text{ if }\tfrac23<x<1\\
        \end{aligned}
      \right.\]
    }
    
  \item \question{$|[0,1]|=|[0,1]\times[0,1]|$.}

    \answer{We shall build a pair of injections
      $f:[0,1]\rightarrow[0,1]^2$ and $g:[0,1]^2\rightarrow
      [0,1]$. The former is easy; we might just define $f(x)$ to be
      the ordered pair $(x,0)$ for every $x$ and that is
      straightforwardly an injection. To build he opposite injection
      we could make use of a scheme of \emph{digit interleaving}. To
      determine $g((x,y))$, we look at the canonical decimal expansion
      of $x$ and $y$ (so, specifically, we consider the expansiion
      which does not end in an infinite string of '9's; such a decimal
      number can also be expressed with an infinite string of '0's,
      and we establish the latter to standardize). Now, given decimal expansions $x=a_na_{n-1}a_{n-2}\ldots a_0.a_{-1}a_{-2}a_{-3}\ldots$ and $y=b_nb_{n-1}b_{n-2}\ldots b_0.b_{-1}b_{-2}b_{-3}\ldots$, where if necessary we pad one or the other of $x$ and $y$ with leading zeroes to have the same number of digits before the decimal point, then we can define
      \[g((x,y))=a_nb_na_{n-1}b_{n-1}a_{n-2}b_{n-2}\ldots
      a_0b_0.a_{-1}b_{-1}a_{-2}b_{-2}\ldots\]
      so, for instance,
      \[g((10\pi,\sqrt3))=g((31.41592653\ldots,01.73205080\ldots))=3011.4713529025605830\ldots\]
      This will be an injection because different decimal-string
      inputs result in different decimal-string outputs, and by
      standardizing away from the ending with an infinite string of 9s,
      we can be assured that different decimal strings represent
      different real numbers. Note that that standardization means
      that $g$ is \emph{not} a surjection; there is no ordered pair
      $(x,y)$ such that $g((x,y))=\frac1{11}=0.09090909\ldots$.}
  \end{enumerate}
\end{enumerate}

\end{document}
