\documentclass{2800hw}
\usepackage{amsmath,amssymb,latexsym}
\usepackage{verbatim}
\usepackage{utf8}
\begin{document}
\topic{Cardinality}
\homework{5}
\maketitle
\begin{exercises}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item
For each of the following pairs of sets, state whether $|A| < |B|$,
$|A| = |B|$, or $|A| > |B|$. Justify your answer, for example by giving a
bijection (no need to prove that it is a bijection), or by referring to examples
from class. As usual, $\mathbb{N}$ is the set of all natural numbers
$\{1, 2, 3, \dots\}$ and $\mathbb{Z}$ is the set of all integers
$\{\dots, -2, -1, 0, 1, 2, \dots\}$.
\begin{enumerate}
\item $A = \{1,2,3\}$, $B = \{a, b, c\}$.
\item $A = \{1,2,3\}$, $B = \{a,b,c,d\}$.
\item $A = \{1,2,3\}$, $B = \mathbb{Z}$.
\item $A = \mathbb{N}$, $B = \mathbb{Z}$.
\item $A = \mathbb{N}$, $B = \{0,1\}^*$, the set of all finite strings of 0's
and 1's.
\item $A = \mathbb{N}$, $B = 2^{\mathbb{N}}$ (the power set of $\mathbb{N}$)
\end{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item
In class, we gave three related definitions:
\begin{description}
\item[Definition of $|\cdot| = |\cdot|$:] We say that $|A| = |B|$ if there exists a bijection from $A$ to $B$.
\item[Definition of $|\cdot| \leq |\cdot|$:] We say that $|A| \leq |B|$ if there exists an injection from $A$ to $B$.
\item[Definition of $|\cdot| \geq |\cdot|$:] We say that $|A| \geq |B|$ if there exists a surjection from $A$ to $B$.
\end{description}
This is very suggestive notation; for example you might expect that if
$|A| \leq |B|$ then $|B| \geq |A|$. In this question you will prove that these
definitions make sense together.
\begin{enumerate}
\item Prove that $|A| \leq |B|$ if and only if $|B| \geq |A|$.
\item Prove that $|A| = |A|$.
\item Prove that if $|A| \leq |B|$ and $|B| \leq |C|$ then $|A| \leq |C|$.
\item Prove that $|A| = |B|$ if and only if both $|A| \leq |B|$ and $|A| \geq |B|$.
\end{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item Given functions $f$ and $g$ from $\mathbb{R}^+$ to $\mathbb{R}^+$
let $F(f,g)$ be the following statement:
\begin{quotation}
$F(f,g) = $``there is some $c>0$ such that for all $x > 1$, $f(x) \leq cg(x)$.''
\end{quotation}
Let $f_1 : x \mapsto x^2$ and let $f_2 : x \mapsto x$. Two students are arguing about
whether $F(f_1,f_2)$. Student one offers the following proof that $F(f_1,f_2)$:
\begin{quotation}
``I wish to prove that there exists $c>0$ such that for all $x > 1$,
$f_1(x) \leq cf_2(x)$. Let $c = x$. Since $x > 1$, we know $c>0$.
Moreover, for any $x > 1$, we have
\begin{displaymath}
cf_2(x) = x \times x = x^2 \geq x^2 = f_1(x)
\end{displaymath}
Thus $F(f_1, f_2)$.''
\end{quotation}
Student two offers the following rebuttal, claiming that $\lnot F(f_1, f_2)$.
\begin{quotation}
``I wish to prove that $\lnot F(f_1,f_2)$. In other words, I need to show that
for all $c > 0$, there exists an $x > 1$ such that $f_1(x) > cf_2(x)$.
Choose an arbitrary $c > 0$. Let $x = c + 1$. Then
\begin{displaymath}
f_1(x) = f_1(c+1) = c^2 + 2c + 1 > c^2 + c = cf_2(c + 1) = cf_2(x)
\end{displaymath}
Note also that since $c > 0$, $x > 1$. Thus there exists such an $x>1$ for each
$c > 0$, so I have shown $\lnot F(f_1,f_2)$.''
\end{quotation}
The student who is incorrect has proved something different than what they
are claiming. Which student is it, and what have they proved?
\end{exercises}
\end{document}