ibl.tex

% One and only one of the next two lines should be uncommented
\documentclass{ibl}  % for making book
% \documentclass[compact]{ibl}  % 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{Numbers}

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 with sign} 
\label{ex:InteractionOfParityWithSign}
\pord.
\begin{exes}
  \begin{exercise}
    If a number is even then its negative is even.
    If a number is odd then its negative is odd.
  \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.  

    Following the prior paragraph, we will 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 paragraph 
    shows that $n$ is even.
    Thus $n$ is even if and only if $-n$ is even.

    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$.
    In addition, $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}
    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)$.

    For the absolute value there are two cases.
    In 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 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 $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}
\end{exes}
\end{problem}

\begin{problem} \notetext{Interaction of parity and multiplication}
Prove the first, and prove or disprove the second.
\begin{exes}
\begin{exercise}
  The product of two evens is even.
  Generalize to any divisor~$d$.  
\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.  

  The first paragraph 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 paragraph could also generalize to: a product of two multiples of
  $d$ is a multiple of~$d^2$.)
\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}
\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}
  Every 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$.
   That is, if $n$ divides~$m$ then so do $n$'s divisors.
\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}  \label{exer:ComparisonDivisibility}
  \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}
\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{answer}
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{answer}
\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}
  The 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}
\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 simply 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$.
That is, ($*$) with $k=0$ says that $S(0)$ implies~$S(1)$, and with the $S(0)$
verification we conclude that $S(1)$ holds.
Then ($*$) with $k=1$ says that $S(0)$ and~$S(1)$ together imply~$S(2)$, 
so we know that $S(2)$ holds.
% 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 larger numbers.
Here 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}
\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}
\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 use~$2$ for the base.
\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}[\maxlength] 
    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{problem}

\begin{problem}[\midlength]
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 \definend{Fibonacci number sequence}
$0,1,1,2,3,5,8,13, \ldots$ is defined by the condition that 
each succeeding number is the sum of the 
prior two $f_{n+1}=f_n+f_{n-1}$, subject to 
$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 it 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 integers $a,b$ with $b>0$ there are unique integers $q,r$ such that 
both $a=bq+r$ and~$0\leq r<b$.
Here $a$ is called the \definend{dividend}, $b$ is the \definend{divisor}, 
$q$ is the \definend{quotient}, and $r$ is the \definend{remainder}.
% 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 three stages.
\begin{exes} 
\begin{exercise}
  Show that~$q$ and~$r$ are unique, assuming that they exist.
  (One way to proceed is to suppose that $a=bq_0+r_0=bq_1+r_1$
   with $0\leq r_0,r_1 <b$ and then show that $q_0=q_1$ and~$r_0=r_1$.)
\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}
  Verify the statement for $a=0$.
  Show that if it holds when~$a>0$ then it holds
  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 note that the set $\setbuilder{a-bq}{q\in\Z}$
  has nonnegative elements and
  apply the Least Number Principle
  to produce the desired~$r$.
\end{exercise}
\begin{answer}
  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}
\end{exes}
\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] Prove.  % \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$,
where $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 do 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}
\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}
\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}
\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.
\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.
  (To prove this last statement, let $m$ be the maximum of $a$ and~$b$
  and consider the set 
  $\setbuilder{m-d}{\text{$d$ is a common divisor of $a$ and~$b$}}$.
  This is a finite, nonempty, set of natural numbers and so has a least element.
  The associated~$d$ is the greatest common divisor.)  
\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 than 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 by definition $\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} 
\end{problem}

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

\begin{df}
The \definend{least common multiple} of two integers $\lcm(a,b)$ 
is the smallest positive integer that is a multiple of each, except that 
it is $0$ if $a$ or~$b$ is $0$.
\end{df}

\begin{problem} Prove each.
\begin{items}
\item \notetext{Existence} Any two integers have a least common multiple.
\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 positive common multiples is not empty.
  The Least Element Principle gives that this set 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}
\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}  
\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}
\end{problem}
% ========== End Euclid's argument of lemma =========== 
\end{euclidproof}


% ========== Start Bezout argument of lemma =========== 
\begin{bezoutproof}
\begin{problem}\notetext{Euclid's Algorithm}
Prove that if $a=bq+r$ then $\gcd(a,b)=\gcd(b,r)$.  
\begin{answer}
With $a=bq+r$, any common divisor of $b$ and~$r$ on the right
also divides~$a$ on the left, 
by Exercise~\ref{ex:DividesAndLinearCombinations}, Linearity.
Thus any common divisor of $b$ and~$r$ is a common divisor of $a$ and~$b$,
and so any common divisor of $b$ and~$r$ is less than the greatest common
divisor $\gcd(a,b)$, by Exercise~\ref{ex:DivisibilityProperties}.\ref{exer:ComparisonDivisibility}
In particular, $\gcd(b,r)\leq\gcd(a,b)$.

Rewrite the equation as $r=a-bq$. 
By similar reasoning\Dash
any common divisor of $a$ and~$b$ is also a common divisor of $r$
and~$b$, implying that any
common divisor of $a$ and~$b$ is less than $\gcd(b,r)$\Dash
we get that in particular $\gcd(a,b)\leq \gcd(b,r)$.
So the two greatest common divisors are equal.

\smallskip
\textit{Alternative proof.}\hspace{1em}
Because $a=bq+r$, any common divisor of $b$ and~$r$ also divides~$a$, 
by Exercise~\ref{ex:DividesAndLinearCombinations}, Linearity.
Thus any common divisor of $b$ and~$r$ is a common divisor of $a$ and~$r$.
Rewrite the equation as $r=a-bq$ and then for the same reason any
common divisor of $a$ and~$b$ also divides~$r$, and so any
common divisor of $a$ and~$b$ is a common divisor of $b$ and~$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 quickly finds the greatest common
divisor for any $a,b\in\Z$ with $a\geq 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)$.
Continuing as though we hadn't noticed the answer is~$11$,
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 remainder of $0$ signals that 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 $123$, $54$
\item $48$, $732$
\end{items}
\begin{answer}
\begin{items}
\item The first step is
  $123=54\cdot 2+15$, followed by $54=15\cdot 3+9$, 
  then $15=9\cdot 1+6$, then $9=6\cdot 1+3$,
  and finally
  $6=3\cdot 2+0$, showing that $\gcd(123,54)=3$.

  Here are the steps for reversing.
  \begin{align*}
    3 &=1\cdot 9-1\cdot 6  \\
      &=1\cdot 9-1\cdot(15-1\cdot 9)=-1\cdot 15+2\cdot 9 \\
      &=-1\cdot 15+2\cdot(54-3\cdot 15)=2\cdot 54-7\cdot 15 \\
      &=2\cdot 54-7\cdot(123-2\cdot 54)=-7\cdot 123+16\cdot 54
  \end{align*}
  This expresses $\gcd(123,54)=3$ as a linear combination of
  $123$ and~$54$.
\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 natural 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. 
\end{answer}
\end{exes}
\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 smallest
  positive value of $\setbuilder{s\cdot ma+t\cdot mb}{s,t\in\Z}$.
  This equals $m$ times the smallest 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$.
  (From this it follows that 
  if $a$ and~$b$ are nonzero then $a/gcd(a,b)$ and $b/\gcd(a,b)$
  are relatively prime.)
\end{exercise}
\begin{answer}
  Apply the prior item, taking $m$ to be~$d$, 
  and also taking $a$ to be~$a/d$ and $b$ to be~$b/d$
  (since $d$ is a common divisor, the results of these divisions are
  integers).
  That gives $\gcd(a,b)=d\cdot\gcd(a/d,b/d)$.
  Divide both sides by~$d$
  (again, the result is an integer).       
\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}
\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}[\maxlength]
Verify 
\begin{items}
\item there are twenty five primes less than one hundred
\item below fifty there are six pairs \definend{twin primes}, two primes
  separated by two
\item the numbers $2^{2^0}+1$, \ldots, $2^{2^4}+1$ are prime.
\end{items}
\begin{answer}
Verification that each of these is prime is easy with a pocket calculator
or a computer script.
\begin{items}
\item 
  They are $2$, $3$, $5$, $7$, $11$, $13$, $17$, $19$, $23$, $29$, $31$, 
  $37$, $41$, $43$, $47$, $53$, $59$, $61$, $67$, $71$, $73$, $79$, $83$, 
  $89$, and~$97$.
\item 
  They are  $(3, 5)$, $(5, 7)$, $(11, 13)$, $(17, 19)$, 
  $(29, 31)$, and~$(41, 43)$.
\item
  The numbers $3$, $5$, $17$, $257$, and~$65537$ are prime.
\end{items}
\end{answer}
\end{problem}

\begin{problem} Prove.
\begin{exes}
\begin{exercise} 
  An integer $n>1$ is composite if and only if it has factors $n=a\cdot b$ 
  (they may be equal) 
  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 it has 
  factors $n=a\cdot b$ that are not trivial\Dash it is not the case that
  one of them is~$1$ and the other~$n$.
  By one of the divisibility properties 
  Exercise~\ref{ex:DivisibilityProperties}, both divisors are less than or
  equal to~$n$.
  They must both be strictly less than~$n$ because by choice of $a,b$ they
  are not trivial factors, and if one were~$n$ then the other would have to
  be~$1$.
  For the same reason neither equals~$1$.

  By a property of the interaction with sign
  Exercise~\ref{ex:InteractionOfParityWithSign}
  we know that if $a|n$ then so also $-a|n$.
  Thus, without loss of generality we can assume 
  that $a$ is positive.
  So, $1<a<n$.
  
  It remains to show that the same is true of~$b$.
  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$.
  We have already shown~$b$ must be less than~$n$.   
\end{answer}
\begin{exercise} 
  Every number greater than $1$ has a prime divisor.
\end{exercise}
\begin{answer}
  We use induction.
  The base step is that the number is~$n=2$, which has the prime divisor 
  of~$2$.

  For the inductive step suppose that the statement is true for the cases 
  $n=2$, \ldots, $n=k$ and consider the case~$k+1$.
  If $k+1$ is prime then thehe 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 in particular~$a$ 
  has at least one prime factor, which is then a prime factor of $k+1$
  (by transitivity of divisibility).  
\end{answer}
\begin{exercise} 
  Every composite number $n>1$ has a prime divisor~$p$ 
  with $p\leq \sqrt{n}$. 
  This inequality cannot be made strict.
\end{exercise}
\begin{answer}
  Because~$n>1$ is composite there are numbers~$a,b\in\Z$ with
  $1<a,b<n$ and $n=ab$.
  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 these factors must be less than or equal 
  to~$\sqrt{n}$.

  We next show that $n$ has a factor that is prime and is less than or
  equal to $\sqrt{n}$.
  Let $c$ be a factor of~$n$ with $c\leq\sqrt{n}$.
  Then $c$ has a prime factor~$p$, which
  is a factor of~$n$ by the transitivity of divisibility. 
  In addition, $P$
  less than or equal to~$c$ by the comparison property of divisibility
  and therefore
  it is less than or equal to~$\sqrt{n}$.    

  Finally, to see that the inequality cannot be made strict take $n=4$.  
\end{answer}
\end{exes}
\end{problem}                   

\begin{problem} \notetext{Euclid's Theorem}
There are infinitely many primes.  
\begin{answer}
For a contradiction, assume otherwise,
that there are finitely many primes 
$p_0=2$, $p_1=3$, \ldots, $p_{n-1}$.

Multiply them and add one $m=(p_0\cdot p_1\cdots p_{n-1})+1$.
This number is greater than~$1$ because it is greater than 
$p_0\cdot p_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~$p_i$.
But dividing~$m$ by any~$p_i$ 
leaves a remainder of~$1$, which
is a contradiction. 
Hence a finite
list of primes is an impossibility.

\textit{Alternate proof.}
For contradiction suppose there are finitely many primes
$2,3,\ldots,p_k$, let $n$ be the product $2\cdot 3\cdots p_k$,
and consider $n-1$.
Since $n-1$ is greater than each prime (as $n$ is greater than
$3\cdot\cdots p_k$ by a factor of $2$), 
some prime $p_i$ divides~$n-1$.
But then $p_i$ divides $n-(n-1)=1$, which 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 $p$ and~$a$ are relatively prime, 
  so 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.
  The base step is $n=2$, that there are two numbers in the product, which
  is proved in the prior item.

  For the inductive step assume that the statement is true for $n=2$, \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}
\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}  
  Any number $n>1$ can be expressed as a product of primes
  $n=p_1^{e_1}p_2^{e_2}\cdots p_k^{e_k}$, and this expression is 
  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 into a product of primes in ascending order will give the
  same result. 
  We prove this in two parts.
\begin{exes}
\begin{exercise} 
  Prove that any $n>1$ can be written as a product of one or more primes.
\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 into two smaller numbers \
  $k+1=a\cdot b$.
  Because these two are smaller
  the inductive hypothesis applies, so each is a product of 
  primes, and so
  $k+1$ is a product of primes.  
\end{answer}
\begin{exercise} 
  Prove that the factorization is unique.
  \hint~you can 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.
  In this case $p_0=q_0\cdots q_{t-1}$, giving a nontrivial factorization of 
  this prime unless $t=1$ and $p_o=q_0$.

  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
  the above result~\ref{ex:EuclidsOtherLemma} shows that
  $p_s$ divides some $q_i$.
  Because $q_i$ is prime we have 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}=n/q_i=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 $s-1=t-1$ and in members 
  $p_0=q_0$, \ldots, $p_{s-1}=q_{t-1}$. 
  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}
\end{problem}

\noindent\remark had we
included~$1$ among the primes then factorization would not be unique
since to any existing factorization we could multiply by 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 abandon unique factorization and 
allow that some exponents are zero).
Prove that
in the prime factorization of
$\gcd(a,b)$ the exponent of $p_i$ is $\min(e_i,f_i)$.
(The proof that in the prime factorization of $\lcm(a,b)$ the exponent of 
$p_i$ is $\max(e_i,f_i)$ is much the same.)
\begin{answer}
  Let $d=\gcd(a,b)$ and consider its prime factorization.
  If $p$ is a prime that divides~$a$ (or~$b$) then
  by \ref{ex:EuclidsOtherLemma} above, $p$ must be one of 
  $p_0$, \ldots, $p_{n-1}$.   
  Accordingly, 
  write the prime factorization of~$d$ as $p_0^{g_0}\cdots p_n^{g_n}$. 
  If for each $i$ we have $g_i=\min(e_i,f_i)$ then $d$~divides both $a$ and~$b$,
  so each exponent $g_i$ is at least as large as $\min(e_i,f_i)$.
  To see that it cannot be larger suppose $g_i>\min(e_i,f_i)$
  and also suppose without loss of generality that $\min(e_i,f_i)=e_i$.
  Expand
  $d\cdot k=a$.
  \begin{equation*}
    p_0^{g_0}\cdots p_i^{g_i}\cdots p_{n-1}^{g_{n-1}}\cdot k
       =p_0^{e_0}\cdots p_i^{e_i}\cdots p_{n-1}^{e_{n-1}}
  \end{equation*}
  This contradicts the uniqueness of prime factorization
  because there are more 
  $p_i$'s on the left than on the right.  
\end{answer}
\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 is raised to an even power.
\end{exercise}
\begin{answer}
  The square is 
  $n^2=(p_0^{e_0}\cdots p_{s-1}^{e_{s-1}})^2=p_0^{2e_0}\cdots p_{s-1}^{2e_{s-1}}$.
  So each prime occurs an even number of times.  
\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 (possibly zero).
  On the left, the prime factorization of~$n^2$ has $2$ raised to an even power
  also, and there is an additional~$2$.
  Thus the left has an odd number of~$2$'s while the right has
  and even number of~$2$'s, which
  contradicts the uniqueness of prime factorizations.   
\end{answer}
% \begin{exercise}[\maxlength] 
%   Prove that $\sqrt{17}$ is irrational. % College Math Journal Jan 2013 pp 53
% \end{exercise}
% \begin{answer}
%   If $\sqrt{17}=n/d$ for $n,d\in\Z$ then $17d^2=n^2$.
%   Expand $d$ and~$n$ into their prime factorizations.
%   Then on the left is an odd number of $17$'s while on the right
%   is an even number, which contradicts uniqueness of 
%   prime factorization. 
% \end{answer}
\end{exes}
\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 avoid
confusion between this and
the subset relation defined below.
As a synonym for set we sometimes say ``collection.''

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''; some authors use a colon~$:$ instead
of a vertical bar).

\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 sets are equal because they contain the same elements, 
  $1$, $3$, and~$5$.
\item These sets are equal because they contain the same elements, 
  $2$, $4$, and~$6$.
\item These sets are not equal because the set on the right contains~$0$
  while the set on the left does not.
\item This is false. 
  The set on the right has three elements, 
  and none of the three is the number~$0$.
  In particular, $\set{0}$ is not equal to~$0$ since it is a set and
  not a number.
\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, provided that $x\in B$ implies that~$x\in A$.
We write $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, for each element of the set
  on the left, $1$, $3$, and~$5$, it 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 because $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. 
\begin{exes}
\begin{exercise} 
   For all sets $A$, both $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, the implication is vacuously true).  
\end{answer}
\begin{exercise} 
  The empty set is unique: if the set~$A$ is empty and 
  the set~$B$ is empty then $A=B$.
\end{exercise}
\begin{answer}
  If $A=\emptyset$ and~$B=\emptyset$ then the two have the
  same elements: the statement `$x\in A$ if and only if~$x\in B$' holds   
  for all $x$.
\end{answer}
\end{exes}
\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}
   Suppose that $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$.
   Thus $x\in A$ implies that $x\in C$, and therefore~$A\subseteq C$.  
\end{answer}
\end{exes}
\end{problem}

\begin{problem}[\maxlength] 
For each, give an example of three sets satisfying the conditions,
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{7}$, $B=\set{2,7}$, $C=\set{1,3,5,7}$
\item $A=\set{5,7}$, $B=\set{2}$, $C=\set{1,3,5,7}$
\item $A=\set{5,7}$, $B=\set{3,7}$, $C=\set{1,3,5,7}$
\end{items}
\end{ans}
\end{problem}

In this book we 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 that 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}$ (or $\mathbb{1}_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 allows sets to contain anything.
This turns out to be naive. 
For, if sets can contain anything then we naturally think of 
the set that contains everything, all sets. 
Note that it has itself as an element.
So, consider the set of all sets that don't contain themselves as 
elements~$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}
\end{problem}






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

\begin{df}
The \definend{complement} of a set~$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 we consider the set of things than than~$100$ then we can
take the complement 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 collection of elements 
from either set 
$A\union B=\setbuilder{x}{\text{$x\in A$ or $x\in B$}}$.  
Their \definend{intersection} is the collection 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 darker color 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 dark region, the complement, is all but the set~$A$.

\begin{problem}
Another tool 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}
We use $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 of these simple results about set operations, 
apply the statement to the sets $A$ and~$B$.
Also pick one 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}
For convenience here is the defintion of the sets again, as well
as a Venn diagram.
\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}
    \hspace*{3em}
    \vcenteredhbox{\includegraphics{asy/venn_two.pdf}}
\end{center}
\begin{items}
\item  Applied to the set~$A$, the complement is 
  $\setcomp{A}=\set{0,1}$ while
  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}$ and
  so $a\in\setcomp{(\setcomp{A})}$.
  Thus $A\subseteq\setcomp{(\setcomp{A})}$.

  Inclusion in the other direction is similar.
  If $x\in\setcomp{(\setcomp{A})}$
  then $x\notin\setcomp{A}$ and
  by definition of the complement $x\in\setcomp{A}$.
  Thus $\setcomp{(\setcomp{A})}\subseteq A$. 
\item The set $A\intersection\emptyset$ 
  is the collection of
  elements of~$\universalset$ that are members of both~$A$ and~$\emptyset$,
  so applied to $A=\set{2,3}$ and $\universalset=\set{0,1,2,3}$ it 
  is~$\set{}$.
  The second one is just as trivial: the collection of all of the members of 
  $\universalset=\set{0,1,2,3}$ that are members of either~$A=\set{2,3}$
  or~$\emptyset=\set{}$ is~$\set{2,3}$.

  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 either $x\in A$ or~$x\in\emptyset$,
  which is equivalent to $x\in A$.
\item The first statement applied to the set $A=\set{2,3}$
  says that the collection of members of both
  $\set{2,3}$ and~$\set{2,3}$ is the set~$A=\set{2,3}$.
  The second statement is similar.

  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 The statement has two containments.
  The application of the statement on the left is that 
  $A\intersection B=\set{3}\subseteq A=\set{2,3}$.
  On the right the application is~$A=\set{2,3}\subseteq A\union B=\set{1,2,3}$.

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

  The right-hand containment's argument is that
  $x\in A$ implies that $x\in A$ or~$x\in B$, and so $A\subseteq A\union B$.
\item For the intersections the application gives that 
  $A\intersection B$ is the collection of elements common to 
  $\set{2,3}$ and $\set{1,3}$, which is $\set{3}$,
  and $B\intersection A=\set{3}$ also.
  The application to the statement about unions is similar: 
  $A\union B=\set{1,2,3}=B\union A$.

  For the proof 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 connective
  `or' is also commutative.
\item This is a three set relationship so 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] \hline
         $1$    &$0$       &$0$       &$4$    \\
         $1$    &$0$       &$1$       &$5$    \\
         $1$    &$1$       &$0$       &$6$    \\
         $1$    &$1$       &$1$       &$7$    
    \end{tabular}
    \hspace*{3em}
    \vcenteredhbox{\includegraphics{asy/venn_three.pdf}}
  \end{center}
  To apply associativity of 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}$.
  Associativity of union is similar.

  The proof that intersection is associative goes
  $(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 the connective `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 logical equivalence
is very like the first so here we only show the first.

The first equivalence has two directions.
For the (i) implies~(ii) direction assume that $A\subseteq B$. 
To show that $A\union B=B$ we do mutual inclusion.
One of those inclusions, that $B\subseteq A\union B$, holds by the definition 
of union.
So, we only need to show that $A\union B\subseteq B$.
For that, let $x$~be an element of $A\union B$ and then
there are two cases, that $x\in A$ or that $x\in B$, and
we must verify that $x\in B$ in both cases.
Verification of the second case, the $x\in B$ case, is trivial,
while verification of the other case is 
immediate from the $A\subseteq B$ assumption.

To get the (ii) implies~(i) direction, assume that $A\union B=B$.
Aiming to show that $A\subseteq B$, assume that $x\in A$.
Then $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] 
  For any two sets,  
  $A-B=A\intersection\setcomp{B}$
  (and thus $A-B\subseteq A$).
\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$.
  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}$, which gives
  $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}
  This is true since
  $A\symdiff B=(A-B)\union(B-A)=(B-A)\union(A-B)=B\symdiff A$.
\end{answer}
\end{exes}
\end{problem}

\begin{problem}
\notetext{De Morgan's Laws}  Prove, for all sets $A$, $B$, and~$C$.
\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, for any
  values of $P$ and~$Q$, as `not($P$) or not($Q$)'.

  We show  $\setcomp{(A\intersection B)}=\setcomp{A}\union\setcomp{B}$
  by mutual containment.
  The other identity is similar.  

  Suppose first that $x\in \setcomp{(A\intersection B)}$.
  Then $x\notin A\intersection B$, so 
  either $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)}$.  

  \remark we could combine those paragraphs into a single chain of 
  double implications, that 
  $x\in \setcomp{(A\intersection B)}$ holds if and only if
  $x\notin A\intersection B$, which is true if and only if 
  either $x\notin A$ or~$x\notin B$,
  which in turn is true if and only if $x\in \setcomp{A}\union\setcomp{B}$.  
\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}
\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
  As with many set examples, 
  to get this one we used the three-set table repeated below with
  the diagram.
  Think of it as listing eight regions that could either be occupied or not.
  We want to have the overlap of all three, area~$7$, empty.
  But we want the pairwise overlaps, areas $3$, $5$, and~$6$, to 
  be nonempty.
  \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}
    \hspace*{3em}
    \vcenteredhbox{\includegraphics{asy/venn_three.pdf}}
  \end{center}
\end{answer}
\end{problem}

\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|$.
% \begin{ans}    
% Since $A$ finite we can list its elements
% $A=\set{a_0,\ldots,a_{n-1}}$.
% Similarly, $B$ is finite so we can list its elements, and because
% $A\subseteq B$, the elements of $A$ are elements of~$B$.
% Thus $B=\set{a_0,\ldots,a_{n-1},b_n,\ldots,b_k}$. 
% Clearly then $|A|\leq |B|$.
% \end{ans}
% \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 the elements of each power set
  $\powerset(\set{0,1})$,   
  $\powerset(\set{0,1,2})$,   
  $\powerset(\set{0})$, and   
  $\powerset(\emptyset)$.
  Find the order of each.   
\begin{answer}
The power set of the two-element set 
$\powerset(\set{0,1})=\set{\emptyset, \set{0}, \set{1}, \set{0,1}}$
has four elements, that is, is of order four.
The power set of the three-element set 
\begin{equation*}
  \powerset(\set{0,1,2})=\set{\emptyset,\set{0},\set{1},\set{2},
                             \set{0,1},\set{1,2},\set{0,2},\set{0,1,2}}
\end{equation*}
has eight elements.
The power set of the singleton $\set{0}$ has two elements
$\powerset(\set{0})=\set{\emptyset,\set{0}}$.
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{items}
\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{items}
\begin{answer}
\begin{items}
\item    
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.

\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 the first, $x$ is also an element of the second.
  In this case the subset~$\set{\emptyset}$ has only one element to check,
  it is indeed 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)$.   
\end{items}
\end{answer}
\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 use induction on the number of elements in~$A$.
The base step is that~$A$ is empty and so 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}$.
Elements $S\in\powerset(A)$\Dash that is, subsets~$S\subseteq A$\Dash
fall into one of two categories: either $a_k\notin S$ or $a_k\in S$.
The inductive hypothesis gives that 
the number of subsets in the first category is $2^{k}$.
Showing that 
the second category also contains~$2^{k}$-many elements will finish the proof
because then
the total of the two categories is 
$2^{k}+2^{k}=2\cdot(2^{k})=2^{k+1}$.

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, this collection has $2^{k}$-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}
A \definend{sequence} $\seq{x_0, x_1, \ldots, x_{n-1}}$
is an ordered list of its \definend{terms} 
$x_0$, $x_1$, \ldots, $x_{n-1}$.
Its \definend{length} $\lh(\seq{x_0, x_1, \ldots, x_{n-1}})$
is the number of terms~$n$.
Two sequences are equal if and only if
they have the same length and
the same terms, in the same order. 
\end{df}

\begin{problem}\pord:
\begin{items}
\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 sequences are not equal because they differ in the first term.
\item These are unequal because 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}$}}$.
We write $A^n$ for for the 
Cartesian product of $n$~equal sets $A\times\cdots\times A$.
\end{df}

Note the distinction between the diamond brackets $\sequence{\cdots}$ 
that denote sequences and the curly braces $\set{\cdots}$ for sets. 
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 may write $\R^2=\setbuilder{(x,y)}{x,y\in\R}$ for the
Cartesian plane.

\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\subseteq 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 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$.
  Similarly, $A\times\emptyset=\emptyset$.
 
  For the other implication, 
  if neither set is empty then there exist some $a\in A$ and~$b\in B$, so 
  $(a,b)\in A\times B$, and thus $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}
  An example where $A\times B\neq B\times A$ is if 
  $A=\set{0}$ and~$B=\set{1}$.
  Then $A\times B=\set{\sequence{0,1}}$ while
  $B\times A=\set{\sequence{1,0}}$ and the two sets are not equal.

  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 in general.
%   For instance, if $A=\set{0}$, $B=\set{1}$, and $C=\set{2}$ then 
%   $(A\times B)\times C=\set{\sequence{\sequence{0,1},2}}$
%   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{0,\sequence{1,2}}}$ 
%   also has a single element that is a sequence with two terms, 
%   the first element here is not a sequence. 
% 
%   \remark we could prove that they are equal only if one of them is empty.  
% \end{answer}
\begin{exercise} 
  Show that this statement is false: 
  $A\times B\subseteq \hat{A}\times \hat{B}$ if and only if
  $A\subseteq \hat{A}$ and $B\subseteq \hat{B}$.
  Patch the statement to make it true.
\end{exercise}
\begin{answer}
  The example 
  $A=\emptyset$, $B=\set{1,2}$, $\hat{A}=\set{a}$, $\hat{B}=\set{1}$
  shows that the statement is false since 
  $A\times B=\emptyset\subseteq \hat{A}\times \hat{B}$ but 
  $B\not\subseteq \hat{B}$.

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

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

  Now assume that $A\not\subseteq \hat{A}$ (the case 
  of $B\not\subseteq \hat{B}$ is similar) and that $a\in A$ 
  but~$a\notin \hat{A}$.
  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 \hat{A}\times \hat{B}$,
  and so $A\times B\neq \hat{A}\times \hat{B}$.     
\end{answer}
\end{exes}
\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)$.
  What is the interaction of Cartesian product and intersection?
\end{exercise}
\begin{answer}
  For union we will use mutual containment.
  For the left-to-right direction
  assume 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$.   

  As to intersection,
  $(A\intersection B)\times C = (A\times C)\intersection (B\times C)$.
  The membership relation $\sequence{x,c}\in (A\intersection B)\times C$
  holds if and only if both
  $x\in A\intersection B$ and~$c\in C$.
  That is true 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}
  Fix the universal set~$\universalset=\Z$.
  If
  $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}
\end{problem}











%===================================================
\chapter{Functions and relations}
% http://gowers.wordpress.com/2009/06/08/why-arent-all-functions-well-defined/
\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$ or $d\mapsto c$ 
and say that $c$ is the \definend{image} of $d$ 
or that $d$ \definend{maps to}~$c$.

A \definend{bean diagram} pictures sets as blobs and 
either shows the entire function 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}

\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}

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 consists of arbitrary pairings.


\begin{problem}[\midlength]
This \textit{hailstone function} $\map{h}{\N}{\N}$ is defined by cases,
\begin{equation*}
  h(n)=\begin{cases}
         n/2  &\text{-- if $n$ is even}  \\
         3n+1 &\text{-- otherwise}
       \end{cases}
\end{equation*}
using a different formula when the input is even than when it is odd.
\begin{items}
  \item Compute $h(n)$ for $n=0$, \ldots, $n=9$.
  \item Starting with $n=6$ iterate the function, that is, 
    compute $h(n)$, then $h(h(n))$, etc., until the result is $1$.
    How many steps does it take?
  \item How many steps does it take starting with $n=11$?
\end{items}
(The \textit{Collatz conjecture} is that for every natural number starting
value, iteration will eventually reach~$1$.
No one knows if it is true.)
\begin{answer}
\begin{items}
  \item $h(0)=0$, $h(1)=4$, $h(2)=1$, $h(3)=10$, $h(4)=2$, $h(5)=16$,
    $h(6)=3$, $h(7)=22$, $h(8)=4$, $h(9)=28$. 
  \item $h(6)=3$, $h(C(6))=10$, etc.
    It takes eight steps: from $6$, to~$3$, and to~$10$, to~$5$, 
    then~$16$, after that~$8$, and~$4$, then~$2$, and finally~$1$.
  \item Starting with $11$ takes fourteen steps, with successive 
    values $11$, $34$, $17$, $52$, $26$, $13$, $40$, $20$, $10$, $5$, 
    $16$, $8$, $4$, $2$, and~$1$.   
\end{items}
\end{answer}
\end{problem}

We are often not careful about 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 of this blurring, 
in the sentence following the definition.)
The distinction between function and graph
is there only because the graph does not determine the codomain and
so we must specify it separately.
(The graph, however, does determine the domain.)

In the edge case that the domain is the empty set, the only function possible
is the empty set of ordered pairs.

\begin{problem}[\maxlength]
Show that 
$\setbuilder{\sequence{q,n}\in \Q^+\!\!\times\Z^+}{\text{$n$ is $q$'s numerator}}$ 
is not the graph of a function.
\begin{answer}
It is not well-defined.
The rational number $1/2$ can be written $2/4$, in which case the numerator 
is different.  
\end{answer}
\end{problem}

\begin{problem}[\maxlength]
When $D$ and $C$ are finite sets,
how many functions 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 the function
$\map{f}{\R^2}{\R}$ whose action is 
$\sequence{x,y}\mapsto x^2-2y^2$.
We typically write 
$f(x,y)$ rather than
$f(\sequence{x,y})$.
We say this $f$ is a \definend{$2$-ary} function (similarly there
are $3$-ary functions, etc.);
the number of arguments is the function's \definend{arity}.

\begin{df}
The \definend{range} of $\map{f}{D}{C}$ is 
$\range(f)=\setbuilder{y\in C}{\text{there is an $x\in D$ such that $f(x)=y$}}$
(it is also denoted $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$
(we also say 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}$.
In the other direction, 
the \definend{inverse image of the element}~$c\in C$ is
the set $f^{-1}(c)=\setbuilder{d\in D}{f(d)=c}$, and 
the \definend{inverse image of the set}~$A\subseteq C$
is $f^{-1}(A)=\setbuilder{d\in D}{f(d)\in A}$.   
\end{df}

Observe that $f^{-1}(c)$ is a set,
not an element.

\begin{problem}
\begin{items}
Where $\map{f}{\R-\setbuilder{n\pi/2}{n\in\Z}}{\R}$ 
is the function $f(x)=\tan(x)$
\item find the image under $f$ of the interval
$\leftclosed{\pi/4}{\pi/2}=\setbuilder{x\in\R}{\pi/4\leq x<\pi/2}$
\item find the image of the set \set{-\pi/3}
\item find the inverse image of the number $1$
% \item find the inverse image of the interval
%   $\closed{16}{25}=\setbuilder{y\in\R}{16\leq y\leq 25}$
\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 There are many angles with a tangent of $1$ so the
  solution is the set $\setbuilder{(\pi/4)+n\pi}{n\in \N}$.
% \item It is the infinite union of intervals
%  $\setbuilder{\closed{\arctan(16)+n\pi}{\arctan(25)+n\pi}}{n\in \N}$.
\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}
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 some $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}

Read $\composed{g}{f}$ aloud as ``$g$ circle $f$'' 
or as~``$g$ composed with $f$''
(or~``$g$ following $f$'').
Note that while
in the expression $\composed{g}{f}$ the $g$ is read 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 of~$f$ but instead is a superset of its range).


\begin{problem} Let $D=\set{0,1,2}$, $C=\set{a,b,c,d}$, 
and $B=\set{\alpha,\beta,\gamma}$ (these letters are not variables, they are
distinct set elements).
Let $\map{f}{D}{C}$ be given by $0\mapsunder{} a$, $1\mapsunder{} c$, 
$2\mapsunder{} d$ and let $\map{g}{C}{B}$
be 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 that 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 outputs from $g$ are not the inputs
  to~$f$, that is, 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
$\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 to~$\R$,
but the formula is~$\composed{f}{g}(x)=(3x+1)^2=9x^2+6x+1$.
\end{answer}
\end{problem}

\begin{problem} Prove each.
\begin{items}
\item
  \notetext{Associativity} 
  $\composed{h}{(\composed{g}{f})}=\composed{(\composed{h}{g})}{f}$    
\item
  Function composition need not be commutative.
\end{items}
\begin{answer}
\begin{items}
\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
  An example of noncommutativity is $\map{f,g}{\R}{\R}$ given by 
  $f(x)=x+2$ and $g(x)=3x+4$.
  Then $\composed{f}{g}\,(x)=3\cdot(x+2)+4=3x+10$ while
  $\composed{g}{f}\,(x)=(3x+4)+2=3x+6$.
\end{items}
\end{answer}
\end{problem}





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

The definition of a function specifies that for every input 
there is exactly one associated output.
This is asymmetric because the 
definition puts no such condition on 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 all 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)=3\cdot ((c-1)/3)+1=(c-1)+1=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}
\end{problem}

\begin{problem}   \label{CorrespondingSetsHaveSameNumberOfElements}
  Prove that, 
  where $D$ and~$C$ are finite sets, 
  if there is a correspondence~$\map{f}{D}{C}$
  then the two have the same number of elements.
  We do this in two halves, each of which is useful on its own.
\begin{exes}
\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.
  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}
\begin{exercise}
  If $f$ is onto then $|C|\leq |D|$.
\end{exercise}
\begin{answer}
  Assume that $\map{f}{D}{C}$ is onto.
  We will prove the statement by induction on the number of elements in
  the domain~$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 
  (otherwise there would be an element of the codomain with no inverse
  image).
  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.
  Aiming to apply the inductive hypothesis, 
  pick some $d_0\in D$ and put it aside by considering 
  $\hat{D}=D-\set{d_0}$ (because this is the $k+1$ case there is at least
  one such element in~$D$).

  There are two cases:
  wither the codomain element $f(d_0)$ is also the image of another domain
  element, some $d\in\hat{D}$, or else it is not.
  In the first case the restriction $\restrictionmap{f}{\hat{D}}$ is onto
  and so the inductive hypothesis applies, giving that 
  $|C|\leq |\hat{D}|<|D|$.

  In the other case, that $d_0$ is the only element of~$D$ associated 
  by~$f$ with the codomain element~$f(d_0)$, let $\hat{C}=C-\set{f(d_0)}$.
  The map~$\map{\restrictionmap{f}{\hat{D}}}{\hat{D}}{\hat{C}}$ is clearly onto.
  So the inductive hypothesis applies: $|\hat{C}|\leq |\hat{D}|$.
  Therefore $|\hat{C}|+1=|C|\leq |D|=|\hat{D}|+1$.
\end{answer}
\end{exes}
\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.
  (With the prior item this gives that a
  composition of correspondences is a correspondence.)
\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} 
  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 for a contradiction 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} 
  Do the other two cases hold? 
\end{exercise}
\begin{answer}
  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}$, $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 onto because $\composed{g}{f}\,(0)=\alpha$ and
  $\composed{g}{f}\,(1)=\beta$.
  But $f$ is not onto because no element of its domain~$D$ is mapped to the
  element $a$ of its codomain~$C$. 
  \begin{center}
    \includegraphics{asy/bean_fcn_onto_counter.pdf}
  \end{center}
  The same function is an example of a composition $\composed{g}{f}$ 
  that is one-to-one but where
  the function performed second~$g$ is not one-to-one.
\end{answer}
\end{exes}
\end{problem}

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

\begin{df}
Given $\map{f}{D}{C}$,
if $\composed{g}{f}$ is the identity function then 
$g$~is a \definend{left inverse} function of~$f$, or what is the
same thing, $f$ is a \definend{right inverse} of~$g$.
If $g$ is both a left and right inverse of~$f$ then
it is an \definend{inverse}
(or a \definend{two-sided inverse}) of~$f$, denoted $f^{-1}$. 
\end{df}

Earlier we defined
$f^{-1}(c)=\setbuilder{d\in D}{f(d)=c}$.
Do not be mislead by this\Dash 
the earlier notation is standard but it is confusing in that it
does not imply that the function has an inverse.

\begin{problem} Show each.
\begin{exes}
\begin{exercise}
Let the map from three-space to the plane $\map{g}{\R^3}{\R^2}$
be projection $(x,y,z)\mapsto(x,y)$
and let $\map{f}{\R^2}{\R^3}$ be injection
$(x,y)\mapsto(x,y,0)$.
Then $g$ is a left inverse of~$f$ but not a right inverse.
\end{exercise}
\begin{answer}
It is a left inverse because $\composed{g}{f}$ has the action
$(x,y)\mapsto(x,y,0)\mapsto(x,y)$ for all $x$ and~$y$.
It is not a right inverse because there is an 
input on which the composition $\composed{f}{g}$ is not the identity, namely
the action is 
$(1,2,3)\mapsto(1,2)\mapsto(1,2,0)$.
\end{answer}
\begin{exercise}
The function $\map{f}{\Z}{\Z}$ given by $f(n)=n^2$ has no left inverse function.
\end{exercise}
\begin{answer}
Observe that $f(2)=f(-2)=4$.
To be a left inverse, any $g$ would have to send $4$ to~$2$ and to send
$4$ to~$-2$ as well.
Since that would make~$g$ be not well-defined, there is no left inverse 
function.   
\end{answer}
\begin{exercise}
Where $D=\set{0,1,2,3}$ and $C=\set{\alpha,\beta}$,
the function $\map{f}{D}{C}$ given by
$0\mapsto \alpha$, $1\mapsto\beta$, $2\mapsto\alpha$, $3\mapsto\beta$
has more than one right inverse.  
\end{exercise}
\begin{answer}
One right inverse is $\map{g_0}{C}{D}$ given by $\alpha\mapsto 0$, 
$\beta\mapsto 1$.
A second is  
$\map{g_1}{C}{D}$ given by $\alpha\mapsto 2$, 
$\beta\mapsto 3$.
\end{answer}
\end{exes}
\end{problem}

\begin{problem} 
Compute each:
\begin{items}
\item 
  where $\map{f}{\Z}{\Z}$ is~$f(a)=a+3$ and 
  $\map{g}{\Z}{\Z}$ is $g(a)=a-3$,
  show that $g$ is inverse to $f$
\item
  where $\map{h}{\Z}{\Z}$ is 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
  if $\map{s}{\R^+}{\R^+}$ is~$s(x)=x^2$,
  find $s$'s inverse
\end{items}
\begin{ans}
\begin{items}
\item
  First, 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~$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
  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{items}
\end{ans}
\end{problem}

\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 since no input is sent to $\beta$.) 
\item If a $h$ 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.
\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)=c$ for some $c\in C$.
  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$ are each 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.
  Here is the verification that one order gives the identity function   
  $\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$
  and the verification of the other order is similar.  
\end{answer}
\end{exes}
\end{problem}





% .....................................
\section{Relations}
A function's graph is a set of pairs,
subject to the condition that the input determines the output.
We next generalize functions 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
(we say $R$ is \definend{$n$-ary}).

If the arity is~$2$ then it is a \definend{binary relation}.
In this case, where $\sequence{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}

\begin{problem}
List five elements of each relation:
\begin{items}
\item $\setbuilder{\sequence{x,y}\in \N^2}{
     \text{$x$ and ~$y$ have the same parity}}$
\item less-than $<$, as a binary relation on $\N$
\item $\setbuilder{\sequence{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}
Compute these.
\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}
\end{problem}

\begin{df} 
Let $R$ be a binary relation on a set~$X$.
The relation is \definend{reflexive} if $\sequence{x,x}\in R$ for all $x\in X$.
The relation is \definend{symmetric} if $\sequence{x,y}\in R$ implies that
$\sequence{y,x}\in R$ for all $x,y\in R$.
The relation is \definend{transitive} if 
$\sequence{x,y}\in R$ and $\sequence{y,z}\in R$ implies that 
$\sequence{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{\sequence{d,m}\in\Z^2}{d\divides m}$.
\end{exercise}
\begin{answer}
  This relation is reflexive since each integer~$n\in Z$ 
  divides itself (in particular, $0\divides 0$).
  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{\sequence{a,a}}{a\in A}$. 
\end{exercise}
\begin{answer}
  This relation is reflexive since for any $a\in A$ we have that
  $\sequence{a,a}\in A$ (this is the minimal reflexive relation on~$A$).
  It is symmetric since if $\sequence{x,y}\in A$ then there is an
  $a\in A$ such that $x=y=a$, and so $\sequence{y,x}\in A$ also.
  Similarly it is transitive since if 
  $\sequence{x,y}\in A$ and~$\sequence{y,z}\in A$ then $x=y=z=a$ 
  for some~$a\in A$, and
  thus $\sequence{x,z}\in A$.
\end{answer}
\begin{exercise}[\midlength]
  The relation on $\R$ of `at least two greater'
  $T=\setbuilder{\sequence{x,y}\in \R^2}{x-y\geq 2}$.
\end{exercise}
\begin{answer}
  This relation is not reflexive since $\sequence{0,0}\notin T$,
  and it is not symmetric since $\sequence{2,0}\in T$ but 
  $\sequence{0,2}\notin T$.
  This relation is transitive since if $\sequence{x,y}\in T$ and 
  $\sequence{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}
\end{problem}

% \begin{problem}[\midlength]
% Show that the binary relation 
% $P=\setbuilder{\sequence{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 $\sequence{x,y}\in P$ then
% the two numbers have the same parity\Dash they 
% are either both even or both odd\Dash
% and so $\sequence{y,x}\in P$.

% Suppose, to prove transitivity, that both $\sequence{x,y}\in P$ 
% and~$\sequence{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 $\sequence{x,z}\in P$.  
% \end{answer}
% \end{problem}

\begin{problem}  \label{ex:EquivModMIsEquivalenceRelation}
Fix a divisor $m\in\Z^+$.
Show that the relation 
$\setbuilder{\sequence{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 that
  $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}[\midlength] 
\label{PlaneLinesAsClasses}
Let $\mathcal{L}$ be the set of lines in the Euclidean plane and consider
the relation
$R=\setbuilder{\sequence{\ell_0,\ell_1}\in \mathcal{L}^2}{\text{the two are parallel, or are equal}}$.
\begin{items}
\item List five elements of~$R$ 
\item where $\ell$ is a vertical line, 
  list five elements of $\mathcal{L}$ that are related to~$\ell$
\item show that it is an equivalence
\end{items}
\begin{answer}
We can express the lines using analytic geometry, by
fixing axes and giving equations.
\begin{items}
\item Parallel lines have the same slope so
  five example pairs are $\sequence{y=2x,y=2x+1}$, 
  $\sequence{y=x,y=x-3}$, 
  $\sequence{y=4x,y=4x}$,
  $\sequence{y=-3,y=-5}$, 
  and~$\sequence{y=(3/2)x+1,y=(3/2)x-1}$.    
\item   
  Five example 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.
  It 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$.
  For transitivity, if $\ell_0$ is parallel to or the same as~$\ell_1$, 
  which itself is parallel or the same as~$\ell_2$, then $\ell_0$
  is parallel to or the same as~$\ell_2$. 
\end{items}
\end{answer}
\end{problem}


\begin{problem}[\maxlength]
  Consider all of the binary relations on $A=\set{0,1}$.
  Characterize each as reflexive or not, symmetric or not,
  and transitive or not.
\begin{answer}
There are four length~$2$ sequences (that is, ordered pairs) in $A^2$.
We can describe all the relations by listing whether or not they
contain each of those four.
Here we write $0$ or~$1$ instead of $F$ or~$T$ so that the relation's
subscript written in binary describes its members.
\begin{center}
  \def\adjrel#1{\makebox[1.5em][l]{#1}} % make R's come out left-adjusted
  \begin{tabular}{c|cccc|ccc}
    relation
    &$\sequence{0,0}$ &$\sequence{0,1}$ &$\sequence{1,0}$ &$\sequence{1,1}$
      &reflexive?  &symmetric?  &transitive?  \\ \hline
    \adjrel{$R_0$} &$0$ &$0$ &$0$ &$0$ &$0$  &$1$  &$1$  \\ 
    \adjrel{$R_1$} &$0$ &$0$ &$0$ &$1$ &$0$  &$1$  &$1$  \\ 
    \adjrel{$R_2$} &$0$ &$0$ &$1$ &$0$ &$0$  &$0$  &$1$  \\ 
    \adjrel{$R_3$} &$0$ &$0$ &$1$ &$1$ &$0$  &$0$  &$1$  \\[0.5ex] % \hline
    \adjrel{$R_4$} &$0$ &$1$ &$0$ &$0$ &$0$  &$0$  &$1$  \\ 
    \adjrel{$R_5$} &$0$ &$1$ &$0$ &$1$ &$0$  &$0$  &$1$  \\ 
    \adjrel{$R_6$} &$0$ &$1$ &$1$ &$0$ &$0$  &$1$  &$0$  \\ 
    \adjrel{$R_7$} &$0$ &$1$ &$1$ &$1$ &$0$  &$1$  &$0$  \\[0.5ex] % \hline
    \adjrel{$R_8$} &$1$ &$0$ &$0$ &$0$ &$0$  &$1$  &$1$  \\ 
    \adjrel{$R_9$} &$1$ &$0$ &$0$ &$1$ &$1$  &$1$  &$1$  \\ 
    \adjrel{$R_{10}$} &$1$ &$0$ &$1$ &$0$ &$0$  &$0$  &$1$  \\ 
    \adjrel{$R_{11}$} &$1$ &$0$ &$1$ &$1$ &$1$  &$0$  &$1$  \\[0.5ex] %\hline
    \adjrel{$R_{12}$} &$1$ &$1$ &$0$ &$0$ &$0$  &$0$  &$1$  \\ 
    \adjrel{$R_{13}$} &$1$ &$1$ &$0$ &$1$ &$1$  &$0$  &$1$  \\ 
    \adjrel{$R_{14}$} &$1$ &$1$ &$1$ &$0$ &$0$  &$1$  &$0$  \\ 
    \adjrel{$R_{15}$} &$1$ &$1$ &$1$ &$1$ &$1$  &$1$  &$1$  
  \end{tabular}
\end{center}
\end{answer}
\end{problem}

\begin{problem} 
Relations can be reflexive or not, 
symmetric or not, and transitive or not, so there are eight cases.
For each combination, give a binary relation on $A=\set{0,1,2}$.
\begin{exes}
\begin{exercise}
  There are four cases 
  that are not reflexive (e.g., one is: not reflexive, not symmetric, and 
  not transitive). 
  For each case give an example relation on $A=\set{0,1,2}$.
\end{exercise}
\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}$.

  Finally 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.)  
\end{answer}
\begin{exercise}
  Give examples for the other four cases.
\end{exercise}
\begin{answer}
  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$.

  The next case 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{exes}
\end{problem}

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

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

To check that the relation is transitive assume that 
$\sequence{p,q}$ is related to~$\sequence{n,d}$
and also that $\sequence{n,d}$ is related to~$\sequence{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 $\sequence{p,q}$ is related to $\sequence{a,b}$.  
\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 
we sometimes write $x\equiv y\pmod R$ instead of $\sequence{x,y}\in 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}[\midlength] 
  Verify that each relation is an equivalence on~$X$.
  Describe the equivalence classes.
\begin{exes}
\begin{exercise} 
  $X=\N$, $x_0\equiv x_1 \pmod R$ if both are even or both are odd. 
\end{exercise}
\begin{answer}
  To verify that it is an equivalence we will check that it is reflexive,
  symmetric, and transitive.

  For reflexive observe that for any $x\in\N$, either both $x$ and~$x$
  are even or both are odd.
  For symmetric, if $x_0\equiv x_1\pmod R$ then $(x_0,x_1)\in R$
  and either both $x_0$ or $x_1$ are even (in which case we also have
  $(x_1,x_0)\in R$) or both are even.
  In either case $x_1\equiv x_0\pmod R$.

  Finally, for transitive assume that $x_0\equiv x_1\pmod R$
  and $x_1\equiv x_2\pmod R$.
  If $x_0$ is odd then $x_1$ is odd also, and therefore $x_2$ is odd.
  The case that $x_0$ is even is similar.
  Either way, $x_0\equiv x_2\pmod R$.

  The equivalence classes are the even numbers
  $\set{0,2,4,\ldots}=\eqclass{0}=\eqclass{2}=\eqclass{4}=\cdots$
  and the odd numbers
  $\set{1,3,5,\ldots}=\eqclass{1}=\eqclass{3}=\eqclass{5}=\cdots$.
\end{answer}
\begin{exercise} 
      $X=\R$, $x_0\equiv x_1\pmod R$ if $x_0-x_1\in \Z$
\end{exercise}
\begin{answer}
  Reflexivitity $x\equiv x\pmod R$ holds because $x-x=0\in\Z$ for any $x\in\R$. 
  Symmetry holds because if $x_0-x_1=k$ is an integer then $x_1-x_0=-k$ is also
  an integer.

  Transitivity is also routine.
  If $x_0\equiv x_1\pmod R$ and $x_1\equiv x_2\pmod R$ then
  $x_0-x_1$ and~$x_1-x_2$ are integers.
  So their sum $x_0-x_2$ is an integer and $x_0\equiv x_2\pmod R$.  

  One example class is 
  $\eqclass{0.25}=\set{\ldots,-1.75,-0.75,0.25,1.25,2.25,\ldots}$
  (note that 
  $\eqclass{0.25}=\eqclass{-1.75}=\eqclass{-0.75}=\eqclass{1.25}=\cdots$).
  Thus there are infinitely many equivalence classes, one for every
  number $r\in\R$ with $0\leq r<1$.  
\end{answer}
\begin{exercise} 
     $X=\Z$, $i\equiv n \pmod R$ if 
      $i\equiv n\pmod 3$
\end{exercise}
\begin{answer}
  The relation is reflexive because for every integer, 
  on division by~$3$ it leaves the same remainder as itself.
  The relation is symmetric because if, on division by~$3$, 
  $i$ leaves the same remainder as~$n$
  then $n$ leaves the same one as~$i$.
  Transitivity is as easy: if $i_0$ leaves the same remainder as~$i_1$,
  which in turn leaves the same remainder as~$i_2$ then all three leave
  the same remainder and in particular $i_0$ and~$i_2$ do. 

  There are three equivalence classes.
  One is 
  $\set{\ldots,-6,-3,0,3,6,9,\ldots}=\eqclass{0}=\eqclass{3}=\eqclass{-3}=\cdots$.
  Another is 
  $\set{\ldots,-5,-2,1,4,7,\ldots}=\eqclass{1}=\eqclass{-2}=\eqclass{4}=\cdots$.
  The last is $\eqclass{2}$.
\end{answer}
\end{exes}
\end{problem}


\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 $\sequence{y,x_0}\in R$, and so $\sequence{y,x_1}\in R$
(by transitivity, with $\sequence{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, $\sequence{y,x_0}\in R$ and~$\sequence{y,x_1}\in R$.
The equivalence relation property of 
symmetry applied to $\sequence{y,x_0}\in R$ yields~$\sequence{x_0,y}\in R$.
Transitivity applied to the 
two $\sequence{x_0,y}\in R$ and~$\sequence{y,x_1}\in R$ yields
that $\sequence{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,
and $\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 subset 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}$; 
      for instance, $P_{0.3}=P_{1.3}$.  
      so what may at first look appear to be two elements of~$\partition{P}$
      is actually a single element.
\end{exercise}
\begin{answer}
  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 $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$).

  Every $P_n$ is nonempty 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 `equivalent modulo~$3$' is an 
  equivalence.
  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}
\end{problem}

\begin{problem} \label{ex:EquivClassesFormPartition}
Prove.
\begin{exes}
\begin{exercise} 
  Where $R$ is an equivalence on the set~$X$, 
  the collection of equivalence classes 
  $\setbuilder{\eqclass{x}}{x\in X}$ forms a partition of~$X$,
  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{\sequence{x,y}\in X^2}{
            \text{$x$ and~$y$ are in the same part}}$ 
  is an equivalence, 
  the relation that \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 $P_{x}\in\partition{P}$ as itself.
  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$.
  Then both $x$ and~$z$ are elements of $P$.  
\end{answer}
\end{exes}
\end{problem}

\begin{problem}
Suppose $\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} 
  Prove that the set of inverse images 
  $\partition{P}=\setbuilder{f^{-1}(c)}{c\in\range(f)}$ 
  form a partition of the domain.
\end{exercise}
\begin{answer}
  Each element $f^{-1}(c)=\setbuilder{d\in D}{f(d)=c}$ of the partition
  $\partition{P}$ is  
  an equivalence classes of the relation in the prior 
  item,
  namely it is the equivalence class $\eqclass{d}$ for any $d$ such that
  $f(d)=c$ (there is such a domain element~$d$ because the map is onto).
  Then by Exercise~\ref{ex:EquivClassesFormPartition} these $f^{-1}(c)$
  partition the domain. 
\end{answer}
\begin{exercise} 
  Consider the map
  $\map{\hat{f}}{\partition{P}}{\range(f)}$ whose action is:
  $\hat{f}(P)$ is defined to be~$f(d)$ where $d\in P$.
  Show that~$\hat{f}$ is a function and that it is one-to-one.
  \remark every function can be modified to be onto by 
    changing its codomain to equal its range.
    This exercise gets one-to-one-ness by modifying the function's domain.
\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}
\end{problem}

\begin{df}
A binary relation~$R$ is \definend{antisymmetric} if
$\sequence{x,y}\in R$ and $\sequence{y,x}\in R$ implies that $x=y$.
A binary 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}
  To show that 
  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$.)

  Transitivity 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 relation 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.
  It is transitive by Exercise~\ref{ex:PropertiesOfSubset}, 
  the Properties of Subset.  
\end{answer}
\end{exes}
\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