\magnification=\magstep1
\overfullrule=0pt
\centerline{MATH 243 -- Mathematical Structures, section 2}
\centerline{Final Exam Solutions}
\bigskip
\noindent
I.  A) Let $p, q$ represent any propositions.  Construct the truth table for 
the proposition
$$(p\ {\rm implies}\ q)\ {\rm if\ and\ only\ if}\ ((p\ {\rm and\ not} q)\ {\rm implies} not p)$$
\bigskip
\noindent
{\it Solution:} 
$$\eqalign{
p \quad q \quad (p\ {\rm implies}\ q)\ & {\rm if\ and\ only\ if}\ ((p\ {\rm and\ not}\ q)\ {\rm implies \ not}\ p)\cr
T \quad T \qquad\qquad T \qquad &\ \ \ T \qquad \qquad\qquad ((F) \qquad\qquad T\qquad F)\cr
T \quad F \qquad\qquad F \qquad &\ \ \ T \qquad \qquad\qquad ((T) \qquad\qquad F\qquad F)\cr 
F \quad T \qquad\qquad T \qquad &\ \ \ T \qquad \qquad\qquad ((F) \qquad\qquad T\qquad T)\cr
F \quad F \qquad\qquad T \qquad &\ \ \ T \qquad \qquad\qquad ((F) \qquad\qquad T\qquad T)\cr}$$
(The column lined lined up under the ``and'' of ``if and only if'' is the truth value of the 
whole proposition.  Note this is the basis of one form of proof by contradiction!)
\bigskip
\noindent
B)  Give the contrapositive form of the statement ``If the product of two integers $x,y$
is even, then $x$ is even or $y$ is even."
\bigskip
\noindent
{\it Solution:}  ``If $x$ is not even (odd) and $y$ is not even (odd), then the product
of the two integers $x,y$ is not even (odd).''
\bigskip
\noindent
C)  Give the converse of the statement in part B.
\bigskip
\noindent
{\it Solution:}  ``If $x$ is even or $y$ is even, then the product $x,y$ is even.''
\bigskip
\noindent
II.  All parts of this question refer to the mapping 
$f : {\bf Z} \to {\bf Z}$ defined by 
$$f(x) = \cases{6x & if $x$ is even\cr
                          2 - x & if $x$ is odd\cr}$$
\bigskip
\noindent
A)  Let $U = \{1,2,3,4,5\}$.  What is $f(U) \cap \{x \in {\bf Z} : x > 0\}$?
\bigskip
\noindent
{\it Solution:}  Since $f(1) = 1$, $f(2) = 12$, $f(3) = -1$, 
$f(4) = 24$, $f(5) = -3$, we see 
$$f(U)\cap \{x \in {\bf Z} : x > 0\} = \{1,12,24\}.$$
\bigskip
\noindent
B)  Let $V = 4{\bf Z}$.  What is $f^{-1}(V)$ for this mapping?
\bigskip
\noindent
{\it Solution:}  Note that if $x$ is odd, then $f(x) = 2 - x$ is also odd.  On 
the other hand, if $x = 2k$ is even, then $f(x) = f(2k) = 6\cdot 2k = 4\cdot 3k \in 4{\bf Z}$.  
Hence $f^{-1}(V) = 2{\bf Z}$  (all even numbers).  
\bigskip 
\noindent
III.  Give a precise statement of the Division Algorithm in ${\bf Z}$ and prove 
the Existence and Uniqueness parts.  
\bigskip
\noindent
{\it Solution:}  Let $N$ and $n > 0$ be integers.  There exist unique integers
$q,r$ such that $N = qn + r$ with $0 \le r < n$.  
\item{} {\it Existence:}  Consider the set $S = \{N - kn\mid k \in {\bf Z}\}$.  
Then $S \cap ({\bf Z}^+ \cup \{0\}) \ne \emptyset$.  (The reason here is that
if $N > 0$, then we can just take $k = 0$ to get a positive element of $S$.  On
the other hand if $N \le 0$, we just need to take $k$ to be a negative integer
with absolute value large enough that $-N < -k n$.)  Now by the Well-Ordering property, 
$S \cap ({\bf Z}^+ \cup \{0\})$ contains a smallest element.  Call this smallest
element $r$, and write $r = N - qn$ (that is, $k = q$ for some particular integer $q$
from the definition of the set $S$).  This gives $N = qn + r$ as required and we
only need to show $0 \le r < n$.  Now, $r \ge 0$ is automatic by the way $r$ was
produced (it's the smallest non-negative element of $S$).  Suppose that $r \ge n$.  
Then in the set $S$ we also have $N - (q + 1)n = N - qn - n = r - n \ge 0$ but $r - n < r$.  
This contradicts the choice of $r$ as the smallest non-negative element in $S$.
With this proof by contradiction, we have shown $r \le n$.  Hence both of the
required conditions hold and the existence part of the proof is complete.

\item{} {\it Uniqueness:}  If $N = q_1 n + r_1$ and also $N = q_2 n + r_2$, 
where $r_1$ and $r_2$ both satisfy the statement of the theorem but $r_1 \ne r_2$, then
we can assume $r_1 > r_2$.  Setting the two expressions for $N$ equal, we have
$q_1n + r_1 = q_2 n + r_2$, so $(q_2 - q_1)n = r_1 - r_2$.  Now $r_1 - r_2 > 0$
but also $r_1 - r_2 \le r_1 < n$.  Hence $r_1 - r_2$ is a multiple of $n$ that
lies strictly between 0 and $n$.  But that is a clear contradiction.  Hence
$r_1 = r_2$, and hence $q_1 = q_2$ as well.   
\bigskip
\noindent
IV.  A)  Use the Euclidean Algorithm to find the integer $d = \gcd(753,156)$
and express $d$ in the form $d = 753m + 156n$ for some integers $m,n$
\bigskip
\noindent
{\it Solution:}  Applying the Euclidean Algorithm,
$$\eqalign{
753 &= 4 \cdot 156 + 129\cr
156 &= 1 \cdot 129 + 27\cr
129 &= 4 \cdot 27 + 21\cr
27 &= 1 \cdot 21 + 6\cr
21 &= 3 \cdot 6 + 3\cr
6 &= 2\cdot 3 + 0\cr
}$$
Hence the last nonzero remainder $3 = \gcd(753,156)$.  Now we apply the Extended
Euclidean Algorithm to find $m,n$:
$$\eqalign{  \quad  &1 \quad 0\cr
             \quad  &0 \quad 1\cr
           4 \quad  &1 \quad -4\cr
           1 \quad  &-1 \quad 5\cr
           4 \quad  &5 \quad -24\cr
           1 \quad  &-6 \quad 29\cr
           3 \quad  &23 \quad -111\cr}$$
Hence $23\cdot 753 + (-111)\cdot 156 = 3$.
\bigskip
\noindent
B)  Let $a,b,c$ be integers.  Prove that $\gcd(ab,c) = 1$ if and only if $gcd(a,c) = 1$ and 
$\gcd(b,c) = 1$.  
\bigskip
\noindent
{\it Solution:}  $\Rightarrow:$  Suppose that $\gcd(ab,c) = 1$.  Then we know this means
there exist integers $m,n$ such that $m\cdot(ab) + n\cdot c = 1$.  But then by the 
commutative and associative laws for multiplication in ${\bf Z}$, 
this implies that $(mb)\cdot a + n\cdot c =1$.  Since $mb$ is an integer, this
implies $\gcd(a,c) = 1$
since $\gcd(a,c)$ is the smallest positive integer in the set of integer linear
combinations $\{pa + qc : p,q\in {\bf Z}\}$.  Similarly, $(ma) \cdot b + n\cdot c =1$
and that implies $\gcd(b,c) = 1$.  
\bigskip
\noindent
$\Leftarrow:$  If $\gcd(a,c) = 1$ and $\gcd(b,c) = 1$, then there exist integers
$m,n,p,q$ such that $ma + nc = 1$ and $pb + qc = 1$.  Multiplying these equations
together, we get $1 = (ma + nc)(pb + qc) = (mp)(ab) + (npb + mqa + nqc)c$.  
Since $mp, npb + mqa + nqc \in {\bf Z}$, this shows $\gcd(ab,c) = 1$.   
\bigskip
\noindent
V.  Let $f : A \to B$ be a mapping and $U,V\subseteq A$.  For each statement give a proof
if the statement is true, or give a counterexample if the statement is false.  (A complete
counterexample consists of specific sets $A,B,U$, and $V$, a mapping $f$, and a justification
of why these data contradict the statement.)
\bigskip
\noindent 
A)  If $f$ is injective and $f(U) \subseteq f(V)$, then $U \subseteq V$.  
\bigskip
\noindent
{\it Solution:}  This statement is {\it true}.  Proof:  Let $x \in U$.  Then 
$f(x) \in f(U)$ by definition.  Since $f(U) \subseteq f(V)$, we also have $f(x) \in f(V)$, 
and so
$f(x) = f(x')$ for some $x'\in V$.  However, we also know that $f$ is
injective, so $x = x' \in V$, so $x \in V$.  Since this holds for all $x \in U$,
$U \subseteq V$.  
\bigskip
\noindent
B) If $f$ is surjective and $f(U) \subseteq f(V)$, then $U \subseteq V$.  
\bigskip
\noindent
{\it Solution:}  This statement is {\it false}.  Here's a counterexample.  Let
$A = \{1,2\}$, $U = \{1\}$, $V=\{2\}$, $B = \{b\}$, and let $f : A \to B$
be the mapping defined by $f(1) = f(2) = b$.  We clearly have $f$ is surjective
and $f(U) \subseteq f(V)$ since both sets are $B = \{b\}$.  However
$U \cap V = \emptyset$, so we do not have $U \subseteq V$.  
\bigskip
\noindent
VI.  All parts of this question refer to $R = {\bf Z}/30{\bf Z}$, in which
the operations are addition and multiplication mod 30.
\bigskip
\noindent
A) Construct the addition and multiplication tables for the subset 
$T = \{[0],[6],[12],[18],[24]\}$ in $R$.
\bigskip
\noindent
{\it Solution:}
The addition table is 
$$\eqalign{
\qquad\ &[0]\ [6]\ [12]\ [18]\ [24]\cr
[0]\     &[0]\ [6]\ [12]\ [18]\ [24]\cr
[6]\     &[6]\ [12]\ [18]\ [24]\ [0]\cr
[12]\    &[12]\ [18]\ [24]\ [0]\ [6]\cr
[18]\    &[18]\ [24]\ [0]\ [6]\ [12]\cr 
[24]\    &[24]\ [0]\ [6]\ [12]\ [18]\cr}$$
The multiplication table is
$$\eqalign{
\qquad\ &[0]\ [6]\ [12]\ [18]\ [24]\cr
[0]\     &[0]\ \ [0]\ \ [0]\ \ [0]\ \ [0]\cr
[6]\     &[0]\ [6]\ [12]\ [18]\ [24]\cr
[12]\    &[0]\ [12]\ [24]\ [6]\ [18]\cr
[18]\    &[0]\ [18]\ [6]\ [24]\ [12]\cr
[24]\    &[0]\ [24]\ [18]\ [12]\ [6]\cr}$$
\bigskip
\noindent
B)  Which elements of $R$ have multiplicative inverses?
Explain how you know.  We have a multiplicative inverse
for $[a]$ if and only if $\gcd(a,30) = 1$.  This is because
having a $b$ such that $[a][b] = [1]$ is equivalent to 
an equation $a\cdot b = 1 + k\cdot 30$ for some integer, 
and this can be rearranged to say $b\cdot a + (-k)\cdot 30 = 1$, 
which is equivalent to $\gcd(a,30) = 1$.  The classes
that have inverses are:
$$[1],[7],[11],[13],[17],[19],[23],[29]$$
\bigskip
\noindent
VII. A) Prove by mathematical induction that 
$${1\over 1\cdot 2} + {1\over 2\cdot 3} + \cdots + {1\over n\cdot(n+1)} = {n\over n+1}$$
for all natural numbers $n \ge 1$.
\bigskip
\noindent
{\it Solution:}  The base case is $n = 1$, and the formula says in that case
$${1\over 1\cdot 2} = {1\over 1 + 1}.$$
This is clearly true since both sides give ${1\over 2}$.  Now for the induction
step, assume that 
$${1\over 1\cdot 2} + {1\over 2\cdot 3} + \cdots + {1\over k\cdot(k+1)} = {k\over k+1}$$
and consider
$${1\over 1\cdot 2} + {1\over 2\cdot 3} + \cdots + {1\over k\cdot(k+1)} + {1\over (k+1)(k+2)}.$$
By the induction hypothesis, this equals
$${k\over k+1} + {1\over (k+1)(k+2)}.$$
Putting these terms over a common denominator, we have
$${k(k+2) + 1\over (k+1)(k+2)} = {k^2 + 2k + 1\over (k+1)(k+2)} = {(k+1)^2\over (k+1)(k+2)}.$$
Canceling one power of $k+1$ between the numerator and denominator, we see this equals
${k+1\over k+2}$, as desired.  The formula is thus true for all $n\ge 1$ by induction.
\bigskip
\noindent
B) What is the least upper bound 
$$L = \sup\left(\left\{{1\over 1\cdot 2} + {1\over 2\cdot 3} + \cdots + {1\over n\cdot(n+1)} : 
n \ge 1\right\}\right)?$$
(This is the same set of numbers as in part A.)  Prove your assertion by showing that for every
real $\epsilon >0$, there exist some $n$ such that 
$$L - \epsilon < {1\over 1\cdot 2} + {1\over 2\cdot 3} + \cdots + {1\over n\cdot(n+1)} = {n\over n+1} \le L.$$
\bigskip
\noindent
{\it Solution:}  The least upper bound is $L = 1$.  This follows by considering the
equality proved in part A.  First, it is clear that ${n \over n+1} \le 1$ for
all $n \in {\bf N}$, so $L = 1$ is an upper bound.  But we also see 
that for all $n \ge 1$, 
$${1\over 1\cdot 2} + {1\over 2\cdot 3} + \cdots + {1\over n\cdot(n+1)} = {n\over n+1} = 1 - {1\over n+1}.$$
For all $\epsilon > 0$, there exist $n \in {\bf N}$ such that ${1\over n+1} < \epsilon$
and that implies 
$$1 - \epsilon < 1 - {1\over n+1} = {n \over n+1} \le 1.$$
This shows that the least upper bound is $L = 1$.
\bigskip
\noindent
C) What does your argument in part B say about the sequence
$$a_n = {1\over 1\cdot 2} + {1\over 2\cdot 3} + \cdots + {1\over n\cdot(n+1)} = {n\over n+1}?$$
\bigskip
\noindent
{\it Solution:}  It says the sequence converges to $L = 1$.

\bye
