\documentclass[11pt,letterpaper]{article}
\usepackage{multicol}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath}
\usepackage{amsfonts}
\usepackage{amssymb}
\usepackage{mathrsfs}
%\usepackage{pstricks, pst-node, pst-plot}

\newcommand{\ds}{\displaystyle}
\newcommand{\bv}{\mathbf}
\newcommand{\lv}{\langle}
\newcommand{\rv}{\rangle}
\newcommand{\Zp}{\mathbb{Z}_+}
\newcommand{\Z}{\mathbb{Z}}

\begin{document}


\begin{center}\begin{large}\textbf{Math 101 - Problem Set 5\\
Due Tuesday, October 17}\end{large}\end{center}



\pagestyle{empty}


\begin{enumerate} 

\item Let $A$ and $B$ be finite sets. Show that the set of all functions $f:A \to B$ is finite.

\item Let $A$ be a set of cardinality $n$, for some $n\in \Zp$. Suppose $A$ has a total ordering $\leq$.

\begin{enumerate}
\item Show that $A$ has a largest element and a smallest element. 

\item Show that $A$ has the same order type as $\{1, 2, \ldots, n\}$ equipped with the standard ordering.

\end{enumerate}

\item Show that every nonempty subset $A \subset \Zp$ has a smallest element. \\
(\textit{Hint: first show that every subset of $\{1, \ldots, n\}$ has a smallest element.})

\item For each of the following subset of $\mathbb{R}^\omega$, either express it as the cartesian product of subsets of $\mathbb{R}$, or explain why that is not possible. Let $\textbf{x}$ denote the $\omega$-tuple $(x_i)_{i \in \Zp}$.

\begin{enumerate}
\item $\{\textbf{x} \mid \textrm{$x_i$ is an integer for all $i$} \}$
\item $\{\textbf{x}\mid \textrm{$x_i \geq i $  for all $i$} \}$
\item $\{\textbf{x}\mid \textrm{$x_i$ is an integer for all $i \geq 100$} \}$
\item $\{\textbf{x}\mid x_1=x_2 \}$
\end{enumerate}


\item Show that $\{0,1\}^{\omega}$ has the same cardinality as $\mathscr{P}(\mathbb{Z}_+)$ by constructing a bijection between them.


\item Let $n \in \Zp$ and let $A_1, A_2, \ldots, A_n$ be nonempty countable sets. Show that the cartesian product $A_1 \times A_2 \times \cdots \times A_n$ is countable.

\item Show that the following sets are countable.

\begin{enumerate}
\item The set $A_n$ of all $n$-element subsets of $\mathbb{Z}_+$ (for $n \in \Zp$).

\item The set $B$ of all finite subsets of $\mathbb{Z}_+$.


\end{enumerate}

\item Show that the set of functions $f: \Zp \to \Zp$ is uncountable.



\end{enumerate}
\end{document}