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