%\magnification=\magstephalf
%\nopagenumbers
%\hsize 18true cm
\input mymacros
\input amssym.def
\def\mathcal#1{{\cal #1}}
\def\lto{\longrightarrow}
\def\imply{\longrightarrow}
\def\iff{\longleftrightarrow}
\def\bimply{\longleftrightarrow}
\def\rr{{\Bbb R}}
\def\nn{{\Bbb N}}
\def\zz{{\Bbb Z}}
\def\rrr{{\mymagtwobf R}}
\def\nnn{{\mymagtwobf N}}
\xdef\startexpage{
\eject
\null
\vskip 1cm
\centerline{\hbox to 6cm{\hrulefill}\ \ \ \hbox to 6cm{\hrulefill}}
\centerline{\hbox to 6cm{\hfill Student's name\hfill}\ \ \ \hbox to
6cm{\hfill Student's I.D. number\hfill}}

\vskip 0.5cm
}
\def\boxoto{\enspace\lower5pt\vbox{\hrule height2.6pt depth-2pt\hbox{\vrule width0.6pt\kern1pt\vbox{\kern1pt\phantom{O}\kern1pt}\kern1.5pt\vrule width0.6pt}\hrule height2.6pt depth-2pt}}
\def\plttr#1{\hbox to 9cm{#1\enspace\hrulefill} \boxoto\ True \ \boxoto\  False\ }
\def\tra{\vskip 0.05cm Translation:
\vskip 1.5cm}
\def\pltt#1{\hbox to 8cm{#1\hfill\enspace is$\,\,\,$a$\,\,\,$}
\boxoto$\,$Tautology \boxoto$\,$Contradiction\ \boxoto$\,$Contingency.}
\def\lr{\leftrightarrow}
\def\plcor{\boxoto\ Correct \ \ \ \boxoto\  Incorrect.}
\def\plhas{\boxoto\ Has a solution \ \ \ \boxoto\  Does not have a solution.}
\raggedbottom
\null
\vskip 3cm
\centerline{{\mymagtwobf MATHEMATICS 300 --- FALL 2002}}

\medbreak
\centerline{{\mymagtwobf INTRODUCTION TO MATHEMATICAL REASONING}}

\medbreak
\centerline{{\mymagtwoit INSTRUCTOR: H\'ector J.  Sussmann}}

\bigbreak
\centerline{{\mymagtwobf SOLUTIONS TO THE SECOND MIDTERM EXAM.}}

\vskip 1cm
\item{{\bf 1.}} \ \ i.  Define ``union.'' {\bf ANSWER.} See book, page 58.

\medbreak
\itemitem{ii.}  Define ``symmmetric difference.''
{\bf ANSWER.} See book, page 63.  {\sl NOTE: Several students
mistakenly defined as ``symmetric difference'' what in reality 
is ``set difference,'' which is a totally different concept.}

\medbreak
\itemitem{iii.}  Define ``Cartesian product.'' {\bf ANSWER.} See book, 
page 67. 

\medbreak
\itemitem{iv.}  Define ``equivalence relation.'' 
{\bf ANSWER.} See book, page 79, for the definition of 
``equivalence relation,'' page 75 for the  definition of what 
it means for a relation to be ``reflexive,'' ``symmetric,''
and ``transitive,'' and pages 72, 73 for the definitions
of ``relation'' and ``relation on a set $A$.''

\medbreak
\itemitem{v.}  Define ``equivalence class.'' {\bf ANSWER.} See book, page 82.

\medbreak
\itemitem{vi.}  Define ``partition.'' {\bf ANSWER.} See book, page 88.

\bigbreak 
\item{{\bf 2.}} \ \ (i) Prove: if $A$, $B$, $C$, $D$ are sets such that
$A\times B=C\times D$, then $A=C$ and $B=D$. 

\medbreak
\itemitem{}  {\bf ANSWER.} This cannot be proved because it is false.
Here is a counterexample: let $A=\{1\}$, $C=\{2\}$, $B=C=\emptyset$.
Then $A\times B=C\times D$, because 
$A\times B=\emptyset$ and $C\times D=\emptyset$. But it is not true
that $A=C$. 

\medbreak 
\itemitem{(ii)} Prove: if $A$, $B$, $C$, $D$ are nonempty sets such that
$A\times B=C\times D$, then $A=C$ and $B=D$. 

\medbreak
\itemitem{}  {\bf PROOF.} Let us first prove that $A=C$. 

$\qquad\qquad$ Let $x$ be arbitrary.

$\qquad\qquad\quad$ Assume that $x\in A$.

$\qquad\qquad\quad$ Since $B\neq\emptyset$, we can pick $y\in B$.

$\qquad\qquad\quad$ Then $(x,y)\in A\times B$.

$\qquad\qquad\quad$ Therefore $(x,y)\in C\times D$, because 
$A\times B=C\times D$.

$\qquad\qquad\quad$ So $x\in C$.

$\qquad\qquad$ Hence $x\in A\imply x\in C$.

$\qquad\qquad$ A similar argument proves that $x\in C\imply x\in A$.

$\qquad\qquad$ Therefore $x\in A\bimply x\in C$.

$\qquad\quad$ Since $x$ was arbitrary, we have shown that
$\forall x,(x\in A\bimply x\in C)$.

$\qquad\quad$ So $A=C$. 

$\qquad\quad$ A similar argument proves that $B=D$.

\vfill\eject
\null
\vskip 1.8cm

\bigbreak
\item{{\bf 3.}} \ (i) Prove: If $R$, $S$ are equivalence relations on 
a set $A$, then $R\cap S$ is an equivalence relation on $A$.

\medbreak
\itemitem{}  {\bf PROOF.} We show that $R\cap S$ is reflexive
on $A$, symmetric, and transitive. To prove that $R\cap S$ is reflexive
on $A$, we let $x$ be an arbitrary member of $A$, and show that
$(x,x)\in R\cap S$. Since $R$ is reflexive on $A$, 
$(x,x)\in R$. Since $S$ is reflexive on $A$, 
$(x,x)\in S$. Therefore $(x,x)\in R\cap S$, as desired.
We now prove that $R\cap S$ is symmetric, i.e., that
if $(x,y)\in R\cap S$ then $(y,x)\in R\cap S$. Let 
$(x,y)\in R\cap S$. Then $(x,y)\in R$ and $(x,y)\in S$. 
Since $R$ is symmetric, $(y,x)\in R$. 
Since $S$ is symmetric, $(y,x)\in S$. Therefore 
$(y,x)\in R\cap S$.  Now let us show that
$R\cap S$ is  transitive. We have to prove that 
if $(x,y)\in R\cap S$ and $(y,z)\in R\cap S$ then 
then $(x,z)\in R\cap S$. Let $x,y,z$ be such that 
$(x,y)\in R\cap S$ and $(y,z)\in R\cap S$. Then 
$(x,y)\in R$, $(x,y)\in S$, $(y,z)\in R$, and
$(y,z)\in S$. Since $R$ is transitive, 
$(x,y)\in R$,  and $(y,z)\in R$, we can conclude that 
$(x,z)\in R$. Since $S$ is transitive, 
$(x,y)\in S$,  and $(y,z)\in S$, we can conclude that 
$(x,z)\in S$. Therefore $(x,z)\in R\cap S$.

\medbreak
\itemitem{(ii)} Prove: If $R$, $S$ are equivalence relations on a set $A$,
then $R\cup S$ is an equivalence relation on $A$.

\medbreak
\itemitem{}  {\bf ANSWER.} This cannot be proved because it is false.
To see this, here is a counterexample. Let $A=\zz$, let $R$ be congruence
modulo 2, let $S$ be congruence modulo 3. Then 
the pairs $(2,4)$ and $(4,7)$ belong to 
$R\cup S$, because $(2,4)\in R$ and $(4,7)\in S$. But the pair
$(2,7)$ does not belong to $R\cup S$, because 
$2$ is neither congruent to $7$ modulo 2, nor 
congruent to $7$ modulo 3. Hence $R\cup S$ is not transitive,
so it is not an equivalence relation.

\item{{\bf 4.}} \ {i.} Let $A=\{(x,y):x\in\zz\wedge y\in\zz\wedge y\neq 0\}$. 
Define a relation $R$ on $A$ by letting
$$
R=\Bigl\{\Big((x,y),(x',y')\Big):xy'=x'y\Bigr\}\,.
$$
Prove that $R$ is an equivalence relation.

\medbreak
\itemitem{}  {\bf PROOF.} We show that $R$ is reflexive
on $A$, symmetric, and transitive. To prove that $R$ is reflexive on
$A$, we let $u$ be an arbitrary member of $A$, and show that $(u,u)\in
R$. Since $u\in A$, $u$ is an ordered pair $(x,y)\in\zz\times\zz$ such
that $y\neq 0$. If we let $x'=x$, $y'=y$, then $xy'=x'y$, because both
sides are equal to $xy$. Hence $\Big((x,y),(x',y')\Big)\in R$. That
is, $(u,u)\in R$. So $R$ is reflexive on $A$.  Next, let us show that
$R$ is symmetric. Suppose $u\in A$, $u'\in A$, are such that
$(u,u')\in R$. Since $u\in A$, $u$ is an ordered pair
$(x,y)\in\zz\times\zz$ such that $y\neq 0$. Since $u'\in A$, $u'$ is
an ordered pair $(x',y')\in\zz\times\zz$ such that $y'\neq 0$.  Since
$(u,u')\in R$, the equality $xy'=x'y$ holds.  But then $x'y=xy'$,
which shows that $(u'u)\in R$.  Hence $R$ is symmetric. Finally, let
us prove that $R$ is transitive.  Suppose $u\in A$, $u'\in A$, $u''\in
A$ are such that $(u,u')\in R$ and $(u',u'')\in R$.
Since $u\in A$, $u$ is an ordered pair
$(x,y)\in\zz\times\zz$ such that $y\neq 0$. Since $u'\in A$, $u'$ is
an ordered pair $(x',y')\in\zz\times\zz$ such that $y'\neq 0$.  Since
$(u,u')\in R$, the equality $xy'=x'y$ holds.
Since $u''\in A$, $u''$ is an ordered pair
$(x'',y'')\in\zz\times\zz$ such that $y''\neq 0$. 
Since $(u',u'')\in R$, the equality $x'y''=x''y'$ holds.
We now multiply $x'y''=x''y'$ by $y$, and get 
$x'y''y=x''y'y$. Since $x'y=xy'$, we have 
$x''y'y=xy'y''$. Therefore $xy'y''=x''y'y$. Since $y'\neq 0$,
we can cancle the factor $y'$ from both sides, and conclude  
that $x''y=xy''$. Therefore $(u,u'')\in R$. So $R$ is transitive.

\medbreak
\itemitem{ii.} Suppose that, instead of defining $A$ as we did in Part i, 
we had defined  $A=\{(x,y):x\in\zz\wedge y\in\zz\}$.  Would $R$
still be an equivalence relation? (Do not just say ``yes'' or ``no.'' 
Justify your answer.) 

\medbreak
\itemitem{}  {\bf ANSWER.} No, $R$ would {\bf not}
be an equivalence relation. To see this, observe 
that if we take $u=(2,3)$, $u'=(0,0)$, and 
$u''=(3,7)$, then $(u,u')\in R$, because
$2\times 0=0\times 3$, and $(u',u'')\in R$, because 
$0\times 7=0\times 3$, but $(u,u'')\notin R$, 
because $2\times 7\neq 3\times 3$. So $R$ is not
transitive.

\vfill\eject
\null
\vskip 1.8cm

\item{{\bf 5.}} \ (i) Prove:
if $A$, $B$ are sets such that $A\Delta B=\emptyset$, then $A=B$.

\medbreak
\itemitem{}  {\bf PROOF.} Let $x$ be arbitrary.

$\qquad\quad$ Suppose $x\in A$. We prove $x\in B$ by contradiction.

$\qquad\qquad$ Suppose $x\notin B$. Then $x\in A-B$. Hence 
$x\in(A-B)\cup(B-A)$. 

$\qquad\qquad$ So $x\in A\Delta B$. This contradicts the fact that 
$A\Delta B=\emptyset$.

$\qquad\quad$ Therefore $x\in B$. 

$\qquad$ Hence $x\in A\imply x\in B$. 

$\qquad$ A similar argument proves that $x\in B\imply x\in A$. 

$\qquad$ Therefore $x\in B\bimply x\in A$. 

Since $x$ was arbitrary, we have shown that 
$\forall x,(x\in B\bimply x\in A)$. 

Hence $A=B$. 

\medbreak
\itemitem{(ii)} Prove: if $A$, $B$ are sets such that $2^A=2^B$, then $A=B$.

\medbreak
\itemitem{}  {\bf PROOF.} Let $x$ be arbitrary.

$\qquad\quad$ Suppose $x\in A$. Then $\{x\}\subseteq A$. So 
$\{x\}\in 2^A$. Since $2^A=2^B$, we have 
$\{x\}\in 2^B$. This says that 

$\qquad\quad$ $\qquad\quad$ $\{x\}\subseteq B$. So 
every member of $\{x\}$ belongs to $B$. Hence
$x\in B$, because $x\in\{x\}$. 

$\qquad$ Hence $x\in A\imply x\in B$. 

$\qquad$ A similar argument proves that $x\in B\imply x\in A$. 

$\qquad$ Therefore $x\in B\bimply x\in A$. 

Since $x$ was arbitrary, we have shown that 
$\forall x,(x\in B\bimply x\in A)$. 

Hence $A=B$. 

\medbreak
\item{{\bf 6.}} Let ${\cal P}$ be a partition of a set 
$A$. Define a relation $R$ on $A$ by letting
$$
R=\{(x,y):\exists X\in{\cal P},(x\in X\wedge y\in X)\}\,.
$$
Prove that $R$ is an equivalence relation.

\medbreak
\itemitem{}  {\bf ANSWER.} This is done in the book, page 89,
Proposition 13.3.

\medbreak
\item{{\bf 7.}} A {\sl telephone number} is a sequence of ten digits such 
that the leftmost digit is neither a $0$ nor a $1$. (The ``digits''
are the symbols $0$, $1$, $2$, $3$, $4$, $5$, $6$, $7$, $8$, $9$.)
Determine how many telephone numbers $N$ there are such that (a)~$N$
consists of four even digits and six odd digits, (b)~the even digits
are all different and occur in increasing order from left to
right. (For example, the number 3247533618 is O.K., but 3267533418 and
3024756318 are not.)  Do {\bf not} just write a number. Show how you
get it.

\medbreak
\item{}  {\bf ANSWER.} Let us divide our numbers into two 
kinds. First, there are the numbers whose leftmost digit
is odd. Second,  there are the numbers whose leftmost digit
is even. To construct a number of the first kind,
we have to do the following:

\itemitem{1.}  Pick a set of four locations out of the nine 
other than the lefmost one, and allocate this set 
to even digits. This can be done in 
${9\choose 4}$ ways.   

\itemitem{2.}  Pick which four even digits to use. Since there is a total 
of five even digits, picking a set of four amounts to picking one,
namely, the one that will not be used. So this can be done 
in 5 ways. Once we know which four even digits we will use, 
and what are the four locations where we will put them, we have only
one way to put them there, because they have to be in increasing order. 

\itemitem{3.}  Pick which odd digits we will use for the other 
six slots. We have four choices for the leftmost slot (because $1$
is not allowed) and five for each of the other five slots, so the total
number of ways to do this is $4\times 5^5$. 

\medbreak\item{}  Hence the number of ways to form a number of the first
kind is ${9\choose 4}\times 5\times 4\times 5^5$, i.e., 
${9\choose 4}\times 4\times 5^6$.

\vfill\eject
\null
\vskip 1.8cm

\medbreak\item{} To construct a number of the second kind,
we have to do the following:

\itemitem{1.}  Pick a set of three locations out of the nine 
other than the lefmost one, and allocate this set 
to even digits. (In addition, of course, the leftmost place
is allocated to an even digit as well.) 
This can be done in ${9\choose 3}$ ways.   

\itemitem{2.}  Pick which four even digits to use. Since we are not allowed
to use $0$ in the leftmost place, the increasing sequence
of four even digits has to be $2,4,6,8$. So we have only one 
option here.

\itemitem{3.}  Pick which odd digits we will use for the other 
six slots. We have five choices for each slot, so the total
number of ways to do this is $5^6$. 

\medbreak\item{}  Hence the number of ways to form a number of the second
kind is ${9\choose 3}\times 5^6$.
$$
5^6\Bigl({9\choose 3}+{9\choose 4}\times 4\Bigr)=
5^6\Bigl({9!\over 6!\times 3!}+{4\times 9!\over 5!\times 4!}\Bigr)
=5^6\Bigl({9\times 8\times 7\over 6}+{4\times 9\times 8\times 7\times 6\over 
24}\Bigr)\,,
$$
which is equal to
$5^6\Bigl(3\times 4\times 7+4\times 3\times 7\times 6\Bigr)$, 
i.e., to $5^6\times 3\times 4\times 7^2$, 
that is, to $5^4\times 3\times 7^2\times 100$, 
which equals $625\times 3\times 49\times 100$, 
i.e., $1,875\times 4,900$, that is, 
{\bf 9,187,500}. 


\medbreak
\item{{\bf 8.}} State and prove the binomial theorem.

\medbreak
\itemitem{}  {\bf ANSWER.} This is done in the book, pages 98-99,
Theorem 14.8.  A different proof, using induction, was given
in class. 




\end

 