\documentclass{article}
\usepackage{graphicx}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{enumerate}
\usepackage{ifthen}
\usepackage{ulem} % for strikethrough \sout{...} command
\usepackage{color}
\usepackage{hyperref}

% for the smiley face
\usepackage{wasysym}

\setlength{\unitlength}{0.1in}

\setlength{\oddsidemargin}{-0.25in}
\setlength{\evensidemargin}{-0.25in}
\setlength{\topmargin}{-0.25in}
\setlength{\headheight}{0.0in}
\setlength{\headsep}{0.0in}
\setlength{\topskip}{0.0in}
\setlength{\textheight}{9.75in}
\setlength{\textwidth}{7in}

\newcommand{\bdot}{\, {\scriptstyle{\bullet}} \,}
\newcommand{\B}[1]{{\bf {#1}}}
\newcommand{\la}{\langle}
\newcommand{\ra}{\rangle}

\newcommand{\myspace}{\parbox[c][0.25in]{0.25in}{\hfill}}
\newcommand{\varspace}[2]{\mbox{\parbox[c][#1]{#2}{\hfill}}}
\newcommand{\force}{{\noindent $\mbox{\;}$}}

\newcommand{\diagquotient}[2]{\displaystyle{{#1 \atop \;}\hspace*{-0.1in} \mbox{\put(0,0){\line(2,1){2}}} \hspace*{0.1in} {\; \atop #2}}}

\newcommand{\bproof}{\noindent {\bf Proof:} \quad}
\newcommand{\eproof}{$\blacksquare$}

\begin{document}

\pagestyle{empty}

\noindent
\parbox{2.25in}{\bf Math 2110}
\hfill {\Large \bf Homework \#10} \hfill
\parbox{2.25in}{\bf \hfill Due: Fri., Nov. $13^\mathrm{th}$, 2020}

\vspace{0.1in}

%\noindent {\large\bf Name:} \underline{\Large\quad My Name Goes Here \quad} \hfill 

\force \hfill Handwritten solutions are fine. \smiley  % uses wasysym package. :)
\hfill \force

\vspace{0.2in}

\noindent
{\it Notational Notes:} $\mathbb{N}$, $\mathbb{Z}$, $\mathbb{Q}$, $\mathbb{R}$ are natural numbers, integers, rational numbers, and real numbers (respectively). 

\vspace{0.1in}

\begin{description}
\item[\#1] Direct cardinality.

\begin{enumerate}[(a)]
\item Show that $|\mathbb{N}^2| \leq |S|$ where $S = \{ A \in \mathcal{P}(\mathbb{N}) \;|\; A \text{ is finite}\}$ by finding an injection (i.e., one-to-one function) from $\mathbb{N}^2$ to $S$. {\it Note:} You should prove your function is one-to-one.

{\it Warning:} One might think of a function like $f(a,b)=\{a,b\}$ (this sends an ordered pair to a finite set). But this function is not one-to-one: $f(1,2)=\{1,2\}$ but $f(2,1)=\{2,1\}=\{1,2\}$ as well. Suggestion: make sure you send $a$ and $b$ to distinct things -- think even vs. odd.


\item Show $\mathbb{O} = \{ 2k+1 \;|\; k \in \mathbb{Z} \} = \{ \dots,-3,-1,1,3,5,\dots\}$ is countably infinite by finding a bijection (i.e., invertible function) between $\mathbb{O}$ and  $\mathbb{N}$. {\it Note:} You should prove your function is invertible (or one-to-one and onto).
\end{enumerate}

\item[\#2] Calculate some cardinalities. Justify your answers using basic cardinal arithmetic and inequalities. 

{\it Note:} Your answers should either be a non-negative integer (0 or 7 or etc.), $\aleph_0$, $\mathfrak{c}=2^{\aleph_0}$, or $2^\mathfrak{c}=2^{2^{\aleph_0}}$.

For example, $|\mathbb{Z}^\mathbb{Z}|=\mathfrak{c}$ ($= 2^{\aleph_0}$) since $|\mathbb{Z}^\mathbb{Z}|=|\mathbb{Z}|^{|\mathbb{Z}|}=\aleph_0^{\aleph_0}$ and $2^{\aleph_0} \leq \aleph_0^{\aleph_0} \leq (2^{\aleph_0})^{\aleph_0} = 2^{\aleph_0^2}=2^{\aleph_0}$ so that $\aleph_0^{\aleph_0} = 2^{\aleph_0}=\mathfrak{c}$.

\begin{enumerate}[(a)]
\item $|10^{\mathcal{P}(\mathbb{Z})}|$

\item $|\mathbb{Z}\times \mathbb{R}^3|+|\mathbb{Q}^\mathbb{N}|$

\item Consider $\mathbb{N}^5$ vs. $5^{\mathbb{N}}$. Do these sets have the same cardinality? Are they countable? (both, either, neither?)

\end{enumerate}

\item[\#3] Define the relation $R = \{ (a,b) \in \mathbb{Z} \;|\; \mathrm{max}\{a,b\}=a \}$. 

{\it For example:} We have $3 \,R\, 2$ since $\mathrm{max}\{3,2\}=3$. On the other hand, $7 \,R\!\!\!/\, 11$ since $\mathrm{max}\{7,11\}=11 \not=7$.

\begin{enumerate}[(a)]
\item Consider the properties: reflexive, symmetric, anti-symmetric, and transitive. If a property holds, prove it. If it fails, give a counter-example. 
\item Is $R$ a partial order? A total order? An equivalence relation? Explain why or why not for each.
\end{enumerate}

\item[\#4] A Modular Arithmetic Problem.

\begin{enumerate}[(a)]
\item Denote the equivalence class of an integer $k$ with respect to the equivalence relation ``mod $n$'' by $[k]$. 

First, list all of the equivalence classes of integers with respect to the equivalence relation ``mod $2$'' (show their contents -- don't just write ``$[0]$'' etc.).

Next, do the same for ``mod $6$''. 

Finally, prove that $f:\mathbb{Z}_2 \to \mathbb{Z}_6$ where $f([x])=[3x]$ is a well-defined function.

\item Let $n$ be a positive integer. Prove that multiplication mod $n$ is well defined. 

In particular, for any $a,b,c,d \in \mathbb{Z}$ where $a \equiv c$ (mod $n$) and $b \equiv d$ (mod $n$) show that $ab \equiv cd$ (mod $n$).
\end{enumerate}

\end{description}





\end{document}