\documentclass{article}

\def\ifsoln{\iftrue}

\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{amsmath}
\usepackage[inline]{enumitem}
\usepackage[colorlinks=true]{hyperref}
\usepackage{comment}

\theoremstyle{definition}
\newtheorem{problem}{Problem}
\newtheorem{definition}[problem]{Definition}
\newtheorem{reading}[problem]{Reading}
\theoremstyle{plain}
\newtheorem{theorem}[problem]{Theorem}

\ifsoln
\newenvironment{solution}{\begin{proof}[Solution.]}{\end{proof}}
\else
\excludecomment{solution}
\fi

\begin{document}

\title{Math 2001 Assignment 38}
\date{Due Monday, December 1}
\author{Your name here}
\maketitle

\begin{center}
\fbox{\textbf{This homework assignment is optional!  You may submit it for extra credit.}}
\end{center}

\begin{reading}
Scheinerman, \S\S1--12, 14--16, 20, 22, 24--26.  These are all of the sections we have discussed in class (\S16 was only discussed briefly) so far.  During the last two weeks of class, we will cover most of this material again but with a new emphasis on counting the sizes of sets.

I strongly recommend rereading all of the material we have covered so far during Thanksgiving break.  Make sure to read \emph{actively}.  Every time you encounter a new definition, write down several examples of the object being defined.  Write down several examples of objects that satisfy some but not all of the conditions of the definition.  If you encounter a term in the text and can't say \emph{exactly} what it means, go back in the text and reread the definition of that term and make up examples and do exercises until you do understand it.

The first 1 to 5 problems in each section are essentially practice with the definitions.  You should be able to do \emph{all} of these definition-oriented questions in the sections we have covered in class.  You can find solutions to many of these questions in the back of the book.

Practicing proof writing is more difficult to do if you don't have someone to read and critique your work.  However, a good way to do improve your proof writing is to practice your proof reading.  Read the proofs in the textbook and make sure you understand why every sentence is there.  There are many exercises in the textbook that ask you to complete proofs that require similar steps to ones givin in the text.  Do these problems on your own and try to be as clear as you possibly can.

Feel free to e-mail me during the break if you have questions.
\end{reading}

\begin{problem}
Scheinerman, \S26, \#12
\end{problem}

\begin{problem}
In class we discussed the proof the Cantor--Sch\"oder--Bernstein theorem.  In this exercise, you will fill in the details of the proof.

Suppose that $A$ and $B$ are sets and that $f : A \rightarrow B$ and $g : B \rightarrow A$ are injections.  Call an element $a \in A$ a \emph{$B$-stopper} if there is a $b \in B$ such that
\begin{equation*}
a = g \circ f \circ g \circ \cdots \circ f \circ g(b) = a
\end{equation*}
and there is not an $a' \in A$ such that $f(a') = b$.  Similarly, call an element $b \in B$ a \emph{$B$-stopper} if there is a $b' \in B$ such that 
\begin{equation*}
b = f \circ g \circ f \circ \cdots \circ f \circ g(b')
\end{equation*}
and there is no $a \in A$ such that $b' = f(a)$.

Let $f^{-1}$ be the function from the image of $f$ to $A$ that sends $b$ to the unique $a \in A$ such that $f(a) = b$.  Let $g^{-1}$ be the function from the image of $g$ to $B$ that sends $a$ to the unique $b \in B$ such that $g(b) = a$.

Define functions $F : A \rightarrow B$ and $G : B \rightarrow A$ by the follwoing rules:
\begin{equation*}
F(a) = \begin{cases} g^{-1}(a) & \text{$a$ is a $B$-stopper} \\ f(a) & \text{$a$ is not a $B$-stopper} \end{cases}
\qquad
G(b) = \begin{cases} g(b) & \text{$b$ is a $B$-stopper} \\ f^{-1}(b) & \text{$b$ is not a $B$-stopper} \end{cases}
\end{equation*}

\begin{enumerate}[label=(\roman{*})]
\item Suppose that $a \in A$.  Prove that $a$ is a $B$-stopper if and only if $f(a)$ is a $B$-stopper. \label{part1}
\item Suppose that $b \in B$.  Prove that $b$ is a $B$-stopper if and only if $g(b)$ is a $B$-stopper. \label{part2}
\item Prove that the formula for $F$ defines a function from $A$ to $B$ and the formula for $G$ defines a function from $B$ to $A$.  (Hint:  Is $a$ in the domain of $g^{-1}$ when $a$ is a $B$-stopper?  Is $b$ in the domain of $f^{-1}$ when $b$ is not a $B$-stopper?) \label{part3}
\item Prove that $G(F(a)) = a$ for all $a \in A$ and that $F(G(b)) = b$ for all $b \in B$. \label{part4}
\item Conclude that $|A| = |B|$.
\end{enumerate}

\end{problem}


\end{document}
