\documentclass[12pt]{article}
\usepackage{amssymb,amsmath,amsthm}
\usepackage{color}
\usepackage{verbatim}
%%% Margins
\setlength{\topmargin}{0pt}
\setlength{\headheight}{0pt}
\setlength{\headsep}{0pt}
\setlength{\topskip}{0pt}
\setlength{\footskip}{0pt}
\setlength{\oddsidemargin}{-20pt}
\setlength{\textheight}{9in}
\setlength{\textwidth}{6.7in}
\setlength{\parindent}{0pt}
\setlength{\parskip}{4ex}
%%% Environments %%%
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{claim}[theorem]{Claim}
\theoremstyle{definition}
\newtheorem{define}{Definition}
\newtheorem{remark}[define]{Remark}
\newtheorem{example}{Example}
\newtheorem{question}{Question}
\newtheorem{algorithm}{Algorithm}
\numberwithin{equation}{section}
%%% Macros %%%
% Some macros to get you started
\DeclareMathOperator{\Vol}{Vol}
\DeclareMathOperator{\im}{im}
\newcommand{\ZZ}{\mathbb{Z}}
\newcommand{\RR}{\mathbb{R}}
\newcommand{\CC}{\mathbb{C}}
\newcommand{\NN}{\mathbb{N}}
\newcommand{\QQ}{\mathbb{Q}}
\begin{document}
\pagestyle{empty}
\begin{center}
{\large MATH 108 Winter 2019 \ - \ {\bf Problem Set 6}}
% Put your name and section here.
{\large due March 1}
\end{center}
\begin{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item Prove that each function is a bijection.
\begin{enumerate}
\item $f:(2,\infty) \to (-\infty,-1)$ defined by $f(x) = \dfrac{-x}{x-2}$.
\item $f:\NN_1 \times \NN_1 \to \NN_1$ defined by $f(x,y) = 2^{x-1}(2y-1)$.
\item $f:\ZZ/8\ZZ \to \ZZ/8\ZZ$ defined by $f(\overline{x}) = \overline{5x-1}$.
\end{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item For postive integers $n$ and $m$, let $[n] = \{1,2,\ldots,n\}$ and $[m] = \{1,2,\ldots,m\}$.
\begin{enumerate}
\item Let $A$ be the set of all functions from $[n]$ to $[m]$. Compute $|A|$ in terms of $n$ and $m$.
\item Let $B$ be the set of all bijective functions from $[n]$ to $[m]$. Compute $|B|$ in terms of $n$ and $m$.
\item Let $C$ be the set of all injective functions from $[n]$ to $[m]$. Compute $|C|$ in terms of $n$ and $m$.
\end{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item Let $A$ and $B$ be finite sets with $|A| = |B|$, and let $f:A\to B$.
\begin{enumerate}
\item Prove that if $f$ is injective, then $f$ is surjective.
\item Prove that if $f$ is surjective, then $f$ is injective.
\end{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item Let $A$ be a finite set and $B$ be an infinite set with $A \subseteq B$. Prove that $B \setminus A$ is infinite.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item For each infinite set, determine if it is countable or uncountable. Then prove your answer.
\begin{enumerate}
\item The set of prime numbers.
\item $\NN_1 \times \NN_1 \times \NN_1$.
%\item The set of all functions from $\NN_1$ to $\{0,1\}$.
\item[(d)] The set of all finite-length binary strings, $\bigcup_{n = 0}^\infty \{0,1\}^n$. (This is the set of all possible computer files.)
\end{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%\item Let $\NN_0^\infty$ denote the set of all infinite sequences of nonnegative integers,
% \[ \NN_0^\infty = \{(a_1,a_2,a_3,\ldots)\mid a_1,a_2,a_3,\ldots \in \NN_0\}. \]
%Use Cantor's diagonalization argument to prove that $\NN_0^\infty$ is uncountable.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\item[7.] Let $\NN_0^\infty$ denote the set of all infinite sequences of nonnegative integers,
\[ \NN_0^\infty = \{(a_1,a_2,a_3,\ldots)\mid a_1,a_2,a_3,\ldots \in \NN_0\}. \]
Let $A$ be the subset of $\NN_0^\infty$ consisting of all sequences that have only a finite number of nonzero entries. Prove that $A$ is countable by finding a bijection between $\NN_1$ and $A$.
[Hint: For each $n \in \NN_1$, use the prime factorization of $n$ to produce a sequence in $A$.]
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\end{enumerate}
\end{document}