\documentclass{article}
\usepackage{amssymb}
\usepackage{multicol}
\usepackage{graphicx}
\usepackage{color}
\usepackage{amsthm}
\usepackage{hyperref}
\usepackage{amsmath}
\usepackage{verbatim}
\usepackage{caption}
\usepackage{subcaption}
\usepackage{amsmath, epsfig}
\setlength{\parskip}{8pt}

\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem{corollary}{Corollary}
%\theoremstyle{Remark}
%\newtheorem{remark}
\renewcommand{\today}{}
\newcommand{\abs}[1]{\left| #1\right|}
\newcommand{\Lap}[1]{\mathcal{L}\left\{#1\right\}}


\addtolength{\topmargin}{-.875in}
\addtolength{\textheight}{1.75in}

\newcommand{\solution}[1]{
\color{red}\begin{quote}Solution:\quad 
\color{black} #1
\end{quote}\color{black}
}
\newcommand{\ba}{\backslash}
\DeclareMathOperator{\Gcd}{gcd}
\renewcommand{\gcd}[2]{\Gcd\left(#1, #2\right)}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\floor}[1]{\left\lfloor #1\right\rfloor}
\newcommand{\C}{\mathbb{C}}
\DeclareMathOperator{\Diam}{diam}
\newcommand{\Mod}[1]{\ (\bmod\ #1)}
\newcommand{\diam}[1]{\Diam\left(#1\right)}


\begin{document}
\title{Math 127 Homework}
\author{Mary Radcliffe}
\date{Due 29 March 2018}
\maketitle

Complete the following problems. Fully justify each response.

NOTE: due to the Spring Break, this homework set is a bit longer than is typical. You only need to turn in those problems marked with (*).

\begin{enumerate}

\item In lecture we defined a finite set $X$ to be of size $n$ if there exists a bijection $f:[n]\to X$.

Prove that if $X, Y$ are finite, and there exists a bijection $f:X\to Y$, then $|X|=|Y|$.

\item (*) Let $X$ be a finite set, and suppose there is a surjection $f:X\to Y$. Prove that $|X|\geq |Y|$. 

\item (*) Let \[X_2=\{n\ | 1\leq n\leq 200, n=k^2\ \exists k\in \Z\},\] \[X_3=\{n\ | \ 1\leq n\leq 200, n=k^3\ \exists k\in \Z\},\] and \[X_4 = \{n\ | \ 1\leq n\leq 200, n=k^4\ \exists k\in \Z\}.\] Determine $|X_2\cup X_3\cup X_4|$.

\item Prove Theorem 4.2.12: De Morgan's Law for sets (finite version).

\item You decide to go to Chipotle for a burrito. Chipotle has many options: 2 choices of rice, 2 choices of beans, 5 choices of meat, 4 choices of salsa, and 5 other toppings (including queso and guacamole). 

How many different burritos could you order having exactly 1 rice, 1 bean, 1 meat, 2 salsas, and 2 other toppings?

\item (*) Let $X=\{ (a_1, a_2, \dots, a_n)\ | \ a_i\in\{0,1\}\forall i\} = \{0,1\}^n$. These are sometimes called bitstrings of length $n$.
\begin{enumerate}
\item Show that there is a bijection between $X$ and $\{f:[n]\to\{0,1\}\}$, the set of functions from $[n]$ to $\{0,1\}$
\item Show that there is a bijection between $X$ and $\mathcal{P}([n])$.
\item Determine $|X|$.
\end{enumerate}

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

\item (*) Let $n, k\in \N$ with $n\geq k$. Prove, by counting in 2 ways, that $k{n\choose k} = (n-k+1){n\choose k-1}$.

\item Let $n, m\in\N$ with $m\leq n$. Prove that\[\sum_{k=m}^n{n\choose k}{k\choose m} = 2^{n-m}{n\choose m}.\]

\item (*) How many subsets of $[20]$ contain a multiple of 4? Prove that your answer is correct.

\item (*) Let $f:X\to Y$ be a bijection. Prove that $X$ is countably infinite if and only if $Y$ is countably infinite.

\item Show directly (without using Proposition 4.3.10) that $\N\times\N$ is countably infinite. (If you cannot derive a bijection, you may look to Problem 4.3.8 for one).

\item (*) Let $X$ be a finite set. Show that $\N^X=\{f:X\to \N\}$ is countably infinite.

\end{enumerate}

\end{document}