\documentclass{article}
\usepackage{amsmath}
\usepackage{amssymb}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\CC}{\mathbb{C}}
\begin{document}
{\bf Worksheet \#5; date: 09/12/2018}
{\bf MATH 55 Discrete Mathematics}
\begin{enumerate}
\item {\em (Rosen 2.3.34) True / False?} If $f$ and $f \circ g$ are one-to-one, then $g$ must be one-to-one.
\item {\em (Challenging; Rosen 2.3.80)} Show that a set $S$ is infinite if and only if there is a proper subset $A$ of $S$ such that there is a one-to-one correspondence between $A$ and $S$.
\item {\em (Rosen 2.4.35, 36)} Use the identity
\[
\frac{1}{k(k+1)} = \frac{1}{k} - \frac{1}{k+1}
\]
to compute $\sum_{k=1}^n \frac{1}{k(k+1)}$.
\item {\em (Rosen 2.4.41)} Find a formula for $\sum_{k=0}^m \lfloor \sqrt{k} \rfloor$.
\item {\em (Rosen 2.5.3)} Deterine whether each of these sets is countable or uncountable. For those that are countably infinite, exhibit a one-to-one- correspondence between the set of positive integers and that set.
\begin{enumerate}
\item all bit strings not containing the bit $0$
\item all positive rational numbers that cannot be written with denominators less than $4$
\item the real numbers not containing $0$ in their decimal representation
\item the real numbers containing only a finite number of $1$s in their decimal representation
\end{enumerate}
\item {\em (Rosen 2.5.11)} Give an example of two uncountable sets $A$ and $B$ such that $A \cap B$ is
\begin{enumerate}
\item finite.
\item countably infinite.
\item uncountable.
\end{enumerate}
\item {\em (Rosen 2.5.17)} If $A$ is an uncountable set and $B$ is a countable set, must $A - B$ be uncountable?
\item {\em True / False?} $|\RR| = |\CC|$
\end{enumerate}
\end{document}