test.tex

% One and only one of the next two lines should be uncommented
% \documentclass{test}  % for making book
\documentclass[compact]{test}  % for making handout for students

\usepackage{testtext} % for the text only; answers-only is another .sty

\usepackage{etoolbox}
\usepackage{comment}
\newbool{euclid}
% \booltrue{euclid}  % Euclid's proof of Euclid's Lemma
\boolfalse{euclid}  % Bezout proof of Euclid's Lemma
\ifbool{euclid}{
  \includecomment{euclidproof}  
  \excludecomment{bezoutproof}
}{
  \excludecomment{euclidproof} 
  \includecomment{bezoutproof}
}

\frontmatter
\begin{document}    
\coverpage{}
\include{flyleaf}
\ifbool{optioncompact}{}{\include{preface}}

\mainmatter
\pagestyle{bodypage}
\chapter{Number Theory}

We begin with results about the integers $\Z=\set{\ldots,-2,-1,0,1,2,\ldots}$.
In this chapter ``number'' means integer.
Some statements refer to the natural numbers $\N=\set{0,1,2,\ldots}$.


% .....................................
\section{Divisibility}

\begin{df}
  For two integers $d,n$ we say that
  $d$ \definend{divides}~$n$
  if there is an integer~$k$ such that $d\cdot k=n$.
  Here, $d$~is the \definend{divisor}, 
  $n$~is the \definend{dividend},
  and~$k$ is the \definend{quotient}.
  (Alternative wordings are:
  $d$~\definend{is a factor of}~$n$,
  or $d$~\definend{goes evenly into}~$n$,
  or $n$~\definend{is a multiple of}~$d$.)
  We denote the relationship as
  $d\divides n$ if $d$~is a divisor of~$n$
  or as $d\ndivides n$ if it is not.
\end{df}

\begin{df}
  A natural number is \definend{even} if it is divisible by~$2$,
  otherwise it is \definend{odd}.
  (Alternative wording is that the number \definend{has even parity}
  or \definend{has odd parity}.)
\end{df}

The notation $d\divides n$ signifies a relationship between two numbers.
It is different than the fraction $d/n$, which is a number.
We can sensibly ask ``Does $2$ divide~$5$?''\spacefactor=1000\
but ``Does $2/5$?''\spacefactor=1000\ is not sensible.   

\begin{problem} \notetext{Interaction of parity and sign} 
\label{ex:InteractionOfParityWithSign}
\pord.
\begin{exes}
  \begin{exercise}
    If a number is even then its negative is even.
  \end{exercise}
  \begin{answer}
    If $n\in\Z$ is even then $n=2k$ for some $k\in\Z$.
    Then $-n=2\cdot(-k)$ shows that the negative is also even.  
  \end{answer}
  \begin{exercise}
    If a number is odd then its negative is odd.
  \end{exercise}
  \begin{answer}
    With the prior item in mind we first show that a number is even
    if and only if its negative is even.
    Suppose that a number $n\in\Z$ has a negative $-n$ that is even.
    Since the negative of $-n$ is~$n$, the prior item shows that $n$ is even.
    Thus $n$ is even if and only if $-n$ is even, and therefore
    if $n$ is not even then $-n$ is also not even.
  \end{answer}
  \begin{exercise}
    If $d\divides a$ then $-d\divides a$ and $d\divides -a$.
  \end{exercise}
  \begin{answer}
    Assume that $d\divides a$ for $d,a\in\Z$, so that 
    $a=dk$ for some~$k\in\Z$.
    For the first, that $-d\divides a$, observe that
    $a=(-d)\cdot(-k)$.
    For the second, observe that $-a=d\cdot(-k)$.
  \end{answer}
  \begin{exercise}
    If $d\divides a$ then $d\divides\absval{a}$.
    (Recall that the absolute value of a number $\absval{a}$ is~$a$ 
    if $a\geq 0$ and is~$-a$ if $a<0$.)
  \end{exercise}
  \begin{answer}
    Suppose that $d\divides a$.
    For the $a\geq 0$ case, the implication that if $d\divides a$ then 
    $d\divides a$ is trivial.
    For the $a<0$ case, 
    the implication that if $d\divides a$ then $d\divides -a$ was
    proved in the prior item.    
  \end{answer}
\end{exes}  
\end{problem}

\begin{problem} \notetext{Interaction of parity and addition}
\pord.
\begin{exes}
\begin{exercise}
  The sum of two evens is even.
  The difference of two evens is even.  
\end{exercise}
\begin{answer}
  Let $a,b\in\Z$ be even so that $a=2m$ and~$b=2n$ for some $m,n\in\Z$.
  Then $a+b=2m+2n=2(m+n)$ is even, and $a-b=2m-2n=2(m-n)$ is even.  
\end{answer}

\begin{exercise}
  The sum of two odds is odd. 
  The difference of two odds is odd.  
\end{exercise}
\begin{answer}
  Both statements are false: for instance $1$ and~$3$ are odd
  but both $1+3$ and~$1-3$ are even.  
\end{answer}

\begin{exercise}
  Where $a,b\in\Z$, the number $a+b$ is even if and only if $a-b$ is even.
\end{exercise}
\begin{answer}
  First suppose that the sum is even, so $a+b=2k$ for some $k\in\Z$.
  Then $a-b=a+b-2b=2k-2b=2(k-b)$ is even.

  The other half is similar:
  if $a-b=2m$ for $m\in\Z$ then $a+b=a-b+2b=2k+2b$ is even.  
\end{answer}

\begin{exercise}
  Generalize the first item to arbitrary divisors~$d$.
\end{exercise}
\begin{answer}
  A reasonable generalization is that for any $d\in\Z$
  the sum and difference of multiples of~$d$ is again a multiple of~$d$.
 
  For a proof
  let $a,b\in\Z$ be multiples of~$d$ so that $a=dm$ and~$b=dn$ 
  for some $m,n\in\Z$.
  Then $a+b=dm+dn=d(m+n)$ is a multiple of~$d$
  and $a-b=dm-dn=d(m-n)$ is multiple of~$d$.    
\end{answer}
% \item The sum of two evens is even.
%   The difference of two evens is even.
% \item The sum of two odds is odd. 
% The difference of two odds is odd.
% \item Where $a,b\in\Z$, the number $a+b$ is even if and only if $a-b$ is even.
% \item Generalize the first item to arbitrary divisors~$d$.
% \end{exes}  
% \begin{ans}
% \begin{exes}
% \item Let $a,b\in\Z$ be even so that $a=2m$ and~$b=2n$ for some $m,n\in\Z$.
%   Then $a+b=2m+2n=2(m+n)$ is even, and $a-b=2m-2n=2(m-n)$ is even.
% \item Both statements are false: for instance $1$ and~$3$ are odd
%   but both $1+3$ and~$1-3$ are even.
% \item First suppose that the sum is even, so $a+b=2k$ for some $k\in\Z$.
%   Then $a-b=a+b-2b=2k-2b=2(k-b)$ is even.

%   The other half is similar:
%   if $a-b=2m$ for $m\in\Z$ then $a+b=a-b+2b=2k+2b$ is even.
% \item A reasonable generalization is that for any $d\in\Z$
%   the sum and difference of multiples of~$d$ is again a multiple of~$d$.
 
%   For a proof
%   let $a,b\in\Z$ be multiples of~$d$ so that $a=dm$ and~$b=dn$ 
%   for some $m,n\in\Z$.
%   Then $a+b=dm+dn=d(m+n)$ is a multiple of~$d$
%   and $a-b=dm-dn=d(m-n)$ is multiple of~$d$.
\end{exes}
\end{problem}

\begin{problem} \notetext{Interaction of parity and multiplication}
\pord.
\begin{exes}
\begin{exercise}
  The product of two evens is even.
\end{exercise}
\begin{answer}
  Let $a,b\in\Z$ be even
  so that $a=2m$ and~$b=2n$ for some $m,n\in\Z$.
  Then $ab=2m\cdot 2n=2(m\cdot 2n)$ is even.  
\end{answer}

\begin{exercise}
  The quotient of two evens, if it is an integer, is even.
\end{exercise}
\begin{answer}
  This is false since both $6$ and~$2$ are even but the quotient $6/2$
  is not even.
\end{answer}

\begin{exercise}[\midlength]
  Generalize the first item to any divisor~$d$.  
\end{exercise}
\begin{answer}
  The first item can generalize to: for any~$d\in\N$, 
  the product of two multiples of~$d$ is a multiple of~$d$.

  For the proof,  let $a,b\in\Z$ be multiples of~$d$
  so that $a=dm$ and~$b=dn$ for some $m,n\in\Z$.
  Then $ab=dm\cdot dn=d(m\cdot dn)$ is a multiple of~$d$.

  (The first item can also generalize to: a product of two multiples of
  $d$ is a multiple of~$d^2$.)
\end{answer}
% \item The product of two evens is even.
% \item The quotient of two evens, if it is an integer, is even.
% \item Generalize the first item to any divisor~$d$.
% \end{exes}  
% \begin{ans}
% \begin{exes}
% \item Let $a,b\in\Z$ be even
%   so that $a=2m$ and~$b=2n$ for some $m,n\in\Z$.
%   Then $ab=2m\cdot 2n=2(m\cdot 2n)$ is even.
% \item This is false since both $6$ and~$2$ are even but the quotient $6/2$
%   is not even.
% \item The first item can generalize to: for any~$din\N$, 
%   the product of two multiples of~$d$ is a multiple of~$d$.

%   For the proof,  let $a,b\in\Z$ be multiples of~$d$
%   so that $a=dm$ and~$b=dn$ for some $m,n\in\Z$.
%   Then $ab=dm\cdot dn=d(m\cdot dn)$ is a multiple of~$d$.

%   (The first item can also generalize to: a product of two multiples of
%   $d$ is a multiple of~$d^2$.)
\end{exes}
\end{problem}

\begin{problem} \notetext{Divisibility Properties} 
\label{ex:DivisibilityProperties}
Let $d$, $m$, and $n$ be integers.
Prove each.
\begin{exes}
\begin{exercise}
  \notetext{Reflexivity} Every number divides itself.
\end{exercise}
\begin{answer}
  Any number $a\in\Z$ satisfies that $a=a\cdot 1$.
\end{answer}
\begin{exercise}
  Every number divides $0$ while
  the only number that $0$ divides is itself.
\end{exercise}
\begin{answer}
  For every $k\in\Z$ the equation~$0=k\cdot 0=0\cdot k$ has~$0$ 
  as a multiple of~$k$.
  That equation also shows that the only number that~$0$ divides is itself. 
\end{answer}
\begin{exercise}
  \notetext{Transitivity} If $d\divides n$ and $n\divides m$ 
   then $d\divides m$.
\end{exercise}
\begin{answer}
  Suppose that $d, n, m\in\Z$ are such that $d\divides n$ and
  $n\divides m$.
  Then there are $i,j\in\Z$ such that $n=di$ and~$m=nj$.
  Substitute to get $m=(di)\cdot j=d\cdot(ij)$, which shows that
  $d$ divides~$m$.
\end{answer}
\begin{exercise}
  \notetext{Cancellation} 
  For $d,n\in\Z$, if for some nonzero integer~$a$ we have that $ad\divides an$ 
  then $d\divides n$.
  Conversely, if $d\divides n$ then $ad\divides an$ for all~$a\in\Z$.
\end{exercise}
\begin{answer}
  Fix~$d,n\in\Z$.
  First suppose that $ad\divides an$ for some $a\in\Z$ such that $a\neq 0$. 
  Then $an=adk$ for some $k\in\Z$ and
  since $a\neq 0$ we can multiply by $1/a$ to get $n=dk$, giving 
  $d\divides n$.
  For the converse, 
  if $d\divides n$ then $n=dk$ for some $k\in\Z$ and for all~$a\in\Z$
  we have $an=adk$, which shows that $ad\divides an$.
\end{answer}
\begin{exercise}
  \notetext{Comparison} 
  For $d,n\in\Z^+$, if $n$ is a multiple of~$d$ then $n\geq d$.
\end{exercise}
\begin{answer}
  Assume $d,n\in\Z^+$.
  Because $n$ is a multiple of $d$ we have that $n=dk$ for some $k\in\Z$.
  Note that $k\geq 1$ since otherwise $n\leq 0$ but $n$ is given as positive.  
  Multiplying by the positive number~$d$ gives $n=dk\geq d$.
\end{answer}
\begin{exercise}
  Every number is divisible by $1$.
  The only numbers that divide~$1$ are $1$ and~$-1$.
\end{exercise}
\begin{answer}
  That every number is divisible by~$1$ follows from the fact that
   for every $a\in\Z$ the equation $a=1\cdot a$ holds.

  For the other part 
  first consider a divisor~$d$ of~$1$ that is a positive integer.
  By the prior item $1\geq d$ so the only such divisor is~$d=1$.
  Clearly $0$ is not a divisor of~$1$ so the only remaining candidates
  are negative integers.
  We have shown that for $d,a\in\Z$, if $d\divides a$ then $-d\divides a$,
  so if a negative number~$d$ divides~$1$ then the positive~$-d$ 
  also divides~$1$.
  Since the only such positive number is~$-d=1$, the only 
  candidate for a negative divisor is $d=-1$. 
\end{answer}
\begin{exercise}
  The largest divisor of $a$ is $\absval{a}$, for $a\in\Z$ with $a\neq 0$.
\end{exercise}
\begin{answer}
  Fix $a\in\Z$. 
  First note that $\absval{a}$ does indeed divide~$a$ because
  if $a\geq 0$ then $\absval{a}\divides a$ follows from 
  $a=\absval{a}\cdot 1$,
  while if $a<0$ then $\absval{a}\divides a$ follows from 
  $a=\absval{a}\cdot(-1)$.

  We finish by showing that no divisor of~$a\neq 0$ is larger than $\absval{a}$.
  We have shown that for $d,a\in\Z$ if $d\divides a$ then $d\divides -a$,
  if a negative~$a$ had a divisor greater than~$\absval{a}$ then the
  positive number~$-a$ would also have such a divisor.
  So we will be done if
  we show there is no dividend~$a>0$ with a divisor larger than $\absval{a}=a$.
  By the Comparison property, a positive dividend is greater than or 
  equal to any of its divisors. 
  Thus~$\absval{a}$ is maximal.
\end{answer}
\begin{exercise}
  Every nonzero integer has only finitely many divisors.
\end{exercise}
\begin{answer}
  By the prior item if $a\neq 0$ then all of the divisors of~$a$
  are in the interval of integers from $-a$ to~$a$. 
\end{answer}
% \item \notetext{Reflexivity} Every number divides itself.
% \item Every number divides $0$ while
%   the only number that $0$ divides is itself.
% \item \notetext{Transitivity} If $d\divides n$ and $n\divides m$ 
%    then $d\divides m$.
% \item \notetext{Cancellation} 
%   For $d,n\in\Z$, if for some nonzero integer~$a$ we have that $ad\divides an$ 
%   then $d\divides n$.
%   Conversely, if $d\divides n$ then $ad\divides an$ for all~$a\in\Z$.
% \item \notetext{Comparison} 
%   For $d,n\in\Z^+$, if $n$ is a multiple of~$d$ then $n\geq d$.
% \item Every number is divisible by $1$.
%   The only numbers that divide~$1$ are $1$ and~$-1$.
% \item The largest divisor of $a$ is $\absval{a}$, for $a\in\Z$ with $a\neq 0$.
% \item Every nonzero integer has only finitely many divisors.
% \end{exes}
% \begin{exes}
% \item Any number $a\in\Z$ satisfies that $a=a\cdot 1$.
% \item For every $k\in\Z$ the equation~$0=k\cdot 0=0\cdot k$ has~$0$ 
%   as a multiple of~$k$.
%   That equation also shows that the only number that~$0$ divides is itself. 
% \item Suppose that $d, n, m\in\Z$ are such that $d\divides n$ and
%   $n\divides m$.
%   Then there are $i,j\in\Z$ such that $n=di$ and~$m=nj$.
%   Substitute to get $m=(di)\cdot j=d\cdot(ij)$, which shows that
%   $d$ divides~$m$.
% \item Fix~$d,n\in\Z$.
%   First suppose that $ad\divides an$ for some $a\in\Z$ such that $a\neq 0$. 
%   Then $an=adk$ for some $k\in\Z$ and
%   since $a\neq 0$ we can multiply by $1/a$ to get $n=dk$, giving 
%   $d\divides n$.
%   For the converse, 
%   if $d\divides n$ then $n=dk$ for some $k\in\Z$ and for all~$a\in\Z$
%   we have $an=adk$, which shows that $ad\divides an$.
% \item Assume $d,n\in\Z^+$.
%   Because $n$ is a multiple of $d$ we have that $n=dk$ for some $k\in\Z$.
%   Note that $k\geq 1$ since otherwise $n\leq 0$ but $n$ is given as positive.  
%   Multiplying by the positive number~$d$ gives $n=dk\geq d$. 
% \item That every number is divisible by~$1$ follows from the fact that
%    for every $a\in\Z$ the equation $a=1\cdot a$ holds.

%   For the other part 
%   first consider a divisor~$d$ of~$1$ that is a positive integer.
%   By the prior item $1\geq d$ so the only such divisor is~$d=1$.
%   Clearly $0$ is not a divisor of~$1$ so the only remaining candidates
%   are negative integers.
%   We have shown that for $d,a\in\Z$, if $d\divides a$ then $-d\divides a$,
%   so if a negative number~$d$ divides~$1$ then the positive~$-d$ 
%   also divides~$1$.
%   Since the only such positive number is~$-d=1$, the only 
%   candidate for a negative divisor is $d=-1$. 
% \item Fix $a\in\Z$. 
%   First note that $\absval{a}$ does indeed divide~$a$ because
%   if $a\geq 0$ then $\absval{a}\divides a$ follows from 
%   $a=\absval{a}\cdot 1$,
%   while if $a<0$ then $\absval{a}\divides a$ follows from 
%   $a=\absval{a}\cdot(-1)$.

%   We finish by showing that no divisor of~$a\neq 0$ is larger than $\absval{a}$.
%   We have shown that for $d,a\in\Z$ if $d\divides a$ then $d\divides -a$,
%   if a negative~$a$ had a divisor greater than~$\absval{a}$ then the
%   positive number~$-a$ would also have such a divisor.
%   So we will be done if
%   we show there is no dividend~$a>0$ with a divisor larger than $\absval{a}=a$.
%   By the Comparison property, a positive dividend is greater than or 
%   equal to any of its divisors. 
%   Thus~$\absval{a}$ is maximal.
% \item By the prior item if $a\neq 0$ then all of the divisors of~$a$
%   are in the interval of integers from $-a$ to~$a$. 
\end{exes}
\end{problem}

\begin{problem}
Give the converse of Reflexivity: what conclusion can you make
if $a\divides b$ and~$b\divides a$?
\begin{ans}
We will show that for $a,b\in\Z$, if both $a\divides b$ and~$b\divides a$
then $a=\pm b$.

By definition $a\divides b$ and~$b\divides a$ implies that $b=ak$
and $a=bm$ for some $k,m\in\Z$.
Substitution gives $a=bm=akm$ and then cancellation gives $1=km$ (cancellation
does not apply if $a=0$ but in this case the proof is easy).
The only divisors of $1$ are $1$ and~$-1$, so $k=\pm 1$ and~$m=\pm 1$. 
Thus $b=\pm a$ and~$a=\pm b$.
\end{ans}
\end{problem}

\begin{problem} \label{ex:DividesAndLinearCombinations}
Suppose that $a,b,c\in\Z$.
\begin{exes}
\begin{exercise}
  Prove that if $a\divides b$ then $a\divides bc$ for all integers~$c$.
\end{exercise}
\begin{answer}
  If $a\divides b$ then $b=ak$ for some~$k\in\Z$.
  Thus $bc=akc=a\cdot(kc)$ is a multiple of~$a$.
\end{answer}
\begin{exercise}
  Prove that if $a\divides b$ and $a\divides c$ then $a$ divides the 
  sum~$b+c$ and difference~$b-c$.
\end{exercise}
\begin{answer}
  Suppose that $a,b,c\in\Z$ and that $a\divides b$ and $a\divides c$.
  Then $b=ak$ and $c=am$ for some $k,m\in\Z$. 
  Substitution  
  $b+c=ak+am=a\cdot(k+m)$
  shows that $a$ divides the sum~$b+c$.
  A similar substitution
  $b-c=ak-am=a\cdot(k-m)$
  shows that $a$ divides the difference.
\end{answer}
\begin{exercise}  % Needed for Bezout's Lemma
  \notetext{Linearity} Generalize the prior item.
\end{exercise}
\begin{answer}
  A natural generalization is that $a$ divides any combination
  $i\cdot b+j\cdot c$ where $i,j\in\Z$.
  The proof is
  $ib+jc=i\cdot (ak)+j\cdot(am)=a\cdot(ik+jm)$.
\end{answer}
\end{exes}
% \begin{exes}
% \item Prove that if $a\divides b$ then $a\divides bc$ for all integers~$c$.
% \item Prove that if $a\divides b$ and $a\divides c$ then $a$ divides the 
%   sum~$b+c$ and difference~$b-c$.
% \item  \notetext{Linearity} Generalize the prior item.
% \end{exes}
% \begin{ans}
% \begin{exes}
% \item If $a\divides b$ then $b=ak$ for some~$k\in\Z$.
%   Thus $bc=akc=a\cdot(kc)$ is a multiple of~$a$
% \item Suppose that $a,b,c\in\Z$ and that $a\divides b$ and $a\divides c$.
%   Then $b=ak$ and $c=am$ for some $k,m\in\Z$. 
%   Substitution  
%   $b+c=ak+am=a\cdot(k+m)$
%   shows that $a$ divides the sum~$b+c$.
%   A similar substitution
%   $b-c=ak-am=a\cdot(k-m)$
%   shows that $a$ divides the difference.
% \item A natural generalization is that $a$ divides any combination
%   $i\cdot b+j\cdot c$ where $i,j\in\Z$.
%   The proof is
%   $ib+jc=i\cdot (ak)+j\cdot(am)=a\cdot(ik+jm)$.
% \end{exes}
% \end{ans}
\end{problem}




% .....................................
\section{Interlude: induction}
Results in the prior section need only proof techniques that are natural
for people with a mathematical aptitude.
However some results to follow require a technique 
that is less natural, mathematical induction.
This section is a pause for an introduction to induction.

We will start with exercises about summations 
(note, though, that induction is not about summation;
we use these only because they make helpful initial exercises).
For example, many people have noticed that the odd natural numbers sum to 
perfect squares: $1+3=4$, $1+3+5=9$, $1+3+5+7=16$, etc.
We will prove the statement,
``The sum $1+3+5+\cdots+(2n+1)$ equals $(n+1)^2$.'' 

That statement has a natural number variable~$n$ that is free, 
meaning that setting $n$ to be $0$, or~$1$, etc., gives 
a family of cases: $S(0)$, or~$S(1)$, 
etc.  
For instance, the statement $S(1)$ asserts that $1+3$ equals $2^2$.
Our induction proofs will all involve statements with one free 
natural number variable.

These proofs have two steps.
For the \definend{base step} 
we will show that the statement holds for some intial number~$i\in\N$.
The \definend{inductive step} is more subtle;
we will show that the following implication holds.
\begin{equation*}
  \begin{tabular}{l} 
  \textit{If} the statement holds from the
   base number up to and including $n=k$  \\
  \hspace*{0.618em}\textit{then} the statement holds also in the~$n=k+1$ case.
  \end{tabular}
  \tag{$*$}
\end{equation*}
The \definend{Principle of Mathematical Induction} is that
completing both steps proves 
that the statement is true for all natural
numbers greater than or equal to~$i$: 
that $S(i)$ is true, and~$S(i+1)$ is true, etc.

For the example statement about odd numbers and squares, 
the intuition behind the principle is first that the base step
directly verifies the statement for the case of the initial number~$n=0$.
Then because the inductive step verifies the implication~($*$) for all $k$, 
that implication applied to~$k=0$ gives 
that the statement is true for the case of the number~$n=1$. 
Now, with the statement established for both $0$ and~$1$, 
apply ($*$) again to conclude that the statement is true for the number~$n=2$.
In this way, induction bootstraps to all natural numbers~$n\geq 0$.
Below is an induction argument for the example statement, 
with separate paragraphs for the base step and the inductive step.

\begin{proof}
  We show that $1+3+\cdots+(2n+1)=(n+1)^2$ by induction.
  For the $n=0$ base step note that on the left the sum has a single term, $1$,
  which equals the value on the right, $1^2$.

  For the inductive step assume that the 
  formula is true for $n=0$, $n=1$, \ldots, $n=k$, and 
  consider the $n=k+1$ case.
  The sum is $1+3+\cdots+(2k+1)+(2(k+1)+1)=1+3+\cdots+(2k+1)+(2k+3)$.
  By the inductive hypothesis the statement is true in the $n=k$ case
  so we can substitute 
  $1+3+\cdots+(2k+1)+(2k+3)=(k+1)^2+(2k+3)=(k^2+2k+1)+(2k+3)=(k+2)^2$.
  This is the required expression for the $n=k+1$~case.
\end{proof}

\begin{problem}
Prove by induction.
\begin{exes}
\begin{exercise}
  $0+1+2+\cdots+n=n(n+1)/2$
\end{exercise}
\begin{answer}
  For the $n=0$ base step note that the sum on the left
  has the single term~$0$
  while the right side is $0\cdot(0+1)/2$, which also equals~$0$.

  For the inductive step take the inductive hypothesis 
  that the statement is true for $n=0$,~\ldots, $n=k$ and consider $n=k+1$.
  We have 
  $0+1+\cdots+k+(k+1)=(k(k+1)/2)+(k+1)=(k+1)\cdot(k/2+1)=(k+1)\cdot(k+2)/2$, 
  as required  
  (the first equality is from applying the inductive hypothesis in 
  the $n=k$ case).
\end{answer} 
\begin{exercise}
  $0+1+4+9+\cdots+n^2=n(n+1)(2n+1)/6$
\end{exercise}
\begin{answer} 
  The $n=0$ base step is that the left side has the single term~$0$
  while the right side is $0\cdot(0+1)\cdot(2\cdot 0+1)/6$, and the 
  two are equal.

  For the inductive step assume that the statement is true for 
  $n=0$,~\ldots, $n=k$ and consider $n=k+1$.
  Applying the inductive hypothesis in the $n=k$ case and reducing gives
  $0+1+4+\cdots+k^2+(k+1)^2=k(k+1)(2k+1)/6+(k+1)^2
    =(k+1)\cdot [k(2k+1)/6+(k+1)]
    =(k+1)\cdot [k(2k+1)+6(k+1)]/6
    =(k+1)\cdot [2k^2+7k+6]/6
    =(k+1)(k+2)(2(k+1)+1)/6$,
  as required.
\end{answer}
% \begin{exercise} 
%    $0+1+8+27+\cdots+n^3=n^2(n+1)^2/4$
% \end{exercise}
% \begin{answer}
%   The base step is~$n=0$.  
%   The left side has the single term $0$ while the right side is 
%   $0^2(1)^2/4$, so they are equal.

%   For the inductive step assume that the statement is true when $n=0$, 
%   \ldots, $n=k$.
%   Then 
%    $0+8+\cdots+k^3+(k+1)^3
%     =k^2(k+1)^2/4+(k+1)^3
%     =(k+1)^2\cdot [(k^2/4)+(k+1)]
%     =(k+1)^2\cdot (k^2+4k+4)/4
%     =(k+1)^2(k+2)^2/4$. 
% \end{answer}
\begin{exercise}
  $1+2+4+8+\cdots+2^n=2^{n+1}-1$
\end{exercise}
\begin{answer} 
The $n=0$ base step has a sum on the left with a single term, $1$.
The expression on the right is $2^1-1=1$, and they are equal.

The inductive hypothesis is that 
the statement is true for the cases $n=0$, \ldots, $n=k$.
The $n=k+1$ summation is
$1+2+4+\cdots+2^k+2^{k+1}$. 
Apply the inductive hypothesis to get
$(2^{k+1}-1)+2^{k+1}=2\cdot 2^{k+1}-1=2^{k+2}-1$, as required. 
\end{answer}
\end{exes}
% \begin{exes}
% \item $0+1+2+\cdots+n=n(n+1)/2$
% \item $0+1+4+9+\cdots+n^2=n(n+1)(2n+1)/6$
% % \item $0+1+8+27+\cdots+n^3=n^2(n+1)^2/4$
% \item $1+2+4+8+\cdots+2^n=2^{n+1}-1$
% \end{exes}
% \begin{ans}
% \begin{exes}
% \item For the $n=0$ base step note that the sum on the left
%   has the single term~$0$
%   while the right side is $0\cdot(0+1)/2$, which also equals~$0$.

%   For the inductive step take the inductive hypothesis 
%   that the statement is true for $n=0$,~\ldots, $n=k$ and consider $n=k+1$.
%   We have 
%   $0+1+\cdots+k+(k+1)=(k(k+1)/2)+(k+1)=(k+1)\cdot(k/2+1)=(k+1)\cdot(k+2)/2$, 
%   as required  
%   (the first equality is from applying the inductive hypothesis in 
%   the $n=k$ case). 
% \item The $n=0$ base step is that the left side has the single term~$0$
%   while the right side is $0\cdot(0+1)\cdot(2\cdot 0+1)/6$, and the 
%   two are equal.

%   For the inductive step assume that the statement is true for 
%   $n=0$,~\ldots, $n=k$ and consider $n=k+1$.
%   Applying the inductive hypothesis in the $n=k$ case and reducing gives
%   $0+1+4+\cdots+k^2+(k+1)^2=k(k+1)(2k+1)/6+(k+1)^2
%     =(k+1)\cdot [k(2k+1)/6+(k+1)]
%     =(k+1)\cdot [k(2k+1)+6(k+1)]/6
%     =(k+1)\cdot [2k^2+7k+6]/6
%     =(k+1)(k+2)(2(k+1)+1)/6$,
%   as required.
% % \item The base step is~$n=0$.  
% %   The left side has the single term $0$ while the right side is 
% %   $0^2(1)^2/4$, so they are equal.

% %   For the inductive step assume that the statement is true when $n=0$, 
% %   \ldots, $n=k$.
% %   Then 
% %    $0+8+\cdots+k^3+(k+1)^3
% %     =k^2(k+1)^2/4+(k+1)^3
% %     =(k+1)^2\cdot [(k^2/4)+(k+1)]
% %     =(k+1)^2\cdot (k^2+4k+4)/4
% %     =(k+1)^2(k+2)^2/4$. 
% \item The $n=0$ base step has a sum on the left with a single term, $1$.
% The expression on the right is $2^1-1=1$, and they are equal.

% The inductive hypothesis is that 
% the statement is true for the cases $n=0$, \ldots, $n=k$.
% The $n=k+1$ summation is
% $1+2+4+\cdots+2^k+2^{k+1}$. 
% Apply the inductive hypothesis to get
% $(2^{k+1}-1)+2^{k+1}=2\cdot 2^{k+1}-1=2^{k+2}-1$, as required. 
% \end{exes}
% \end{ans}
\end{problem}

\begin{problem}
Prove each by induction.  Suppose that $a,b\in\R$ and that $r\in\R$ with $r\neq 1$.
\begin{exes}
\begin{exercise} \notetext{Geometric Series} 
  $1+r+r^2+\cdots+r^n=(r^{n+1}-1)/(r-1)$
\end{exercise}
\begin{answer} 
  The $n=0$ base step has the single term~$1$ in the left summation and
  $(r^1-1)/(r-1)$ on the right, and they are equal.

  For the inductive step assume that the statement is true for 
  $n=0$, \ldots, $n=k$.
  The $n=k+1$ case is
  $1+r+r^2+r^3+\cdots+r^k+r^{k+1}
  =(r^{k+1}-1)/(r-1)+r^{k+1}
  =[r^{k+1}-1+r^{k+1}(r-1)]/(r-1)
  =[r\cdot r^{k+1}-1]/(r-1)
  =(r^{k+2}-1)/(r-1)$ for $r\neq 1$.
\end{answer}
\begin{exercise} \notetext{Arithmetic Series}  
  $b+(a+b)+(2a+b)+\cdots+(na+b)=(n(n+1)/2)\cdot a+(n+1)\cdot b$
\end{exercise}
\begin{answer} 
  The base step is~$n=0$.
  The summation on the left has one term, $b$, 
  while the expression on the right is     
  $0\cdot a+1\cdot b$, so the two sides are equal.

  For the inductive step assume that the statement holds when $n=0$, 
  \ldots, $n=k$ and consider the $n=k+1$~case.
  We have
  $b+(a+b)+(2a+b)+\cdots+(ka+b)+((k+1)a+b)
  =[(k(k+1)/2)\cdot a+(k+1)\cdot b]+((k+1)a+b)
  =[(k+1)\cdot((k/2)+1)]\cdot a+[k+2]\cdot b
  =((k+1)(k+2)/2)\cdot a+(k+2)\cdot b$,
  as required. 
\end{answer}
\end{exes}
% \item \notetext{Geometric Series} For all $r\in\R$ with $r\neq 1$ we have
%   $1+r+r^2+\cdots+r^n=(r^{n+1}-1)/(r-1)$.
% \item \notetext{Arithmetic Series} We have
%   $b+(a+b)+(2a+b)+\cdots+(na+b)=(n(n+1)/2)\cdot a+(n+1)\cdot b$
%   for all $a,b\in\R$.
% \end{exes}
% \begin{ans}
% \begin{exes}
% \item The $n=0$ base step has the single term~$1$ in the left summation and
%   $(r^1-1)/(r-1)$ on the right, and they are equal.

%   For the inductive step assume that the statement is true for 
%   $n=0$, \ldots, $n=k$.
%   The $n=k+1$ case is
%   $1+r+r^2+r^3+\cdots+r^k+r^{k+1}
%   =(r^{k+1}-1)/(r-1)+r^{k+1}
%   =[r^{k+1}-1+r^{k+1}(r-1)]/(r-1)
%   =[r\cdot r^{k+1}-1]/(r-1)
%   =(r^{k+2}-1)/(r-1)$ for $r\neq 1$.
% \item The base step is~$n=0$.
% The summation on the left has one term, $b$, 
% while the expression on the right is     
% $0\cdot a+1\cdot b$, so the two sides are equal.

% For the inductive step assume that the statement holds when $n=0$, 
% \ldots, $n=k$ and consider the $n=k+1$~case.
% We have
% $b+(a+b)+(2a+b)+\cdots+(ka+b)+((k+1)a+b)
% =[(k(k+1)/2)\cdot a+(k+1)\cdot b]+((k+1)a+b)
% =[(k+1)\cdot((k/2)+1)]\cdot a+[k+2]\cdot b
% =((k+1)(k+2)/2)\cdot a+(k+2)\cdot b$,
% as required. 
% \end{exes}
% \end{ans}
\end{problem}

\begin{problem}
Prove by induction that $n<2^n$ for all $n\in\N$.  
\begin{ans}
The $n=0$ base case is that $0$ is less than~$2^0$, which is clear.

For the inductive step assume that the statement holds when 
$n=0$, \ldots, $n=k$ and consider the~$n=k+1$ case.
We have $k+1<2^k+1\leq 2^{k+1}$ (the second holds because $2^k<2^{k+1}$). 
\end{ans}
\end{problem}

\begin{problem}
Prove each by induction.
\begin{exes}
\begin{exercise}
  For all $n\in\N$, the number~$n^2+n$ is even.
\end{exercise}
\begin{answer}
  For the $n=0$ base step observe that $0^2+0$ is even.
  For the inductive step assume the statement for $n=0$, \ldots, $n=k$
  and consider the $n=k+1$ case.
  We have $(k+1)^2+(k+1)=k^2+2k+1+k+1=(k^2+k)+(2k+2)$. 
  By the inductive hypothesis $k^2+k$ is even, and clearly $2k+2$ is even, 
  so the sum is even.
\end{answer}
\begin{exercise} 
  For all $n\geq 2$ the number $n^3-n$ is divisible by $6$.
  \hint take the base case to be $2$.
\end{exercise}
\begin{answer}
  The base step is $n=2$.
  Since $6$ divides $2^3-2=8-2$, the statement holds in this case.

  For the inductive step assume that the statement is true for 
  the cases $n=0$, \ldots, $n=k$.
  In the $n=k+1$ case, consider 
  $(k+1)^3-(k+1)=(k^3+3k^2+3k+1)-(k+1)=(k^3+3k^2+3k)-k$.
  The inductive hypothesis gives that $6$ divides $(k^3-k)$ so we will
  be finished if we show that it divides  $3k^2+3k$.
  We have $3k^2+3k=3\cdot k(k+1)$, and since
  $k(k+1)$ is even (this was shown in the prior item),
  the product is divisible by $6$.  
\end{answer}
\begin{exercise} 
  If $n\in\N$ then $4\divides 13^n-1$.
\end{exercise}
\begin{answer}
  The $n=0$ base step is clear, since four divides $13^0-1=0$.
  For the inductive step assume that the statement is true for all cases 
  with $0\leq n\leq k$ and consider the $n=k+1$ case.
  Then $13^{k+1}-1=(13^{k+1}-13)+(13-1)=13(13^k-1)+12$.
  The first term is divisible by~$4$ by the inductive hypothesis, while the
  second term is obviously divisible by~$4$, and so the statement holds in 
  this case.

  \remark
  this illustrates that 
  sometimes when you have finished a proof by induction, 
  while you now are sure that the statement is true, 
  you can nonetheless be left with the sense
  that you are not sure really \emph{why} it is true.
  You can prove that this statement holds in a 
  way that gives more intuition by plugging $13$ into the formula for a
  geometric series. 
\end{answer}
\begin{exercise} 
    If $n\in\Z^+$ then
    $(1+\sfrac{1}{1})\cdot(1+\sfrac{1}{2})\,\cdots\,(1+\sfrac{1}{n})=n+1$.
\end{exercise}
\begin{answer}
  The base step is a product with $n=1$~term.
  The left side is $(1+\sfrac{1}{1})=2$ while the right side is $1+1=2$,
  and they are equal.

  Assume the inductive hypothesis, that the statement is true for
  $n=1$, \ldots, $n=k$ and consider the $n=k+1$ case.
  We have
  $(1+\sfrac{1}{1})\cdot(1+\sfrac{1}{2})\,\cdots\,(1+\sfrac{1}{k})\cdot(1+\sfrac{1}{k+1})
  =
  (k+1)\cdot(1+\sfrac{1}{k+1})
  =(k+1)+(k+1)/(k+1)
  =k+2$.  
\end{answer}
\end{exes}
% \end{ans}
% \item For all $n\in\N$, the number~$n^2+n$ is even.
% \item For all $n\geq 2$ the number $n^3-n$ is divisible by $6$.
%   \hint take the base case to be $2$.
% \item If $n\in\N$ then $4\divides 13^n-1$.
% \item If $n\in\Z^+$ then
%     $(1+\sfrac{1}{1})\cdot(1+\sfrac{1}{2})\,\cdots\,(1+\sfrac{1}{n})=n+1$.
% \end{exes}
% \begin{ans}
% \begin{exes}
% \item For the $n=0$ base step observe that $0^2+0$ is even.
%   For the inductive step assume the statement for $n=0$, \ldots, $n=k$
%   and consider the $n=k+1$ case.
%   We have $(k+1)^2+(k+1)=k^2+2k+1+k+1=(k^2+k)+(2k+2)$. 
%   By the inductive hypothesis $k^2+k$ is even, and clearly $2k+2$ is even, 
%   so the sum is even.
% \item The base step is $n=2$.
%   Since $6$ divides $2^3-2=8-2$, the statement holds in this case.

%   For the inductive step assume that the statement is true for 
%   the cases $n=0$, \ldots, $n=k$.
%   In the $n=k+1$ case, consider 
%   $(k+1)^3-(k+1)=(k^3+3k^2+3k+1)-(k+1)=(k^3+3k^2+3k)-k$.
%   The inductive hypothesis gives that $6$ divides $(k^3-k)$ so we will
%   be finished if we show that it divides  $3k^2+3k$.
%   We have $3k^2+3k=3\cdot k(k+1)$, and since
%   $k(k+1)$ is even (this was shown in the prior item),
%   the product is divisible by $6$.  
% \item The $n=0$ base step is clear, since four divides $13^0-1=0$.
%   For the inductive step assume that the statement is true for all cases 
%   with $0\leq n\leq k$ and consider the $n=k+1$ case.
%   Then $13^{k+1}-1=(13^{k+1}-13)+(13-1)=13(13^k-1)+12$.
%   The first term is divisible by~$4$ by the inductive hypothesis, while the
%   second term is obviously divisible by~$4$, and so the statement holds in 
%   this case.

%   \remark
%   this illustrates that 
%   sometimes when you have finished a proof by induction, 
%   while you now are sure that the statement is true, 
%   you can nonetheless be left with the sense
%   that you are not sure really \emph{why} it is true.
%   You can prove that this statement holds in a 
%   way that gives more intuition by plugging $13$ into the formula for a
%   geometric series. 
% \item The base step is a product with $n=1$~term.
%   The left side is $(1+\sfrac{1}{1})=2$ while the right side is $1+1=2$,
%   and they are equal.

%   Assume the inductive hypothesis, that the statement is true for
%   $n=1$, \ldots, $n=k$ and consider the $n=k+1$ case.
%   We have
%   $(1+\sfrac{1}{1})\cdot(1+\sfrac{1}{2})\,\cdots\,(1+\sfrac{1}{k})\cdot(1+\sfrac{1}{k+1})
%   =
%   (k+1)\cdot(1+\sfrac{1}{k+1})
%   =(k+1)+(k+1)/(k+1)
%   =k+2$.
% \end{exes}
% \end{ans}
\end{problem}

\begin{problem}
Prove that $n+1$-term sums of reals commute:
$a_0+a_1+\cdots+a_n=a_n+\cdots+a_0$ for all $n\geq 1$,
starting from the assumption that sum of two terms commutes.
\begin{answer}
The $n=1$ base step is the commutativity assumption $a_0+a_1=a_1+a_0$.

For the inductive step assume the statement is true for all 
sums of~$n+1$ terms with 
with $1\leq n\leq k$, and consider a sequence with $n=k+2$~terms.
We have 
$a_0+a_1+\cdots+a_k+a_{k+1}
=(a_0+a_1+\cdots+a_k)+a_{k+1}
=a_{k+1}+(a_0+a_1+\cdots+a_k)$ with the second equality coming from
two-term commutativity.
By the inductive hypothesis that is equal to 
$a_{k+1}+(a_k+\cdots+a_0)=a_{k+1}+a_k+\cdots+a_0$.
\end{answer}
\end{problem}

\begin{problem}[\maxlength]
The sequence of \definend{Fibonacci numbers}
$0,1,1,2,3,5,8,13, \ldots$ is defined by the condition that 
each succeeding number in the sequence is the sum of the 
two numbers before it $f_{n+1}=f_n+f_{n-1}$, subject to the initial conditions
$f_0=0$ and~$f_1=1$.
Where does this argument, which purports to show that
all Fibonacci numbers are even, go wrong?
``The base case is clear since $0$ is even.  
For the inductive step, assume the statement 
is true for all cases up to and including $n=k$.
By definition 
the next case $f_{k+1}$ is the sum of the two prior numbers, which by
the inductive hypothesis are both even.  
Thus their sum is even.''   
\begin{answer}
The recurrence $f_{n+1}=f_n+f_{n-1}$ first applies to computing $f_2$.
So to begin we must verify that both $f_0$ and~$f_1$ are even.
Of course, $f_1=1$ is not even.
\end{answer}
\end{problem}

While many induction arguments use the inductive 
hypothesis only in the $n=k$ case,
some break from that pattern.

\begin{problem}
The game of Nim starts with two piles, each containing $n$~chips.
Two players take turns picking a pile and removing 
some nonzero number of chips from that pile. 
The winner is the player who takes the final chip.
Prove by induction on~$n$ that the second player always wins by
playing this way: whatever number of chips the first player removes
from one pile, the second player removes the same number from the other pile.
\begin{answer}
The base step is where the two piles have $n=1$~chips.
The first player must pick a pile and must remove a chip, leaving one chip
in one pile, so the second player wins.

For the inductive step assume that the strategy wins when there are two piles
with $n=1$, \ldots, $n=k$~chips and consider two piles with
$k+1$~chips.
The first player picks a pile and removes some nonzero number of chips.
If the second player removes the same number of chips from the other
pile then we have reduced to a game with equal-sized piles, each
with~$k$ or fewer chips, which the inductive hypothesis says
is a win for the second player.  
\end{answer}
\end{problem}

\begin{df}
The \definend{Least Number Principle} 
(or \definend{Well-ordering Principle})
is that any nonempty 
subset of the natural
numbers has a least element.  
\end{df}

\begin{problem}
Show that the Principle of Induction implies the Least Number 
Principle.
\hint
show by induction that if a set of natural numbers does not
have a least element then that set is empty.
\begin{answer}
We shall use induction to prove for all $n\in\N$ that if a set~$A$ 
of natural numbers has no
least element then $A$ does not contain~$n$.

The base case is easy since if $A$ were to contains~$0$ then it would
clearly have a least element.
For the inductive step assume that the statement is true in the cases
$n=0$, \ldots, $n=k$ and consider the statement in the case~$n=k+1$.
If~$A$ has no least element and~$A$ does not contain any of $0$, \ldots,~$k$ 
then~$A$ cannot contain~$k+1$ either, since it would be least.   
\end{answer}
\end{problem}





% .....................................
\section{Division}
\begin{problem} \notetext{Division Theorem} For any integer 
\definend{divisor}~$b>0$ and \definend{dividend}~$a\,$ there is a unique pair of
integers, the \definend{quotient}~$q$ and \definend{remainder}~$r$,
such that $a=bq+r$ and $0\leq r<b$.
We prove this in steps.
\begin{exes} 
\begin{exercise}
  Show that~$q$ and~$r$ are unique.
\end{exercise}
\begin{answer}
  Suppose that $q_0,r_0\in\Z$ and $q_1,r_1\in\Z$ are such that
  $a=bq_0+r_0$ where $0\leq r_0<b$, and also
  $a=bq_1+r_1$ where $0\leq r_1<b$.
  Subtract to get $0=b\cdot(q_0-q_1)+(r_0-r_1)$ where $-b<r_0-r_1<b$.
  Rearrange the inequality to $1>(r_0-r_1)/(-b)>1$
  Rearrange the equation to $-b\cdot(q_0-q_1)=(r_0-r_1)$
  and divide by $-b$ to get $q_0-q_1=(r_0-r_1)/(-b)$.
  Thus  $1>q_0-q_1>-1$ and since $q_0-q_1$ is an integer, and
  the only integer strictly between those two is zero, we have $q_0-q_1=0$.
  With that, the equation $q_0-q_1=(r_0-r_1)/(-b)$ yields that $r_0-r_1=0$.
\end{answer}
\begin{exercise}
  Show that the statement is true if $a=0$.
  Show also that if the statement is true for~$a>0$ then it is true
  for~$a<0$.
\end{exercise} 
\begin{answer}
  If $a=0$ then the statement holds with $q=0$ and~$r=0$.
  Next assume that the statement holds for any positive dividend
  and consider a negative~$a$.
  Since $-a$ is positive, $-a=bq+r$ for some 
  $q,r\in\Z$ with $0\leq r<b$.
  Multiplying by $-1$ gives $a=b(-q)-r$ and
  rewriting this as $a=b\cdot(q-1)+(b-r)$ satisfies the condition on the
  remainder $0\leq b-r<b$ for for all~$r$ except $r=0$.
  The $r=0$ case is easy: $a=b(-q)+0$ satisfies the statement.   
\end{answer}
\begin{exercise} 
  Prove the statement for $a>0$.
  \hint you can consider the set of integers $\setbuilder{a-bq}{q\in\Z}$,
  note that it has nonnegative elements,
  apply the Least Number Principle
  to produce a smallest nonnegative element, and show that this is the desired
  remainder~$r$.
\end{exercise}
\begin{answer}
  We follow the hint.
  Consider the set $E=\setbuilder{a-bq}{q\in\Z}$.
  Because $a>0$, the element of~$E$ associated with $q=0$ is nonegative,
  so the subset of $E$ comprised of natural numbers $\hat{E}$ is nonempty.
  By the Least Number Principle, $\hat{E}$ has a smallest element;
  call it~$r$.
  We will be done if we show that~$0\leq r<b$.

  Suppose, to get a contradiction, that~$r$ is not 
  an element of that interval and so $r\geq b$.
  Since $r$ is an element of~$E$ there is some associated
  $q_r\in\Z$ such that $a-b\cdot q_r=r$.
  This paragraph's assumption that $r\geq b$
  gives that $r-b$ is a nonegative number smaller than~$r$, and
  $r-b=a-b\cdot (q_r-1)$ gives that $r-b$ is an element of $\hat{E}$.
  This contradicts the choice of~$r$ as the least element of~$\hat{E}$.
\end{answer}
% \begin{exercise}
%    What to do if $b\leq 0$?
% \end{exercise}
\end{exes}
% \begin{exes} 
% \item
%   Prove that~$q$ and~$r$ are unique.
% \item Show that the statement is true for $a=0$.
%   Show also that if the statement is true for~$a>0$ then it is true
%   for~$a<0$. 
% \item Prove the statement for $a>0$.
%   \hint you can consider the set of integers $\setbuilder{a-bq}{q\in\Z}$,
%   note that it has nonnegative elements,
%   apply the Least Number Principle
%   to produce a smallest nonnegative element, and show that this is the desired
%   remainder~$r$.
% % \item 
% % What to do if $b\leq 0$?
% \end{exes}
% \begin{ans}
% \begin{exes}
% \item Suppose that $q_0,r_0\in\Z$ and $q_1,r_1\in\Z$ are such that
%   $a=bq_0+r_0$ where $0\leq r_0<b$, and also
%   $a=bq_1+r_1$ where $0\leq r_1<b$.
%   Subtract to get $0=b\cdot(q_0-q_1)+(r_0-r_1)$ and $-b<r_0-r_1<b$.
%   Rearrange the equation $-b\cdot(q_0-q_1)=(r_0-r_1)$,
%   and divide by $-b$ to get $q_0-q_1=(r_0-r_1)/(-b)$.
%   Thus  $-1<q_0-q_1<1$ and since $q_0-q_1\in\Z$ we have $q_0-q_1=0$.
%   With that, the equation $q_0-q_1=(r_0-r_1)/(-b)$ shows that $r_0-r_1=0$.
% \item
%   If $a=0$ then the statement holds with $q=0$ and~$r=0$.

%   Next assume that the statement holds for any positive dividend
%   and consider a negative~$a$.
%   Since $-a$ is positive, $-a=bq+r$ for some 
%   $q,r\in\Z$ with $0\leq r<b$.
%   Multiplying by $-1$ gives $a=b(-q)-r$ and
%   rewriting this as $a=b\cdot(q-1)+(b-r)$ satisfies the condition on the
%   remainder $0\leq b-r<b$ for for all~$r$ except $r=0$.
%   The $r=0$ case is easy: $a=b(-q)+0$ satisfies the statement. 
% \item We follow the hint.
%   Consider the set $E=\setbuilder{a-bq}{q\in\Z}$.
%   Because $a>0$, the element of~$E$ associated with $q=0$ is nonegative,
%   so the subset of $E$ comprised of natural numbers $\hat{E}$ is nonempty.
%   By the Least Number Principle, $\hat{E}$ has a smallest element;
%   call it~$r$.
%   We will be done if we show that~$0\leq r<b$.

%   Suppose, to get a contradiction, that~$r$ is not 
%   an element of that interval and so $r\geq b$.
%   Since $r$ is an element of~$E$ there is some associated
%   $q_r\in\Z$ such that $a-b\cdot q_r=r$.
%   This paragraph's assumption that $r\geq b$
%   gives that $r-b$ is a nonegative number smaller than~$r$, and
%   $r-b=a-b\cdot (q_r-1)$ gives that $r-b$ is an element of $\hat{E}$.
%   This contradicts the choice of~$r$ as the least element of~$\hat{E}$.
% \end{exes}
% \end{ans}
\end{problem}

\noindent 
Observe that the divisor must be positive.
Observe also that $r=0$ if and only if $b\divides a$. 

\begin{df}
Where $m>0$, the remainder when $a$ is divided by~$m$ is
the \definend{modulus} $a\bmod m$.
Two numbers $a,b$ are \definend{congruent modulo $m$}, 
written $a\equiv c\pmod m$, 
if they leave the same remainder when divided by~$m$, that is,
if they have the same modulus with respect to~$m$.
\end{df}

\begin{problem}[\midlength]  \pord:
\begin{items}
\item $a\bmod b=b\bmod a$
\item $a\bmod b=-a\bmod b$
\item $b\bmod b=1$
\end{items}
\begin{ans}
\begin{exes}
\item This is false.
  A counterexample is that $2\bmod 1=0$ but $1\bmod 2=1$.
\item This is false.
  A counterexample is that $1\bmod 3=0$ but $-1\bmod 3=2$.
\item This is false;
  $1\bmod 1=0$.     
\end{exes}
\end{ans}
\end{problem}

\begin{problem} \label{ex:AEquivBpmodMIFFABDifferBYMultipleOfM}
Prove that $a\equiv b\pmod m$ if and only if $m\divides (a-b)$,
that is, if and only if $a$ and~$b$ differ by a multiple of~$m$
(for $m>0$).  
\begin{answer}
If $a\equiv b\pmod m$ if and only if they leave the same remainder,
$a=mq_a+r$ and~$b=bq_b+r$ for some $q_a,q_b\in\Z$.
That's equivalent to $a-b=m\cdot(q_a-q_b)$, 
which is true if and only if $a-b$ is divisible by~$m$.
\end{answer}
\end{problem}

\begin{problem}
Let $a,b,c,d,m$ be integers with $m>0$, and
$a\equiv b\pmod m$, and $c\equiv d\pmod m$.
Prove each.
\begin{exes}
\begin{exercise}
  $a+c\equiv b+d\pmod m$
\end{exercise}
\begin{answer}
  By the prior exercise, $a\equiv b\pmod m$ holds iff 
  $(a-b)$ is a multiple of~$m$, 
  so $a-b=mi$ for some~$i\in\Z$.
  Similarly, $c\equiv d\pmod m$ holds iff $m\divides (c-d)$, 
  so $c-d=mj$ for some~$j\in\Z$.
  Adding gives $(a+c)-(b+d)=m(i+j)$, which holds if and only if
  $m\divides (a+c)-(b+d)$, which in turn is equivalent to
  $a+c\equiv b+d\pmod m$.
\end{answer}
\begin{exercise} 
  $ac\equiv bd\pmod m$
\end{exercise}
\begin{answer}
  We have that $a\equiv b\pmod m$ holds if and only if
  $a$ and~$b$ differ by a multiple of~$m$, so 
  $a=b+mi$ for some~$i\in\Z$. 
  Similarly $c=d+mj$ for some~$j\in\Z$.
  Multiplying gives $ac=bd+m\cdot(id+mij+jb)$, 
  which is equivalent to $ac\equiv bd\pmod m$.   
\end{answer}
\begin{exercise}[\maxlength] 
  $a^n\equiv b^n\pmod m$ for all $n\in\Z^+$
\end{exercise}
\begin{answer}
  We will show this by induction on the power~$n$.
  The $n=1$ base step is true by the introductory assumption that 
  $a\equiv b\pmod m$.
  For the inductive step assume that the statement is true in the cases
  $n=1$, \ldots, $n=k$.
  The $k+1$ case is an application of the prior item with 
  $a^k\cdot a$ on the left of the equivalence and $b^k\cdot b$ on the
  right.  
\end{answer}
\end{exes}
% \begin{exes}
% \item $a+c\equiv b+d\pmod m$
% \item $ac\equiv bd\pmod m$
% \item $a^n\equiv b^n\pmod m$ for all $n\in\Z^+$.
% \end{exes}
% \begin{ans}
% \begin{exes}
% \item By the prior exercise, $a\equiv b\pmod m$ holds iff 
%   $(a-b)$ is a multiple of~$m$, 
%   so $a-b=mi$ for some~$i\in\Z$.
%   Similarly, $c\equiv d\pmod m$ holds iff $m\divides (c-d)$, 
%   so $c-d=mj$ for some~$j\in\Z$.
%   Adding gives $(a+c)-(b+d)=m(i+j)$, which holds if and only if
%   $m\divides (a+c)-(b+d)$, which in turn is equivalent to
%   $a+c\equiv b+d\pmod m$.
% \item We have that $a\equiv b\pmod m$ holds if and only if
%   $a$ and~$b$ differ by a multiple of~$m$, so 
%   $a=b+mi$ for some~$i\in\Z$. 
%   Similarly $c=d+mj$ for some~$j\in\Z$.
%   Multiplying gives $ac=bd+m\cdot(id+mij+jb)$, 
%   which is equivalent to $ac\equiv bd\pmod m$. 
% \item We will show this by induction on the power~$n$.
%   The $n=1$ base step is true by the introductory assumption that 
%   $a\equiv b\pmod m$.
%   For the inductive step assume that the statement is true in the cases
%   $n=1$, \ldots, $n=k$.
%   The $k+1$ case is an application of the prior item with 
%   $a^k\cdot a$ on the left of the equivalence and $b^k\cdot b$ on the
%   right.
% \end{exes}
% \end{ans}
\end{problem}

\begin{df}
For any real number~$x$,
its \definend{floor} $\floor{x}$ is
the greatest integer less than or equal to~$x$.  
\end{df}

\begin{problem} Prove each.
\begin{exes} 
\begin{exercise} 
  The quotient when $a$ is divided by $b$ is $\floor{a/b}$.
\end{exercise}
\begin{answer}
  The quotient~$q$ when $a$ is divided by~$b$ is defined by the
  property that $a=bq+r$ where~$0\leq r<b$.
  So to show that $\floor{a/b}$ is the quotient we must show that
  $a=b\cdot\floor{a/b}+(a-b\floor{a/b})$, which is clear, and we must also
  show that the remainder~$a-b\floor{a/b}$
  satisfies $0\leq a-b\floor{a/b}< b$.
  
  By the definition of floor, $x-1<\floor{x}\leq x$ for any real~$x$. 
  Thus we have
  $(a/b)-1< \floor{a/b}\leq a/b$ and multiplication by~$b$ gives
  $a-b< b\cdot\floor{a/b}\leq a$.
  Therefore $b\cdot\floor{a/b}$ is at a minimum $0$ less than~$a$, and
  at a maximum $b-1$ less than~$a$, as required.
\end{answer}
\begin{exercise} 
  $a =b\cdot\floor{a/b}+a\bmod b$
\end{exercise}    
\begin{answer}
  This is immediate from the prior item and the 
  definition of $a\bmod b$ as the remainder.  
\end{answer}
\begin{exercise} 
  $b\cdot(a\bmod m)=(ba)\bmod{(bm)}$
\end{exercise}
\begin{answer}
  Where $a, b, m\in\Z$ and $m>0$ we have
  $b\cdot(a\bmod m)=b\cdot(a-m\floor{a/m})
  =ba- bm\floor{a/m}
  =ba- bm\floor{ba/bm}
  =ba\bmod bm$.    
\end{answer}
\end{exes}
% \begin{exes} 
% \item The quotient when $a$ is divided by $b$ is $\floor{a/b}$.
% \item $a =b\cdot\floor{a/b}+a\bmod b$.    
% \item $b\cdot(a\bmod m)=(ba)\bmod{(bm)}$.    
% \end{exes}
% \begin{ans}
% \begin{exes}
% \item The quotient~$q$ when $a$ is divided by~$b$ is defined by the
%   property that $a=bq+r$ where~$0\leq r<b$.
%   So to show that $\floor{a/b}$ is the quotient we must show that
%   $a=b\cdot\floor{a/b}+(a-b\floor{a/b})$, which is clear, and we must also
%   show that the remainder~$a-b\floor{a/b}$
%   satisfies $0\leq a-b\floor{a/b}< b$.
  
%   By the definition of floor, $x-1<\floor{x}\leq x$ for any real~$x$. 
%   Thus we have
%   $(a/b)-1< \floor{a/b}\leq a/b$ and multiplication by~$b$ gives
%   $a-b< b\cdot\floor{a/b}\leq a$.
%   Therefore $b\cdot\floor{a/b}$ is at a minimum $0$ less than~$a$, and
%   at a maximum $b-1$ less than~$a$, as required.
% \item This is immediate from the prior item and the 
%   definition of $a\bmod b$ as the remainder.
% \item Where $a, b, m\in\Z$ and $m>0$ we have
%   $b\cdot(a\bmod m)=b\cdot(a-m\floor{a/m})
%   =ba- bm\floor{a/m}
%   =ba- bm\floor{ba/bm}
%   =ba\bmod bm$.    
% \end{exes}
% \end{ans}
\end{problem}

\begin{problem}[\midlength]  \notetext{Pigeonhole Principle}  Prove each.
\begin{exes}
\begin{exercise} 
  For a finite list of real numbers,
  the maximum is at least as big as the average.
\end{exercise}
\begin{answer}
  Let the real numbers be $p_0$, \ldots, $p_{n-1}$.
  The average is $a=(p_0+\cdots+p_{n-1})/n$ and so 
  $p_0+\cdots+p_{n-1}=na$.
  If each number were less than average $p_i<a$ then the sum
  $p_0+\cdots+p_{n-1}$ would be less than $na$, so at least
  one must be at least average.  
\end{answer}
\begin{exercise} If you put $n$-many papers into fewer than $n$-many
  pigeonholes then at least one hole gets at least two papers.
\end{exercise}
\begin{answer}
  Form the list where there are~$p_i$-many papers in the $i$-th pigeonhole.
  The average number of papers per hole is greater than~$1$, 
  so the maximum number is greater than~$1$.
  Since each $p_i$ is a natural number, the maximum must be at least~$2$.  
\end{answer}
\end{exes}
% \begin{exes}
% \item For a finite list of real numbers,
%   the maximum is at least as big as the average.
% \item If you put $n$-many papers into fewer than $n$-many
%   pigeonholes then at least one hole gets at least two papers.    
% \end{exes}
% \begin{ans}
% \begin{exes}
% \item Let the real numbers be $p_0$, \ldots, $p_{n-1}$.
%   The average is $a=(p_0+\cdots+p_{n-1})/n$ and so 
%   $p_0+\cdots+p_{n-1}=na$.
%   If each number were less than average $p_i<a$ then the sum
%   $p_0+\cdots+p_{n-1}$ would be less than $na$, so at least
%   one must be at least average.
% \item Form the list where there are~$p_i$-many papers in the $i$-th pigeonhole.
%   The average number of papers per hole is greater than~$1$, 
%   so the maximum number is greater than~$1$.
%   Since each $p_i$ is a natural number, the maximum must be at least~$2$.      
% \end{exes}
% \end{ans}
\end{problem}







% .....................................
\section{Common divisors and common multiples}

\begin{df}
An integer is a \definend{common divisor} of two others if it
divides both of them.
The \definend{greatest common divisor} of two integers 
is the largest of their common divisors,
except that we take the greatest common divisor of $0$ and $0$ 
to be $0$.
Write $\gcd(a,b)$ for the greatest common divisor
of $a$ and~$b$.
\end{df}

% TODO redundancy in the exercises?
\begin{problem}
Prove.
\begin{exes} 
\begin{exercise} \notetext{Existence} 
   Any $a,b\in\Z$ have a greatest common divisor.
\end{exercise}
\begin{answer}
  If $a=b=0$ then $\gcd(a,b)$ exists. 
  If $a=0$ and~$b\neq 0$ then, since every number divides~$0$, the set of 
  common divisors of the two is the set of divisors of~$b$, 
  the largest of which is~$\absval{b}$.
  In the same way, if $a\neq 0$ and~$b=0$ then the greatest common divisor 
  is~$\absval{a}$.

  So suppose that each number is nonzero.
  In this case the number~$1$ is a common divisor, so when we establish that 
  there is a common divisor that is greatest we will know it is positive.
  To establish that, note that each number has finitely many divisors and
  so the overlap\Dash the set of divisors common to both\Dash is finite.
  A finite set of integers must have an element that is greatest.  
\end{answer}
\begin{exercise} \notetext{Commutativity} 
  $\gcd(a,b)=\gcd(b,a)$
\end{exercise}
\begin{answer}
  The two sets 
  $\setbuilder{m\in\Z}{\text{$m\divides a$ and $m\divides b$\,}}$
  and 
  $\setbuilder{n\in\Z}{\text{$n\divides b$ and $n\divides a$\,}}$
  are equal and so have the same greatest element. 
  That is, the definition is symmetric in $a$ and~$b$.  
\end{answer}
\begin{exercise} 
  For any $a\in\Z$, both $\gcd(a,a)=\absval{a}$ 
  and~$\gcd(a,0)=\absval{a}$.
\end{exercise}
\begin{answer}
  The Divisibility Properties in \ref{ex:DivisibilityProperties}
  include that for any~$a\neq 0$ the largest divisor is $\absval{a}$.
  In the case that $a=0$ the definition of greatest common divisor 
  is that $\gcd(0,0)=0=\absval{0}$.

  For the other half, 
  every number divides zero, so the condition that $\gcd(a,0)$ be a common
  divisor reduces to the condition that it divide~$a$.
  As in the previous paragraph, one of the Divisibility Properties  
  is that for any nonzero integer~$a$ the largest divisor is $\absval{a}$.
  If $a=0$ then the equation is also true.  
\end{answer}
\begin{exercise} 
  If $d$ is a common divisor of $a$ and~$b$ then so is~$\absval{d}$.
  Thus common divisors are limited to the interval from $-\gcd(a,b)$
  to $\gcd(a,b)$.
\end{exercise}
\begin{answer}
  If $d$ is nonnegative then the statement is trivial.
  If $d$ is negative then
  this is immediate from \ref{ex:InteractionOfParityWithSign},
  which says that if $d$ divides a number then so does $-d$.  
\end{answer}
\begin{exercise} 
  $\gcd(a,b)=\gcd(\absval{a},\absval{b})$
\end{exercise}
\begin{answer}
  If both numbers are zero then the statement is clearly true.
  For the other case note that for any
  integer $c$, a number is a divisor of $c$ if and only if it divides 
  the absolute value~$\absval{c}$.
  Thus, the set of divisors of both~$a$ and~$b$ 
  is the same as the set of divisors of both~$\absval{a}$ and~$\absval{b}$, \
  and therefore the two sets have the same greatest element.  
\end{answer}
\begin{exercise}[\midlength] 
  If both numbers are nonzero then 
  $0< \gcd(a,b)\leq\min(\absval{a},\absval{b})$.
  If either is zero then the greatest common divisor is the 
  maximum of the absolute values.
\end{exercise}
\begin{answer}
  If both numbers are nonzero then~$1$ is a common divisor so 
  the greatest common divisor is greater then zero.
  For the other inequality,
  where $d$ is a common divisor, 
  because it divides~$a$ we have that $d\leq\absval{a}$ and
  because it divides~$b$ we have that $d\leq\absval{b}$.
  Thus $d$ is less than or equal to the minimum of the two.

  If $a=b=0$ then $\gcd(a,b)=0$, which is the maximum of the absolute values. 
  If $a=0$ and~$b\neq 0$ then the set of 
  common divisors of the two equals the set of divisors of~$b$, 
  the greatest of which $\gcd(a,b)=\absval{b}$ is larger than zero.
  In the same way, if $a\neq 0$ and~$b=0$ then the greatest common divisor 
  is~$\absval{a}>0$.
\end{answer}
\end{exes} 
% \begin{exes} 
% \item \notetext{Existence} Any $a,b\in\Z$ have a greatest common divisor.
% \item \notetext{Commutativity} $\gcd(a,b)=\gcd(b,a)$
% \item If either number is nonzero then 
%   $0\leq \gcd(a,b)\leq\min(\absval{a},\absval{b})$.
%   If both are nonzero then the first
%   inequality is strict.
% \item If $d$ is a common divisor of $a$ and~$b$ then so is~$\absval{d}$.
%   Thus common divisors are limited to the interval from $-\gcd(a,b)$
%   to $\gcd(a,b)$.
% \item For any $a\in\Z$, both $\gcd(a,a)=\absval{a}$ 
%   and~$\gcd(a,0)=\absval{a}$.
% \item $\gcd(a,b)=\gcd(\absval{a},\absval{b})$
% \end{exes} 
% \begin{ans}
% \begin{exes}
% \item If $a=b=0$ then $\gcd(a,b)$ exists. 
%   If $a=0$ and~$b\neq 0$ then, since every number divides~$0$, the set of 
%   common divisors of the two is the set of divisors of~$b$, 
%   the largest of which is~$\absval{b}$.
%   In the same way, if $a\neq 0$ and~$b=0$ then the greatest common divisor 
%   is~$\absval{a}$.

%   So suppose that each number is nonzero.
%   In this case the number~$1$ is a common divisor, so when we establish that 
%   there is a common divisor that is greatest we will know it is positive.
%   To establish that, note that each number has finitely many divisors and
%   so the overlap\Dash the set of divisors common to both\Dash is finite.
%   A finite set of integers must have an element that is greatest.
% \item The two sets 
%   $\setbuilder{m\in\Z}{\text{$m\divides a$ and $m\divides b$\,}}$
%   and 
%   $\setbuilder{n\in\Z}{\text{$n\divides b$ and $n\divides a$\,}}$
%   are equal and so have the same greatest element. 
%   That is, the definition is symmetric in $a$ and~$b$.
% \item If $a=b=0$ then $\gcd(a,b)=0$. 
%   If $a=0$ and~$b\neq 0$ then the set of 
%   common divisors of the two equals the set of divisors of~$b$, 
%   the greatest of which $\gcd(a,b)=\absval{b}$ is larger than zero.
%   In the same way, if $a\neq 0$ and~$b=0$ then the greatest common divisor 
%   is~$\absval{a}>0$.

%   If each number is nonzero then~$1$ is a common divisor so 
%   the greatest common divisor is greater then zero.
%   For the other inequality,
%   where $d$ is a common divisor, 
%   because it divides~$a$ we have that $d\leq\absval{a}$ and
%   because it divides~$b$ we have that $d\leq\absval{b}$.
%   Thus $d$ is less than or equal to the minimum of the two. 
% \item If $d$ is nonnegative then the statement is trivial.
%   If $d$ is negative then
%   this is immediate from \ref{ex:InteractionOfParityWithSign},
%   which says that if $d$ divides a number then so does $-d$.
% \item The Divisibility Properties in \ref{ex:DivisibilityProperties}
%   include that for any~$a\neq 0$ the largest divisor is $\absval{a}$.
%   In the case that $a=0$ the definition of greatest common divisor 
%   is that $\gcd(0,0)=0=\absval{0}$.

%   For the other half, 
%   every number divides zero, so the condition that $\gcd(a,0)$ be a common
%   divisor reduces to the condition that it divide~$a$.
%   As in the previous paragraph, one of the Divisibility Properties  
%   is that for any nonzero integer~$a$ the largest divisor is $\absval{a}$.
%   If $a=0$ then the equation is also true.
% \item If both numbers are zero then the statement is clearly true.
%   For the other case note that for any
%   integer $c$, a number is a divisor of $c$ if and only if it divides 
%   the absolute value~$\absval{c}$.
%   Thus, the set of divisors of both~$a$ and~$b$ 
%   is the same as the set of divisors of both~$\absval{a}$ and~$\absval{b}$, \
%   and therefore the two sets have the same greatest element.
% \end{exes}
% \end{ans}
\end{problem}

\begin{df}
Two numbers are \definend{relatively prime} 
(or \definend{coprime}, sometimes denoted~$a\perp b$) if their 
greatest common divisor is $1$.
\end{df}

\begin{df}
The \definend{least common multiple} of two numbers $\lcm(a,b)$ 
is the smallest natural number that is a multiple of each.
\end{df}

\begin{problem} Prove each.
\begin{items}
\item \notetext{Existence} Any two integers have a least common multiple.
  If the integers are nonzero then the lcm is positive
\item \notetext{Commutativity} $\lcm(a,b)=\lcm(b,a)$
\end{items}
\begin{answer}
\begin{items}
\item The absolute value of the product of the two is a common multiple,
  and is positive if neither number is zero.
  So the set of nonnegative common multiples is not empty.
  Any nonempty set of natural numbers has a least element.
\item The definition is symmetric in $a$ and~$b$.
  That is, the two sets
  $\setbuilder{m\in\Z}{\text{$a\divides m$ and $b\divides m$}}$
  and     
  $\setbuilder{m\in\Z}{\text{$b\divides m$ and $a\divides m$}}$
  are equal, and so have the same smallest nonnegative element.
\end{items}
\end{answer}
\end{problem}



% ========== Start Euclid's argument of lemma =========== 
\begin{euclidproof}
\begin{problem}
For each pair $a,b$ compute $\gcd(a,b)$, $\lcm(a,b)$, $ab$, and
$\gcd(a,b)\cdot\lcm(a,b)$.
\begin{exes}
% \begin{exercise} 
%   $a=6$, $b=15$
% \end{exercise}
% \begin{answer} 
%   $\gcd(a,b)=3$, $\lcm(a,b)=30$, $ab=90$, $\gcd(a,b)\cdot\lcm(a,b)=90$
% \end{answer}
\begin{exercise} 
  $a=18$, $b=35$
\end{exercise}  
\begin{answer}
  $\gcd(a,b)=1$, $\lcm(a,b)=630$, $ab=630$, $\gcd(a,b)\cdot\lcm(a,b)=630$
\end{answer}
\begin{exercise} 
  $a=20$, $b=-14$
\end{exercise}
\begin{answer}
  $\gcd(a,b)=2$, $\lcm(a,b)=140$, $ab=-280$, $\gcd(a,b)\cdot\lcm(a,b)=280$  
\end{answer}
\end{exes}
% \begin{exes}
% % \item $a=6$, $b=15$
% \item $a=18$, $b=35$  
% \item $a=20$, $b=-14$
% \end{exes}
% \begin{ans}
% \begin{exes}
% % \item $\gcd(a,b)=3$, $\lcm(a,b)=30$, $ab=90$, $\gcd(a,b)\cdot\lcm(a,b)=90$
% \item $\gcd(a,b)=1$, $\lcm(a,b)=630$, $ab=630$, $\gcd(a,b)\cdot\lcm(a,b)=630$
% \item $\gcd(a,b)=2$, $\lcm(a,b)=140$, $ab=-280$, $\gcd(a,b)\cdot\lcm(a,b)=280$
% \end{exes}
% \end{ans}
\end{problem}

\begin{problem} Let $a$ and~$b$ be integers.
\begin{exes}  %% TODO check the zero and negative cases.
\begin{exercise} 
   Prove that any common multiple of two nonzero
   numbers is divisible by their 
  least common multiple.
  \hint apply the Division-Remainder theorem with the divisor $\lcm(a,b)$.
\end{exercise}
\begin{answer}
  Let $\ell=\lcm(a,b)$ and suppose that $m$ is a common multiple
  of the two numbers.

  Dividing $m$ by~$\ell$ gives 
  $m=\ell\cdot q+r$ with $0\leq r< \ell$.
  In $r=m-\ell q$ 
  each term on the right is a multiple
  of both $a$ and~$b$ and so 
  $r$ is a common multiple of $a$ and~$b$.
  Because the remainder $r$ is less than the least common multiple~$\ell$,
  we conclude that $r=0$ and so $\ell\divides m$.  
\end{answer}
\begin{exercise} 
  Prove that the product of two nonzero numbers is divisible by their 
  least common multiple.
\end{exercise}
\begin{answer}
  The product $ab$ is a common multiple of the two.
  Apply the prior item.
\end{answer}
\begin{exercise} 
  Let $d$ be defined by 
  $ab=\lcm(a,b)\cdot d$, except that if either $a$ or~$b$ is zero
  then $d=\max\set{\absval{a},\absval{b}}$.
  Prove that any common divisor of $a$ and~$b$ also divides~$d$.
\end{exercise}
\begin{answer}
  If $a=0$ and~$b=0$ then $d=0$, and any number divides~$0$.
  If one of $a$ and~$b$ is zero and one is not then without loss of generality
  we can take $a=0$, $b\neq 0$.
  Since all numbers divide~$0$ the condition that a number~$c$ 
  is a common divisor of $a$ and~$b$
  becomes just that $c$ divides~$b$.
  So in this case we must show that any divisor of $b$ divides the 
  absolute value of~$b$, which we know to be true by the divisibility 
  properties~\ref{ex:DivisibilityProperties}.

  The remaining case is that both numbers are nonzero.
  First note that in this case,
  by the previous item, the least common multiple of $a,b\in\Z$ divides
  the product~$ab$.
  So $d$ is an integer for all pairs $a,b$ of nonzero numbers
  and we can sensibly apply the definition of `divides' to
  $a$ and~$d$, and to $b$ and~$d$.
  
  Let~$c$ be a common divisor so that $a=c\cdot k_a$ and $b=c\cdot k_b$.
  The number $ck_ak_b$ is a common multiple of $a$ and~$b$. 
  By the first item it is divisible by the least common multiple  
  $\ell\divides ck_ak_b$.
  Multiplication by $cd$ gives $\ell\cdot cd\divides ck_ak_b\cdot cd$.
  Regroup to $(\ell c)d\divides (ck_a)(ck_b)d$, which is
  $ab\cdot c\divides ab\cdot d$, and therefore by cancellation $c\divides d$,
  as desired.  
\end{answer}
\begin{exercise} 
  Prove that $\gcd(a,b)\leq\absval{d}$.
\end{exercise}
\begin{answer}
  The number~$d$ is zero only if both $a$ and~$b$ are
  zero.
  In this case the equation is true: $\gcd(0,0)=0\leq d=0$.

  In the $d\neq 0$ case we can apply the 
  Divisibility property~\ref{ex:DivisibilityProperties} that the
  largest divisor of a nonzero number is the absolute value of that number.
  By the prior item, any common divisor of $a$ and~$b$ will divide~$d$.
  One such common divisor is $\gcd(a,b)$.
  Thus $\gcd(a,b)\leq\absval{d}$.  
\end{answer}
\begin{exercise} 
  Prove that $\absval{d}=\gcd(a,b)$. 
\end{exercise}
\begin{answer}
  After the previous item, we need only show that $\gcd(a,b)\geq\absval{d}$. 
  Because $\ell=\lcm(a,b)$ is a common multiple of the two, 
  both $\ell/a$ and~$\ell/b$ are integers. 
  Rewriting the equation~$ab=\ell d$ to 
  $a=(\ell/b)\cdot d$ shows that~$d$ is a divisor of~$a$, and similarly
  it is a divisor of~$b$.
  Thus $d$ is a common divisor and so $\absval{d}\leq \gcd(a,b)$.  
\end{answer}
\begin{exercise} 
  Prove that any common divisor of two numbers also divides their
  greatest common divisor.
\end{exercise}
\begin{answer}
  This is immediate from the prior items.  
\end{answer}
\begin{exercise} 
  Prove that $\lcm(a,b)\cdot\gcd(a,b)=\absval{ab}$. 
\end{exercise}
\begin{answer}
  This is immediate from the prior items.
\end{answer}
\end{exes}  
% \begin{exes}
% \item Prove that any common multiple of two nonzero
%    numbers is divisible by their 
%   least common multiple.
%   \hint apply the Division-Remainder theorem with the divisor $\lcm(a,b)$.
% \item Prove that the product of two nonzero numbers is divisible by their 
%   least common multiple.
% \item Let $d$ be defined by 
%   $ab=\lcm(a,b)\cdot d$, except that if either $a$ or~$b$ is zero
%   then $d=\max\set{\absval{a},\absval{b}}$.
%   Prove that any common divisor of $a$ and~$b$ also divides~$d$.
% \item Prove that $\gcd(a,b)\leq\absval{d}$.
% \item Prove that $\absval{d}=\gcd(a,b)$. 
% \item Prove that any common divisor of two numbers also divides their
%   greatest common divisor.
% \item Prove that $\lcm(a,b)\cdot\gcd(a,b)=\absval{ab}$. 
% \end{exes}  
% \begin{ans}  %% TODO check the zero and negative cases.
% \begin{exes}
% \item Let $\ell=\lcm(a,b)$ and suppose that $m$ is a common multiple
%   of the two numbers.

%   Dividing $m$ by~$\ell$ gives 
%   $m=\ell\cdot q+r$ with $0\leq r< \ell$.
%   In $r=m-\ell q$ 
%   each term on the right is a multiple
%   of both $a$ and~$b$ and so 
%   $r$ is a common multiple of $a$ and~$b$.
%   Because the remainder $r$ is less than the least common multiple~$\ell$,
%   we conclude that $r=0$ and so $\ell\divides m$.
% \item The product $ab$ is a common multiple of the two.
%   Apply the prior item.
% \item If $a=0$ and~$b=0$ then $d=0$, and any number divides~$0$.
%   If one of $a$ and~$b$ is zero and one is not then without loss of generality
%   we can take $a=0$, $b\neq 0$.
%   Since all numbers divide~$0$ the condition that a number~$c$ 
%   is a common divisor of $a$ and~$b$
%   becomes just that $c$ divides~$b$.
%   So in this case we must show that any divisor of $b$ divides the 
%   absolute value of~$b$, which we know to be true by the divisibility 
%   properties~\ref{ex:DivisibilityProperties}.

%   The remaining case is that both numbers are nonzero.
%   First note that in this case,
%   by the previous item, the least common multiple of $a,b\in\Z$ divides
%   the product~$ab$.
%   So $d$ is an integer for all pairs $a,b$ of nonzero numbers
%   and we can sensibly apply the definition of `divides' to
%   $a$ and~$d$, and to $b$ and~$d$.
  
%   Let~$c$ be a common divisor so that $a=c\cdot k_a$ and $b=c\cdot k_b$.
%   The number $ck_ak_b$ is a common multiple of $a$ and~$b$. 
%   By the first item it is divisible by the least common multiple  
%   $\ell\divides ck_ak_b$.
%   Multiplication by $cd$ gives $\ell\cdot cd\divides ck_ak_b\cdot cd$.
%   Regroup to $(\ell c)d\divides (ck_a)(ck_b)d$, which is
%   $ab\cdot c\divides ab\cdot d$, and therefore by cancellation $c\divides d$,
%   as desired.
% \item The number~$d$ is zero only if both $a$ and~$b$ are
%   zero.
%   In this case the equation is true: $\gcd(0,0)=0\leq d=0$.

%   In the $d\neq 0$ case we can apply the 
%   Divisibility property~\ref{ex:DivisibilityProperties} that the
%   largest divisor of a nonzero number is the absolute value of that number.
%   By the prior item, any common divisor of $a$ and~$b$ will divide~$d$.
%   One such common divisor is $\gcd(a,b)$.
%   Thus $\gcd(a,b)\leq\absval{d}$.
% \item
%   After the previous item, we need only show that $\gcd(a,b)\geq\absval{d}$. 
%   Because $\ell=\lcm(a,b)$ is a common multiple of the two, 
%   both $\ell/a$ and~$\ell/b$ are integers. 
%   Rewriting the equation~$ab=\ell d$ to 
%   $a=(\ell/b)\cdot d$ shows that~$d$ is a divisor of~$a$, and similarly
%   it is a divisor of~$b$.
%   Thus $d$ is a common divisor and so $\absval{d}\leq \gcd(a,b)$.
% \item This is immediate from the prior items.
% \item This is immediate from the prior items.
% \end{exes}
% \end{ans}
\end{problem}

\begin{problem}  \label{ex:EuclidsLemma}
\begin{exes} 
\begin{exercise}
  Prove that
  dividing by the greatest common divisor leaves no common divisors:
  $a/\gcd(a,b)$ and $b/\gcd(a,b)$ are relatively prime.
\end{exercise}
\begin{answer}
  Let $\gcd(a,b)$ be~$d$ and suppose that $\gcd(a/d,\,b/d)=c$.
  Then $c\cdot k_a=a/d$ and~$c\cdot k_b=b/d$ for some numbers $k_a, k_b\in\Z$.
  Thus $cd\cdot k_a=a$ and $cd\cdot k_b=b$ and so $cd$ is a common divisor
  of $a$ and~$b$. 
  But $d$ is the greatest of the common divisors and so $c=1$, 
  or else $cd$ would be a common divisor
  that is larger than the greatest common divisor.      
\end{answer}
\begin{exercise} \notetext{Euclid's Lemma}  
  If $a$ and~$b$ are relatively prime then $a\divides bc$ implies that 
  $a\divides c$.
\end{exercise}
\begin{answer}
  Since $a\divides bc$ we know that $a$ is nonzero.
  If $b=0$ then because $\gcd(a,b)=1$ we have that $\absval{a}=1$ 
  and therefore $a\divides c$.

  In the $b\neq 0$ case, the assumption that $\gcd(a,b)=1$ 
  along with the equation $\absval{ab}=\gcd(a,b)\cdot\lcm(a,b)$ implies that 
  $\lcm(a,b)=\absval{ab}$.
  Because $a\divides bc$, the product $bc$ is a common 
  multiple of $a$ and~$b$ and so it is divisible by the least common multiple
  $\lcm(a,b)\divides bc$, giving that $ab\divides bc$.  
  Cancellation then gives that $a\divides c$.  
\end{answer}
\end{exes}
% \begin{exes} 
% \item 
%   Prove that
%   dividing by the greatest common divisor leaves no common divisors:
%   $a/\gcd(a,b)$ and $b/\gcd(a,b)$ are relatively prime.
% \item \notetext{Euclid's Lemma}  
%   If $a$ and~$b$ are relatively prime then $a\divides bc$ implies that 
%   $a\divides c$.
% \end{exes}
% \begin{ans}
% \begin{exes}
% \item
%   Let $\gcd(a,b)$ be~$d$ and suppose that $\gcd(a/d,\,b/d)=c$.
%   Then $c\cdot k_a=a/d$ and~$c\cdot k_b=b/d$ for some numbers $k_a, k_b\in\Z$.
%   Thus $cd\cdot k_a=a$ and $cd\cdot k_b=b$ and so $cd$ is a common divisor
%   of $a$ and~$b$. 
%   But $d$ is the greatest of the common divisors and so $c=1$, 
%   or else $cd$ would be a common divisor
%   that is larger than the greatest common divisor.    
% \item
%   Since $a\divides bc$ we know that $a$ is nonzero.
%   If $b=0$ then because $\gcd(a,b)=1$ we have that $\absval{a}=1$ 
%   and therefore $a\divides c$.

%   In the $b\neq 0$ case, the assumption that $\gcd(a,b)=1$ 
%   along with the equation $\absval{ab}=\gcd(a,b)\cdot\lcm(a,b)$ implies that 
%   $\lcm(a,b)=\absval{ab}$.
%   Because $a\divides bc$, the product $bc$ is a common 
%   multiple of $a$ and~$b$ and so it is divisible by the least common multiple
%   $\lcm(a,b)\divides bc$, giving that $ab\divides bc$.  
%   Cancellation then gives that $a\divides c$. 
% \end{exes}
% \end{ans}
\end{problem}
% ========== End Euclid's argument of lemma =========== 
\end{euclidproof}


% ========== Start Bezout argument of lemma =========== 
\begin{bezoutproof}
% TODO check answers
\begin{problem}\notetext{Euclid's Algorithm}
Prove that if $a=bq+r$ then $\gcd(a,b)=\gcd(b,r)$.  
\begin{answer}
Because $a=bq+r$ any common divisor of $b$ and~$r$ also divides~$a$, 
by Linearity~\ref{ex:DividesAndLinearCombinations}.
Rewrite the equation as $r=a-bq$ and then for the same reason any
common divisor of $a$ and~$b$ also divides~$r$.
So the pairs $b,r$ and $a,b$ have the same common divisors, and
therefore the same greatest common divisor.
\end{answer}
\end{problem}

The algorithm associated with this result finds the greatest common
divisor for any $a,b\in\Z$ with $b\neq 0$.  
For instance, to find $\gcd(803,154)$ divide the larger by
the smaller $803=154\cdot 5+33$ and then the above result shows that  
$\gcd(803,154)=\gcd(154,33)$.
Next, since $154=33\cdot 4+22$ the above result gives
$\gcd(154,33)=\gcd(33,22)$.
By eye we spot the answer of $11$ but continuing as though we hadn't noticed
we get $33=22\cdot 1+11$, so $\gcd(33,22)=\gcd(22,11)$.
Finally, $22=11\cdot 2+0$ gives that 
$\gcd(22,11)=11$, so the algorithm terminates with $\gcd(803,154)=11$.

We can reverse this calculation.
From $33=22\cdot 1+11$ we can  
express the greatest common divisor~$11$ as a combination 
$11=1\cdot 33-1\cdot 22$.
Next, 
the equation $154=33\cdot 4+22$ lets us express
the $11$ as a combination 
$11=1\cdot 33-1\cdot (154-4\cdot 33)=-1\cdot 154+5\cdot 33$
of the pair $154,33$.
Backing up still further, the equation 
$803=154\cdot 5+33$
gives $11=-1\cdot 154+5\cdot (803-5\cdot 154)=5\cdot 803-26\cdot 154$, so 
we can express the greatest common divisor as a combination of our
initial pair~$803,154$.


\begin{df}
A number $c$ is a \definend{linear combination} of two others $a$ and~$b$
if it has the form $c=a\cdot m+b\cdot n$ for some $m,n\in\Z$.  
\end{df}

\begin{problem}
Use Euclid's Algorithm to find the greatest common divisor and 
reverse that to express the greatest common divisor as a 
linear combination of the two:
\begin{items}
\item $15$, $25$
\item $48$, $732$
\end{items}
\begin{answer}
\begin{items}
\item To get the greatest common divisor the first step is
  $25=15\cdot 1+10$ followed by $15=10\cdot 1+5$ and finally
  $10=5\cdot 2+0$ shows that $\gcd(25,15)=5$.

  Reversing those starts with $5=1\cdot 15-1\cdot 10$.
  Use the equation $25=15\cdot 1+10$ to substitute 
  $5=1\cdot 15-1\cdot(1\cdot 25-1\cdot 15)=-1\cdot 25+2\cdot 15$.
  This expresses $\gcd(25,15)=5$ as a linear combination of
  $25$ and~$15$.
\item Start by dividing the larger by the smaller
  $732=48\cdot 15+12$.
  The next step is $48=12\cdot 4+0$, so $\gcd(732,48)=12$.

  Reversing is trivial:
  $12=1\cdot 732-12\cdot 48$.
\end{items}
\end{answer}
\end{problem}

\begin{problem} Prove.  \label{ex:Bezout}
\begin{exes}
\begin{exercise} 
  Euclid's algorithm terminates.
\end{exercise}
\begin{answer}
  Since $\gcd(a,b)=\gcd(\pm a, \pm b)$ we can restrict to $a\geq 0$
  and $b>0$.
  Write $a$ as~$a_0$ and~$b$ as~$b_0$.
  The first step of the algorithm divides the larger number by the smaller; 
  without loss of generality we have $a_0=b_0\cdot q_0+r_0$ with 
  $0\leq r_0< b_0$.
  If the remainder~$r$ is not zero, which would mean the algorithm 
  terminated,
  then we next have $b_0=r_0\cdot q_1+r_1$ with $0\leq r_1< r_0$.
  Therefore $0\leq r_1<r_0<b$.

  In this way the remainders $r_i$ form a sequence of positive numbers that
  are falling.
  Such a sequence must be finite so that for some~$i$ 
  an~$r_i$ is zero and the algorithm terminates.  
\end{answer}
\begin{exercise}[\midlength]
  The greatest common divisors of two numbers is a linear combination of 
  the two.
\end{exercise}
\begin{answer}
  The above calculation reversing Euclid's algorithm proves by
  construction that the greatest common divisor can be expressed 
  a combination of the two. 
\end{answer}
\begin{exercise} \notetext{B\'ezout's Lemma} 
  The greatest common divisor of two numbers is the smallest positive
  number that is a linear combination of the two.
\end{exercise}
\begin{answer}
  The $a=b=0$ case is separate:
  $\gcd(a,b)=0$ by definition and for any $s$ and $t$ we
  have that $0=\gcd(a,b)=s\cdot a+t\cdot b=s\cdot 0+t\cdot 0$.

  The remaining case is that one number or the other is nonzero.
  Consider the set of linear combinations 
  $\mathcal{L}=\setbuilder{sa+tb}{s,t\in\Z}$.
  Not all its elements are~$0$ since
  one of $a$ or~$b$ is nonzero and taking $1$ times that element
  plus $0$~times the other gives a nonzero member). 
  If $\mathcal{L}$ has a 
  negative element then negating the coefficients $s$ and~$t$ gives 
  a positive element, thus $\mathcal{L}$ has a positive element.
  Any set of positive integers has a least element;
  call that~$d$.

  For any combination $sa+tb$, because the greatest common divisor
  $\gcd(a,b)$ goes into both $a$ and~$b$ it also divides $sa+tb$  
  (from Linearity~\ref{ex:DividesAndLinearCombinations}).
  Therefore $\gcd(a,b)\leq d$.

  The prior item shows $d\leq\gcd(a,b)$ and so the two are equal. 

  % Let the two numbers be $a,b\in\Z$; we want to show that there are
  % $s,t\in\Z$ so that $\gcd(a,b)=s\cdot a+t\cdot b$.

  % The $a=b=0$ case is separate.
  % In this case $\gcd(a,b)=0$ by definition and for any $s$ and $t$ we
  % have $0=\gcd(a,b)=s\cdot a+t\cdot b=s\cdot 0+t\cdot 0$.

  % The other case is that either number is nonzero.
  % Consider the set of linear combinations 
  % $\mathcal{L}=\setbuilder{sa+tb}{s,t\in\Z}$.
  % It has a positive element since not all its elements are~$0$
  % (one of $a$ or~$b$ is nonzero and taking $1$ times that element
  % plus zero times the other gives a nonzero member), and if it has a 
  % negative element then negating the coefficients $s$ and~$t$ gives 
  % a positive element.
  % Any set of positive integers has a least positive element.
  % Call that element~$d\in\mathcal{L}$.
  % We will show that $d=\gcd(a,b)$.

  % By the first item any divisor common to $a$ and $b$ also divides 
  % a combination of the two, so $\gcd(a,b)\divides d=sa+bt$, and therefore
  % $\gcd(a,b)\leq d$.

  % For the inequality in the other direction, 
  % we will show that $d$ is a common divisor.
  % To show that $d\divides a$ write $a=dq+r$ with $0\leq r<d$ and
  % substitute: $r=a-dq=a-(sa+tb)\cdot q=(1-s)\cdot a-t\cdot b$.
  % Because~$d$ is the minimal positive combination, and becasue $r<d$,
  % this implies that the remainder~$r$ is zero and so $d\divides a$.
  % In the same way $d\divides b$.
  % As a common divisor, $d\leq\gcd(a,b)$.  
\end{answer}
\end{exes}
% \begin{exes}
% \item Euclid's algorithm terminates.
% \item The greatest common divisors of two numbers is a linear combination of 
% the two.
% \item \notetext{B\'ezout's Lemma} 
% The greatest common divisor of two numbers is the smallest positive
% number that is a linear combination of the two.
% \end{exes}
% \begin{ans}
% \begin{exes}
% \item Since $\gcd(a,b)=\gcd(\pm a, \pm b)$ we can restrict to $a\geq 0$
%   and $b>0$.
%   Write $a$ as~$a_0$ and~$b$ as~$b_0$.
%   The first step of the algorithm divides the larger number by the smaller; 
%   without loss of generality we have $a_0=b_0\cdot q_0+r_0$ with 
%   $0\leq r_0< b_0$.
%   If the remainder~$r$ is not zero, which would mean the algorithm 
%   terminated,
%   then we next have $b_0=r_0\cdot q_1+r_1$ with $0\leq r_1< r_0$.
%   Therefore $0\leq r_1<r_0<b$.

%   In this way the remainders $r_i$ form a sequence of positive numbers that
%   are falling.
%   Such a sequence must be finite so that for some~$i$ 
%   an~$r_i$ is zero and the algorithm terminates.
% \item The above calculation reversing Euclid's algorithm proves by
%   construction that the greatest common divisor can be expressed 
%   a combination of the two.
% \item   The $a=b=0$ case is separate.
%   Here $\gcd(a,b)=0$ by definition and for any $s$ and $t$ we
%   have $0=\gcd(a,b)=s\cdot a+t\cdot b=s\cdot 0+t\cdot 0$.

%   The other case is that one number or the other is nonzero.
%   Consider the set of linear combinations 
%   $\mathcal{L}=\setbuilder{sa+tb}{s,t\in\Z}$.
%   It has a positive element since not all its elements are~$0$
%   (one of $a$ or~$b$ is nonzero and taking $1$ times that element
%   plus zero times the other gives a nonzero member), and if it has a 
%   negative element then negating the coefficients $s$ and~$t$ gives 
%   a positive element.
%   Any set of positive integers has a least positive element.
%   Call that element~$d\in\mathcal{L}$.

%   For any combination $sa+tb$, because the greatest common divisor
%   $\gcd(a,b)$ goes into both $a$ and~$b$ it also divides $sa+tb$  
%   (from Linearity~\ref{ex:DividesAndLinearCombinations})
%   Therefore $\gcd(a,b)\leq d$.

%   The prior item shows $d\leq\gcd(a,b)$ and so the two are equal. 

%   % Let the two numbers be $a,b\in\Z$; we want to show that there are
%   % $s,t\in\Z$ so that $\gcd(a,b)=s\cdot a+t\cdot b$.

%   % The $a=b=0$ case is separate.
%   % In this case $\gcd(a,b)=0$ by definition and for any $s$ and $t$ we
%   % have $0=\gcd(a,b)=s\cdot a+t\cdot b=s\cdot 0+t\cdot 0$.

%   % The other case is that either number is nonzero.
%   % Consider the set of linear combinations 
%   % $\mathcal{L}=\setbuilder{sa+tb}{s,t\in\Z}$.
%   % It has a positive element since not all its elements are~$0$
%   % (one of $a$ or~$b$ is nonzero and taking $1$ times that element
%   % plus zero times the other gives a nonzero member), and if it has a 
%   % negative element then negating the coefficients $s$ and~$t$ gives 
%   % a positive element.
%   % Any set of positive integers has a least positive element.
%   % Call that element~$d\in\mathcal{L}$.
%   % We will show that $d=\gcd(a,b)$.

%   % By the first item any divisor common to $a$ and $b$ also divides 
%   % a combination of the two, so $\gcd(a,b)\divides d=sa+bt$, and therefore
%   % $\gcd(a,b)\leq d$.

%   % For the inequality in the other direction, 
%   % we will show that $d$ is a common divisor.
%   % To show that $d\divides a$ write $a=dq+r$ with $0\leq r<d$ and
%   % substitute: $r=a-dq=a-(sa+tb)\cdot q=(1-s)\cdot a-t\cdot b$.
%   % Because~$d$ is the minimal positive combination, and becasue $r<d$,
%   % this implies that the remainder~$r$ is zero and so $d\divides a$.
%   % In the same way $d\divides b$.
%   % As a common divisor, $d\leq\gcd(a,b)$.
% \end{exes}
% \end{ans}
\end{problem}

\begin{problem}
You are given three buckets. 
The first two are marked $6$~liters and $11$~liters
while the last one, which is quite large, is unmarked.
Taking water from a nearby pond, use those buckets
to end with $8$~liters in the unmarked one.  
\begin{answer}
The greatest common divisor of $6$ and~$11$ is~$1$.
Reversing Euclid's algorithm (or simply spotting the relation by eye) 
gives $1=2\cdot 6-1\cdot 11$.
Thus $8=16\cdot 6- 8\cdot 11$
so you can get $8$~liters by filling 
the $6$~liter bucket sixteen times, pouring each in the 
large bucket, and then draining off the large bucket into the
$11$~liter bucket eight times.

If you are annoyed by assuming the large bucket is of unbounded size, you
can instead
first fill the $6$~liter bucket and pour that into the $11$~liter bucket.
Next fill the $6$~liter bucket again and pour what you can into the~$11$.
You are left with $1$~liter in the small bucket.  
Pour that into the large unmarked bucket.
Repeat seven more times.    
\end{answer}
\end{problem}

\begin{problem}  \label{ex:EuclidsLemma}
Let $a,b\in\Z$ and $m\in\N$. 
Prove each.
\begin{exes}
\begin{exercise} 
  $\gcd(ma,mb)=m\cdot\gcd(a,b)$
\end{exercise}
\begin{answer}
  If both $a$ and~$b$ are zero then the equation is trivial.
  If one or both numbers are nonzero then by 
  B\'ezout's Lemma~\ref{ex:Bezout}, $\gcd(ma,mb)$ is the least
  positive value of $\setbuilder{s\cdot ma+t\cdot mb}{s,t\in\Z}$.
  This equals $m$ times the least positive member of 
  $\setbuilder{sa+tb}{s,t\in\Z}$, 
  which is $m\cdot\gcd(a,b)$.  
\end{answer}
\begin{exercise} 
  If $d$ is a common divisor of $a$ and~$b$ then 
  $\gcd(a/d,\,b/d)=\gcd(a,b)/d$.
  This shows that 
  dividing by the greatest common divisor leaves no common divisors:
  if $a$ and~$b$ are nonzero then $a/gcd(a,b)$ and $b/\gcd(a,b)$
  are relatively prime.
\end{exercise}
\begin{answer}
  This is immediate from the prior item on taking $m$ to be~$d$, 
  and also taking $a$ to be~$a/d$ and $b$ to be~$b/d$.       
\end{answer}
\begin{exercise} \notetext{Euclid's Lemma}  
  If $a$ and~$b$ are relatively prime then $a\divides bc$ implies that 
  $a\divides c$.
\end{exercise}
\begin{answer}
  The numbers $a$ and~$b$ are relatively prime so $\gcd(a,b)=1$.
  The first item gives $\gcd(ca,cb)=c$.
  Thus $c=s\cdot ac+t\cdot bc$ for some $s,t\in\Z$, and
  because $a\divides ac$ and~$a\divides bc$ we have by Linearity that
  $a\divides c$.
\end{answer}
\end{exes}
% \begin{exes}
% \item $\gcd(ma,mb)=m\cdot\gcd(a,b)$
% \item If $d$ is a common divisor of $a$ and~$b$ then 
%   $\gcd(a/d,\,b/d)=\gcd(a,b)/d$.
%   This implies that 
%   dividing by the greatest common divisor leaves no common divisors:
%   if $a$ and~$b$ are nonzero then $a/gcd(a,b)$ and $b/\gcd(a,b)$
%   are relatively prime.
% \item \notetext{Euclid's Lemma}  
%   If $a$ and~$b$ are relatively prime then $a\divides bc$ implies that 
%   $a\divides c$.
% \end{exes}
% \begin{ans}
% \begin{exes}
% \item If both $a$ and~$b$ are zero then the equation is trivial.
%   If one or both numbers are nonzero then by 
%   B\'ezout's Lemma~\ref{ex:Bezout}, $\gcd(ma,mb)$ is the least
%   positive value of $\setbuilder{s\cdot ma+t\cdot mb}{s,t\in\Z}$.
%   This equals $m$ times the least positive member of 
%   $\setbuilder{sa+tb}{s,t\in\Z}$, 
%   which is $m\cdot\gcd(a,b)$.
% \item This is immediate from the prior item on taking $m$ to be~$d$, 
%   and also taking $a$ to be~$a/d$ and $b$ to be~$b/d$.     
% \item The numbers $a$ and~$b$ are relatively prime so $\gcd(a,b)=1$.
%   The first item gives $\gcd(ca,cb)=c$.
%   Thus $c=s\cdot ac+t\cdot bc$ for some $s,t\in\Z$, and
%   because $a\divides ac$ and~$a\divides bc$ we have by Linearity that
%   $a\divides c$.
% \end{exes}
% \end{ans}
\end{problem}
\end{bezoutproof}
% ========== End Bezout argument of lemma =========== 











% .....................................
\section{Primes}
\begin{df}
An integer greater than~$1$
is \definend{prime} if its only divisors are~$1$ and itself.
A number greater than~$1$ that is not prime is~\definend{composite}.  
\end{df}

\begin{problem} Prove.
\begin{exes}
\begin{exercise} 
  An integer $n>1$ is composite if and only if it has factors $a,b$ 
  such that $1<a,b<n$.  
\end{exercise}
\begin{answer}
  The `if' direction, that if it has such factors then it is composite,
  is clear.
  For `only if' assume that $n$ is composite so
  that at least one of its divisors~$a$ satisfies that $1<a<n$.
  Consider $b\in\Z$ such that $ab=n$; we will be finished when we show 
  that $1<b<n$.
  First, $b$ is positive because $a$ and~$n$ are positive.
  Next,~$b$ must be greater than~$1$ because $0<b\leq 1$ 
  implies that $ab\leq a<n$.
  Finally,~$b$ must be less than~$n$ because $1<a$ implies that $b<ab=n$.   
\end{answer}
\begin{exercise} 
  Every number greater than $1$ has a prime divisor.
\end{exercise}
\begin{answer}
  We use induction to prove that
  every number greater than one has a prime divisor.
  The base step is~$n=2$, which has a prime divisor, namely~$2$ itself.

  For the inductive step suppose that the statement is true for the cases 
  $n=2$, \ldots, $n=k$ and consider $k+1$.
  If $k+1$ is prime then we are done, the prime divisor is $k+1$~itself.
  Otherwise $k+1$ is composite.
  By the prior item it has factors $a,b$ with $1<a,b<k+1$.
  The inductive hypothesis applies to these numbers, and so~$a$ has at
  least one prime factor, which is then a prime factor of $k+1$.  
\end{answer}
\begin{exercise} 
  Every composite number $n>1$ has a prime divisor~$p$ 
  with $p\leq \sqrt{n}$.
\end{exercise}
\begin{answer}
  Because~$n>1$ is composite there are numbers~$a,b\in\Z$ with
  $1<a,b<n$.
  If both~$a>\sqrt{n}$ and~$b>\sqrt{n}$ then we would have that
  $a\cdot b>\sqrt{n}\cdot\sqrt{n}=n$,
  so at least one of the factors of~$n$ must be less than or equal 
  to~$\sqrt{n}$.

  We finish by showing that $n$ has a factor in that category that is prime.
  Let $c$ be a factor of~$n$ with $c\leq\sqrt{n}$.
  Then $c$ has a prime factor~$p$.
  This~$p$ is a factor of~$n$ by the Transitivity property. 
  It is 
  less than or equal to~$c$ by the Comparison property and therefore
  is less than or equal to~$\sqrt{n}$.    
\end{answer}
\begin{exercise} 
  Show that the prior inequality cannot be made strict.
\end{exercise}
\begin{answer}
  Take $n=4$.  
\end{answer}
\end{exes}
% \begin{exes}
% \item An integer $n>1$ is composite if and only if it has factors $a,b$ 
%   such that $1<a,b<n$.  
% \item Every number greater than $1$ has a prime divisor.
% \item Every composite number $n>1$ has a prime divisor~$p$ 
%   with $p\leq \sqrt{n}$.
% \item Show that the prior inequality cannot be made strict.     
% \end{exes}
% \begin{ans}
% \begin{exes}
% \item The `if' direction, that if it has such factors then it is composite,
%   is clear.
%   For `only if' assume that $n$ is composite so
%   that at least one of its divisors~$a$ satisfies that $1<a<n$.
%   Consider $b\in\Z$ such that $ab=n$; we will be finished when we show 
%   that $1<b<n$.
%   First, $b$ is positive because $a$ and~$n$ are positive.
%   Next,~$b$ must be greater than~$1$ because $0<b\leq 1$ 
%   implies that $ab\leq a<n$.
%   Finally,~$b$ must be less than~$n$ because $1<a$ implies that $b<ab=n$. 
% \item We use induction to prove that
%   every number greater than one has a prime divisor.
%   The base step is~$n=2$, which has a prime divisor, namely~$2$ itself.

%   For the inductive step suppose that the statement is true for the cases 
%   $n=2$, \ldots, $n=k$ and consider $k+1$.
%   If $k+1$ is prime then we are done, the prime divisor is $k+1$~itself.
%   Otherwise $k+1$ is composite.
%   By the prior item it has factors $a,b$ with $1<a,b<k+1$.
%   The inductive hypothesis applies to these numbers, and so~$a$ has at
%   least one prime factor, which is then a prime factor of $k+1$.
% \item Because~$n>1$ is composite there are numbers~$a,b\in\Z$ with
%   $1<a,b<n$.
%   If both~$a>\sqrt{n}$ and~$b>\sqrt{n}$ then we would have that
%   $a\cdot b>\sqrt{n}\cdot\sqrt{n}=n$,
%   so at least one of the factors of~$n$ must be less than or equal 
%   to~$\sqrt{n}$.

%   We finish by showing that $n$ has a factor in that category that is prime.
%   Let $c$ be a factor of~$n$ with $c\leq\sqrt{n}$.
%   Then $c$ has a prime factor~$p$.
%   This~$p$ is a factor of~$n$ by the Transitivity property. 
%   It is 
%   less than or equal to~$c$ by the Comparison property and therefore
%   is less than or equal to~$\sqrt{n}$.  
% \item Take $n=4$.
% \end{exes}
% \end{ans}
\end{problem}                   

\begin{problem} \notetext{Euclid's Theorem}
There are infinitely many primes.  
\begin{answer}
To obtain a contradiction, assume otherwise.
Assume that there are finitely many primes: 
$p_0=2$, $p_1=3$, \ldots, $p_{n-1}$.
Consider the number $m=(p_0\cdotp_1\cdots p_{n-1})+1$.

This number is greater than~$1$ because it is greater than 
$p_0\cdotp_1\cdots p_{n-1}$, 
which is a product of $n>0$-many numbers, each of which is greater than~$1$.
Thus~$m$ has a prime factor, which by the assumption is one of the~$p_i$.
But~$m$ is constructed so that dividing it by any~$p_i$ 
leaves a remainder of~$1$.
This is a contradiction, so the assumption that there is a finite
list of primes is impossible.
\end{answer}
\end{problem}

\begin{problem} 
Suppose that $p$ is a prime.  Prove each.\label{ex:EuclidsOtherLemma}
\begin{exes}
\begin{exercise} 
  If  $p\divides ab$ then either $p\divides a$ or $p\divides b$.
\end{exercise}
\begin{answer}
  Let $d=\gcd(p,a)$.
  Then $d$ is a positive number such that $d\divides p$ and~$d\divides a$.
  Because $p$ is prime, either $d=p$ or~$d=1$.
  If $d=p$ then $p\divides a$.
  If $d=1$ then Euclid's Lemma~\ref{ex:EuclidsLemma} shows that 
  $p\divides b$.
\end{answer}
\begin{exercise} 
  If $p\divides a_0\cdot a_1\cdots a_{n-1}$ then $p$ divides at least one~$a_i$.
\end{exercise}
\begin{answer}
  We prove this by induction on the size of the product.
  The base step is $n=1$, that there are two numbers in the product.
  This is proved in the prior item.

  For the inductive step assume that the statement is true for $n=1$, \ldots,
  $n=k$ and suppose that $n=k+1$, that $p\divides a_0\cdots a_{k-1}a_k$.
  Taking $a_0\cdots a_{k-1}$ as~$a$ and $a_k$ as~$b$, the prior item applies
  to show that $p\divides a_0\cdots a_{k-1}$ or~$p\divides a_k$.
  In the latter case we are done while in the former case the
  inductive hypothesis applies to show that $p$ divides one of the factors.  
\end{answer}
\end{exes}
% \begin{exes}
% \item If  $p\divides ab$ then either $p\divides a$ or
% $p\divides b$.
% \item If $p\divides a_0\cdot a_1\cdots a_{n-1}$ then 
% $p$ divides at least one~$a_i$.    
% \end{exes}
% \begin{ans}
% \begin{exes}
% \item Let $d=\gcd(p,a)$.
%   Then $d$ is a positive number such that $d\divides p$ and~$d\divides a$.
%   Because $p$ is prime, either $d=p$ or~$d=1$.
%   If $d=p$ then $p\divides a$.
%   If $d=1$ then Euclid's Lemma~\ref{ex:EuclidsLemma} shows that 
%   $p\divides b$.
% \item We prove this by induction on the size of the product.
%   The base step is $n=1$, that there are two numbers in the product.
%   This is proved in the prior item.

%   For the inductive step assume that the statement is true for $n=1$, \ldots,
%   $n=k$ and suppose that $n=k+1$, that $p\divides a_0\cdots a_{k-1}a_k$.
%   Taking $a_0\cdots a_{k-1}$ as~$a$ and $a_k$ as~$b$, the prior item applies
%   to show that $p\divides a_0\cdots a_{k-1}$ or~$p\divides a_k$.
%   In the latter case we are done while in the former case the
%   inductive hypothesis applies to show that $p$ divides one of the factors.
% \end{exes}
% \end{ans}
\end{problem}


% Gowers: http://gowers.wordpress.com/2011/11/13/why-isnt-the-fundamental-theorem-of-arithmetic-obvious/
% and
% http://gowers.wordpress.com/2011/11/18/proving-the-fundamental-theorem-of-arithmetic/
\begin{problem} \notetext{Fundamental Theorem of Arithmetic}  
Prove.
\begin{exes}
\begin{exercise} 
  Any number $n>1$ can be written as a product of one or more primes
  $n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$.
\end{exercise}
\begin{answer}
  We do induction.
  For the base step, observe that $n=2$ is the product of one prime. 
  For the inductive step assume that the statement holds when $n=2$, \ldots, 
  $n=k$ and consider~$n=k+1$.
  Every number greater than~$1$ factors $k+1=a\cdot b$ into two smaller
  numbers.
  Because these two are smaller
  the inductive hypothesis applies, so each is a product of 
  primes.
  Then $k+1=ab$ can be written as a product of primes.  
\end{answer}
\begin{exercise} 
  That factorization is essentially unique:~if 
  $n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$ and the primes
  are in ascending order $p_1<p_2<\cdots<p_k$ then any other
  factorization of~$n$ into a product of primes in ascending order will give the
  same result. 
  \hint~suppose that there are two factorizations into primes 
   $n=p_0\cdots p_{s-1}$ and $n=q_0\cdots q_{t-1}$ in ascending order 
   and use induction on~$s$.
\end{exercise}
\begin{answer}
  Assume that $n=p_0\cdots p_{s-1}$ with $s\geq 1$ and
  $p_0\leq\cdots \leq p_{s-1}$, 
  and also that $n=q_0\cdots q_{t-1}$ with $t\geq 1$ 
  and $q_0\leq\cdots \leq q_{t-1}$.
  We will show that $s=t$ and that $p_i=q_i$ for each $i$.

  We use induction on~$s$.
  The base step is~$s=1$ so that $n=p_0$ is prime.
  Now $p_0=q_0\cdots q_{t-1}$ and this is a nontrivial factorization of a prime
  unless $t=1$.

  For the inductive step assume that the factorization is unique for
  $s=1$, \ldots, $s=k$ and consider the $s=k+1$ case, with
  $n=p_0\cdots p_{s-1}\cdot p_s$.   
  Assume that there is another prime factorization $n=q_0\cdots q_{t-1}$
  for $t\geq 1$ and $q_0\leq\cdots \leq q_{t-1}$.

  We first show that $p_s$ equals some $q_i$.
  Because $p_s\divides n$ we have $p_s\divides q_0\cdots q_{t-1}$ and so
  by the above result~\ref{ex:EuclidsOtherLemma} shows that
  $p_s$ divides some $q_i$.
  Because $q_i$ is prime this shows that $p_s$ equals~$q_i$,
  since primes don't have any divisors other than~$1$ and themselves.

  To finish, cancel the primes.
  That is, consider 
  $n/p_s=p_0\cdots p_{s-1}=q_0\cdots q_{i-1}\cdot q_{i+1}\cdots q_{t-1}$.
  There remains at least one prime on the right (by the assumption that 
  $s=k+1$), so the inductive hypothesis applies. 
  Therefore
  the ascending sequence of $q$'s without~$q_i$ 
  equals the ascending sequence of $p$'s without~$p_s$,
  both in length and in members. 
  Obviously then the entire sequence of $q$'s equals the entire sequence of
  $p$'s, again in length and in individual members.   
\end{answer}
\end{exes}
% \begin{exes}
% \item Any number $n>1$ can be written as a product of one or more primes
% $n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$.
% \item That factorization is essentially unique:~if 
% $n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$ and the primes
% are in ascending order $p_1<p_2<\cdots<p_k$ then any other
% factorization of~$n$ into a product of primes in ascending order will give the
% same result. 
% \hint~suppose that there are two factorizations into primes $n=p_0\cdots p_{s-1}$
% and $n=q_0\cdots q_{t-1}$ in ascending order and use induction on~$s$.     
% \end{exes}
% \begin{ans}
% \begin{exes}
% \item We do induction.
% For the base step, observe that $n=2$ is the product of one prime. 
% For the inductive step assume that the statement holds when $n=2$, \ldots, 
% $n=k$ and consider~$n=k+1$.
% Every number greater than~$1$ factors $k+1=a\cdot b$ into two smaller
% numbers.
% Because these two are smaller
% the inductive hypothesis applies, so each is a product of 
% primes.
% Then $k+1=ab$ can be written as a product of primes.
% \item Assume that $n=p_0\cdots p_{s-1}$ with $s\geq 1$ and
% $p_0\leq\cdots \leq p_{s-1}$, 
% and also that $n=q_0\cdots q_{t-1}$ with $t\geq 1$ 
% and $q_0\leq\cdots \leq q_{t-1}$.
% We will show that $s=t$ and that $p_i=q_i$ for each $i$.

% We use induction on~$s$.
% The base step is~$s=1$ so that $n=p_0$ is prime.
% Now $p_0=q_0\cdots q_{t-1}$ and this is a nontrivial factorization of a prime
% unless $t=1$.

% For the inductive step assume that the factorization is unique for
% $s=1$, \ldots, $s=k$ and consider the $s=k+1$ case, with
% $n=p_0\cdots p_{s-1}\cdot p_s$.   
% Assume that there is another prime factorization $n=q_0\cdots q_{t-1}$
% for $t\geq 1$ and $q_0\leq\cdots \leq q_{t-1}$.

% We first show that $p_s$ equals some $q_i$.
% Because $p_s\divides n$ we have $p_s\divides q_0\cdots q_{t-1}$ and so
% by the above result~\ref{ex:EuclidsOtherLemma} shows that
% $p_s$ divides some $q_i$.
% Because $q_i$ is prime this shows that $p_s$ equals~$q_i$,
% since primes don't have any divisors other than~$1$ and themselves.

% To finish, cancel the primes.
% That is, consider 
% $n/p_s=p_0\cdots p_{s-1}=q_0\cdots q_{i-1}\cdot q_{i+1}\cdots q_{t-1}$.
% There remains at least one prime on the right (by the assumption that $s=k+1$),
% so the inductive hypothesis applies. 
% Therefore
% the ascending sequence of $q$'s without~$q_i$ 
% equals the ascending sequence of $p$'s without~$p_s$,
% both in length and in members. 
% Obviously then the entire sequence of $q$'s equals the entire sequence of
% $p$'s, again in length and in individual members. 
% \end{exes}
% \end{ans}\
\end{problem}

\noindent\remark had we included~$1$ among the primes then this theorem would
not
hold\Dash factorization would not be unique, 
since to any existing factorization we could add more $1$'s.

\begin{problem}[\midlength] 
True or false:
% From: http://gowers.wordpress.com/2011/11/13/why-isnt-the-fundamental-theorem-of-arithmetic-obvious/
\begin{items}
\item $5\cdot 7\cdot 19\neq 3\cdot 11\cdot 17$
\item $47\cdot 863\neq 73\cdot 557$
\item $1357\cdot 4183\neq 1081\cdot 5251$ % due to David Speyer
\end{items}
\begin{answer}
\begin{items}
\item All the numbers are prime, and they are different.
\item These numbers are prime, and different.
\item The two sides are equal (the numbers are non-prime).     
\end{items}
\end{answer}
\end{problem}

% \begin{ex}
% Give (and prove) a condition of the prime factorizations of $a$ and~$b$
% equivalent to their being relatively prime.
% \end{ex}

\begin{problem}[\maxlength]
Suppose that two numbers have prime factorizations 
of $a=p_0^{e_0}\cdots p_{n-1}^{e_{n-1}}$
and $b=p_0^{f_0}\cdots p_{n-1}^{f_{n-1}}$
(to use the same primes, we allow that some of the exponents are zero).
Prove each.
\begin{exes}
\begin{exercise}
  In the prime factorization of
  $\gcd(a,b)$ the exponent of $p_i$ is $\min(e_i,f_i)$.
\end{exercise}
\begin{answer}
  Let $d=\gcd(a,b)$.
  Note that if $p$ is a prime that divides~$a$ and~$b$ then
  by \ref{ex:EuclidsOtherLemma} above, $p$ must be one of the 
  $p_0$, \ldots, $p_{n-1}$.   
  So let the prime factorization of~$d$ be $p_0^{g_0}\cdots p_n^{g_n}$. 
  If $g_i=\min(e_i,f_i)$ for each~$i$ then $d$~divides both $a$ and~$b$.
  If $g_i>\min(e_i,f_i)$ then, supposing without loss of generality
  that the smaller of $e_i$ and~$f_i$ is $e_i$, writing
  $d\cdot k=a$ gives $p_0^{g_0}\cdots p_i^{g_i}\cdots p_{n-1}^{g_{n-1}}\cdot k$
  equal to $p_0^{e_0}\cdots p_i^{e_i}\cdots p_{n-1}^{e_{n-1}}$, and 
  canceling the most factors of~$p_i$ possible (that is, cancel-ling $p_i^{e_i}$)
  gives a contradiction because there is at least one factor
  of $p_i$ on one side but no such factor on the other.  
\end{answer}
\begin{exercise} 
  In the prime factorization of $\lcm(a,b)$ the exponent of 
  $p_i$ is $\max(e_i,f_i)$.
\end{exercise}
\begin{answer}
  This argument is just like the prior item's.    
\end{answer}
\end{exes}
% \begin{exes}
% \item
%   In the prime factorization of
%   $\gcd(a,b)$ the exponent of $p_i$ is $\min(e_i,f_i)$.
% \item In the prime factorization of $\lcm(a,b)$ the exponent of 
%   $p_i$ is $\max(e_i,f_i)$.
% \end{exes}
% \begin{ans}
% \begin{exes}
% \item Let $d=\gcd(a,b)$.
%   Note that if $p$ is a prime that divides~$a$ and~$b$ then
%   by \ref{ex:EuclidsOtherLemma} above, $p$ must be one of the 
%   $p_0$, \ldots, $p_{n-1}$.   
%   So let the prime factorization of~$d$ be $p_0^{g_0}\cdots p_n^{g_n}$. 
%   If $g_i=\min(e_i,f_i)$ for each~$i$ then $d$~divides both $a$ and~$b$.
%   If $g_i>\min(e_i,f_i)$ then, supposing without loss of generality
%   that the smaller of $e_i$ and~$f_i$ is $e_i$, writing
%   $d\cdot k=a$ gives $p_0^{g_0}\cdots p_i^{g_i}\cdots p_{n-1}^{g_{n-1}}\cdot k$
%   equal to $p_0^{e_0}\cdots p_i^{e_i}\cdots p_{n-1}^{e_{n-1}}$, and 
%   canceling the most factors of~$p_i$ possible (that is, cancel-ling $p_i^{e_i}$)
%   gives a contradiction because there is at least one factor
%   of $p_i$ on one side but no such factor on the other.
% \item  This argument is just like the prior item's.  
% \end{exes}
% \end{ans}
\end{problem}

\begin{problem}[\midlength] \notetext{Existence of Irrational Numbers}
\begin{exes}
\begin{exercise} 
  Prove that if a number is a square then in its prime factorization 
  each prime occurs an even number of times.
\end{exercise}
\begin{answer}
  The square of $n=p_0^{e_0}\cdots p_{s-1}^{e_{s-1}}$ is
  $n=p_0^{2e_0}\cdots p_{s-1}^{2e_{s-1}}$.  
\end{answer}
\begin{exercise} 
  Prove that $\sqrt{2}$ is irrational.
\end{exercise}
\begin{answer}
  Suppose that $\sqrt{2}=n/d$ for $n,d\in\Z$.
  Clearing the fraction and squaring gives $2\cdot n^2=d^2$.
  On the right, the prime factorization of~$d^2$ has $2$ raised to an even 
  power.
  On the left, the prime factorization of~$n^2$ has $2$ raised to an even power
  also, but there is another factor of~$2$ on the right.
  Thus the left has an odd number of factors of~$2$ while the right has
  and even number of factors of~$2$.
  This contradicts the uniqueness of factorizations, showing the 
  original supposition to be false.   
\end{answer}
% \begin{exercise} 
%   Prove that $\sqrt{17} is irrational.$ % College Math Journal Jan 2013 pp 53
% \end{exercise}
\end{exes}
% \begin{exes}
% \item Prove that if a number is a square then in its prime factorization 
%   each prime occurs an even number of times.
% \item Prove that $\sqrt{2}$ is irrational.
% % \item Prove that $\sqrt{17} is irrational.$ % College Math Journal Jan 2013 pp 53
% \end{exes}
% \begin{ans}
% \begin{exes}
% \item The square of $n=p_0^{e_0}\cdots p_{s-1}^{e_{s-1}}$ is
%   $n=p_0^{2e_0}\cdots p_{s-1}^{2e_{s-1}}$.
% \item Suppose that $\sqrt{2}=n/d$ for $n,d\in\Z$.
%   Clearing the fraction and squaring gives $2\cdot n^2=d^2$.
%   On the right, the prime factorization of~$d^2$ has $2$ raised to an even 
%   power.
%   On the left, the prime factorization of~$n^2$ has $2$ raised to an even power
%   also, but there is another factor of~$2$ on the right.
%   Thus the left has an odd number of factors of~$2$ while the right has
%   and even number of factors of~$2$.
%   This contradicts the uniqueness of factorizations, showing the 
%   original supposition to be false. 
% \end{exes}
% \end{ans}
\end{problem}










%===================================================
\chapter{Sets}
\begin{df}
A \definend{set} is a collection that is definite\Dash every 
object either
definitely is contained in the collection or definitely is not.
An object~$x$ that belongs to a set~$A$ is an \definend{element}
or \definend{member}
of the set, written $x\in A$
(to denote that $x$ is not an element of $A$ write~$x\notin A$).
Two sets are equal if and only if they have the same elements.
\end{df}
\noindent Read `$\in$' as ``is an element of'' rather than ``in'' to ease
confusion with 
the subset relation defined below.
We sometimes say ``collection'' as a synonym for set.

We usually specify a set either by listing or by
describing its elements.
Thus we may write 
the set of the primes less than ten either 
as $P=\set{2, 3, 5, 7}$ 
or as~$P=\setbuilder{p\in\N}{\text{$p$ is prime and $p<10$}}$ 
(read the vertical bar as ``such that'').

\begin{problem}[\midlength] 
Decide if each is true and justify your decision.
\begin{items}
\item $\set{1,3,5}=\set{5,3,1}$    
\item $\set{2, 4, 6}=\set{2, 4, 6, 4}$    
\item $\set{1, 3}=\set{n\in\N\suchthat n<5}$ 
\item $0\in\set{1,2,\set{0}}$   
\item $4\in\set{n\in\N\suchthat n^2<50}$
\end{items}
\begin{answer}
\begin{items}
\item These two sets are equal because they contain the same elements, 
  $1$, $3$, and~$5$.
\item These two sets are equal because they contain the same elements, 
  $2$, $4$, and~$6$.
\item These sets are not equal because the set on the left contains~$2$
  while the set on the right does not.
\item This is false because the set on the right has three elements, 
  and by inspection none of the three is the number~$0$;
  in particular, $\set{0}$ is not equal to~$0$.
\item This is true because $4^2$ is less than $50$.    
\end{items}
\end{answer}
\end{problem}

\begin{df}
The set~$B$ is a \definend{subset} of the set~$A$
if every element of $B$ is an element of~$A$,
that is, if $x\in B$ implies that~$x\in A$.
This is denoted $B\subseteq A$.
\end{df}

\begin{df}
The set without any elements is the \definend{empty set} $\emptyset$.  
\end{df}

\begin{problem} Decide each, with justification.
\begin{items}
\item $\set{1,3,5}\subseteq\set{1,3, 5, 7, 9}$
\item $\set{1, 3, 5}\in\set{1, 3, 5, 7, 9}$   
\item $\set{1,3,5}\subseteq\setbuilder{n\in\N}{\text{$n$ is prime}}$
\item $\emptyset\subseteq\set{1, 2, 3, 4}$
\item $\N\subseteq\Z$
\item $\set{2}\in\set{1, \set{2}, 3}$
\item $\set{2}\subseteq\set{1, \set{2}, 3}$
\end{items}
\begin{answer}
\begin{items}
\item This is true because, by inspection, each of the elements of the set
  on the left, $1$, $3$, and~$5$, is an element of the set on the right.
\item The set $\set{1,3,5}$ is not an element of the set on the right.
  All elements of the set on the right are numbers.
\item This is not true since~$1$ is an element of the set on the left
  but not of the set on the right.
\item This is true since $x\in\emptyset$ implies that $x\in\set{1, 2, 3, 4}$. 
  (The implication is vacuous.)
% \item This is true since every natural number is an integer.
\item This is true since $\set{2}$ is the second element listed as a
  member of the set on the right.
\item This is not true since $2$ is an element of the set on the left but
  not an element of the set on the right.
\end{items}
\end{answer}
\end{problem}

\begin{problem} \label{ex:EmptySetUnique}
Prove, for all sets $A$. 
\begin{exes}
\begin{exercise} 
  $A\subseteq A$ and $\emptyset\subseteq A$
\end{exercise}
\begin{answer}
  For the first, let $x$ be an element of the set on the left, $A$.
  Then $x$ is an element of the set on the right, $A$, obviously.
  For the second, observe that the implication 
  `if $x\in\emptyset$ then $x\in A$' is true 
  because any implication with a false first clause is true
  (that is, it is vacuously true).  
\end{answer}
\begin{exercise} 
  The empty set is unique: if $A$ is empty and $B$ is empty then $A=B$.
\end{exercise}
\begin{answer}
  If $A=\emptyset$ and~$B=\emptyset$ then $A=B$ because they have the
  same elements: the statement `$x\in A$ if and only if~$x\in B$' holds   
  for all $x$.  
\end{answer}
\end{exes}
% \begin{exes}
% \item $A\subseteq A$ and $\emptyset\subseteq A$
% \item The empty set is unique: if $A$ is empty and $B$ is empty then $A=B$.
% \end{exes}
% \begin{ans}
% \begin{exes}
% \item For the first, let $x$ be an element of the set on the left, $A$.
%   Then $x$ is an element of the set on the right, $A$, obviously.

%   For the second, observe that the implication 
%   `if $x\in\emptyset$ then $x\in A$' is true 
%   because any implication with a false first clause is true
%   (that is, it is vacuously true).
% \item If $A=\emptyset$ and~$B=\emptyset$ then $A=B$ because they have the
%   same elements: the statement `$x\in A$ if and only if~$x\in B$' holds   
%   for all $x$.
% \end{exes}
% \end{ans}
\end{problem}

\begin{problem}  \label{ex:PropertiesOfSubset}
Prove, for any sets $A$, $B$, and~$C$.
\begin{exes} 
\begin{exercise} \notetext{Mutual Inclusion}
  If $A\subseteq B$ and $B\subseteq A$ then $A=B$.
\end{exercise}  
\begin{answer}
   Since $A\subseteq B$, any element of~$A$ is also an element of~$B$.
   Since $B\subseteq A$, any element of~$B$ is also an element of~$A$.
   Thus they contain the same elements.  
\end{answer}
\begin{exercise} \notetext{Transitivity}
  If $A\subseteq B$ and~$B\subseteq C$ then~$A\subseteq C$.  
\end{exercise}
\begin{answer}
   Consider $x\in A$.
   Because $A\subseteq B$ we have that~$x\in B$ and with that, because
   $B\subseteq C$ we have that $x\in C$.
   So $x\in A$ implies that $x\in C$, and therefore~$A\subseteq C$.  
\end{answer}
\end{exes}
% \begin{exes} 
% \item \notetext{Mutual Inclusion}
%   If $A\subseteq B$ and $B\subseteq A$ then $A=B$.  
% \item \notetext{Transitivity}
%   If $A\subseteq B$ and~$B\subseteq C$ then~$A\subseteq C$.  
% \end{exes}
% \begin{ans}
% \begin{exes}
% \item Since $A\subseteq B$, any element of~$A$ is also an element of~$B$.
%    Since $B\subseteq A$, any element of~$B$ is also an element of~$A$.
%    Thus they contain the same elements.
% \item Consider $x\in A$.
%    Because $A\subseteq B$ we have that~$x\in B$ and with that, because
%    $B\subseteq C$ we have that $x\in C$.
%    So $x\in A$ implies that $x\in C$, and therefore~$A\subseteq C$.
% \end{exes}
% \end{ans}
\end{problem}

\begin{problem}[\maxlength] 
For each, give example sets or show that no example is possible.
\begin{items}
\item $A\subseteq B$, $B\not\subseteq C$, $A\subseteq C$
\item $A\not\subseteq B$, $B\not\subseteq C$, $A\subseteq C$
\item $A\not\subseteq B$ $B\subseteq C$, $A\subseteq C$    
\end{items}
\begin{ans}
\begin{items}
\item $A=\set{0}$, $B=\set{0,1,2}$, $C=\set{0,1}$
\item $A=\set{0}$, $B=\set{2}$, $C=\set{0,1}$
\item $A=\set{0}$, $B=\set{1}$, $C=\set{0,1}$
\end{items}
\end{ans}
\end{problem}

In this book we will always work inside of a \definend{universal set}, 
denoted $\universalset$.
For instance, in the first chapter on number theory  
the universal set is~$\universalset=\Z$.
There, if we say we are considering 
the set of things less than~$100$ then 
we are considering the set of integers less than~$100$.

\begin{df}
The \definend{characteristic function} of a set~$A$ is a map
$\charfcn{A}$ (whose domain is the universal set) such that
$\charfcn{A}(x)=1$ if~$x\in A$, and $\charfcn{A}(x)=0$ if~$x\notin A$.  
\end{df}

\begin{problem}[\maxlength] 
\notetext{Russell's Paradox}
The definition that we gave of sets allows them to contain anything, so 
consider a set that contains all sets.
It has itself as an element.
So
consider the set of all sets that have themselves as elements and  
also the set of all sets that don't.
Call the latter set~$D=\setbuilder{S}{S\notin S}$.
\begin{exes}
\begin{exercise} 
  Show that assuming $D$ is an element of itself leads to a contradiction.
\end{exercise}
\begin{answer}
  If~$D$ were to have itself as an element 
  then it wouldn't satisfy the condition
  $S\notin S$, so $D$ would not be in the collection 
  $\setbuilder{\text{set~$S$}}{S\notin S}$.
  That is, in this case $D\notin D$, a contradiction.   
\end{answer}
\begin{exercise} 
  Show that assuming $D$ is not an element of itself also leads to a
  contradiction.  
\end{exercise}
\begin{answer}
  If $D$ does not have itself for an element then it satisfies the
  condition $S\notin S$, so $D\in D$, a contradiction.  
\end{answer}
\end{exes}
% \begin{exes}
% \item Show that assuming $D$ is an element of itself leads to a contradiction.
% \item Show that assuming $D$ is not an element of itself also leads to a
% contradiction.  
% \end{exes}
% \begin{ans}
% Let $D$ be the set of all sets~$S$ that do not contain themselves
% $D=\setbuilder{S}{S\notin S}$.
% \begin{exes}
% \item If~$D$ were to have itself as an element 
%   then it wouldn't satisfy the condition
%   $S\notin S$, so $D$ would not be in the collection 
%   $\setbuilder{\text{set~$S$}}{S\notin S}$.
%   That is, in this case $D\notin D$, a contradiction. 
% \item If $D$ does not have itself for an element then it satisfies the
%   condition $S\notin S$, so $D\in D$, a contradiction.
% \end{exes}
% \end{ans}
\end{problem}






% .....................................
\section{Operations}

\begin{df}
Let $A$ be a set.
The \definend{complement} of $A$, denoted $\setcomp{A}$, is the 
set of objects that are not elements of~$A$.  
\end{df}

\noindent\remark
working inside of a universal set makes the complement
operation sensible. 
For instance, in a number theory discussion where $\universalset=\Z$, 
if $A$ is the set of objects greater than~$100$ then we can
take the complement of~$A$ and the result is another subset of 
$\universalset$, so 
we are still in number theory.

\begin{df}
Let $A$ and $B$ be sets.
Their \definend{union} is the set of elements 
from either set 
$A\union B=\setbuilder{x}{\text{$x\in A$ or $x\in B$}}$.  
Their \definend{intersection} is the set of elements 
from both sets
$A\intersection B=\setbuilder{x}{\text{$x\in A$ and $x\in B$}}$.  
\end{df}

Picture set operations with \definend{Venn diagrams}.
\begin{center}
  \grf{asy/venn_union.pdf}{$A\union B$}
  \hspace*{3em}
  \grf{asy/venn_int.pdf}{$A\intersection B$}
  \hspace*{3em}
  \grf{asy/venn_comp.pdf}{$\setcomp{A}$}
\end{center}
In each diagram
the region inside the rectangle depicts the universal set and the 
region inside each circle depicts the set.
On the left the part in mauve (light purple) shows 
the union as containing all of the two sets joined, 
the middle shows the intersection
containing only the region common to both,
and on the right the mauve region, the complement, is all but the set~$A$.

\begin{problem}
Another tool for illustrating set relationships is this table describing 
two sets.
\begin{center} \small
  \begin{tabular}{cc|c}
    $x\in A$  &$x\in B$  &row number \\ \hline
    $0$       &$0$       &$0$  \\
    $0$       &$1$       &$1$  \\
    $1$       &$0$       &$2$  \\
    $1$       &$1$       &$3$  
  \end{tabular}
\end{center}
Use the bits $0$ and~$1$ instead of $F$ and~$T$ so that each
row is the binary representation of its row number.
That table gives $A=\set{2,3}$, $B=\set{1,3}$, 
and~$\universalset=\set{0,1,2,3}$.
For each item below, illustrate the statements using these sets.
Then pick one item and prove it:
\begin{items}
\item the complement of the complement is the original set
  $\setcomp{(\setcomp{A})}=A$  
\item $A\intersection\emptyset=\emptyset$ and $A\union\emptyset=A$  
\item \notetext{Idempotence} $A\intersection A=A$ and $A\union A=A$    
\item $A\intersection B\subseteq A\subseteq A\union B$  
\item \notetext{Commutativity}
   $A\intersection B=B\intersection A$ and
   $A\union B=B\union A$ 
\item \notetext{Associativity} 
  $(A\intersection B)\intersection C=A\intersection (B\intersection C)$
  and
  $(A\union B)\union C=A\union (B\union C)$ 
\end{items}
\begin{answer}
\begin{items}
\item  The illustration is that the complement is 
  $\setcomp{A}=\set{0,1}$.
  Then the complement of the complement is~$\setcomp{\setcomp{A}}=\set{2,3}$.
  
  The proof 
  is by mutual inclusion, that both~$A\subseteq\setcomp{(\setcomp{A})}$
  and~$\setcomp{(\setcomp{A})}\subseteq A$.
  For the first inclusion suppose that $a\in A$.
  By the definition of complement $a\notin\setcomp{A}$.
  Thus $a\in\setcomp{(\setcomp{A})}$,
  and so $A\subseteq\setcomp{(\setcomp{A})}$.

  Inclusion in the other direction is similar.
  Suppose that $x\in\setcomp{(\setcomp{A})}$.
  Then $x\notin\setcomp{A}$.
  By definition of the complement then $x\in\setcomp{A}$.
  Thus $\setcomp{(\setcomp{A})}\subseteq A$. 
\item In the illustration $A=\set{2,3}$ so the collection of
  elements of~$\universalset$ that are members of either~$A$ or~$\emptyset$
  is~$\set{2,3}$.
  The other one is as trivial: all of the members of 
  $\universalset=\set{0,1,2,3}$ that are members of both~$A=\set{2,3}$
  and~$\emptyset=\set{}$ are members of~$\emptyset$.

  The proof of the first equality is: $x\in A\intersection\emptyset$
  iff $x\in A$ and~$x\in\emptyset$, 
  which, because an `and' statement holds if and only if both halves hold
  and here the second clause never holds,
  is equivalent to $x\in\emptyset$. 

  For the second equality, 
  $x\in A\union\emptyset$ iff $x\in A$ or~$x\in\emptyset$,
  which is equivalent to $x\in A$.
\item The illustration of the first is that the collection of members of both
  $\set{2,3}$ and~$\set{2,3}$ is the set~$A=\set{2,3}$.
  The second illustration, the intersection one, is the same.

  The first is true because
  $x\in A\intersection A$ if and only if
  both $x\in A$ and~$x\in A$, 
  which is true if and only if $x\in A$.
  The proof of the second is similar.
\item There are two containments to illustrate.
  The one on the left is that $A\intersection B=\set{3}\subseteq A=\set{2,3}$.
  On the right is~$A=\set{2,3}\subseteq A\union B=\set{1,2,3}$.

  To prove the first containment $A\intersection B\subseteq A$ observe that 
  $x\in A\intersection B$ implies that
  $x\in A$ and $x\in B$, so in particular $x\in A$.
  Thus $A\intersection B\subseteq A$.

  The second containment is just as straightforward:
  $x\in A$ implies that $x\in A$ or~$x\in B$, and so $A\subseteq A\union B$.
\item The illustration of the intersections is: $A\intersection B=\set{3}$
  while $B\intersection A=\set{3}$ also.
  The unions is: $A\union B=\set{1,2,3}$ while $B\union A=\set{1,2,3}$.

  For the proof, first we show that
  $A\intersection B=B\intersection A$.
  By the definition of intersection,  
  $A\intersection B=\setbuilder{x}{\text{$x\in A$ and $x\in B$}}
    =\setbuilder{x}{\text{$x\in B$ and $x\in A$}}=B\intersection A$.
  (The middle equality holds by the commutativity of `and'.)

  Equality for union is similar since, like `and', the logical connective
  `or' is also commutative.
\item For this three-set relationship we use this table.
  \begin{center} \small
    \begin{tabular}{ccc|c}
      $x\in A$  &$x\in B$  &$x\in C$  &row number \\ \hline
         $0$    &$0$       &$0$       &$0$    \\
         $0$    &$0$       &$1$       &$1$    \\
         $0$    &$1$       &$0$       &$2$    \\
         $0$    &$1$       &$1$       &$3$    \\[.5ex]
         $1$    &$0$       &$0$       &$4$    \\
         $1$    &$0$       &$1$       &$5$    \\
         $1$    &$1$       &$0$       &$6$    \\
         $1$    &$1$       &$1$       &$7$    
    \end{tabular}
  \end{center}
  For intersection, $A\intersection B=\set{6,7}$ and so
  $(A\intersection B)\intersection C=\set{7}$ while
  $B\intersection C=\set{3,7}$ so $A\intersection(B\intersection C)=\set{7}$.
  Union is similar.

  The proof of each is a consequence of the observation that the 
  logical connective used in the definition is associative.
  For intersection,
  $(A\intersection B)\intersection C=
    \setbuilder{x}{\text{$x\in A\intersection B$ and $x\in C$}}
    =
    \setbuilder{x}{\text{($x\in A$ and $x\in B$) and $x\in C$}}
    =
    \setbuilder{x}{\text{$x\in A$ and ($x\in B$ and $x\in C$)}}
   =
    \setbuilder{x}{\text{$x\in A$ and $x\in B\intersection C$}}
   =
   A\intersection (B\intersection C)$
   (the second equality holds because `and' is associative).
   Union is similar.
\end{items}
\end{answer}
\end{problem}

% \begin{problem}
% Give a formula relating $\charfcn{A}$ and $\charfcn{B}$ to
%   $\charfcn{A\intersection B}$.
% Do the same for union, and for complementation.
% \begin{answer}
%   The formula relating $\charfcn{A}$ and $\charfcn{B}$ to
%   $\charfcn{A\intersection B}$ is 
%   $\charfcn{A\intersection B}=\charfcn{A}\cdot\charfcn{B}$.
%   To verify this formula there are two cases: $x\in A\intersection B$ 
%   and~$x\notin A\intersection B$.
%   If $x\in A\intersection B$ then $x\in A$ and $x\in B$, so 
%   $\charfcn{A}(x)=\charfcn{B}(x)=1$ and the product is correct.
%   If $x\notin A\intersection B$ then either $x\notin A$ or~$x\notin B$,
%   so at least one of $\charfcn{A}(x)$ or~$\charfcn{B}(x)$ is zero, 
%   and here also the product is correct.

%   For the union the formula is    
%   $\charfcn{A\union B}=\charfcn{A}+\charfcn{B}-\charfcn{A\intersection B}$.
%   To verify the formula we can check four cases:
%   (i)~$x\in A$ and~$x\notin B$, 
%   (ii)~$x\notin A$ and~$x\in B$, 
%   (iii)~$x\in A\intersection B$, 
%   and (iv)~$x\notin A$ and~$x\notin B$.
%   Verification of the formula in these cases is as in the prior paragraph.

%   The complement formula is    
%   $\charfcn{\setcomp{A}}=1-\charfcn{A}$.
%   There are two cases to verify: 
%   $x\in A$ and~$x\notin A$.
%   These cases are straightforward.
% \end{answer}
% \end{problem}

\begin{problem}[\maxlength] 
Prove that the following are equivalent:
(i)~$A\subseteq B$,
(ii)~$A\union B=B$,    
and (iii)~$A\intersection B=A$.
\begin{answer}
One way to prove this is to 
show that (i) holds iff (ii)~holds, and also show that (i) holds iff~(iii) 
holds.
The second is very like the first so here we only show the first.

The first equivalence has two directions.
For the first direction assume that $A\subseteq B$. 
To check that $A\union B=B$ we need to check mutual inclusion.
One of those inclusions, that $B\subseteq A\union B$, holds by the definition 
of union so we only need  $A\union B\subseteq B$.
Let $x$~be an element of $A\union B$.
There are two cases, that $x\in A$ or that $x\in B$, and in both cases
we must verify that $x\in B$.
The $x\in B$ verification is trivial and the other is 
immediate from the $A\subseteq B$ assumption.

To get the first equivalence's other direction assume that $A\union B=B$.
With this, for any $x\in A$ we have that $x\in A\union B$ and so $x\in B$.
Thus $x\in A$ implies $x\in B$, which is the definition of $A\subseteq B$.
\end{answer}
\end{problem}

\begin{df}
The \definend{difference} of two sets is $A-B=\setbuilder{x\in A}{x\notin B}$.  
The \definend{symmetric difference} is 
$A\symdiff B=(A-B)\union(B-A)$.
\end{df}

\noindent If $A\subseteq X$ then $X-A$ is the same as $\setcomp{A}$
where $X$ is the universal set $\universalset=X$.     

% \begin{problem}
% Draw the Venn diagram for difference and symmetric difference.  
% \begin{answer}
% These are the Venn diagrams for difference and symmetric difference.
% \begin{center}
%   \grf{asy/venn_diff.pdf}{$A- B$}
%   \hspace*{3em}
%   \grf{asy/venn_symdiff.pdf}{$A\symdiff B$}
% \end{center}  
% \end{answer}
% \end{problem}

\begin{problem} \pord.
\begin{exes}
\begin{exercise} 
  $A-B\subseteq A$
\end{exercise}
\begin{answer}
  This is true.
  If $x\in A-B$
  then by the definition of set difference $x\in A$ (but $x\notin B$).
  This implication is the requirement for $A\subseteq B$.  
\end{answer}
\begin{exercise}[\midlength] 
  $A-B=A\intersection\setcomp{B}$
\end{exercise}
\begin{answer}
  We will show the sets are equal by mutual inclusion.
  For the left-to-right inclusion $A-B\subseteq A\intersection \setcomp{B}$
  suppose that $x\in A-B$.
  Then by the definition of set difference both $x\in A$ and $x\notin B$ hold.
  Therefore $x$ is an element of the intersection 
  $x\in A\intersection\setcomp{B}$.
  
  For the $A\intersection\setcomp{B}\subseteq A-B$ inclusion suppose that
  $x\in A\intersection\setcomp{B}$.
  Then $x\in A$ and $x\in\setcomp{B}$, so $x\notin B$.
  By the definition of set difference then, $x\in A-B$.  
\end{answer}
\begin{exercise}[\midlength] 
  For all pairs of sets, $A-B=B-A$.
\end{exercise}
\begin{answer}
  This is false.
  One example is $A=\set{0,1}$ and~$B=\set{1,2}$.
  Then $A-B=\set{0}$ while~$B-A=\set{2}$.  
\end{answer}
\begin{exercise} 
  For all pairs of sets, $A\symdiff B=B\symdiff A$.
\end{exercise}
\begin{answer}
  We will prove that the two are equal.
  One way is that 
  $A\symdiff B=\setbuilder{x}{\text{$x\in A-B$ and $x\in B-A$}}
              =\setbuilder{x}{\text{$x\in B-A$ and $x\in A-B$}}
              =B\symdiff A$.  
\end{answer}
\end{exes}
% \begin{exes}
% \item $A-B\subseteq A$
% \item $A-B=A\intersection\setcomp{B}$
% \item For all pairs of sets, $A-B=B-A$.
% \item For all pairs of sets, $A\symdiff B=B\symdiff A$.
% \end{exes}
% \begin{ans}
% \begin{exes}
% \item  This is true.
%   If $x\in A-B$
%   then by the definition of set difference $x\in A$ (but $x\notin B$).
%   This implication is the requirement for $A\subseteq B$.
% \item We will show the sets are equal by mutual inclusion.

%   For the left-to-right inclusion $A-B\subseteq A\intersection \setcomp{B}$
%   suppose that $x\in A-B$.
%   Then by the definition of set difference both $x\in A$ and $x\notin B$ hold.
%   Therefore $x$ is an element of the intersection 
%   $x\in A\intersection\setcomp{B}$.
  
%   For the $A\intersection\setcomp{B}\subseteq A-B$ inclusion suppose that
%   $x\in A\intersection\setcomp{B}$.
%   Then $x\in A$ and $x\in\setcomp{B}$, so $x\notin B$.
%   By the definition of set difference then, $x\in A-B$.
% \item This is false.
%   One example is $A=\set{0,1}$ and~$B=\set{1,2}$.
%   Then $A-B=\set{0}$ while~$B-A=\set{2}$.
% \item We will prove that the two are equal.
%   One way is that 
%   $A\symdiff B=\setbuilder{x}{\text{$x\in A-B$ and $x\in B-A$}}
%               =\setbuilder{x}{\text{$x\in B-A$ and $x\in A-B$}}
%               =B\symdiff A$.
% \end{exes}
% \end{ans}
\end{problem}

\begin{problem}
\notetext{De Morgan's Laws}  Prove.
\begin{exes}
\begin{exercise} 
  $\setcomp{(A\intersection B)}=\setcomp{A}\union\setcomp{B}$
  and
  $\setcomp{(A\union B)}=\setcomp{A}\intersection\setcomp{B}$ 
\end{exercise}
\begin{answer}
  \remark: these two are a consequence of the fact that logical negation
  satisfies that `not($P$ and $Q$)' has the same truth value as
  `not($P$) or not($Q$)'.

  We show  $\setcomp{(A\intersection B)}=\setcomp{A}\union\setcomp{B}$
  by mutual containment.
  Suppose first that $x\in \setcomp{(A\intersection B)}$ so that
  $x\notin A\intersection B$.
  Then $x\notin A$ or $x\notin B$.
  and so $x\in \setcomp{A}\union\setcomp{B}$.
  Thus $\setcomp{(A\intersection B)}\subseteq\setcomp{A}\union\setcomp{B}$.

  Suppose now that $x\in \setcomp{A}\union\setcomp{B}$.
  Then $x\in\setcomp{A}$ or~$x\in\setcomp{B}$.
  Restated, that is $x\notin A$ or $x\notin B$,
  which gives that $x\notin (A\intersection B)$ and
  so $x\in\setcomp{(A\intersection B)}$.
  Thus $\setcomp{A}\union\setcomp{B}\subseteq\setcomp{(A\intersection B)}$.
  
  The other identity is similar.  
\end{answer}
\begin{exercise} \notetext{Distributivity} 
  $A\union (B\intersection C)=(A\union B)\intersection (A\union C)$
  and 
  $A\intersection (B\union C)=(A\intersection B)\union (A\intersection C)$
\end{exercise}
\begin{answer}
  For $A\union (B\intersection C)=(A\union B)\intersection (A\union C)$
  first suppose that $x\in A\union (B\intersection C)$.
  Then $x\in A$ or $x\in B\intersection C$.
  In the case that $x\in A$ we have both that $x\in A\union B$ and that
  $x\in A\union C$.
  In the case that $x\in B\intersection C$, so $x\in B$ and~$x\in C$, 
  we have both that $x\in A\union B$ and that~$x\in A\union C$.
  Since in either case $x\in (A\union B)\intersection (A\union C)$,
  we know that 
  $A\union (B\intersection C)\subseteq (A\union B)\intersection (A\union C)$.

  Now suppose that $x\in (A\union B)\intersection (A\union C)$.
  Then $x\in A\union B$ and also $x\in A\union C$.
  There are two cases: either~$x\in A$ or $x\notin A$.
  If $x\in A$ then $x\in A\union (B\intersection C)$.
  If $x\notin A$ then because $x\in A\union B$ we know that $x\in B$
  and because $x\in A\union C$ we know that $x\in C$.
  So in this case also $x\in A\union (B\intersection C)$.
  Thus 
  $(A\union B)\intersection (A\union C)\subseteq A\union (B\intersection C)$.

  Therefore, by mutual containment, the two sets are equal.
  The other identity is similar.  
\end{answer}
\end{exes}
% \begin{exes}
% \item 
%   $\setcomp{(A\intersection B)}=\setcomp{A}\union\setcomp{B}$
%   and
%   $\setcomp{(A\union B)}=\setcomp{A}\intersection\setcomp{B}$ 
% \item \notetext{Distributivity} 
% $A\union (B\intersection C)=(A\union B)\intersection (A\union C)$
%  and $A\intersection (B\union C)=(A\intersection B)\union (A\intersection C)$
% \end{exes}
% \begin{ans}
% \begin{exes}
% \item (These two are a consequence of the fact that logical negation
%   satisfies that `not($P$ and $Q$)' has the same truth value as
%   `not($P$) or not($Q$)'.)

%   We show  $\setcomp{(A\intersection B)}=\setcomp{A}\union\setcomp{B}$
%   by mutual containment.
%   Suppose first that $x\in \setcomp{(A\intersection B)}$ so that
%   $x\notin A\intersection B$.
%   Then $x\notin A$ or $x\notin B$.
%   and so $x\in \setcomp{A}\union\setcomp{B}$.
%   Thus $\setcomp{(A\intersection B)}\subseteq\setcomp{A}\union\setcomp{B}$.

%   Suppose now that $x\in \setcomp{A}\union\setcomp{B}$.
%   Then $x\in\setcomp{A}$ or~$x\in\setcomp{B}$.
%   Restated, that is $x\notin A$ or $x\notin B$,
%   which gives that $x\notin (A\intersection B)$ and
%   so $x\in\setcomp{(A\intersection B)}$.
%   Thus $\setcomp{A}\union\setcomp{B}\subseteq\setcomp{(A\intersection B)}$.
  
%   The other identity is similar.
% \item For $A\union (B\intersection C)=(A\union B)\intersection (A\union C)$
%   first suppose that $x\in A\union (B\intersection C)$.
%   Then $x\in A$ or $x\in B\intersection C$.
%   In the case that $x\in A$ we have both that $x\in A\union B$ and that
%   $x\in A\union C$.
%   In the case that $x\in B\intersection C$, so $x\in B$ and~$x\in C$, 
%   we have both that $x\in A\union B$ and that~$x\in A\union C$.
%   Since in either case $x\in (A\union B)\intersection (A\union C)$,
%   we know that 
%   $A\union (B\intersection C)\subseteq (A\union B)\intersection (A\union C)$.

%   Now suppose that $x\in (A\union B)\intersection (A\union C)$.
%   Then $x\in A\union B$ and also $x\in A\union C$.
%   There are two cases: either~$x\in A$ or $x\notin A$.
%   If $x\in A$ then $x\in A\union (B\intersection C)$.
%   If $x\notin A$ then because $x\in A\union B$ we know that $x\in B$
%   and because $x\in A\union C$ we know that $x\in C$.
%   So in this case also $x\in A\union (B\intersection C)$.
%   Thus 
%   $(A\union B)\intersection (A\union C)\subseteq A\union (B\intersection C)$.

%   Therefore, by mutual containment, the two sets are equal.
%   The other identity is similar.
% \end{exes}
% \end{ans}
\end{problem}

\begin{df}
Two sets are \definend{disjoint} if their intersection is empty.  
\end{df}

\begin{problem}[\midlength]
 \pord: $A\intersection B$ and $A\symdiff B$ are disjoint.
\begin{answer}
  The statement is true.
  By definition $A\symdiff B=\setbuilder{x}{\text{$x\in A-B$ or $x\in B-A$}}$.
  In the $x\in A-B$ case, $x\notin B$ and so $x\notin A\intersection B$.
  The $x\in B-A$ case is similar.
  Thus $(A\symdiff B)\intersection (A\intersection B)$ has no elements.  
\end{answer}
\end{problem}

\begin{problem}
  Find three sets $A$, $B$, and $C$, such that 
  $A\intersection B\intersection C$ is empty but the sets are
  not pairwise disjoint, that is, none of $A\intersection B$, 
  $A\intersection C$, or $B\intersection C$ is empty. 
\begin{answer}
  One example is $A=\set{5,6}$, $B=\set{3,6}$, and 
  $C=\set{3,5}$.
  \remark
  to get this example we used the three-set table.
  \begin{center} \small
    \begin{tabular}{ccc|c}
      $x\in A$  &$x\in B$  &$x\in C$  &row number \\ \hline
         $0$    &$0$       &$0$       &$0$    \\
         $0$    &$0$       &$1$       &$1$    \\
         $0$    &$1$       &$0$       &$2$    \\
         $0$    &$1$       &$1$       &$3$    \\[.5ex]
         $1$    &$0$       &$0$       &$4$    \\
         $1$    &$0$       &$1$       &$5$    \\
         $1$    &$1$       &$0$       &$6$    \\
         $1$    &$1$       &$1$       &$7$    
    \end{tabular}
  \end{center}
  Think of it as listing eight regions that could either be occupied or not.
  We want a number to fall in $A\intersection C$ so put
  $5$ into~$A$ and~$C$ (so the ``$A$ overlap~$C$'' region is occupied).
  We want a number in $A\intersection B$ so put~$6$ into each.
  We want a number in $B\intersection C$ so put~$3$ into each.  
\end{answer}
\end{problem}
% \begin{exes}
% \item \pord: $A\intersection B$ and $A\symdiff B$ are disjoint.  
% \item Find three sets $A$, $B$, and $C$, such that 
% $A\intersection B\intersection C$ is empty but the sets are
% not pairwise disjoint, that is, none of $A\intersection B$, 
% $A\intersection C$, or $B\intersection C$ is empty. 
% \end{exes}
% \begin{ans}
% \begin{exes}
% \item The statement is true.
%   By definition $A\symdiff B=\setbuilder{x}{\text{$x\in A-B$ or $x\in B-A$}}$.
%   In the $x\in A-B$ case, $x\notin B$ and so $x\notin A\intersection B$.
%   The $x\in B-A$ case is similar.
%   Thus $(A\symdiff B)\intersection (A\intersection B)$ has no elements.
% \item One example is $A=\set{5,6}$, $B=\set{3,6}$, and 
%   $C=\set{3,5}$.
%   \remark
%   to get this example we used the three-set table.
%   \begin{center} \small
%     \begin{tabular}{ccc|c}
%       $x\in A$  &$x\in B$  &$x\in C$  &row number \\ \hline
%          $0$    &$0$       &$0$       &$0$    \\
%          $0$    &$0$       &$1$       &$1$    \\
%          $0$    &$1$       &$0$       &$2$    \\
%          $0$    &$1$       &$1$       &$3$    \\[.5ex]
%          $1$    &$0$       &$0$       &$4$    \\
%          $1$    &$0$       &$1$       &$5$    \\
%          $1$    &$1$       &$0$       &$6$    \\
%          $1$    &$1$       &$1$       &$7$    
%     \end{tabular}
%   \end{center}
%   Think of it as listing eight regions that could either be occupied or not.
%   We want a number to fall in $A\intersection C$ so put
%   $5$ into~$A$ and~$C$ (so the ``$A$ overlap~$C$'' region is occupied).
%   We want a number in $A\intersection B$ so put~$6$ into each.
%   We want a number in $B\intersection C$ so put~$3$ into each.
% \end{exes}
% \end{ans}

\begin{df}
For a finite set~$A$, the \definend{order} $|A|$ is the number of elements.
\end{df}

% \begin{problem}
%   For finite sets, if $A\subseteq B$ then $|A|\leq |B|$
% \end{problem}

\begin{df}
For a set~$A$ the \definend{power set} $\powerset(A)$ is the set of all
subsets of~$A$.
\end{df}

\begin{problem}[\midlength] 
  List 
  $\powerset(\set{a,b})$,   
  $\powerset(\set{a,b,c})$,   
  $\powerset(\set{a})$, and   
  $\powerset(\emptyset)$.
  Find the order of each.   
\begin{answer}
The power set
$\powerset(\set{a,b})=\set{\emptyset, \set{a}, \set{b}, \set{a,b}}$
of the two-element set has four elements.
The power set 
$\powerset(\set{a,b,c})=\set{\emptyset,\set{a},\set{b},\set{c},
                             \set{a,b},\set{b,c},\set{a,c},\set{a,b,c}}$
of the three-element set has eight elements.
The power set of the singleton $\set{a}$ has two elements
$\powerset(\set{a})=\set{\emptyset,\set{a}}$.
The power set of the empty set has one element
$\powerset(\emptyset)=\set{\emptyset}$.   
\end{answer}
\end{problem}

\begin{problem}  
Let $A=\set{\emptyset,\set{\emptyset}}$.
Decide, with justification, whether each is true or false.
\begin{exes}
\begin{exercise} 
  $\emptyset\in\powerset(A)$, 
  $\emptyset\subseteq\powerset(A)$    
\end{exercise}
\begin{answer}
The power set of a two-element set $\set{a,b}$ is 
$\powerset(\set{a,b})=\set{\emptyset,\set{a},\set{b},\set{a,b}}$.
Taking $\emptyset$ for~$a$ and $\set{\emptyset}$ for~$b$ we have
$\powerset(S)=\set{\emptyset, \set{\emptyset}, \set{\set{\emptyset}}, 
                   \set{\emptyset, \set{\emptyset}}}$.

  So, the first clause is true by inspection; 
  the empty set is the first element
  of $\powerset(A)$ listed.
  The second is true by the earlier result~\ref{ex:EmptySetUnique}
  that the empty set is a subset of all sets.
\end{answer}
\begin{exercise} 
  $\set{\emptyset}\in\powerset(A)$, 
  $\set{\emptyset}\subseteq\powerset(A)$    
\end{exercise}
\begin{answer}
  Again the first is true by inspection, 
  since one of the elements of $\powerset(A)$ is 
  $\set{\emptyset}$.  (It is listed second.)

  The second is true.
  To verify that one set is a subset of another we can check that for all
  elements~$x$ of that one, $x$ is also an element of the other.
  In this case the subset~$\set{\emptyset}$ has only one element to check,
  and the first item above checks that it is an element of~$\powerset(A)$.
\end{answer}
\begin{exercise} 
  $\set{\set{\emptyset}}\in\powerset(A)$,    
  $\set{\set{\emptyset}}\subseteq\powerset(A)$    
\end{exercise}
\begin{answer}
  The first is true by inspection, since it is the element that is listed
  third.
  To verify the second,
  that $\set{\set{\emptyset}}$ is a subset of~$\powerset(A)$
  we can check that each of its elements are elements of the power set.
  It has only one element, namely~$\set{\emptyset}$.
  That is indeed one of the elements of~$\powerset(A)$, as checked in 
  an item above.   
\end{answer}
\end{exes}
% \begin{exes}
% \item $\emptyset\in\powerset(A)$, 
%   $\emptyset\subseteq\powerset(A)$    
% \item $\set{\emptyset}\in\powerset(A)$, 
%   $\set{\emptyset}\subseteq\powerset(A)$    
% \item $\set{\set{\emptyset}}\in\powerset(A)$,    
%   $\set{\set{\emptyset}}\subseteq\powerset(A)$    
% \end{exes}
% \begin{ans}
% The power set of a two-element set $\set{a,b}$ is 
% $\powerset(\set{a,b})=\set{\emptyset,\set{a},\set{b},\set{a,b}}$.
% Taking $\emptyset$ for~$a$ and $\set{\emptyset}$ for~$b$ we have
% $\powerset(S)=\set{\emptyset, \set{\emptyset}, \set{\set{\emptyset}}, 
%                    \set{\emptyset, \set{\emptyset}}}$.
% \begin{exes}
% \item The first is true by inspection, the empty set is the first element
%   of $\powerset(A)$ listed.

%   The second is true by the earlier result~\ref{ex:EmptySetUnique}
%   that the empty set is a subset of all sets.
% \item Again the first is true by inspection, 
%   since one of the elements of $\powerset(A)$ is 
%   $\set{\emptyset}$.  (It is listed second.)

%   The second is true.
%   To verify that one set is a subset of another we can check that for all
%   elements~$x$ of that one, $x$ is also an element of the other.
%   In this case the subset~$\set{\emptyset}$ has only one element to check,
%   and the first item above checks that it is an element of~$\powerset(A)$.
% \item The first is true by inspection, since it is the element that is listed
%   third.

%   To verify the second,
%   that $\set{\set{\emptyset}}$ is a subset of~$\powerset(A)$
%   we can check that each of its elements are elements of the power set.
%   It has only one element, namely~$\set{\emptyset}$.
%   That is indeed one of the elements of~$\powerset(A)$, as checked in 
%   an item above. 
% \end{exes}
% \end{ans}
\end{problem}

\begin{problem} \pord:
if $A\subseteq B$ then $\powerset(A)\subseteq\powerset(B)$.  
% \item $\powerset(A)=\powerset(B)$ iff $A=B$  
\begin{answer}
This is true.
Let $A\subseteq B$ and consider $x\in\powerset(A)$.
Then~$x$ is a subset of~$A$.
Any subset of~$A$ is a subset of~$B$ by 
the Transitivity property of~\ref{ex:PropertiesOfSubset},
so $x$ is a subset of~$B$.
Therefore $\powerset(A)\subseteq\powerset(B)$.
\end{answer}
\end{problem}

\begin{problem}
Where~$A$ is a finite set, prove that $|\powerset(A)|=2^{|A|}$.    
\begin{answer}
We prove this by induction on the number of elements in~$A$.
The base step is that~$A$ has zero-many elements.
The power set of the empty set has
one element $\powerset(\emptyset)=\set{\emptyset}$ and
since $2^0=1$, the statement is true in this case. 

For the inductive step suppose that the statement is true for the 
$n=0$, \ldots, $n=k$ cases and consider a set
with $k+1$~elements
$A=\set{a_0, \ldots, a_{k-1},a_k}$.
For each element~$S\in\powerset(A)$, that is, each subset~$S\subseteq A$,
either $a_k\in S$ or $a_k\notin S$.
The number of subsets in the first category is $2^{k-1}$ by the inductive
hypothesis.
Showing that 
the second category also contains~$2^{k-1}$-many elements will finish the proof
because then
the total of the two categories is 
$2^{k-1}+2^{k-1}=2\cdot(2^{k-1})=2^k$.

We will show that the collection of subsets containing~$a_k$
has the same number of elements as the collection of subsets that do not
contain~$a_k$
(as noted in the prior paragraph, the inductive hypothesis gives that
the second collection has $2^{k-1}$-many elements).
To prove that, with every subset~$S$ of $A$ that contains~$a_k$ we associate
a subset $\hat{S}$ that does not contain~$a_k$,
namely $\hat{S}=S-\set{a_k}$.
Clearly for each such~$S$ there is one and only one such~$\hat{S}$.
So, the two collections\Dash the set of subsets of $A$ containing~$a_k$
and the set of subsets of~$A$ that do not contain~$a_k$\Dash match
up element-by-element, and therefore have the same number of elements.
\end{answer}
\end{problem}





% .....................................
\section{Cartesian product}

\begin{df}
The \definend{sequence\/} $\seq{x_0, x_1, \ldots, x_{n-1}}$
formed from the \definend{terms} 
(or \definend{elements}) $x_0$, $x_1$, \ldots, $x_{n-1}$ 
is an ordered list of objects.
The \definend{length} of a sequence $\lh(\seq{x_0, x_1, \ldots, x_{n-1}})$
is the number of terms~$n$.
Two sequences $\seq{x_0, x_1, \ldots, x_{n-1}}$ and
$\seq{y_0, y_1, \ldots, y_{m-1}}$ are equal if and only if
they have the same length and
the same terms, in the same order:
$n=m$ and
$x_0=y_0$, $x_1=y_1$, \ldots, $x_{n-1}=y_{n-1}$. 
\end{df}

\begin{problem}\pord:
\begin{items}
\item $\set{3, 4, 4, 5}=\set{4, 3, 5}$
\item $\sequence{3, 4, 5}=\sequence{4, 3, 5}$
\item $\sequence{3, 4, 4, 5}=\sequence{3,4,5}$  
\end{items}
\begin{answer}
\begin{items}
\item These two are sets that contain the same elements, $3$, $4$, and~$5$,
  and so are equal.
\item These sequences are not equal because they differ in the first term.
\item These sequences are not equal because they have different lengths.
  (In addition, they differ in their third terms.)
\end{items}
\end{answer}
\end{problem}

\begin{df}
For sets $A_0$, $A_1$, \ldots, $A_{n-1}$
the \definend{Cartesian product} 
is the set of all length~$n$ sequences
$A_0\times A_1\times \cdots \times A_{n-1}
  =\setbuilder{\sequence{a_0,a_1,\ldots,a_{n-1}}}{\text{$a_0\in A_0$, \ldots, and~$a_{n-1}\in A_{n-1}$}}$.
If the sets are the same we write $A\times\cdots\times A$ 
as~$A^n$.
\end{df}

A sequence of length two is often called an \definend{ordered pair} and 
written with parentheses $(x_0,x_1)$
(similarly we have ordered triples, four-tuples, etc.).
Thus, we write 
Cartesian coordinates of points in the plane as members of
$\R^2=\setbuilder{(x,y)}{x,y\in\R}$.

\begin{problem}
Prove that $\N^2\subseteq \Z^2$.
Generalize. 
\begin{answer}
Any element of $\N^2$ is a sequence of length two $\sequence{a,b}$ where
$a,b\in\N$.
Since $\N\subseteq\Z$, that is a sequence of length two of elements of~$\Z$, 
and so is an element of~$\Z^2$.

The generalization is that $A\subseteq B$ implies that~$A^n=B^n$ for all 
$n\in\N$.
The argument is straightforward, just as in the prior paragraph,
except for the~$n=0$ case.
A length zero sequence~$\sequence{}$ is empty and so any two 
length zero sequences are equal (they have the same length and do not 
differ on any of their terms).
Thus $A^0=B^0=\set{\sequence{}}$.
\end{answer}
\end{problem}

\begin{problem} \notetext{Algebra of Cartesian Product}
\begin{exes}
\begin{exercise} 
  Prove that $A\times B=\emptyset$ iff $A=\emptyset$ or~$B=\emptyset$.
\end{exercise}
\begin{answer}
  If $A=\emptyset$ then $A\times B=\emptyset$ because there are no 
  sequences with a first term drawn from $\emptyset$.
  For the same reason, $A\times\emptyset=\emptyset$.
 
  If neither set is empty then there exist some $a\in A$ and~$b\in B$, so 
  $(a,b)\in A\times B$, and $A\times B$ is not empty.  
\end{answer}
\begin{exercise} 
  Show that there are sets so that $A\times B\neq B\times A$.
  Under what circumstances is $A\times B=B\times A$?
\end{exercise}
\begin{answer}
  The two sets $A\times B$ and~$B\times A$ are not equal. 
  For instance, if $A=\set{0}$ and~$B=\set{1}$ then 
  $A\times B=\set{\sequence{0,1}}$
  while
  $B\times A=\set{\sequence{1,0}}$.

  If $A\times B$ and $B\times A$ are the same set then either that set is empty 
  and so either $A$ is empty or $B$ is empty,
  or it is not.
  If it is not empty then for each of its elements $\sequence{x,y}$,
  we have both that $x\in A$ and that $x\in B$ (and similarly for~$y$).
  Clearly in this case $A=B$.  
\end{answer}
\begin{exercise} 
  Is $(A\times B)\times C$ equal to $A\times (B\times C)$?
\end{exercise}
\begin{answer}
  The two sets $(A\times B)\times C$ and~$A\times (B\times C)$ 
  are not equal.
  For instance, if $A=\set{a}$, $B=\set{b}$, and $C=\set{c}$ then 
  $(A\times B)\times C=\set{\sequence{\sequence{a,b},c}}$
  has a single element, a sequence with two terms, the first
  of which is a sequence.
  But while $A\times(B\times C)=\set{\sequence{a,\sequence{b,c}}}$ 
  also has a single element that is a sequence with two terms, 
  the first element here is not a sequence. 

  \remark they are equal only if one of them is empty.  
\end{answer}
\begin{exercise} 
  Show that this statement is false: 
  $A\times B\subseteq A^\prime\times B^\prime$ if and only if
  $A\subseteq A^\prime$ and $B\subseteq B^\prime$.
  Patch the statement to make it true.
\end{exercise}
\begin{answer}
  The example 
  $A=\emptyset$, $B=\set{1,2}$, $A^\prime=\set{a}$, $B^\prime=\set{1}$
  shows that the statement is false since 
  $A\times B=\emptyset\subseteq A^\prime\times B^\prime$ but 
  $B\not\subseteq B^\prime$.

  The adjusted statement is: for all nonempty sets,  
  $A\times B\subseteq A^\prime\times B^\prime$ if and only if
  $A\subseteq A^\prime$ and $B\subseteq B^\prime$.
  We will prove the `if' and `only if' clauses separately.

  For `only if' suppose that $A\subseteq A^\prime$ and~$B\subseteq B^\prime$.
  Then any element of~$A\times B$ is a pair $\sequence{a,b}$. 
  Because of the subset relationship, $a\in A^\prime$ and~$b\in B^\prime$
  and so $\sequence{a,b}\in A^\prime\times B^\prime$.
  Thus $A\times B\subseteq A^\prime\times B^\prime$.

  Now assume that $A\not\subseteq A^\prime$ (the case 
  of $B\not\subseteq B^\prime$ is similar) and that $a\in A$ 
  but~$a\notin A^\prime$.
  Because $B$ is not empty there is a~$b\in B$ and 
  so~$\sequence{a,b}\in A\times B$.
  But $\sequence{a,b}\notin A^\prime\times B^\prime$,\
  and so $A\times B\neq A^\prime\times B^\prime$.     
\end{answer}
\end{exes}
% \begin{exes}
% \item Prove that $A\times B=\emptyset$ iff $A=\emptyset$ or~$B=\emptyset$.
% \item Show that there are sets so that $A\times B\neq B\times A$.
%   Under what circumstances is $A\times B=B\times A$?
% \item Is $(A\times B)\times C$ equal to $A\times (B\times C)$?
% \item Show that this statement is false: 
%   $A\times B\subseteq A^\prime\times B^\prime$ if and only if
%   $A\subseteq A^\prime$ and $B\subseteq B^\prime$.
%   Patch the statement to make it true.
% \end{exes}
% \begin{ans}
% \begin{exes}
% \item If $A=\emptyset$ then $A\times B=\emptyset$ because there are no 
%   sequences with a first term drawn from $\emptyset$.
%   For the same reason, $A\times\emptyset=\emptyset$.
 
%   If neither set is empty then there exist some $a\in A$ and~$b\in B$, so 
%   $(a,b)\in A\times B$, and $A\times B$ is not empty.
% \item The two sets $A\times B$ and~$B\times A$ are not equal. 
%   For instance, if $A=\set{0}$ and~$B=\set{1}$ then 
%   $A\times B=\set{\sequence{0,1}}$
%   while
%   $B\times A=\set{\sequence{1,0}}$.

%   If $A\times B$ and $B\times A$ are the same set then either that set is empty 
%   and so either $A$ is empty or $B$ is empty,
%   or it is not.
%   If it is not empty then for each of its elements $\sequence{x,y}$,
%   we have both that $x\in A$ and that $x\in B$ (and similarly for~$y$).
%   Clearly in this case $A=B$.
% \item The two sets $(A\times B)\times C$ and~$A\times (B\times C)$ 
%   are not equal.
%   For instance, if $A=\set{a}$, $B=\set{b}$, and $C=\set{c}$ then 
%   $(A\times B)\times C=\set{\sequence{\sequence{a,b},c}}$
%   has a single element, a sequence with two terms, the first
%   of which is a sequence.
%   But while $A\times(B\times C)=\set{\sequence{a,\sequence{b,c}}}$ 
%   also has a single element that is a sequence with two terms, 
%   the first element here is not a sequence. 

%   \remark they are equal only if one of them is empty.
% \item The example 
%   $A=\emptyset$, $B=\set{1,2}$, $A^\prime=\set{a}$, $B^\prime=\set{1}$
%   shows that the statement is false since 
%   $A\times B=\emptyset\subseteq A^\prime\times B^\prime$ but 
%   $B\not\subseteq B^\prime$.

%   The adjusted statement is: for all nonempty sets,  
%   $A\times B\subseteq A^\prime\times B^\prime$ if and only if
%   $A\subseteq A^\prime$ and $B\subseteq B^\prime$.
%   We will prove the `if' and `only if' clauses separately.

%   For `only if' suppose that $A\subseteq A^\prime$ and~$B\subseteq B^\prime$.
%   Then any element of~$A\times B$ is a pair $\sequence{a,b}$. 
%   Because of the subset relationship, $a\in A^\prime$ and~$b\in B^\prime$
%   and so $\sequence{a,b}\in A^\prime\times B^\prime$.
%   Thus $A\times B\subseteq A^\prime\times B^\prime$.

%   Now assume that $A\not\subseteq A^\prime$ (the case 
%   of $B\not\subseteq B^\prime$ is similar) and that $a\in A$ 
%   but~$a\notin A^\prime$.
%   Because $B$ is not empty there is a~$b\in B$ and 
%   so~$\sequence{a,b}\in A\times B$.
%   But $\sequence{a,b}\notin A^\prime\times B^\prime$,\
%   and so $A\times B\neq A^\prime\times B^\prime$.   
% \end{exes}
% \end{ans}
\end{problem}

\begin{problem}[\maxlength] 
\notetext{Interaction of Cartesian product with other set operations}
\begin{exes}
\begin{exercise}
  Prove that $(A\union B)\times C=(A\times C)\union(B\times C)$.
\end{exercise}
\begin{answer}
  Assume first that $\sequence{x,c}\in (A\union B)\times C$.
  Then $x\in A\union B$ and so either $x\in A$ or~$x\in B$.
  If $x\in A$ then $\sequence{x,c}\in A\times C$, while 
  if $x\in B$ then $\sequence{x,c}\in B\times C$, and so 
  $\sequence{x,c}\in (A\times C)\union (B\times C)$.
  Thus $(A\union B)\times C\subseteq (A\times C)\union (B\times C)$.
  
  To get containment in the other direction assume that 
  $\sequence{x,c}\in (A\times C)\union (B\times C)$.
  Then either $\sequence{x,c}\in A\times C$ or~$\sequence{x,c}\in B\times C$.
  If $\sequence{x,c}\in A\times C$ then~$x\in A$ and so 
  $\sequence{x,c}\in (A\union B)\times C$.
  The  $\sequence{x,c}\in B\times C$ case is similar.
  Thus $(A\times C)\union (B\times C)\subseteq (A\union B)\times C$.   
\end{answer}
\begin{exercise}
  What is the interaction of Cartesian product and intersection?
\end{exercise}
\begin{answer}
\item We will prove that 
  $(A\intersection B)\times C = (A\times C)\intersection (B\times C)$.
  For contrast with the prior item
  we will use a sequence of if and only if statements.

  We have that $\sequence{x,c}\in (A\intersection B)\times C$
  if and only if both
  $x\in A\intersection B$ and~$c\in C$.
  That holds if and only if both
  $\sequence{x,c}\in A\times C$ and~$\sequence{x,c}\in B\times C$ are true,
  which in turn is equivalent to
  $\sequence{x,c}\in (A\times C)\intersection (B\times C)$.  
\end{answer}
\begin{exercise} 
  Show that in general $\setcomp{(A\times B)}$ does not equal 
  $\setcomp{A}\times\setcomp{B}$.
\end{exercise}
\begin{answer}
  If the universal set is $\universalset=\Z$,
  $A=\set{0}$, and $B=\set{1}$ then $A\times B=\set{\sequence{0,1}}$,
  so $\setcomp{(A\times B)}=\Z^2-\set{\sequence{0,1}}$,
  while $\setcomp{A}\times\setcomp{B}=(\Z-\set{0})\times(\Z-\set{1})$.
  The two sets are not equal. 
  For instance, $\sequence{0,2}\in \setcomp{A\times B}$
  while $\sequence{0,2}\notin\setcomp{A}\times\setcomp{B}$.  
\end{answer}
\end{exes}
% \begin{exes}
% \item Prove that $(A\union B)\times C=(A\times C)\union(B\times C)$
% \item What happens for intersection?
% \item Show that in general $\setcomp{(A\times B)}$ does not equal 
%   $\setcomp{A}\times\setcomp{B}$.
% \end{exes}
% \begin{ans}
% \begin{exes}
% \item Assume first that $\sequence{x,c}\in (A\union B)\times C$.
%   Then $x\in A\union B$ and so either $x\in A$ or~$x\in B$.
%   If $x\in A$ then $\sequence{x,c}\in A\times C$, while 
%   if $x\in B$ then $\sequence{x,c}\in B\times C$, and so 
%   $\sequence{x,c}\in (A\times C)\union (B\times C)$.
%   Thus $(A\union B)\times C\subseteq (A\times C)\union (B\times C)$.
  
%   To get containment in the other direction assume that 
%   $\sequence{x,c}\in (A\times C)\union (B\times C)$.
%   Then either $\sequence{x,c}\in A\times C$ or~$\sequence{x,c}\in B\times C$.
%   If $\sequence{x,c}\in A\times C$ then~$x\in A$ and so 
%   $\sequence{x,c}\in (A\union B)\times C$.
%   The  $\sequence{x,c}\in B\times C$ case is similar.
%   Thus $(A\times C)\union (B\times C)\subseteq (A\union B)\times C$. 
% \item We will prove that 
%   $(A\intersection B)\times C = (A\times C)\intersection (B\times C)$.
%   For contrast with the prior item
%   we will use a sequence of if and only if statements.

%   We have that $\sequence{x,c}\in (A\intersection B)\times C$
%   if and only if both
%   $x\in A\intersection B$ and~$c\in C$.
%   That holds if and only if both
%   $\sequence{x,c}\in A\times C$ and~$\sequence{x,c}\in B\times C$ are true,
%   which in turn is equivalent to
%   $\sequence{x,c}\in (A\times C)\intersection (B\times C)$.
% \item If the universal set is $\universalset=\Z$,
%   $A=\set{0}$, and $B=\set{1}$ then $A\times B=\set{\sequence{0,1}}$,
%   so $\setcomp{(A\times B)}=\Z^2-\set{\sequence{0,1}}$,
%   while $\setcomp{A}\times\setcomp{B}=(\Z-\set{0})\times(\Z-\set{1})$.
%   The two sets are not equal. 
%   For instance, $\sequence{0,2}\in \setcomp{A\times B}$
%   while $\sequence{0,2}\notin\setcomp{A}\times\setcomp{B}$.
% \end{exes}
% \end{ans}
\end{problem}











%===================================================
\chapter{Functions, relations}
\begin{df}
A \definend{function}~$f$ (or \definend{map} or \definend{morphism}) 
from \definend{domain} set~$D$
to \definend{codomain} set~$C$, written $\map{f}{D}{C}$,
is a sequence consisting of the two sets along with a \definend{graph}, 
a set of pairs $(d,c)\in D\times C$ that is 
\definend{well-defined}: for each $d\in D$ there is
exactly one $c\in C$ such that $(d,c)$ is an element of the graph. 
Functions are equal only if they have the same domain, codomain,
and graph.
\end{df}

\noindent Thus, a function associates each element~$d$ from the domain,
called an \definend{argument} or~\definend{input},
with an element~$c$ from the codomain, 
called a~\definend{value} or~\definend{output},
subject to the condition that $d$ determines~$c$. 
We write $f(d)=c$ and say that $c$ is the \definend{image} of $d$ 
or that $d$ \definend{maps to}~$c$.

A \definend{bean diagram} pictures the domain and 
codomain as blobs and 
either shows the function as a whole as a simple arrow   
or else shows the function's action on individual elements 
with arrows that begin with a bar.
\begin{center}
  \grf{asy/bean_fcn.pdf}{$\map{f}{D}{C}$}
  \hspace{8em}
  \grf{asy/bean_fcn_elets.pdf}{$a\mapsunder{}f(a)$ and $b\mapsunder{}f(b)$}
\end{center}
% In place of $\map{f}{D}{C}$ you may see $D\mapsvia{f} C$ and
% in place of $f(d)=c$ you may see $d\mapsunder{f}c$.

\begin{problem} Decide if each is a function:\label{FindFunctions}
\begin{items}
\item $D=\set{0,1,2}$, $C=\set{3,4,5}$,
  $G=\set{(0,3), (1,4), (2,5)}$    
\item $D=\set{0,1,2}$, $C=\set{3,4,5}$,
  $G=\set{(0,3), (1,4), (2,3)}$    
\item $D=\set{0,1,2}$, $C=\set{3,4,5}$,
  $G=\set{(0,3), (1,4)}$    
\item $D=\set{0,1,2}$, $C=\N$,
  $G=\set{(0,3), (1,3), (2,3)}$    
\item $D=\N$, $C=\N$,
  $G=\set{(0,3), (1,4), (2,5)}$    
\item $D=\set{0,1,2}$, $C=\set{3,4,5}$,
  $G=\set{(0,3), (1,4), (2,4), (0,5)}$    
\item $D=\N$, $C=\N$,
  $G=\setbuilder{(d,c)\in D\times C}{c=d^2}$    
\end{items}
\begin{answer}
\begin{items}
\item This is a function.
  By inspection, for each pair $(x,y)\in G$ we have that
  $x\in D$ and that~$y\in C$.
  Also by inspection we have that for each $x\in D$ there is one and only 
  one~$c\in C$ such that~$(x,y)\in G$.  
\item This is a function; the fact that there is a value associated with 
  two separate arguments is not an issue.
  The proof is the same as for the prior item.   
\item This is not a function. 
  There is an element of the domain,
  $2\in D$, with no associated value.
  That is, there is no $c\in C$ such that $(2,c)\in G$. 
\item  This is a function; the fact that the codomain contains many 
  elements that are not associated with any argument in the domain is 
  not an issue.
  The verification is the same as for the first item.  
\item This is not a function.
  There is an element of the domain. $3\in D$, that is not associated with 
  any value; that is, there is no $c\in C$ such that $(3,c)\in G$.   
\item This is not a function because there is an element of the domain,
  $0\in D$, that is associated with two different values.  
\item This is a function. 
  First, for each pair $(x,y)\in G$ we have that
  $x\in D$ and that~$y\in C$.
  Also, we have that for each $x\in D$ there is one and only 
  one associated~$c\in C$, namely $c=d^2$.  
\end{items}
\end{answer}
\end{problem}

\remark we often blur the distinction between a function and its graph.
For instance we may say, ``a function is an input-output relationship'' 
when technically it is the function's graph that is the pairing.
(We've already done some blurring, in the sentence following the definition.)
The distinction between function and graph
is there only because the graph does not determine the codomain,
so we must specify it separately.
(The graph does determine the domain so that information is  
redundant.)

Do not think that a function must have a formula.
The final item in the prior exercise has a formula but for other items 
$G$ just has arbitrary pairings.

\begin{problem}[\maxlength]
Let $D$ and $C$ be finite sets.
How many maps are there from $D$ to $C$?
\begin{answer}
For each element of the domain, in making a function we have a choice 
of associating it with any of $|C|$-many values.
Thus the number of possible function is $|C|^{|D|}$.
\end{answer}
\end{problem}

A function may have multiple arguments; one example is 
$\sequence{x,y}\mapsunder{f}x^2-2y^2$.
We write this map $\map{f}{\R^2}{\R}$ as 
$f(x,y)$ rather than
$f(\sequence{x,y})$.
The number of arguments is the function's \definend{arity}.

\begin{df}
For $\map{f}{D}{C}$,
the \definend{range} is the set
$\setbuilder{y\in C}{\text{there is a $x\in D$ such that $f(x)=y$}}$,
denoted $\range(f)$ (or $f(D)$).
\end{df}

\begin{problem}
For each item in Exericse~\ref{FindFunctions}, 
if it is a function then find its range.  
\begin{answer}
\begin{items}
\item The range is $\set{3,4,5}=C$.    
\item The range is $\set{3,4}$.
\item This is not a function.   
\item The range is $\set{3}$.
\item This is not a function.   
\item This is not a function.   
\item The range is the set of perfect squares $\setbuilder{a^2}{a\in\N}$.   
\end{items}
\end{answer}
\end{problem}

\begin{df}
Let $\map{f}{D}{C}$.
The \definend{restriction} of $f$ to $B\subseteq D$ is
the function $\map{\restrictionmap{f}{B}}{B}{C}$ whose action is given by 
$\restrictionmap{f}{B}(b)=f(b)$ for all $b\in B$.
A synonym is that
$f$ is an \definend{extension} of~$\restrictionmap{f}{B}$.
The \definend{image} of the set $B$ under $f$, 
denoted $\image(f)$ (or $f(B)$),
is the range of the function $\restrictionmap{f}{B}$.
\end{df}

\begin{problem}
Find the image of each set under the real function $f(x)=\tan(x)$:
\begin{items}
\item $\leftclosed{\pi/4}{\pi/2}=\setbuilder{x\in\R}{\pi/4\leq x<\pi/2}$
\item \set{-\pi/3}
% \item $\R^+$  
\end{items}
\begin{answer}
\begin{items}
\item $f(\leftclosed{\pi/4}{\pi/2})=\leftclosed{1}{\infty}
             =\setbuilder{x\in\R}{1\leq x<\infty}$ 
\item $f(\set{\pi/3})=\set{\sqrt{3}}$
% \item The function $f(x)=\tan(x)$ isn't defined for all values in $\R^+$.
%   In particular, the function isn't defined for $x=\pi/4$.
%   Thus, $\restrictionmap{f}{\R^+}$ isn't defined, and so the
%   image isn't defined.
\end{items}
\end{answer}
\end{problem}

\begin{df}
Let $\map{f}{D}{C}$.
The \definend{inverse image of the element}~$c\in C$ is
the set $f^{-1}(c)=\setbuilder{d\in D}{f(d)=c}$.
The \definend{inverse image of the set}~$A\subseteq C$
is the set $f^{-1}(A)=\setbuilder{d\in D}{f(d)\in A}$.   
\end{df}

\begin{problem}
Find the inverse image of each under the function $\map{f}{\R}{\R}$ 
given by $x\mapsto x^2$:
\begin{items}
\item $9$
\item $\closed{16}{25}=\setbuilder{y\in\R}{16\leq y\leq 25}$
\end{items}
\begin{answer}
\begin{items}
\item It is the set $\set{3,-3}$, sometimes abbreviated as $\pm 3$.
\item It is the union $\closed{4}{5}\union \closed{-5}{-4}$.    
\end{items}
\end{answer}
\end{problem}

\begin{problem}
Prove that $f^{-1}(A)$ is the union of the sets $f^{-1}(a)$ over all $a\in A$.
\begin{answer}
We have that, where $D$ is the domain, 
$f^{-1}(A)=\setbuilder{d\in D}{f(d)\in A}$.
Restated, this is $\setbuilder{d\in D}{\text{$f(d)=a$ for $a\in A$}}$.
This is the union over all $a\in A$ of the 
sets $S_a=\setbuilder{d\in D}{f(d)=a}$.  
\end{answer}
\end{problem}





% .....................................
\section{Composition}

\begin{df}
The \definend{composition} of
two functions
$\map{f}{D}{C}$ and $\map{g}{C}{B}$ 
is $\map{\composed{g}{f}}{D}{B}$ given by 
$\composed{g}{f}(d)=g(f(d))$.
\end{df}

\begin{center}
  \includegraphics{asy/bean_fcn_comp.pdf}  
\end{center}

Note that, 
although when reading the expression $\composed{g}{f}$ from left to right 
the $g$ comes first, 
the function that is applied first is~$f$. 
Note also that the codomain of~$f$ is the domain of~$g$
(we sometimes allow a composition when the domain of~$g$ is not the 
entire codomain, but instead is a superset of the range of~$f$).

Read $\composed{g}{f}$ aloud as ``$g$ circle $f$'' 
or~``$g$ composed with $f$''
(or~``$g$ following $f$'').

\begin{problem} Let $D=\set{0,1,2}$, $C=\set{a,b,c,d}$, 
and $B=\set{\alpha,\beta,\gamma}$.
Suppose that $\map{f}{D}{C}$ is given by $0\mapsunder{} a$, $1\mapsunder{} c$, 
$2\mapsunder{} d$ and that $\map{g}{C}{B}$
is given by 
$a\mapsunder{}\alpha$, $b\mapsunder{} \beta$, $c\mapsunder{}\gamma$,
and $d\mapsunder{}\alpha$.
\begin{items}
\item Compute $\composed{g}{f}$ on all arguments or show that the composition
  is not defined.
\item Compute $\composed{f}{g}$ on all arguments or show it is not defined.
\item Find the range of $f$, $g$, and any defined compositions    
\end{items}
\begin{answer}
\begin{items}
\item The function $\map{\composed{g}{f}}{D}{B}$ is given by 
  $0\mapsunder{}\alpha$, $1\mapsunder{}\gamma$, and $2\mapsunder{}\alpha$.
\item This map is not defined since the codomain of~$g$ is not equal to 
  the domain of~$f$.
\item The range of~$f$ is $\set{a,c,d}$.
  The range of~$g$ is $\set{\alpha,\beta,\gamma}$. 
  The range of $\composed{g}{f}$ is $\set{\alpha,\gamma}$.
\end{items}
\end{answer}
\end{problem}

\begin{problem}[\midlength]
Let $\map{f}{\R}{\R}$ be $f(x)=x^2$ and let $\map{g}{\R}{\R}$ be~$g(x)=3x+1$.
Find the domain, codomain, and a formula for each of
$\composed{g}{f}$ and $\composed{f}{g}$.  
\begin{answer}
For $\composed{g}{f}$ the domain and codomain are~$\R$ while a formula is
$\composed{g}{f}(x)=3x^2+1$.
The map~$\composed{f}{g}$ also has domain and codomain equal tp~$\R$,
by the formula is~$\composed{f}{g}(x)=(3x+1)^2=9x^2+6x+1$.
\end{answer}
\end{problem}

\begin{problem} Prove each.
\begin{exes}
\begin{exercise}
  \notetext{Associativity} 
  $\composed{h}{(\composed{g}{f})}=\composed{(\composed{h}{g})}{f}$    
\end{exercise}
\begin{answer}
  The action of the map on the left side
  is $(\composed{h}{(\composed{g}{f})(x)}=h(\composed{g}{f}(x))
       =h(g(f(x)))$.
  The action of the map on the right side  
  is $(\composed{(\composed{h}{g})}{f})(x)=(\composed{h}{g})(f(x))
      =h(g(f(x)))$.
  The two actions are equal\Dash the two give the same association of inputs
  with outputs\Dash so the maps are equal.  
\end{answer}
\begin{exercise} 
  Function composition need not be commutative.
\end{exercise}
\begin{answer}
  One example of noncommutativity is $\map{f,g}{\R}{\R}$ given by 
  $f(x)=x+1$ and $g(x)=2x+3$.
  The formula for $\composed{f}{g}$ is $2\cdot(x+1)+3=2x+5$ while
  the formula for $\composed{g}{f}$ is $(2x+3)+1=2x+4$.
  Thus, for instance, the two differ on argument~$0$.  
\end{answer}
\end{exes}
% \begin{exes}
% \item\notetext{Associativity} 
%   $\composed{h}{(\composed{g}{f})}=\composed{(\composed{h}{g})}{f}$    
% \item Function composition need not be commutative.
% \end{exes}
% \begin{ans}
% \begin{exes}
% \item The action of the map on the left side
%   is $(\composed{h}{(\composed{g}{f})(x)}=h(\composed{g}{f}(x))
%        =h(g(f(x)))$.
%   The action of the map on the right side  
%   is $(\composed{(\composed{h}{g})}{f})(x)=(\composed{h}{g})(f(x))
%       =h(g(f(x)))$.
%   The two actions are equal\Dash the two give the same association of inputs
%   with outputs\Dash so the maps are equal.
% \item One example of noncommutativity is $\map{f,g}{\R}{\R}$ given by 
%   $f(x)=x+1$ and $g(x)=2x+3$.
%   The formula for $\composed{f}{g}$ is $2\cdot(x+1)+3=2x+5$ while
%   the formula for $\composed{g}{f}$ is $(2x+3)+1=2x+4$.
%   Thus, for instance, the two differ on argument~$0$.
% \end{exes}
% \end{ans}
\end{problem}





% .....................................
\section{Inverse}

The definition of a function specifies that for every argument in the
domain there is 
exactly one associated value.
The definition puts no such condition on the elements of the codomain.

\begin{df}
A function is \definend{one-to-one} (or an \definend{injection}) 
if for each value there is at most
one associated argument, that is, if $f(d_0)=f(d_1)$ implies that $d_0=d_1$
for elements $d_0,d_1$ of the domain.
A function is \definend{onto} (or a \definend{surjection}) 
if for each value there is at least
one associated argument, that is, if for each element $c$ of the codomain
there exists an element $d$ of the domain such that $f(d)=c$.
A function that is both one-to-one and onto, so that for every value there
is exactly one associated argument, is a 
\definend{correspondence} (or \definend{bijection}, or \definend{permutation}).
\end{df}

\begin{problem} 
  Let $\map{f}{\R}{\R}$ be $f(x)=3x+1$ and 
  $\map{g}{\R}{\R}$ be $g(x)=x^2+1$.
\begin{exes}
\begin{exercise} 
  Show that $f$ is one-to-one, and onto.
\end{exercise}
\begin{answer}
  For one-to-one, suppose that $f(x_0)=f(x_1)$ for $x_0,x_1\in\R$.
  Then $3x_0+1=3x_1+1$.
  Subtract the~$1$'s and divide by~$3$ to conclude that $x_0=x_1$.
  Thus~$f$ is one-to-one.   

  For onto, fix a member of the codomain~$c\in\R$.
  Observe that $d=(c-1)/3$ is a member of the domain and that 
  $f(d)=c$.
  Thus $f$ is onto.  
\end{answer}
\begin{exercise} 
  Show that $g$ is not one-to-one, and not onto.
\end{exercise}
\begin{answer}
  The function~$g$ is not one-to-one because $g(2)=g(-2)$.
  It is not onto because no element of the domain~$\R$ is mapped by~$g$
  to the element $-1$ of the codomain.          
\end{answer}
\end{exes}
% \begin{exes}
% \item Show that $f$ is one-to-one.
% \item Show that $f$ is onto.    
% \item Show that $g$ is not one-to-one, and also that it is not onto.
% \end{exes}
% \begin{ans}
% \begin{exes}
% \item Suppose that $f(x_0)=f(x_1)$ for $x_0,x_1\in\R$.
%   Then $3x_0+1=3x_1+1$.
%   Subtract the~$1$'s and divide by~$3$ to conclude that $x_0=x_1$.
%   Thus~$f$ is one-to-one. 
% \item Fix a member of the codomain~$c\in\R$.
%   Observe that $d=(c-1)/3$ is a member of the domain and that 
%   $f(d)=c$.
%   Thus $f$ is onto.
% \item The function~$g$ is not one-to-one because $g(2)=g(-2)$.
%   It is not onto because no element of the domain~$\R$ is mapped by~$g$
%   to the element $-1$ of the codomain.        
% \end{exes}
% \end{ans}
\end{problem}

\begin{problem}   \label{CorrespondingSetsHaveSameNumberOfElements}
  Proving these two items shows that, 
  where $D$ and~$C$ are finite sets, 
  if there is a correspondence~$\map{f}{D}{C}$
  then the two sets have the same number of elements.
\begin{exes}
\begin{exercise}
  If $f$ is onto then $|C|\leq |D|$.
\end{exercise}
\begin{answer}
  Assume that $\map{f}{D}{C}$ is onto and
  that the sets are finite.
  We will prove the statement by induction on the number of elements in~$D$.
  The base step is that~$D$ has no elements at all, so $D=\emptyset$.
  The only function with an empty domain is the function whose graph is 
  empty. 
  Since this function is onto, the codomain~$C$ is also empty, 
  and also has no elements.
  So the statement holds in this case.

  For the inductive step assume that the statement is true when $|D|=0$, 
  $|D|=1$, \ldots, $|D|=k$ and consider the~$|D|=k+1$ case.
  Put an element of~$D$ aside by picking some $d\in D$ and considering 
  $\hat{D}=D-\set{d}$ (because this is the $k+1$ case there is at least
  one such element in~$D$).
  The inductive hypothesis applies to $\hat{D}$ so the number of elements in
  the range of the restriction map 
  $\map{\restrictionmap{f}{\hat{D}}}{\hat{D}}{\range(\restrictionmap{f}{\hat{D}})}$
  is less than or equal to the number of elements in the domain of that map
  $|\range(\restrictionmap{f}{\hat{D}})|\leq |\hat{D}|$.

  Now add the element~$d$ back by returning to considering~$D$ and the 
  map~$\map{f}{D}{C}$.
  The set~$D$ has one element more than the set~$\hat{D}$.
  And $\range(f)=C$ is no more than one element larger than
  $\range(\restrictionmap{f}{\hat{D}})$.
  Thus $|C|\leq|D|$.  
\end{answer}
\begin{exercise} 
  If $f$ is one-to-one then $|C|\geq |D|$.
\end{exercise}
\begin{answer}
  Assume that $\map{f}{D}{C}$ is one-to-one and
  that the sets are finite.
  We will do induction on the number of elements in~$D$.
  The base step is that~$|D|=0$.
  The codomain cannot have fewer elements than this
  so~$|C|\geq |D|$ holds in this case.

  For the inductive step assume that the statement is true when $|D|=0$, 
  \ldots, $|D|=k$ and consider~$|D|=k+1$.
  Pick some $d\in D$ and consider 
  $\hat{D}=D-\set{d}$ (because this is the $k+1$ case there is at least
  one such element).
  The inductive hypothesis applies to $\hat{D}$ so that 
  the number of elements in the range of the restriction map 
  $\map{\restrictionmap{f}{\hat{D}}}{\hat{D}}{\range(\restrictionmap{f}{\hat{D}})}$
  is at least as great as the number of elements in the domain of that map
  $|\range(\restrictionmap{f}{\hat{D}})|\geq |\hat{D}|$.

  Now extend to~$D$ and the map~$\map{f}{D}{C}$.
  The set~$D$ has one element more than the set~$\hat{D}$.
  Because~$f$ is one-to-one, the value~$f(d)$ is not in 
  the range of the restriction map~$\range(\restrictionmap{f}{\hat{D}})$.
  Thus $\range(f)$ is one element larger than
  $|\range(\restrictionmap{f}{\hat{D}})|$.
  Therefore $|C|\geq|D|$.  
\end{answer}
\end{exes}
% \begin{exes}
% \item If $f$ is onto then $|C|\leq |D|$.
% \item If $f$ is one-to-one then $|C|\geq |D|$.
% \end{exes}
% \begin{ans}
% \begin{exes}
% \item Assume that $\map{f}{D}{C}$ is onto and
%   that the sets are finite.
%   We will prove the statement by induction on the number of elements in~$D$.
%   The base step is that~$D$ has no elements at all, so $D=\emptyset$.
%   The only function with an empty domain is the function whose graph is 
%   empty. 
%   Since this function is onto, the codomain~$C$ is also empty, 
%   and also has no elements.
%   So the statement holds in this case.

%   For the inductive step assume that the statement is true when $|D|=0$, 
%   $|D|=1$, \ldots, $|D|=k$ and consider the~$|D|=k+1$ case.
%   Put an element of~$D$ aside by picking some $d\in D$ and considering 
%   $\hat{D}=D-\set{d}$ (because this is the $k+1$ case there is at least
%   one such element in~$D$).
%   The inductive hypothesis applies to $\hat{D}$ so the number of elements in
%   the range of the restriction map 
%   $\map{\restrictionmap{f}{\hat{D}}}{\hat{D}}{\range(\restrictionmap{f}{\hat{D}})}$
%   is less than or equal to the number of elements in the domain of that map
%   $|\range(\restrictionmap{f}{\hat{D}})|\leq |\hat{D}|$.

%   Now add the element~$d$ back by returning to considering~$D$ and the 
%   map~$\map{f}{D}{C}$.
%   The set~$D$ has one element more than the set~$\hat{D}$.
%   And $\range(f)=C$ is no more than one element larger than
%   $\range(\restrictionmap{f}{\hat{D}})$.
%   Thus $|C|\leq|D|$.
% \item Assume that $\map{f}{D}{C}$ is one-to-one and
%   that the sets are finite.
%   We will do induction on the number of elements in~$D$.
%   The base step is that~$|D|=0$.
%   The codomain cannot have fewer elements than this
%   so~$|C|\geq |D|$ holds in this case.

%   For the inductive step assume that the statement is true when $|D|=0$, 
%   \ldots, $|D|=k$ and consider~$|D|=k+1$.
%   Pick some $d\in D$ and consider 
%   $\hat{D}=D-\set{d}$ (because this is the $k+1$ case there is at least
%   one such element).
%   The inductive hypothesis applies to $\hat{D}$ so that 
%   the number of elements in the range of the restriction map 
%   $\map{\restrictionmap{f}{\hat{D}}}{\hat{D}}{\range(\restrictionmap{f}{\hat{D}})}$
%   is at least as great as the number of elements in the domain of that map
%   $|\range(\restrictionmap{f}{\hat{D}})|\geq |\hat{D}|$.

%   Now extend to~$D$ and the map~$\map{f}{D}{C}$.
%   The set~$D$ has one element more than the set~$\hat{D}$.
%   Because~$f$ is one-to-one, the value~$f(d)$ is not in 
%   the range of the restriction map~$\range(\restrictionmap{f}{\hat{D}})$.
%   Thus $\range(f)$ is one element larger than
%   $|\range(\restrictionmap{f}{\hat{D}})|$.
%   Therefore $|C|\geq|D|$.
% \end{exes}
% \end{ans}
\end{problem}

\begin{problem} \label{InteractionOneToONeOntoWithComposition}
Prove.
\begin{exes}
\begin{exercise} 
  A composition of one-to-one functions is one-to-one.
\end{exercise}
\begin{answer}
  Let $\map{f}{D}{C}$ and~$\map{g}{C}{B}$ be one-to-one.
  Suppose that $\composed{g}{f}(x_0)=\composed{g}{f}(x_1)$ for
  some $x_0,x_1\in D$.
  Then $g(f(x_0))=g(f(x_1))$.
  The function~$g$ is one-to-one so since the values $g(f(x_0))$ 
  and~$g(f(x_1))$ are equal, the arguments $f(x_0)$ and~$f(x_1)$ are
  also equal.
  The function~$f$ is one-to-one and so $x_0=x_1$.
  Because $\composed{g}{f}(x_0)=\composed{g}{f}(x_1)$ implies that
  $x_0=x_1$, the composition is one-to-one.  
\end{answer}
\begin{exercise} 
  A composition of onto functions is onto.
\end{exercise}
\begin{answer}
  Let $\map{f}{D}{C}$ and~$\map{g}{C}{B}$ be functions that are onto.
  Fix an element of the codomain of the composition~$b\in B$.
  The function~$g$ is onto so there is a $c\in C$ such that $g(c)=b$.
  The function~$f$ is onto so there is a $d\in D$ such that $f(d)=c$.
  Then $\composed{g}{f}(d)=b$, and so the composition is onto.
\end{answer}
\begin{exercise} 
  A composition of correspondences is a correspondence.
\end{exercise}
\begin{answer}
  This is immediate from the prior two items. 
\end{answer}
% \end{exes}
% \begin{exes}
% \item A composition of one-to-one functions is one-to-one.
% \item A composition of onto functions is onto.
% \item A composition of correspondences is a correspondence.    
% \end{exes}
% \begin{ans}
% \begin{exes}
% \item Let $\map{f}{D}{C}$ and~$\map{g}{C}{B}$ be one-to-one.
%   Suppose that $\composed{g}{f}(x_0)=\composed{g}{f}(x_1)$ for
%   some $x_0,x_1\in D$.
%   Then $g(f(x_0))=g(f(x_1))$.
%   The function~$g$ is one-to-one so since the values $g(f(x_0))$ 
%   and~$g(f(x_1))$ are equal, the arguments $f(x_0)$ and~$f(x_1)$ are
%   also equal.
%   The function~$f$ is one-to-one and so $x_0=x_1$.
%   Because $\composed{g}{f}(x_0)=\composed{g}{f}(x_1)$ implies that
%   $x_0=x_1$, the composition is one-to-one.
% \item Let $\map{f}{D}{C}$ and~$\map{g}{C}{B}$ be functions that are onto.
%   Fix an element of the codomain of the composition~$b\in B$.
%   The function~$g$ is onto so there is a $c\in C$ such that $g(c)=b$.
%   The function~$f$ is onto so there is a $d\in D$ such that $f(d)=c$.
%   Then $\composed{g}{f}(d)=b$, and so the composition is onto.
% \item This is immediate from the prior two items. 
% \end{exes}
% \end{ans}
% \end{problem}

% \begin{problem} 
% \begin{exes}
\begin{exercise} 
  If $\composed{g}{f}$ is onto then $g$ is onto.
\end{exercise}
\begin{answer}
  Let $\map{f}{D}{C}$ and~$\map{g}{C}{B}$ be such that 
  the composition $\composed{g}{f}$ is onto.
  Suppose that~$g$ is not onto.
  Then there is a~$b\in B$ such that there is no~$c\in C$
  with~$g(c)=b$.
  But this means that there is no~$d\in D$ such that 
  $b=g(f(d))$, contradicting that the composition is onto.
  So the supposition is false and $g$ must be onto.  
\end{answer}
\begin{exercise} 
  If $\composed{g}{f}$ is one-to-one then $f$ is one-to-one.
\end{exercise}
\begin{answer}
  Let $\map{f}{D}{C}$ and~$\map{g}{C}{B}$ be such that 
  the composition $\composed{g}{f}$ is one-to-one.
  Suppose that~$f$ is not one-to-one.
  Then there are $d_0,d_1\in D$ with $d_0\neq d_1$ such that $f(d_0)=f(d_1)$.
  But this implies that $g(f(d_0))=g(f(d_1))$, contradicting that 
  the composition is one-to-one.
  Thus the supposition is false and $f$ is one-to-one.  
\end{answer}
\begin{exercise}[\maxlength] 
  Do the other two cases hold? 
\end{exercise}
\begin{answer}
  The other two cases do not hold.
  
  First we give an example of a composition $\composed{g}{f}$ that is onto
  but where~$f$ is not onto.   
  Let $D=\set{0,1,2}$, $C=\set{a,b,c}$, and $B=\set{\alpha, \beta}$.
  Let $f$ map $0\mapsunder{} b$, $1\mapsunder{}b$, and~$2\mapsunder{} c$.
  Let $g$ map $a\mapsunder{} \alpha$, $b\mapsunder{}\alpha$, 
  and~$c\mapsunder{} \beta$. 
  Then $\composed{g}{f}$ is onto because $\composed{g}{f}(0)=\alpha$ and
  $\composed{g}{f}(2)=\beta$.
  But $f$ is not onto because no element of its domain~$D$ is mapped to the
  element $a$ of its codomain~$C$. 

  Next is an example of a composition that is one-to-one but where
  the function performed second is not one-to-one.
  Let $D=\set{0,1}$, $C=\set{a,b,c}$, and $B=\set{\alpha, \beta}$.
  Let $f$ map $0\mapsunder{} b$, and~$1\mapsunder{}c$.
  Let $g$ map $a\mapsunder{} \alpha$, $b\mapsunder{}\alpha$, 
  and~$c\mapsunder{} \beta$. 
  Then $\composed{g}{f}$ is one-to-one because 
  $\composed{g}{f}(0)\neq\composed{g}{f}(1)$.
  But $g$ is not one-to-one because $g(a)=g(b)$. 
\end{answer}
\end{exes}
% \begin{exes}
% \item Prove that if $\composed{g}{f}$ is onto then $g$ is onto.
% \item Prove that if $\composed{g}{f}$ is one-to-one then $f$ is one-to-one.
% \item Do the other two cases hold?     
% \end{exes}
% \begin{ans}
% \begin{exes}
% \item Let $\map{f}{D}{C}$ and~$\map{g}{C}{B}$ be such that 
%   the composition $\composed{g}{f}$ is onto.
%   Suppose that~$g$ is not onto.
%   Then there is a~$b\in B$ such that there is no~$c\in C$
%   with~$g(c)=b$.
%   But this means that there is no~$d\in D$ such that 
%   $b=g(f(d))$, contradicting that the composition is onto.
%   So the supposition is false and $g$ must be onto.
% \item Let $\map{f}{D}{C}$ and~$\map{g}{C}{B}$ be such that 
%   the composition $\composed{g}{f}$ is one-to-one.
%   Suppose that~$f$ is not one-to-one.
%   Then there are $d_0,d_1\in D$ with $d_0\neq d_1$ such that $f(d_0)=f(d_1)$.
%   But this implies that $g(f(d_0))=g(f(d_1))$, contradicting that 
%   the composition is one-to-one.
%   Thus the supposition is false and $f$ is one-to-one.
% \item The other two cases do not hold.
  
%   First is an example of a composition $\composed{g}{f}$ that is onto
%   but where~$f$ is not onto.   
%   Let $D=\set{0,1,2}$, $C=\set{a,b,c}$, and $B=\set{\alpha, \beta}$.
%   Let $f$ map $0\mapsunder{} b$, $1\mapsunder{}b$, and~$2\mapsunder{} c$.
%   Let $g$ map $a\mapsunder{} \alpha$, $b\mapsunder{}\alpha$, 
%   and~$c\mapsunder{} \beta$. 
%   Then $\composed{g}{f}$ is onto because $\composed{g}{f}(0)=\alpha$ and
%   $\composed{g}{f}(2)=\beta$.
%   But $f$ is not onto because no element of its domain~$D$ is mapped to the
%   element $a$ of its codomain~$C$. 

%   Next is an example of a composition that is one-to-one but where
%   the function performed second is not one-to-one.
%   Let $D=\set{0,1}$, $C=\set{a,b,c}$, and $B=\set{\alpha, \beta}$.
%   Let $f$ map $0\mapsunder{} b$, and~$1\mapsunder{}c$.
%   Let $g$ map $a\mapsunder{} \alpha$, $b\mapsunder{}\alpha$, 
%   and~$c\mapsunder{} \beta$. 
%   Then $\composed{g}{f}$ is one-to-one because 
%   $\composed{g}{f}(0)\neq\composed{g}{f}(1)$.
%   But $g$ is not one-to-one because $g(a)=g(b)$. 
% \end{exes}
% \end{ans}
\end{problem}

\begin{df}
An \definend{identity function} $\map{\identity}{D}{D}$ has
$\identity(d)=d$ for all $d\in D$.
\end{df}

\begin{df}
A function \definend{inverse} to $\map{f}{D}{C}$ is 
$\map{f^{-1}}{C}{D}$ such that 
$\composed{f^{-1}}{f}$ is the identity map on~$D$ and
$\composed{f}{f^{-1}}$ is the identity map on~$C$.
\end{df}

\begin{problem} 
These exercises compute inverses.
\begin{exes}
\begin{exercise} 
  Let $\map{f}{\Z}{\Z}$ be~$f(a)=a+3$ and let
  $\map{g}{\Z}{\Z}$ be $g(a)=a-3$.
  Show that $g$ is inverse to $f$.
\end{exercise}
\begin{answer}
  Observe first that the domain of each equals the codomain of the other,
  so their composition is defined both ways.
  Now, $\composed{g}{f}(a)=g(f(a))=g(a+3)=(a+3)-3=a$
  is the identity map.
  Similarly, $\composed{f}{g}(a)=(a-3)+3$ is also the identity map.
  Thus they are inverse.  
\end{answer}
\begin{exercise} 
  Let $\map{h}{\Z}{\Z}$ be the function that returns
  $n+1$ if $n$ is even, and returns $n-1$ if $n$ is odd.
  Find a function inverse to~$h$.
\end{exercise}
\begin{answer}
  The inverse of~$s$ is the map~$\map{r}{\R^+}{\R^+}$ given my 
  $r(x)=\sqrt{x}$.
  The domain of each is the codomain of the other,
  and both $\composed{s}{r}$ and~$\composed{r}{s}$ are the identity function.  
\end{answer}
\begin{exercise}[\maxlength] 
  Let $\map{s}{\R^+}{\R^+}$ be~$s(x)=x^2$.
  Find the map that is inverse to $s$.
\end{exercise}
\begin{answer}
  The inverse of~$h$ is itself.
  The domain and codomain are equal, as required. 
  If~$n$ is odd then $\composed{h}{h}(n)=h(n-1)=(n-1)+1=n$ because 
  $n-1$ is even in this case.
  Similarly if~$n$ is even then $\composed{h}{h}=(n+1)-1=n$.  
\end{answer}
\begin{exercise} 
  Show that $\map{t}{\R}{\R}$ given by $t(x)=x^2$
  has no inverse.
\end{exercise}
\begin{answer}
  Consider the element~$4$ of the codomain.
  It is the image of two different elements of the domain
  $t(2)=t(-2)=4$. 
  Any map $u$ that would be the inverse of~$t$ would have to associate~$4$ 
  in its domain with both~$2$ and~$-2$, and so would not be well-defined.  
\end{answer}
\end{exes}
% \begin{exes}
% \item Let $\map{f}{\Z}{\Z}$ be~$f(a)=a+3$ and let
%   $\map{g}{\Z}{\Z}$ be $g(a)=a-3$.
%   Show that $g$ is inverse to $f$.
% \item Let $\map{h}{\Z}{\Z}$ be the function that returns
%   $n+1$ if $n$ is even, and returns $n-1$ if $n$ is odd.
%   Find a function inverse to~$h$.
% \item Let $\map{s}{\R^+}{\R^+}$ be~$s(x)=x^2$.
%   Find the map that is inverse to $s$.    
% \item Show that $\map{t}{\R}{\R}$ given by $t(x)=x^2$
%   has no inverse.
% \end{exes}
% \begin{ans}
% \begin{exes}
% \item Observe first that the domain of each equals the codomain of the other,
%   so their composition is defined both ways.
%   Now, $\composed{g}{f}(a)=g(f(a))=g(a+3)=(a+3)-3=a$
%   is the identity map.
%   Similarly, $\composed{f}{g}(a)=(a-3)+3$ is also the identity map.
%   Thus they are inverse.
% \item The inverse of~$s$ is the map~$\map{r}{\R^+}{\R^+}$ given my 
%   $r(x)=\sqrt{x}$.
%   The domain of each is the codomain of the other,
%   and both $\composed{s}{r}$ and~$\composed{r}{s}$ are the identity function.
% \item The inverse of~$h$ is itself.
%   The domain and codomain are equal, as required. 
%   If~$n$ is odd then $\composed{h}{h}(n)=h(n-1)=(n-1)+1=n$ because 
%   $n-1$ is even in this case.
%   Similarly if~$n$ is even then $\composed{h}{h}=(n+1)-1=n$.
% \item Consider the element~$4$ of the codomain.
%   It is the image of two different elements of the domain
%   $t(2)=t(-2)=4$. 
%   Any map $u$ that would be the inverse of~$t$ would have to associate~$4$ 
%   in its domain with both~$2$ and~$-2$, and so would not be well-defined.
% \end{exes}
% \end{ans}
\end{problem}

\begin{problem}
  Find a domain and codomain, and a pair of maps $\map{f}{D}{C}$ 
  and~$\map{g}{C}{D}$,
  such that $\composed{g}{f}$ is the identity but $\composed{f}{g}$
  is not.
\begin{answer}
Let $\map{f}{\N^2}{\N^3}$ be the injection map
$\sequence{a,b}\mapsunder{}\sequence{a,b,0}$
and let 
$\map{g}{\N^3}{\N^2}$ be the projection function
$\sequence{a,b,c}\mapsunder{}\sequence{a,b}$.
Then the action of $\composed{g}{f}$ is 
$\sequence{a,b}\mapsunder{}\sequence{a,b,0}\mapsunder{}\sequence{a,b}$.
But the action in the other direction~$\composed{f}{g}$ is not the identity
$\sequence{a,b,c}\mapsunder{}\sequence{a,b}\mapsunder{}\sequence{a,b,0}$;
one instance is that $\composed{f}{g}(\sequence{1,2,3})$ equals
$\sequence{1,2,0}$, not $\sequence{1,2,3}$.     
\end{answer}
\end{problem}

If $\composed{g}{f}$ is the identity function then we say that 
$g$~is a \definend{left inverse} of~$f$\!, or what is the
same thing, that $f$ is a \definend{right inverse} of~$g$.
If $g$ is both a left and right inverse of~$f$ then, 
as above, we say just that it is
an inverse of~$f$ (or for emphasis, a \definend{two-sided inverse}). 

\begin{problem}
Let $D=\set{0,1,2}$ and~$C=\set{\alpha,\beta,\gamma}$.
Also let $\map{f,g}{D}{C}$ be given by
$f(0)=\alpha$, $f(1)=\beta$, $f(2)=\gamma$, and
$g(0)=\alpha$, $g(1)=\alpha$, $g(2)=\gamma$.
Then:
\begin{items}
\item verify that $f$ is a correspondence
\item construct an inverse for~$f$\!
\item verify that~$g$ is not a correspondence
\item show that~$g$ has no inverse 
\end{items}
\begin{answer}
\begin{items}
\item By inspection $f$ is both one-to-one and onto.
\item Reverse the association made by $f$ so that $f^{-1}(\alpha)=0$,
  $f^{-1}(\beta)=1$, and~$f^{-1}(\gamma)=2$.
\item The map~$g$ is not one-to-one since $g(0)=g(1)$.
  (In addition, $g$ is not onto.) 
\item If the function~$\map{h}{C}{D}$ were to be the inverse of~$g$
  then both $h(\alpha)=0$ and~$h(\alpha)=1$, 
  which violates the definition of a function.   
\end{items}
\end{answer}
\end{problem}

\begin{problem} \label{PropertiesOfInverses}
Prove each.
\begin{exes}
\begin{exercise} 
  A function has an inverse if and only if that 
  function is a correspondence.
\end{exercise}
\begin{answer}
  Let $\map{f}{D}{C}$ have an inverse~$\map{f^{-1}}{C}{D}$.

  Suppose that $f$ is not one-to-one.
  Then there are unequal elements~$d_0,d_1\in D$
  such that $f(d_0)=f(d_1)$.
  Let~$c\in C$ be that value~$c=f(d_0)$ and consider~$f^{-1}(c)$.
  If $f^{-1}(c)\neq d_0$ then we have a contradiction since the 
  action $d_0\mapsunder{}c\mapsunder{}f^{-1}(c)$
  of $\composed{f^{-1}}{f}$ is not the identity on~$d_0$.
  If $f^{-1}(c)=d_0$ then we have a similar contradiction for the
  action of $\composed{f^{-1}}{f}$ on~$d_1$.
  These contradictions together show that~$f$ is one-to-one.
   
  Now suppose that~$f$ is not onto,
  so that there is a~$c\in C$ with no associated~$d\in D$.
  The map~$\composed{f}{f^{-1}}$
  cannot give $c=\composed{f}{f^{-1}}(c)=f(f^{-1}(c))$, 
  because $c\notin\range(f)$, so this supposition yields a contradiction.
  Therefore~$f$ is onto.  
\end{answer}
\begin{exercise} 
  If a function has an inverse then that inverse
  is unique.
\end{exercise}
\begin{answer}
  Suppose that $\map{f}{D}{C}$ has two inverses $\map{g_0}{C}{D}$
  and~$\map{g_1}{C}{D}$.
  We will show that the two make the same associations, that is, they 
  have the same graph and
  thus are the same function.

  So let $c$ be an element of the domain~$C$ of the two.
  The prior item shows that~$f$ is onto so there is a~$d\in D$ such that
  $f(d)=c$.
  The prior item shows also that~$f$ is one-to-one so there is only 
  one~$d$ with that property, and so $d=g_0(c)=g_1(c)$.  
\end{answer}
\begin{exercise} 
  The inverse of a correspondence is a correspondence.  
\end{exercise}
\begin{answer}
  An inverse is a function that has an inverse: the inverse of~$f^{-1}$
  is~$f$.
  By the first item then, $f^{-1}$ is a correspondence.  
\end{answer}
\begin{exercise} 
  If $f$ and $g$ each is invertible then so is 
  $\composed{g}{f}$, and $(\composed{g}{f})^{-1}=\composed{f^{-1}}{g^{-1}}$.
\end{exercise}
\begin{answer}
  The composition of $\composed{f^{-1}}{g^{-1}}$ with~$\composed{g}{f}$,
  in either order, is the identity map.
  The order this way  
  $\composed{(\composed{f^{-1}}{g^{-1}})}{(\composed{g}{f})}(x)
  =(\composed{f^{-1}}{g^{-1}})(g(f(x)))
  =f^{-1}(g^{-1}(g(f(x))))
  =f^{-1}(f(x))=x$
  gives the identity,
  and the other order is similar.  
\end{answer}
\end{exes}
% \begin{exes}
% \item A function has an inverse if and only if that 
%   function is a correspondence.
% \item If a function has an inverse then that inverse
%   is unique.
% \item The inverse of a correspondence is a correspondence.  
% \item If $f$ and $g$ each is invertible then so is 
%   $\composed{g}{f}$, and $(\composed{g}{f})^{-1}=\composed{f^{-1}}{g^{-1}}$.
% \end{exes}
% \begin{ans}
% \begin{exes}
% \item Let $\map{f}{D}{C}$ have an inverse~$\map{f^{-1}}{C}{D}$.

%   Suppose that $f$ is not one-to-one.
%   Then there are unequal elements~$d_0,d_1\in D$
%   such that $f(d_0)=f(d_1)$.
%   Let~$c\in C$ be that value~$c=f(d_0)$ and consider~$f^{-1}(c)$.
%   If $f^{-1}(c)\neq d_0$ then we have a contradiction since the 
%   action $d_0\mapsunder{}c\mapsunder{}f^{-1}(c)$
%   of $\composed{f^{-1}}{f}$ is not the identity on~$d_0$.
%   If $f^{-1}(c)=d_0$ then we have a similar contradiction for the
%   action of $\composed{f^{-1}}{f}$ on~$d_1$.
%   These contradictions together show that~$f$ is one-to-one.
   
%   Now suppose that~$f$ is not onto,
%   so that there is a~$c\in C$ with no associated~$d\in D$.
%   The map~$\composed{f}{f^{-1}}$
%   cannot give $c=\composed{f}{f^{-1}}(c)=f(f^{-1}(c))$, 
%   because $c\notin\range(f)$, so this supposition yields a contradiction.
%   Therefore~$f$ is onto.
% \item Suppose that $\map{f}{D}{C}$ has two inverses $\map{g_0}{C}{D}$
%   and~$\map{g_1}{C}{D}$.
%   We will show that the two make the same associations, that is, they 
%   have the same graph and
%   thus are the same function.

%   So let $c$ be an element of the domain~$C$ of the two.
%   The prior item shows that~$f$ is onto so there is a~$d\in D$ such that
%   $f(d)=c$.
%   The prior item shows also that~$f$ is one-to-one so there is only 
%   one~$d$ with that property, and so $d=g_0(c)=g_1(c)$.
% \item An inverse is a function that has an inverse: the inverse of~$f^{-1}$
%   is~$f$.
%   By the first item then, $f^{-1}$ is a correspondence.
% \item The composition of $\composed{f^{-1}}{g^{-1}}$ with~$\composed{g}{f}$,
%   in either order, is the identity map.
%   The order this way  
%   $\composed{(\composed{f^{-1}}{g^{-1}})}{(\composed{g}{f})}(x)
%   =(\composed{f^{-1}}{g^{-1}})(g(f(x)))
%   =f^{-1}(g^{-1}(g(f(x))))
%   =f^{-1}(f(x))=x$
%   gives the identity,
%   and the other order is similar.
% \end{exes}
% \end{ans}
\end{problem}





% .....................................
\section{Relations}
A function's graph is a set of $n$~tuples
subject to the condition that the input determines the output.
We now consider the generalization that we get by dropping that condition.  

\begin{df}
A \definend{relation} on sets $A_0$, \ldots, $A_{n-1}$ is a subset
$R\subseteq A_0\times \cdots \times A_{n-1}$. 
If all of the sets are the same $A_0=A_1=\cdots =A$
then we say it is a relation on~$A$.

The number of sets~$n$ is the \definend{arity} of the relation
and we say it is \definend{$n$-ary}.
If the arity is~$2$ then it is a \definend{binary relation}.
In this case, where $(a_0,a_1)\in R$ we say 
that $a_0$ is~\definend{$R$-related} to~$a_1$,
sometimes written $a_0Ra_1$.
\end{df}

Observe that that if $\map{f}{D}{C}$ is a function then 
its graph is a relation on $D\times C$.

\begin{problem}
List five elements of each relation:
\begin{items}
\item $\setbuilder{(x,y)\in \N^2}{\text{$x$ and ~$y$ have the same parity}}$
\item less-than $<$, as a binary relation on $\N$
\item $\setbuilder{(x,y,z)\in\N^3}{x^2+y^2=z^2}$
\end{items}
\begin{answer}
\begin{items}
\item Five pairs from the relation are
  $\sequence{0,2}$, $\sequence{1,3}$, $\sequence{1,1}$, 
  $\sequence{0,4}$, 
 and~$\sequence{1,101}$.    
\item Five elements of this binary relation are 
  $\sequence{0,1}$, $\sequence{0,2}$, $\sequence{1,2}$, $\sequence{0,3}$,
  and~$\sequence{100,1001}$. 
\item Five elements of this $3$-ary relation are
  $\sequence{3,4,5}$, $\sequence{5,12,13}$, $\sequence{7,24,25}$, 
  $\sequence{8,15,17}$, and~$\sequence{0,0,0}$.
\end{items}
\end{answer}
\end{problem}

\begin{problem}
These are exercises in computing relations.
\begin{exes}
\begin{exercise}
  Consider the set~$A=\set{0,1}$.
  List all the elements of the relation 
  $E=\setbuilder{(x,y)\in A\times\powerset(A)}{x\in y}$.
\end{exercise}
\begin{answer}
  There are four: $\sequence{0,\set{0}}$, 
  $\sequence{1,\set{1}}$, $\sequence{0,\set{0,1}}$, 
  and~$\sequence{1,\set{0,1}}$.   
\end{answer}
\begin{exercise} 
  Let $\map{f}{D}{C}$ be a function.
  Show that 
  $R_f=\setbuilder{(x,y)\in D^2}{f(x)=f(y)}$
  is a binary relation.
  Where $f(x)=x^2$ with domain and codomain~$\R$,
  list five elements of $R_f$. 
\end{exercise}
\begin{answer}
  The set $R_f$ is a subset of the set of ordered pairs~$C^2$,
  so it is a binary relation on~$C$.

  Where $\map{f}{\R}{\R}$ is $f(x)=x^2$ then five elements are
  $\sequence{-1,1}$, $\sequence{-2,2}$, $\sequence{0,0}$,
  $\sequence{1,-1}$, and $\sequence{1,1}$.  
\end{answer}
\end{exes}
% \begin{exes}
% \item Show that if $\map{f}{D}{C}$ is a function then 
%   its graph is a relation.
% \item
%   Consider the set~$A=\set{0,1}$.
%   List all the elements of the relation 
%   $E=\setbuilder{(x,y)\in A\times\powerset(A)}{x\in y}$.
% \item Let $\map{f}{D}{C}$ be a function.
%   Show that 
%   $R_f=\setbuilder{(x,y)\in D^2}{f(x)=f(y)}$
%   is a binary relation.
%   Where $f(x)=x^2$ with domain and codomain~$\R$,
%   list five elements of $R_f$. 
% \end{exes}
% \begin{ans}
% \begin{exes}
% \item By definition its graph is a binary relation on~$D\times C$.
% \item There are four: $\sequence{0,\set{0}}$, 
%   $\sequence{1,\set{1}}$, $\sequence{0,\set{0,1}}$, 
%   and~$\sequence{1,\set{0,1}}$. 
% \item The set $R_f$ is a subset of the set of ordered pairs~$C^2$,
%   so it is a binary relation on~$C$.

%   Where $\map{f}{\R}{\R}$ is $f(x)=x^2$ then five elements are
%   $\sequence{-1,1}$, $\sequence{-2,2}$, $\sequence{0,0}$,
%   $\sequence{1,-1}$, and $\sequence{1,1}$.
% \end{exes}
% \end{ans}
\end{problem}

\begin{df} 
Let $R$ be a binary relation on a set~$X$.
The relation is \definend{reflexive} if $(x,x)\in R$ for all $x\in X$.
The relation is \definend{symmetric} if $(x,y)\in R$ implies that
$(y,x)\in R$ for all $x,y\in R$.
The relation is \definend{transitive} if 
$(x,y)\in R$ and $(y,z)\in R$ implies that 
$(x,z)\in R$ for all elements $x,y,z\in R$.
A relation that satisfies all three conditions is an
\definend{equivalence relation}.  
\end{df}

\begin{problem} 
  For each of the three conditions reflexive, symmetric, 
  or transitive,
  prove or disprove that the relation satisfies the condition.
\begin{exes}
\begin{exercise} 
  The ``goes into'' relation
  $D=\setbuilder{(d,m)\in\Z^2}{d\divides m}$.
\end{exercise}
\begin{answer}
  This relation is reflexive since each integer~$n\in Z$ 
  divides itself.
  It is not symmetric since $1\divides 2$ but $2\ndivides 1$.
  This relation is transitive by Exercise~\ref{ex:DivisibilityProperties}.
\end{answer}
\begin{exercise}
  For any set~$A$ the \definend{diagonal relation} on $A$ 
  is $\setbuilder{(a,a)}{a\in A}$. 
\end{exercise}
\begin{answer}
  This relation is reflexive since for any $a\in A$ we have that
  $(a,a)\in A$ (this is the minimal reflexive relation on~$A$).
  It is symmetric since if $(x,y)\in A$ then there is an
  $a\in A$ such that $x=y=a$, and so $(y,x\in A)$ also.
  Similarly it is transitive since if 
  $(x,y)\in A$ and~$(y,z)\in A$ then $x=y=z=a$ for some~$a\in A$, and
  thus $(x,z)\in A$.
\end{answer}
\begin{exercise}[\midlength]
  The relation on $\R$ of `at least two greater'
  $T=\setbuilder{(x,y)\in \R^2}{x-y\geq 2}$.
\end{exercise}
\begin{answer}
  This relation is not reflexive since $(0,0)\notin T$,
  and it is not symmetric since $(2,0)\in T$ but 
  $(0,2)\notin T$.
  This relation is transitive since if $(x,y)\in T$ and $(y,z)\in T$ 
  then $x-y\geq 2$ and~$y-z\geq 2$, so addition gives that $x-z\geq 4$.
\end{answer}
\end{exes}
% \begin{exes}
% \item The ``goes into'' relation
%   $D=\setbuilder{(d,m)\in\Z^2}{d\divides m}$.
% \item
%   For any set~$A$ the \definend{diagonal relation} on $A$ 
%   is $\setbuilder{(a,a)}{a\in A}$. 
% \item
%   The relation on~$\R$ of `at least two greater'
%   $T=\setbuilder{(x,y)\in \R^2}{x-y\geq 2}$.
% \end{exes}
% \begin{ans}
% \begin{exes}
% \item This relation is reflexive since each integer~$n\in Z$ 
%   divides itself.
%   It is not symmetric since $1\divides 2$ but $2\ndivides 1$.
%   This relation is transitive by Exercise~\ref{ex:DivisibilityProperties}.
% \item This relation is reflexive since for any $a\in A$ we have that
%   $(a,a)\in A$ (this is the minimal reflexive relation on~$A$).
%   It is symmetric since if $(x,y)\in A$ then there is an
%   $a\in A$ such that $x=y=a$, and so $(y,x\in A)$ also.
%   Similarly it is transitive since if 
%   $(x,y)\in A$ and~$(y,z)\in A$ then $x=y=z=a$ for some~$a\in A$, and
%   thus $(x,z)\in A$.
% \item This relation is not reflexive since $(0,0)\notin T$,
%   and it is not symmetric since $(2,0)\in T$ but 
%   $(0,2)\notin T$.
%   This relation is transitive since if $(x,y)\in T$ and $(y,z)\in T$ 
%   then $x-y\geq 2$ and~$y-z\geq 2$, so addition gives that $x-z\geq 4$.
% \end{exes}
% \end{ans}
\end{problem}

\begin{problem}[\midlength]
Recall that two integers have the same parity if they are both odd or 
both even.
Show that the binary relation 
$P=\setbuilder{(x,y)\in\Z^2}{\text{$x$ and $y$ have the same parity}}$  
is an equivalence.
\begin{answer}
For reflexivity, observe that a number has the same parity as itself.
For symmetry, if $(x,y)\in P$ then
two numbers have the same parity\Dash are either both even or both odd\Dash
and so $(y,x)\in P$.

The case of transitivity is as straightforward.
Suppose that both $(x,y)\in P$ and~$(y,z)\in P$.
Then $x$ and~$y$ have the same parity, and also $y$ and~$z$ have the same
parity, and consequently $x$ and~$z$ have the same parity.
So $(x,z)\in P$.  
\end{answer}
\end{problem}

\begin{problem}  \label{ex:EquivModMIsEquivalenceRelation}
Fix a divisor $m\in\Z^+$.
Show that the relation 
$\setbuilder{(a,b)\in\Z^2}{a\equiv b\pmod m}$  
is an equivalence.
\begin{answer}
  Call the relation~$M$.
  Exercise~\ref{ex:AEquivBpmodMIFFABDifferBYMultipleOfM}
  shows that for $m>0$ the statement $a\equiv b\pmod m$
  is equivalent to the statement that $m\divides (a-b)$, that
  the two differ by a multiple of~$m$.

  With that, reflexivity is clear because $m\divides (a-a)$.
  Symmetry is also clear because if $\sequence{a,b}\in M$ 
  then $a\equiv b\pmod m$, so
  $m\divides (a-b)$, and so $a-b=m\cdot k$ for some~$k\in\Z$.
  Switch signs to get $b-a=m\cdot(-k)$, and so $\sequence{b,a}\in M$.

  For transitivity, $\sequence{a,b}, \sequence{b,c}\in M$ gives
  $a-b=mk_0$ and $b-c=mk_1$ for some~$k_0,k_1\in Z$.
  Add: $(a-b)+(b-c)=m\cdot(k_0-k_1)$. 
  Then $a-c$ is a multiple of~$m$.
\end{answer}
\end{problem}

\begin{problem}[\maxlength]
  Characterize all of the binary relations on $A=\set{0,1}$
  as reflexive or not, symmetric or not,
  and transitive or not.
\begin{answer}
There are four ordered pairs in $A^2$.
We can describe all the relations by listing whether or not they
contain each of those four.
\begin{center}
  \begin{tabular}{cccc|ccc}
    $\sequence{0,0}$ &$\sequence{0,1}$ &$\sequence{1,0}$ &$\sequence{1,1}$
      &reflexive?  &symmetric?  &transitive?  \\ \hline
    $0$ &$0$ &$0$ &$0$ &$0$  &$1$  &$1$  \\ 
    $0$ &$0$ &$0$ &$1$ &$0$  &$1$  &$1$  \\ 
    $0$ &$0$ &$1$ &$0$ &$0$  &$0$  &$1$  \\ 
    $0$ &$0$ &$1$ &$1$ &$0$  &$0$  &$1$  \\ \hline
    $0$ &$1$ &$0$ &$0$ &$0$  &$0$  &$1$  \\ 
    $0$ &$1$ &$0$ &$1$ &$0$  &$0$  &$1$  \\ 
    $0$ &$1$ &$1$ &$0$ &$0$  &$1$  &$0$  \\ 
    $0$ &$1$ &$1$ &$1$ &$0$  &$1$  &$0$  \\ \hline
    $1$ &$0$ &$0$ &$0$ &$0$  &$1$  &$1$  \\ 
    $1$ &$0$ &$0$ &$1$ &$1$  &$1$  &$1$  \\ 
    $1$ &$0$ &$1$ &$0$ &$0$  &$0$  &$1$  \\ 
    $1$ &$0$ &$1$ &$1$ &$1$  &$0$  &$1$  \\ \hline
    $1$ &$1$ &$0$ &$0$ &$0$  &$0$  &$1$  \\ 
    $1$ &$1$ &$0$ &$1$ &$1$  &$0$  &$1$  \\ 
    $1$ &$1$ &$1$ &$0$ &$0$  &$1$  &$0$  \\ 
    $1$ &$1$ &$1$ &$1$ &$1$  &$1$  &$1$  
  \end{tabular}
\end{center}
\end{answer}
\end{problem}

\begin{problem} 
  There are eight combinations of reflexive or not, 
  symmetric or not, and transitive or not.
  For each, find a binary relation on $A=\set{0,1,2}$
  satisfying that combination.
\begin{answer}
  The first is a relation that is not reflexive, not symmetric, and
  not transitive.
  The relation~$R_0=\set{\sequence{0,1},\sequence{1,2}}$
  is not reflexive because it does not contain~$\sequence{0,0}$, 
  is not symmetric because while it contains~$\sequence{0,1}$
  it does not contain~$\sequence{1,0}$, and not transitive
  because it contains $\sequence{0,1}$ and~$\sequence{1,2}$
  but it does not contain~$\sequence{0,2}$.

  Next is a relation that is not reflexive and not symmetric but that is
  transitive.
  The relation~$R_1=\set{\sequence{0,1}}$
  is not reflexive because it does not contain~$\sequence{0,0}$,
  and is not symmetric because while it contains $\sequence{0,1}$ it does not
  contain~$\sequence{1,0}$.
  But it is transitive.
  For all cases where $R_1$ contains $\sequence{x,y}$ and~$\sequence{y,z}$
  it also contains~$\sequence{x,z}$. 
  (This is vacuously true; there are zero-many cases
  where it contains $\sequence{x,y}$ and~$\sequence{y,z}$
  because the only candidate for $\sequence{x,y}$ is~$\sequence{0,1}$
  and then $\sequence{0,1}$ cannot be $\sequence{y,z}$ since $y$ is~$1$.)

  Next is a relation that is not reflexive, is symmetric, and is 
  not transitive.
  One such is the relation~$R_2=A^2-\set{\sequence{2,2}}$.
  It is not reflexive since it does not contain~$\sequence{2,2}$.
  It is symmetric since for each~$\sequence{x,y}$ it contains~$\sequence{y,x}$,
  as it contains all pairs except $\sequence{2,2}$ and  
  $\sequence{x,y}=\sequence{2,2}$ is the symmetric image only of itself.
  It is not transitive since it contains~$\sequence{2,1}$ and~$\sequence{1,2}$
  but does not contain~$\sequence{2,2}$.

  Case~three is a relation that is not reflexive, but is symmetric and is 
  transitive.
  Consider $R_3=\set{0,1}^2
  =\set{\sequence{0,0},\sequence{0,1},\sequence{1,0},\sequence{1,1}}$.
  It is not reflexive because it does not contain~$\sequence{2,2}$.
  It is symmetric by inspection; for each of the four elements,
  $R_3$ contains the symmetric image.
  It is transitive because for any set~$B$, the relation $B^2$ is 
  transitive (it contains all pairs so it must contain the required pair), 
  and so~$\set{0,1}^2$ is transitive. 
  (Another example relation satisfying this case is the empty relation.)

  A relation that is reflexive, not symmetric, and not transitive is
  $R_4=\set{\sequence{0,0},\sequence{1,1},\sequence{2,2}}$.
  By inspection it is  reflexive and symmetric.
  It is transitive because the condition  
  $\sequence{x,y},\sequence{y,x}\in R_4$ is only met in the trivial case that
  $x=y$.

  Next comes a relation that is reflexive, is not symmetric, and is transitive.
  One such relation is 
  $R_5=\set{\sequence{0,0}, \sequence{1,1}, \sequence{2,2}, \sequence{0,1}}$.
  It is clearly reflexive.
  It is not symmetric because it contains~$\sequence{0,1}$ but 
  not~$\sequence{1,0}$.
  For transitive there are only two nontrivial matching cases:
  (i)~$\sequence{0,0},\sequence{0,1}\in R_5$ and~$\sequence{0,1}\in R_5$
  and
  (ii)~$\sequence{0,1},\sequence{1,1}\in R_5$ and~$\sequence{1,1}\in R_5$.

  Case~six is 
  a relation that is reflexive, symmetric, and not transitive.
  Consider the relation~$R_6
  =\set{\sequence{0,0}, \sequence{1,1}, \sequence{2,2}}
  \union\set{\sequence{0,1},\sequence{1,2},\sequence{1,0},\sequence{2,1}}$.
  By inspection it is reflexive and symmetric.
  It is not transitive because it contains $\sequence{0,1}$ and~$\sequence{1,2}$
  but does not contain~$\sequence{0,2}$.

  Finally, a relation that meets all three conditions
  is $R_7=A^2$.
  It is clearly reflexive.
  It is symmetric and transitive because both of those require that 
  if some pair or pairs are elements of~$R_7$ then another 
  pair is an element of~$R_7$.
  Since~$R_7$ contains all pairs, each implication must be
  satisfied.
\end{answer}
\end{problem}

% \begin{ex} \label{RationalsAsEqClasses}
% Consider the relation
% $\setbuilder{((p,q),(n,d))\in (\Z\times\Z^+)^2}{pd=qn}$
% (restated, the pair $(p,q)\\Z\times\Z^+$\ is related to the pair~$(n,d)$
% if $pd=qn$).
% List five elements.
% Prove that it is an equivalence relation.
% \begin{ans}
% Each element is a pair of pairs.
% Five elements are~$((1,2),(2,4))$, 
% $((-1,2),(2,-4))$,  
% $((0,1),(0,4))$,  
% $((3,3),(-2,-2))$,  
% and~$((10,5),(2,1))$.

% The relation is reflexive, each $(p,q)\in\Z\times\Z^+$ is related to itself, 
% because $pq=qp$. 
% To verify that it is symmetric assume that $(p,q)$ is related to~$(n,d)$.
% Then $pd=qn$, which gives $nq=dp$, and so $(n,d)$ is related to~$(p,q)$.

% To check that the relation is transitive assume that 
% $(p,q)$ is related to~$(n,d)$
% and also that $(n,d)$ is related to~$(a,b)$.
% Then $pd=qn$ and~$nb=da$.
% Multiply both sides of the first equation by $ab$ to get $pdab=qnab$, regroup as
% $pb\cdot(da)=qa\cdot(nb)$, and cancel $da=nb$ to get $pb=qa$.
% This shows that $(p,q)$ is related to $(a,b)$.  
% \end{ans}
% \end{ex}

\begin{problem}[\midlength] 
\label{PlaneLinesAsClasses}
Let $\mathcal{L}$ be the set of lines in the Euclidean plane and consider
the relation
$R=\setbuilder{(\ell_0,\ell_1)\in \mathcal{L}^2}{\text{the two are parallel, or the same}}$.
\begin{items}
\item List five elements.
% \item Fix a vertical line $\ell$ (for instance, the $x$-axis 
%   $\setbuilder{(x,0)}{x\in\R}$).
%   List five elements of $\mathcal{L}$ that are related to~$\ell$.
\item Show that $R$ is an equivalence
\end{items}
\begin{answer}
We can express the lines using analytic geometry, 
fixing a $xy$-axes, and giving the equations.
\begin{items}
\item Parallel lines have the same slope so
  five pairs are $(y=2x,y=2x+1)$, $(y=x,y=x-3)$, $(y=4x,y=4x)$,
  $(y=-3,y=-5)$, and~$(y=(3/2)x+1,y=(3/2)x-1)$.    
% \item   
%   Five lines related to a vertical line are~$x=1$, $x=2$, $x=-1$, $x=100$, 
%   and the line $x=0$~itself.
\item The relation is reflexive since two lines that are the same are
  explicitly given as related.
  The relation is symmetric since if $\ell_0$ is related to~$\ell_1$
  then they are parallel or the same, and in either case
  $\ell_1$ is related to~$\ell_0$.
  If $\ell_0$ is parallel to or the same as~$\ell_1$, 
  which is parallel or the same as~$\ell_2$ then $\ell_0$
  is parallel to or the same as~$\ell_2$, so the relation is
  transitive. 
\end{items}
\end{answer}
\end{problem}

\begin{problem}[\maxlength]
What is wrong with this purported proof that in the definition
of an equivalence relation, the condition of reflexivity is redundant?
``For any $x$, symmetry is that $x$ is related to~$y$ 
implies that $y$ is related to~$x$.
By transitivity we have $x$ is related to~$y$ and $y$ is related to~$x$ 
together imply that $x$ is related to~$x$.
Therefore, symmetry and transitivity together imply reflexivity.''  
\begin{answer}
Consider the relation   
$R=\set{\sequence{0,0},\sequence{0,1},\sequence{1,0},\sequence{1,1}}$
on the set~$A=\set{0,1,2}$.
This relation is symmetric and transitive but is not reflexive.
The implication `if $x$ is related to~$y$ then $y$ is related to~$x$'
is true in the case of $x=2$ and~$y=2$, but it is vacuously true.
\end{answer}
\end{problem}

\begin{df}
If $R$ is an equivalence relation on~$X$ then instead of $(x,y)\in R$
we may write $x\equiv y\pmod R$.
The \definend{equivalence class} of $x\in X$ is the set
$\eqclass{x}=\setbuilder{y\in X}{y\equiv x\pmod R}$.   
\end{df}

\begin{problem} Let $R$ be an equivalence on~$X$.
Prove that the following are equivalent statements for $x_0,x_1\in X$:
(i)~$x_0\equiv x_1\pmod R$
(ii)~$\eqclass{x_0}=\eqclass{x_1}$    
and (iii)~$\eqclass{x_0}\intersection\eqclass{x_1}\neq \emptyset$.
\begin{answer}
We will prove this three-long chain of implications: 
statement~(i) implies statement~(ii),
statement~(ii) implies statement~(iii),
and
statement~(iii) implies statement~(i).

First assume that statement~(i) holds, so that $x_0\equiv x_1\pmod R$.
The equivalence classes $\eqclass{x_0}$ and~$\eqclass{x_1}$ are sets so
we will prove that they are equal by mutual containment.
If $y\in\eqclass{x_0}$ then $y\equiv x_0 \pmod R$,
so $(y,x_0)\in R$, and so $(y,x_1)\in R$
(by transitivity, with $(x_0,x_1)\in R$),
showing that $y\in\eqclass{x_1}$.
Containment the other way is similar.
Thus statement~(i) implies statement~(ii).

That statement~(ii) implies statement~(iii) is trivial.

Finally, assume statement~(iii).
Let $y$ be an element of $\eqclass{x_0}\intersection\eqclass{x_1}$.
Then $y\equiv x_0\pmod R$ and~$y\equiv x_1\pmod R$,
that is, $(y,x_0)\in R$ and~$(y,x_1)\in R$.
The equivalence relation property of 
symmetry applied to $(y,x_0)\in R$ yields~$(x_0,y)\in R$.
Transitivity applied to the two $(x_0,y)\in R$ and~$(y,x_1)\in R$ yields
that $(x_0,x_1)\in R$, and so $x_0\equiv x_1\pmod R$.
Therefore~(iii) implies~(i).
\end{answer}
\end{problem}

\begin{df}
A \definend{partition}~$\partition{P}$ of a set $X$ is a 
collection of nonempty subsets of~$P\subseteq X$ such that every 
element $x\in X$ is in exactly one of the $P$'s.
That is, $\partition{P}$ partitions~$X$ if and only if each
$P\in\partition{P}$ is nonempty,
$\partition{P}$ \definend{covers}~$X$
(the union of all $P\in\partition{P}$ is equal to~$X$),
and the $P$ are \definend{pairwise disjoint}
(if $P\intersection \hat{P}\neq\emptyset$ then $P=\hat{P}$).
\end{df}

\begin{center}
  \grf{asy/bean_partition.pdf}{Set~$X$ partitioned into four parts $\partition{P}=\set{P_0,P_1,P_2,P_3}$}
\end{center}

\begin{problem} 
  Verify that~$\partition{P}$ is a partition of~$X$.  
  How many elements are in~$\partition{P}$?
\begin{exes}
\begin{exercise} 
  $X=\N$, $\partition{P}=\set{P_0,P_1}$, 
  where~$P_0$ is the set of even numbers
  and $P_1$ is the set of odd numbers
\end{exercise}
\begin{answer}
  To verify that it is a partition we will check the three conditions.
  First, that no element $P_i\in \partition{P}$ is empty is clear.
  Second, that every element of~$\N$ is an element of some~$P_i$ is
  also clear.
  The third is also clear; no element of~$\N$ is both even and odd.

  Finally, $\partition{P}$ has two elements since $P_0\neq P_1$.  
\end{answer}
\begin{exercise} 
      $X=\R$, $\partition{P}=\setbuilder{P_x}{x\in \R}$
      where $P_x=\setbuilder{y\in\R}{x-y\in \Z}$
      \hspace{0.75em}\hint some unequal reals $x_0\neq x_1$ 
      are associated with equal parts $P_{x_0}=P_{x_1}$  
      so what may naively appear to be two elements of~$\partition{P}$
      is actually a single element.
\end{exercise}
\begin{answer}
  Before we start we observe that there are $x_0,x_1\in\R$ such that
  $P_{x_0}=P_{x_1}$; an example is $x_0=0.25$ and~$x_1=1.25$.

  To prove that $\partition{p}$ is a partition, first note that $x\in P_x$.
  For this reason no~$P_x$ is empty and also
  every $x\in\R$ is an element of some~$P\in\partition{P}$.

  To show that the $P$'s are pairwise disjoint 
  we must show that
  if $P_x\intersection P_y\neq\emptyset$ then~$P_x=P_y$.
  So suppose that $z\in P_x\intersection P_y$.
  Then $x-z\in\Z$ and~$y-z\in \Z$.
  
  To prove that $P_x=P_y$ by mutual containment assume $a\in P_x$.
  Then $x-a\in\Z$.
  The expression $(y-z)-(x-z)+(x-a)$ is a combination of three integers,
  and so is an integer $y-a\in\Z$.
  Thus $a\in P_y$.
  Containment in the other direction is similar.

  This partition~$\partition{P}$ has infinitely many elements.
  One element is $P_{0.25}=P_{1.25}=\cdots$, and there is a $P$ for every
  number between zero and one.  
\end{answer}
\begin{exercise} 
     $X=\Z$, $\partition{P}=\setbuilder{P_n}{n\in\Z}$
      where $P_n=\setbuilder{i\in\Z}{i\equiv n\pmod 3}$
      % \hspace{0.75em}%
      % \hint some pairs $i\neq j$ have $P_i=P_j$. 
\end{exercise}
\begin{answer}
  Before we begin observe that 
  for some pairs $i,j\in\Z$ the sets $P_i$ and~$P_j$ are equal;
  one example is that $P_1=P_4$ (numbers in either set leave a remainder 
  of~$1$ on division by~$3$).

  No $P_n$ is empty because $n\in P_n$, as~$n\equiv n\pmod 3$.
  For the same reason every~$n\in\N$ is an element of at least
  one~$P$.

  To prove that the $P$'s are pairwise disjoint
  we will prove that if 
  $P_i\intersection P_j\neq \emptyset$ then $P_i=P_j$.
  Fix $x\in P_i\intersection P_j$, which implies that
  $x\equiv i\pmod 3$ and~$x\equiv j\pmod 3$.

  To verify that the two sets $P_i$ and~$P_j$ are equal by mutual
  containment, start with~$y\in P_i$.
  Then $y\equiv i\pmod 3$.
  Exercise~\ref{ex:EquivModMIsEquivalenceRelation}
  shows that the relation of `equivalent modulo~$3$' is an 
  equivalence relation.
  Symmetry implies that $i\equiv x\pmod 3$ and, 
  together with $y\equiv i\pmod 3$,
  transitivity implies that $y\equiv x\pmod 3$.
  Apply transitivity again, using $x\equiv j\pmod 3$, to conclude that
  $y\equiv j\pmod 3$. 
  Thus~$y\in P_j$.
  Containment in the other direction is similar.  

  Finally, $\partition{P}$ has three elements: 
  one is $P_0=P_3=P_{-3}=\cdots\hbox{}$ and the other two are
  $P_1=P_4=P_{-2}=\cdots{}$ and~$P_2=P_5=P_{-1}=\cdots\hbox{}$.  
\end{answer}
\end{exes}
% \begin{exes}
% \item $X=\N$, $\partition{P}=\set{P_0,P_1}$, 
%   where~$P_0$ is the set of even numbers
%   and $P_1$ is the set of odd numbers
% \item $X=\R$, $\partition{P}=\setbuilder{P_x}{x\in \R}$
%       where $P_x=\setbuilder{y\in\R}{x-y\in \Z}$
%       \hspace{0.75em}\hint some unequal reals $x_0\neq x_1$ 
%       are associated with equal parts $P_{x_0}=P_{x_1}$  
%       so what may naively appear to be two elements of~$\partition{P}$
%       is actually a single element.
% \item $X=\Z$, $\partition{P}=\setbuilder{P_n}{n\in\Z}$
%       where $P_n=\setbuilder{i\in\Z}{i\equiv n\pmod 3}$
%       % \hspace{0.75em}%
%       % \hint some pairs $i\neq j$ have $P_i=P_j$. 
% \end{exes}
% \begin{ans}
% \begin{exes}
% \item To verify that it is a partition we will check the three conditions.
%   First, that no element $P_i\in \partition{P}$ is empty is clear.
%   Second, that every element of~$\N$ is an element of some~$P_i$ is
%   also clear.
%   The third is also clear; no element of~$\N$ is both even and odd.

%   Finally, $\partition{P}$ has two elements since $P_0\neq P_1$.
% \item Before we start we observe that there are $x_0,x_1\in\R$ such that
%   $P_{x_0}=P_{x_1}$; an example is $x_0=0.25$ and~$x_1=1.25$.

%   To prove that $\partition{p}$ is a partition, first note that $x\in P_x$.
%   For this reason no~$P_x$ is empty and also
%   every $x\in\R$ is an element of some~$P\in\partition{P}$.

%   To show that the $P$'s are pairwise disjoint 
%   we must show that
%   if $P_x\intersection P_y\neq\emptyset$ then~$P_x=P_y$.
%   So suppose that $z\in P_x\intersection P_y$.
%   Then $x-z\in\Z$ and~$y-z\in \Z$.
  
%   To prove that $P_x=P_y$ by mutual containment assume $a\in P_x$.
%   Then $x-a\in\Z$.
%   The expression $(y-z)-(x-z)+(x-a)$ is a combination of three integers,
%   and so is an integer $y-a\in\Z$.
%   Thus $a\in P_y$.
%   Containment in the other direction is similar.

%   This partition~$\partition{P}$ has infinitely many elements.
%   One element is $P_{0.25}=P_{1.25}=\cdots$, and there is a $P$ for every
%   number between zero and one.
% \item  Before we begin observe that 
%   for some pairs $i,j\in\Z$ the sets $P_i$ and~$P_j$ are equal;
%   one example is that $P_1=P_4$ (numbers in either set leave a remainder 
%   of~$1$ on division by~$3$).

%   No $P_n$ is empty because $n\in P_n$, as~$n\equiv n\pmod 3$.
%   For the same reason every~$n\in\N$ is an element of at least
%   one~$P$.

%   To prove that the $P$'s are pairwise disjoint
%   we will prove that if 
%   $P_i\intersection P_j\neq \emptyset$ then $P_i=P_j$.
%   Fix $x\in P_i\intersection P_j$, which implies that
%   $x\equiv i\pmod 3$ and~$x\equiv j\pmod 3$.

%   To verify that the two sets $P_i$ and~$P_j$ are equal by mutual
%   containment, start with~$y\in P_i$.
%   Then $y\equiv i\pmod 3$.
%   Exercise~\ref{ex:EquivModMIsEquivalenceRelation}
%   shows that the relation of `equivalent modulo~$3$' is an 
%   equivalence relation.
%   Symmetry implies that $i\equiv x\pmod 3$ and, 
%   together with $y\equiv i\pmod 3$,
%   transitivity implies that $y\equiv x\pmod 3$.
%   Apply transitivity again, using $x\equiv j\pmod 3$, to conclude that
%   $y\equiv j\pmod 3$. 
%   Thus~$y\in P_j$.
%   Containment in the other direction is similar.  

%   Finally, $\partition{P}$ has three elements: 
%   one is $P_0=P_3=P_{-3}=\cdots\hbox{}$ and the other two are
%   $P_1=P_4=P_{-2}=\cdots{}$ and~$P_2=P_5=P_{-1}=\cdots\hbox{}$.
% \end{exes}
% \end{ans}
\end{problem}

\begin{problem} \label{ex:EquivClassesFormPartition}
Prove.
\begin{exes}
\begin{exercise} 
  Where $R$ is an equivalence, 
  the collection of equivalence classes 
  $\setbuilder{\eqclass{x}}{x\in X}$ forms a partition of~$X$.
  We say that it is the partition \definend{induced} by the relation.
\end{exercise}
\begin{answer}
  Let $\partition{P}$ be the collection $\setbuilder{\eqclass{x}}{x\in X}$.
 
  Note that $x\in\eqclass{x}$ by reflexivity.
  Thus no element of the partition is empty, and 
  every element of~$X$ is in some element of the partition.

  We must prove that the elements of~$\partition{P}$ are pairwise disjoint:
  if $\eqclass{x}\intersection\eqclass{y}\neq\emptyset$
  then~$\eqclass{x}=\eqclass{y}$ are equal.
  So suppose that $z\in\eqclass{x}\intersection\eqclass{y}$.
  Then $z\equiv x\pmod R$ and~$z\equiv y\pmod R$.

  To show the equality of the sets $\eqclass{x}$ and~$\eqclass{y}$ 
  by mutual inclusion, assume $a\in\eqclass{x}$.
  Then $a\equiv x\pmod R$.
  From $z\equiv x\pmod R$, symmetry gives $x\equiv z\pmod R$.
  Apply transitivity to $a\equiv x\pmod R$ and~$x\equiv z\pmod R$ to
  derive that $a\equiv z\pmod R$.
  With that and $z\equiv y\pmod R$, transitivity gives
  that $a\equiv y\pmod R$. 
  Thus $a\in\eqclass{y}$.
  Containment in the other direction is similar.    
\end{answer}
\begin{exercise} 
  Where $\partition{P}$ is a partition of~$X$, 
  the relation 
  $R=\setbuilder{(x,y)\in X^2}{\text{$x$ and~$y$ are in the same part}}$ 
  is an equivalence.
  We say that this relation \definend{arises from} the partition. 
\end{exercise}
\begin{answer}
  Suppose that $\partition{P}$ is a partition. 

  The relation~$R$ is reflexive because any~$x\in X$ is an element of
  the same part as itself
  (the parts $P\in\partition{P}$ are sets and the set~$P$ containing~$x$
  is known to contain~$x$).
  The relation~$R$ is symmetric because if $x$ is in the same part as~$y$
  then $y$ is in the same part as~$x$.

  For transitivity assume that $x,y,z\in X$ are such that 
  $x$ is in the same part as~$y$, and 
  $y$ is in the same part as~$z$.
  That is, there is a $P\in\partition{P}$ such that
  both $x$ and~$y$ are elements of~$P$, 
  and also both $y$ and~$z$ are elements of~$P$.
  Clearly then both $x$ and~$z$ are in the same part, $P$.  
\end{answer}
\end{exes}
% \begin{exes}
% \item Where $R$ is an equivalence, 
%   the collection of equivalence classes 
%   $\setbuilder{\eqclass{x}}{x\in X}$ forms a partition of~$X$.
%   We say that it is the partition \definend{induced} by the relation.
% \item Where $\partition{P}$ is a partition of~$X$, 
%   the relation 
%   $R=\setbuilder{(x,y)\in X^2}{\text{$x$ and~$y$ are in the same part}}$ 
%   is an equivalence.
%   We say that this relation \definend{arises from} the partition. 
% \end{exes}
% \begin{ans}
% \begin{exes}
% \item Let $\partition{P}$ be the collection $\setbuilder{\eqclass{x}}{x\in X}$.
 
%   Note that $x\in\eqclass{x}$ by reflexivity.
%   Thus no element of the partition is empty, and 
%   every element of~$X$ is in some element of the partition.

%   We must prove that the elements of~$\partition{P}$ are pairwise disjoint:
%   if $\eqclass{x}\intersection\eqclass{y}\neq\emptyset$
%   then~$\eqclass{x}=\eqclass{y}$ are equal.
%   So suppose that $z\in\eqclass{x}\intersection\eqclass{y}$.
%   Then $z\equiv x\pmod R$ and~$z\equiv y\pmod R$.

%   To show the equality of the sets $\eqclass{x}$ and~$\eqclass{y}$ 
%   by mutual inclusion, assume $a\in\eqclass{x}$.
%   Then $a\equiv x\pmod R$.
%   From $z\equiv x\pmod R$, symmetry gives $x\equiv z\pmod R$.
%   Apply transitivity to $a\equiv x\pmod R$ and~$x\equiv z\pmod R$ to
%   derive that $a\equiv z\pmod R$.
%   With that and $z\equiv y\pmod R$, transitivity gives
%   that $a\equiv y\pmod R$. 
%   Thus $a\in\eqclass{y}$.
%   Containment in the other direction is similar.  
% \item Suppose that $\partition{P}$ is a partition. 

%   The relation~$R$ is reflexive because any~$x\in X$ is an element of
%   the same part as itself
%   (the parts $P\in\partition{P}$ are sets and the set~$P$ containing~$x$
%   is known to contain~$x$).
%   The relation~$R$ is symmetric because if $x$ is in the same part as~$y$
%   then $y$ is in the same part as~$x$.

%   For transitivity assume that $x,y,z\in X$ are such that 
%   $x$ is in the same part as~$y$, and 
%   $y$ is in the same part as~$z$.
%   That is, there is a $P\in\partition{P}$ such that
%   both $x$ and~$y$ are elements of~$P$, 
%   and also both $y$ and~$z$ are elements of~$P$.
%   Clearly then both $x$ and~$z$ are in the same part, $P$.
% \end{exes}
% \end{ans}
\end{problem}

\begin{problem}
Suppose that $\map{f}{D}{C}$.
\begin{exes}
\begin{exercise} 
  Show that the relation
  $R=\setbuilder{(d_0,d_1)\in D^2}{f(d_0)=f(d_1)}$ 
  is an equivalence on~$D$.
\end{exercise} 
\begin{answer}
  The relation~$R$ is reflexive because $f(d)=f(d)$ for any $d\in D$.
  It is symmetric because if $f(d_0)=f(d_1)$ then~$f(d_1)=f(d_0)$.
  It is transitive because if $f(d_0)=f(d_1)$ and also~$f(d_1)=f(d_2)$ 
  then $f(d_0)=f(d_2)$.  
\end{answer}
\begin{exercise} 
  Show that the set of inverse images 
  $\partition{P}=\setbuilder{f^{-1}(c)}{c\in C}$ form a partition of the domain.
\end{exercise}
\begin{answer}
  They are the equivalence classes of the relation in the prior 
  item.
  By Exercise~\ref{ex:EquivClassesFormPartition} they form a
  partition of the domain.  
\end{answer}
\begin{exercise} 
  Consider the map
  $\map{\hat{f}}{\partition{P}}{C}$ whose action is given by:
  $\hat{f}(P)=f(d)$ where $d\in P$.
  Show that~$\hat{f}$ is a function, and that it is one-to-one.
\end{exercise}
\begin{answer}
  To show that $\hat{f}$ is a function we need to show that
  it is well-defined.
  For this, note that $f(d_0)=f(d_1)$ for all $d_0,d_1\in P$
  by definition of the parts~$P$, so 
  the value of~$\hat{f}$ is the same no matter which representative~$d\in P$
  is used to compute that value.
  Restated, $\hat{f}(P)=c$ where $P=f^{-1}(c)$.

  To show that $\hat{f}$ is one-to-one suppose that $\hat{f}(P_0)=\hat{f}(P_1)$.
  Then $f(d_0)=f(d_1)$ for some $d_0\in P_0$ and~$d_1\in P_1$.
  Since $f$ gives the same value on these two arguments,
  the two are in the same inverse image and so  
  by the definition of the parts as the inverse images,
  $P_0=P_1$.  
\end{answer}
\begin{exercise} 
  Show that if $f$ is onto then so is~$\hat{f}$.
\end{exercise}
\begin{answer}
  If $f$ is onto then for any $c\in C$ there is a~$d\in D$
  such that $f(d)=c$.
  So one of the equivalence classes~$P$ that is an element of~$\partition{P}$ 
  is the set of 
  $d\in D$ such that $f(d)=c$.
  Then $\hat{f}(P)=c$.  
\end{answer}
\end{exes}
% \begin{exes}
% \item Show that the relation
%   $R=\setbuilder{(d_0,d_1)\in D^2}{f(d_0)=f(d_1)}$ 
%   is an equivalence on~$D$. 
% \item Show that the set of inverse images 
%   $\partition{P}=\setbuilder{f^{-1}(c)}{c\in C}$ form a partition of the domain.
% \item Consider the map
%   $\map{\hat{f}}{\partition{P}}{C}$ whose action is given by:
%   $\hat{f}(P)=f(d)$ where $d\in P$.
%   Show that~$\hat{f}$ is a function, and that it is one-to-one.
% \item Show that if $f$ is onto then so is~$\hat{f}$.
% \end{exes}
% \begin{ans}
% \begin{exes}
% \item The relation~$R$ is reflexive because $f(d)=f(d)$ for any $d\in D$.
%   It is symmetric because if $f(d_0)=f(d_1)$ then~$f(d_1)=f(d_0)$.
%   It is transitive because if $f(d_0)=f(d_1)$ and also~$f(d_1)=f(d_2)$ 
%   then $f(d_0)=f(d_2)$.
% \item They are the equivalence classes of the relation in the prior 
%   item.
%   By Exercise~\ref{ex:EquivClassesFormPartition} they form a
%   partition of the domain.
% \item  To show that $\hat{f}$ is a function we need to show that
%   it is well-defined.
%   For this, note that $f(d_0)=f(d_1)$ for all $d_0,d_1\in P$
%   by definition of the parts~$P$, so 
%   the value of~$\hat{f}$ is the same no matter which representative~$d\in P$
%   is used to compute that value.
%   Restated, $\hat{f}(P)=c$ where $P=f^{-1}(c)$.

%   To show that $\hat{f}$ is one-to-one suppose that $\hat{f}(P_0)=\hat{f}(P_1)$.
%   Then $f(d_0)=f(d_1)$ for some $d_0\in P_0$ and~$d_1\in P_1$.
%   Since $f$ gives the same value on these two arguments,
%   the two are in the same inverse image and so  
%   by the definition of the parts as the inverse images,
%   $P_0=P_1$.
% \item If $f$ is onto then for any $c\in C$ there is a~$d\in D$
%   such that $f(d)=c$.
%   So one of the equivalence classes~$P$ that is an element of~$\partition{P}$ 
%   is the set of 
%   $d\in D$ such that $f(d)=c$.
%   Then $\hat{f}(P)=c$.
% \end{exes}
% \end{ans}
\end{problem}

\begin{df}
A binary relation~$R$ is \definend{antisymmetric} if
$(x,y)\in R$ and $(y,x)\in R$ implies that $x=y$.
A relation is a \definend{partial ordering} if it is 
reflexive, antisymmetric, and transitive.  
\end{df}

\begin{problem} Prove each.
\begin{exes}
\begin{exercise}[\midlength]
  The usual less than or equal to relation~$\leq$ on 
  the real numbers is a partial order.
\end{exercise}
\begin{answer}
  We must show that it is reflexive, antisymmetric, and transitive.
  Reflexive is trivial\Dash for any $r\in\R$ we have $r\leq r$.
  Antisymmetric is also easy since if $r_0\leq r_1$ and~$r_1\leq r_0$
  then $r_0=r_1$.
  And transitive is no harder because if $r_0\leq r_1$ and~$r_1\leq r_2$
  then $r_0\leq r_2$.  
\end{answer}
\begin{exercise} 
  The relation `divides' on $\N$ is a partial order.
\end{exercise}
\begin{answer}
  This is like the prior item in that we just cite known results.
  To show this relation is reflexive just recall that for all $a\in\N$ we have
  $a\divides a$.
  Antisymmetric is that if $a\divides b$ and~$b\divides a$ then
  $a=b$.
  (\remark antisymmetric would not hold if the relation were over
  $\Z$ because there the two $a\divides b$ and~$b\divides a$ together imply
  only that $a=\pm b$.)
  Transitive is the statement that $a\divides b$ and~$b\divides c$ imply
  that $a\divides c$, which appears
  in the Divisibility Properties, Exercise~\ref{ex:DivisibilityProperties}.  
\end{answer}
\begin{exercise} 
  For any set~$A$ the relation $\subseteq$ on $\powerset(A)$ is
  a partial order.
\end{exercise}
\begin{answer}
  This is reflexive since $A\subseteq A$.
  This is antisymmetric by mutual containment: 
  if $A_0\subseteq A_1$ and~$A_1\subseteq A_0$ then the two are equal.
  This is transitive by Exercise~\ref{ex:PropertiesOfSubset}, 
  the Properties of Subset.  
\end{answer}
\end{exes}
% \begin{exes}
% \item The usual less than or equal to relation~$\leq$ on 
% the real numbers is a partial order.
% \item The relation `divides' on $\N$ is a partial order.
% \item For any set~$A$ the relation $\subseteq$ on $\powerset(A)$ is
% a partial order.
% \end{exes}
% \begin{ans}
% \begin{exes}
% \item We must show that it is reflexive, antisymmetric, and transitive.
%   Reflexive is trivial\Dash for any $r\in\R$ we have $r\leq r$.
%   Antisymmetric is also easy since if $r_0\leq r_1$ and~$r_1\leq r_0$
%   then $r_0=r_1$.
%   And transitive is no harder because if $r_0\leq r_1$ and~$r_1\leq r_2$
%   then $r_0\leq r_2$.
% \item This is like the prior item in that we just cite known results.
%   To show this relation is reflexive just recall that for all $a\in\N$ we have
%   $a\divides a$.
%   Antisymmetric is that if $a\divides b$ and~$b\divides a$ then
%   $a=b$.
%   (\remark antisymmetric would not hold if the relation were over
%   $\Z$ because there the two $a\divides b$ and~$b\divides a$ together imply
%   only that $a=\pm b$.)
%   Transitive is the statement that $a\divides b$ and~$b\divides c$ imply
%   that $a\divides c$, which appears
%   in the Divisibility Properties, Exercise~\ref{ex:DivisibilityProperties}.
% \item This is reflexive since $A\subseteq A$.
%   This is antisymmetric by mutual containment: 
%   if $A_0\subseteq A_1$ and~$A_1\subseteq A_0$ then the two are equal.
%   This is transitive by Exercise~\ref{ex:PropertiesOfSubset}, 
%   the Properties of Subset.
% \end{exes}
% \end{ans}
\end{problem}

\begin{problem}
Can a relation be both symmetric and antisymmetric?  
\begin{answer}
Yes.
One example is the empty relation $R=\emptyset$ on any set.
Another example is the relation of equality 
$R=\setbuilder{(x,x)}{x\in\N}$ on $\N$.
\end{answer}
\end{problem}





%===================================================
% \ifbool{optioncompact}{}{\include{infinity}}


%===================================================
% \ifbool{optioncompact}{}{\include{appendix}}
\end{document}


TODO