\documentclass{article}
\usepackage{amssymb, mathrsfs, enumitem}
\usepackage{tikz-cd}
\usepackage{multicol}
\usepackage{graphicx}
\usepackage{color}
\usepackage{amsthm}
\usepackage{hyperref}
\usepackage{verbatim}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{amsmath, epsfig, colortbl}
\setlength{\parskip}{8pt}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{cor}{Corollary}
\theoremstyle{definition}
\newtheorem{prop}{Proposition}
\newtheorem{fact}{Fact}
\newtheorem{example}{Example}
\newtheorem{definition}{Definition}
\renewcommand{\today}{}


\addtolength{\topmargin}{-.875in}
\addtolength{\oddsidemargin}{-.8in}
\addtolength{\textwidth}{1.6in}
\addtolength{\textheight}{1.75in}


\newcommand{\abs}[1]{\left| #1\right|}
\newcommand{\la}{\Leftarrow}
\newcommand{\ra}{\Rightarrow}
\renewcommand{\iff}{\Leftrightarrow}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\floor}[1]{\left\lfloor #1\right\rfloor}
\newcommand{\ceil}[1]{\left\lceil #1\right\rceil}
\renewcommand{\P}{\mathcal{P}}
\newcommand{\inv}[1]{#1^{-1}}

\newcommand{\eps}{\epsilon}
\newcommand{\N}{\mathbb{N}}

\newcommand{\ba}{\backslash}


\begin{document}
\title{Math 127 Homework}
\author{Mary Radcliffe}
\date{Due 9 April 2019}
\maketitle

Complete the following problems. Fully justify each response. You need only turn in those problems marked with a (*).
\begin{enumerate}

\item (*) A {\it partition of $n$} is a sequence of integers $(a_1, a_2, \dots, a_k)$ such that $a_i\geq 0$ for each $i$, and $\displaystyle\sum_{i=1}^k a_i = n$. The number $k$ is called the number of parts of the partition.
\begin{enumerate}
\item Let $S(n, k)$ denote the set of partitions of $n$ into $k$ parts. Calculate $|S(n, k)|$ for at least 4 different choices of $(n, k)$. Make sure to use both differing $n$ values and differing $k$ values.
\item Find a bijection between ${[n+k-1]\choose k-1}$ and $S(n, k)$. Conclude that $|S(n, k)|={n+k-1\choose k-1}$.

Hint: If you're not sure how to construct the bijection, look at some examples with small $k$ (like $k=2$). It might help to think about the numbers in $[n+k-1]$ along a number line.
\end{enumerate}

\item Let $X$ and $Y$ be finite sets. Define $X^Y=\{f:Y\to X\}$, the set of all possible functions from $Y$ to $X$. Prove that $|X^Y|=|X|^{|Y|}$.

\item Prove Theorem 2 in the \href{http://math.cmu.edu/~mradclif/teaching/127S19/Notes/Infinite%20Cardinality.pdf}{Infinite Cardinality Notes}.

\item (*) Prove Theorem 4 in the \href{http://math.cmu.edu/~mradclif/teaching/127S19/Notes/Infinite%20Cardinality.pdf}{Infinite Cardinality Notes}. Hint: Use a technique similar to that described in the proof of Theorem 3. 

\item Let $X$ be a countable set. Prove that $\{A\subseteq X\ | \ A\hbox{ is finite}\}$ is countable.

\item (*) Let $a, b\in\R$ with $a<b$. Prove that $|\{x\in \R\ | \ a< x< b\}|=|\{x\in \R\ | \ 0<x<1\}|$.

\item Use the technique of Theorem 5 in the \href{http://math.cmu.edu/~mradclif/teaching/127S19/Notes/Infinite%20Cardinality.pdf}{Infinite Cardinality Notes} to prove Theorem 6.

\item (*) Let $X=\{x\in \R\ | \ \hbox{the decimal representation of $x$ contains only 4s and 7s}\}$. Is $X$ countable or uncountable? Prove that your answer is correct.

\item\begin{enumerate}
\item Let $X$ be the set of all sequences $(a_1, a_2, a_3, \dots)$ in $\N$ having the property that $a_i\leq a_{i+1}$ for all $i\geq 1$. For example, here is an element of $X$: $(1, 4, 6, 10, 26, 1583, \dots)$. Is $X$ countable or uncountable? Prove that your answer is correct.

\item Let $X$ be the set of all sequences $(a_1, a_2, a_3, \dots)$ in $\N$ having the property that $a_i\geq a_{i+1}$ for all $i\geq 1$. For example, here is an element of $X$: $(19, 16, 2, 1, 1, 1, 1, \dots)$. Is $X$ countable or uncountable? Prove that your answer is correct.
\end{enumerate}

\item Prove that $|\R\times \R|=|\R|$.

\item (*) For each of the following sets, determine if it is finite, countably infinite, or uncountable. You need not prove your answer is correct, but you should give a reason for your response.
\begin{enumerate}
\item $\{x\in\R\ | \ x^2\in \Z\}$
\item For some $n\in\N$, $\{(a_1, a_2, \dots, a_n)\in\N^n\ | \ a_1+a_2+\dots+a_n<5000\}$
\item $\{S\in\P(\N)\ | \ \N\ba S\hbox{ is finite}\}$
\item $\R\ba S$, where $S$ is a countable set
\item $\{x\in \R\ | \ \hbox{there is a decimal expansion of $x$ with only even digits}\}$
\end{enumerate}

\end{enumerate}
\end{document}