\documentclass[11pt]{article}
\usepackage{latexsym,amsmath,amssymb}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{0in}
\setlength{\textheight}{8.0in}
\begin{document}
\centerline{Mathematics 243, section 3 -- Algebraic Structures}
\centerline{Problem Set 4}
\centerline{{\bf due:} October 5, 2012}
\vskip 10pt
\noindent
{\it `A' Section}
\bigskip
\begin{enumerate}
\item[1.]  Consider the following relations defined on the set $\mathbb{Z}$.
In each case, say whether the relation is reflexive, symmetric, transitive.
Justify your answers.
\begin{enumerate}
\item[a.] $xRy$ if and only if $(-1)^x = (-1)^y$
\item[b.] $xRy$ if and only if $x\cdot y \ge 0$
\item[c.] $xRy$ if and only if $|x - y| \le 2$
\item[d.] $xRy$ if and only if $x$ has the same number of base 10
digits as $y$, ignoring signs of $x,y$.    
\item[e.] $xRy$ if and only if the sum of the base 10 digits of 
$x$ is the same as the sum of the base 10 digits of $y$, ignoring
signs of $x,y$.  
\end{enumerate}
\item[2.]   Which of the relations in question 1 are equivalence 
relations?  For those that are, say exactly which integers make
up the equivalence class $[11]$ using correct set notation.  
\item[3.]  Let $R$ be the relation on $\mathbb{Z}$ defined by
$xRy$ if and only if $4x - 15y$ is a multiple of $11$.  Show
that $R$ is an equivalence relation and describe all of the 
equivalence classes for $R$.  
\item[4.]  Decide whether each of the following statements
is true.  For those that are true, give a short proof using 
the postulates for $\mathbb{Z}$ given in \S 2.1 of the text.
For those that are false, give a counterexample.
\begin{enumerate}
\item[a.]  If $xy = xz$ for integers $x,y,z$, then $y = z$.
\item[b.]  If $x < y$, then $x^2 < y^2$.
\item[c.]  If $z - x < z - y$, then $y < x$.   
\end{enumerate}
\end{enumerate}
\vskip 10pt
\noindent
{\it `B' Section}
\vskip 10pt
\begin{enumerate}
\item[1.]  In class we showed that the distinct equivalence
classes of an equivalence relation $R$ on a set $A$ give 
a partition of $A$.  Conversely, suppose 
$$A = \bigcup_{\lambda \in {\cal L}} A_\lambda$$
is a partition of $A$.  Show that the relation $R$ on 
$A$ defined by:
$$aRa' \Leftrightarrow a,a' \text{ are both
elements of the same subset} A_\lambda$$
is an equivalence
relation on A.
\item[2.]  In both parts of this problem, you will be
working in $\mathbb{Z}$, using the postulates from \S 2.1
\begin{enumerate}
\item[a.]  Show that if $x\cdot y = 0$, then $x = 0$ or 
$y = 0$.  (Hint:  Argue by contraposition.  By the trichotomy postulate 4, if $x \ne 0$,
then $x \in \mathbb{Z}^+$ or $-x \in \mathbb{Z}^+$, and 
the same is true for $y$.)  
\item[b.]  From part a, deduce the cancellation law in 
$\mathbb{Z}$:  If $x\cdot y = x\cdot z$ and $x \ne 0$, then
$y = z$.
\end{enumerate}
\item[3.]  Prove by mathematical induction:
\begin{enumerate}
\item[a.]  For all $n \in \mathbb{Z}^+$, 
$$1^2 + 2^2 + \cdots + n^2 = \frac{n(n+1)(2n+1)}{6}.$$
\item[b.]  For all $n \in \mathbb{Z}^+$,
$$\frac{1}{1\cdot 2} + \frac{1}{2\cdot 3} + \cdots + \frac{1}{n(n+1)} = \frac{n}{n + 1}$$
\item[c.]  For all $n \ge 2$, $n^3 > 1 + 2n$.
\item[d.]  If $|A| = n$, then $|{\mathcal P}(A)| = 2^n$.  (Suggestion:  For the induction 
step, one proof comes like this.  Let $A = \{a_1,\ldots,a_k,a_{k+1}\}$.  Every subset of $A$ is of one of
two types -- the ones containing $a_{k+1}$ and the ones not containing $a_{k+1}$.
Count the number of subsets of each type by using the induction hypothesis.)
\end{enumerate}
\item[4.]  The binomial coefficients are the numbers 
$$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$
(where $0! = 1$ by convention).  
\begin{enumerate}
\item[a.]  Show using the definition that for all $k$ with $1 \le k \le n$, 
$$\binom{n}{k} + \binom{n}{k-1} = \binom{n+1}{k}$$
(this is often known as the Pascal's triangle identity for binomial coefficients,
because it is the fact underlying the way the coefficients can be computed from 
the Pascal's triangle table).  
\item[b.]  (The Binomial Theorem)  Show by induction that for all $n\ge 1$ and
all $a,b \in \mathbb{R}$
$$(a + b)^n = \sum_{\ell=0}^n \binom{n}{\ell} a^\ell b^{n-\ell}$$
(that is, for each $\ell$, $0 \le \ell \le n$, 
the number $\binom{n}{\ell}$ is exactly the coefficient of the
term $a^\ell b^{n-\ell}$ appearing in the expansion of $(a + b)^n$ -- the lower
index $\ell$ is the same as the exponent of $a$).  
\end{enumerate}
\end{enumerate}
\end{document}
