<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\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| &lt; |B|$,
$|A| = |B|$, or $|A| &gt; |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&gt;0$ such that for all $x &gt; 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&gt;0$ such that for all $x &gt; 1$,
$f_1(x) \leq cf_2(x)$.  Let $c = x$.  Since $x &gt; 1$, we know $c&gt;0$.
Moreover, for any $x &gt; 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 &gt; 0$, there exists an $x &gt; 1$ such that $f_1(x) &gt; cf_2(x)$.
Choose an arbitrary $c &gt; 0$.  Let $x = c + 1$.  Then
\begin{displaymath}
f_1(x) = f_1(c+1) = c^2 + 2c + 1 &gt; c^2 + c = cf_2(c + 1) = cf_2(x)
\end{displaymath}
Note also that since $c &gt; 0$, $x &gt; 1$.  Thus there exists such an $x&gt;1$ for each
$c &gt; 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}
</pre></body></html>