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

%%% 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 Fall 2019 \ -  \ {\bf Problem Set 8}}

% Put your name and section here.
{\large due November 22}
\end{center}


\begin{enumerate}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

	\item Let $X,Y,Z,W$ be sets with $|X| = |Z|$ and $|Y| = |W|$.
	 \begin{enumerate}
      \item Cardinal addition is defined by $|X|+|Y| = |X \cup Y|$ where $X$ and $Y$ are disjoint.  Prove that cardinal addition is well-defined, meaning that
	   \[ |X| + |Y| = |Z| + |W| \]
      where $X$ and $Y$ are disjoint and $Z$ and $W$ are disjoint.
	  \item Cardinal multiplication is defined by $|X|\cdot|Y| = |X \times Y|$.  Prove that cardinal multiplication is well-defined, meaning that
	   \[ |X|\cdot |Y| = |Z|\cdot |W|. \]
      \item Cardinal exponentiation is defined by $2^{|X|} = |\mathcal{P}(X)|$.  Prove that cardinal exponentiation is well-defined, meaning that
       \[ 2^{|X|} = 2^{|Z|}. \]
	 \end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

	\item Let $n$ be a positive integer.  Prove that the set of positive integer divisors of $n$ is finite.
	
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

	\item
	 \begin{enumerate}
      \item Prove that $|\{x\in \RR \mid -1 < x < 1\}| = |\RR|$.
      \item Prove that $|\{x\in \RR \mid -1 \leq x \leq 1\}| = |\RR|$.
     \end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

	\item Prove each of the following sets is countable.
	 \begin{enumerate}
	  \item The set of prime numbers.
	  \item $\ZZ \times \ZZ$.
	  \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 Prove that the set of irrational numbers, $\RR \setminus \QQ$, is uncountable.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

	\item Use Cantor's diagonalization argument to prove that the set of all functions from $\ZZ_{>0}$ to $\ZZ_{>0}$ is uncountable.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

	\item Let $X$ be an infinte set.
	 \begin{enumerate}
	  \item Prove that $|X| \geq \aleph_0$.
	  \item Prove that $|X|+1 = |X|$.

	  [Hint:  First prove it for the case that $X$ is countably infinite.  Then for the general case, part (a) implies that $X$ has a countably infinite subset $Y$.  Use the fact that $|Y|+1 = |Y|$.]
	 \end{enumerate}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\end{enumerate}
\end{document}


