\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}


