\documentclass[12pt]{article}
\usepackage{fullpage,amsmath,amsfonts,graphicx}

\begin{document}

\title{General Mathematics and Computational Science I}
\author{Exercise 3}
\date{September 21, 2006}
\maketitle

\begin{enumerate}

\item Recall that we defined $\mathbb{Z}$ to be the set of equivalence
classes of tuples $(a,b)$ with $a,b \in \mathbb{Z}_+$ with respect to
the equivalence relation
\begin{equation*}
  (a,b) \sim (a',b') \qquad \text{if and only if} \qquad
  a + b' = a' + b \,.
\end{equation*}
Define an order relation by
\begin{equation*}
  (a,b) < (c,d) \qquad \text{if and only if} \qquad a+d<b+c \,. 
  \tag{*}
\end{equation*}
Show that if $(a,b)\sim(a',b')$ and $(a,b)<(c,d)$, then
$(a',b')<(c,d)$.

\emph{Remark:} This, together with the corresponding statement for the
second operand, shows that $\mathbb{Z}$ is well-ordered by relation
(*).

\item Check if the following functions are injective, surjective
or bijective.  
\begin{itemize}
\item[(i)] $f\colon \mathbb{N}\rightarrow \mathbb{N}$, given by
$f(n)=n+1$. \item[(ii)] $f\colon \mathbb{Z}\times \mathbb{Z}\rightarrow
\mathbb{Z}$, given by $f(n,m)=\min \{m,n \}$.
\item[(iii)]$f\colon \mathbb{N}\rightarrow \mathbb{N}$ with
$f(2n)=2n-1$ for all $n > 0$ and $f(2n+1)=2n+2$ for all $n\geq 0$.
\end{itemize}
(If one of the properties fails, give a counter example.  Otherwise
give a short proof.)

\item Multiplication on $\mathbb{N}$ can be defined, similar to
addition, as the unique map $G \colon \mathbb{N} \times \mathbb{N} \to
\mathbb{N}$ with the following properties:
\begin{itemize}
\item[(M1)] $G(a,1) = a$ for all $a \in \mathbb{N}$,
\item[(M2)] $G(a,s(b)) = G(a,b) + a$ for all $a,b \in \mathbb{N}$.
\end{itemize}
Use this definition to prove that
\begin{equation*}
  2 \times 2 = 4
\end{equation*}
where $2 \equiv s(1)$, $3 \equiv s(2)$, and $4\equiv s(3)$.

\end{enumerate}
\end{document}
