\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{Solutions for Problem Set 2}
\centerline{{\bf due:} September 14, 2012}
\vskip 10pt
\noindent
{\it `A' Section}
\bigskip
\begin{enumerate}
\item[1.]  Let $f : \mathbb{Z} \to \mathbb{Z}$ and $g : \mathbb{Z} \to \mathbb{Z}$ be 
the indicated functions.  In each case, say whether $f, g, f\circ g, g\circ f$ are
one-to-one (injective) or onto (surjective), both, or neither.  Justify your answers.
\begin{enumerate}
\item[a.]  $f(x) = 3x$, $g(x) = 4 - x$
\item[] {\it Solution:}  $f$ is one-to-one since $f(x) = 3x = 3x' = f(x')$ implies
$3(x - x') = 0$ in $\mathbb{Z}$.  Hence $x - x' = 0$, so $x = x'$.  $f$ is not onto
because, for instance, there is no $x \in \mathbb{Z}$ such that $f(x) = 3x = 1$.  
$g$ is one-to-one since $4 - x = 4 - x'$ implies $x = x'$.  $g$ is also onto, since
given any integer $y$, $g(x) = 4 - x = y$ when $x = 4 - y$.  $(f\circ g)(x) = 3(4 - x) = 12 - 3x$.
This is one-to-one since $12 - 3x = 12 - 3x'$ implies $3(x - x') = 0$, so $x = x'$ as
before.  This function is not onto since there is no integer $x$ such that 
$(f \circ g)(x) = 12 - 3x = 1$ (for instance).  Finally $g \circ f$ is the 
function $(g\circ f)(x) = 4 - 3x$.  This is one-to-one and not onto for reasons
similar to those given for $f \circ g$.  
\item[b.]  $f(x) = |x|$, $g(x) = \begin{cases} x & \text{ if } x \text{ is even }\\
                                              x-1 & \text{ if } x \text{ is odd }\end{cases}$.
\item[] {\it Solution:}  $f$ is neither one-to-one nor onto, because $f(x) = f(-x)$ and $f$
takes only nonnegative values.  $g$ is neither one-to-one nor onto.  For instance $g(2) = 2 = g(3)$
so $g$ is not one-to-one.  $g$ is not onto either because it takes only even values.
$(f\circ g)(x) = \begin{cases} |x| & \text{ if } x \text{ is even }\\
                                              |x-1| & \text{ if } x \text{ is odd }\end{cases}$
is neither one-to-one nor onto since $g$ is not one-to-one and $f$ is not onto.  
$(g\circ f)(x) = \begin{cases} |x| & \text{ if } x \text{ is even }\\
                                              |x|-1 & \text{ if } x \text{ is odd }\end{cases}$
is neither one-to-one nor onto since $f$ is not one-to-one and $g$ is not onto.  
\end{enumerate}
\item[2.]  Consider the binary operation on $\mathbb{Z}$ given by 
$$x * y = x + y + 5$$
\begin{enumerate}
\item[a.]  Is $*$ commutative?  Why or why not?
\item[] {\it Solution:}  Yes, since by commutativity of addition in 
$\mathbb{Z}$, $y * x = y + x + 5 = x + y + 5 = x * y$ is true for all $x,y \in \mathbb{Z}$.
\item[b.]  Is $*$ associative?  Why or why not?
\item[] {\it Solution:}  We have 
$$(x * y)* z = (x + y + 5) * z = (x + y + 5) + z + 5 = x + y + z + 10.$$
On the other hand,
$$x * (y * z) = x * (y + z + 5) = x + (y + z + 5) + 5 = x + y + z + 10.$$
Since these are the same for all $x,y,z \in \mathbb{Z}$, the operation is
associative.   
\item[c.]  Is there an identity element for $*$.  What is the identity, or why not?
\item[] {\it Solution:}  Yes, $e = -5$ acts as an identity since 
$x * (-5) = x + (-5) + 5 = x$ and $(-5) * x = (-5) + x + 5 = x$ for all $x \in \mathbb{Z}$.  
\item[d.]  Are there any elements of $\mathbb{Z}$ that have inverses under this
operation?  What are they, and what are the inverses?  
\item[] {\it Solution:}  The inverse of $x$ for this operation is the integer
$y$ that satisfies $x * y = -5$ (the identity from part c).  Given $x$, 
$x + y + 5 = -5$ when $y = -x - 10$.  so $-x - 10$ is the inverse of $x$ under
this operation. 
\end{enumerate}
\item[3.]  Let $A = \{x,y,z,w\}$ and let $*$ be the binary operation on $A$
given by the following table:
\[
\begin{array}{rrrrrr}
          *& \vline & x & y & z & w \\ \hline
          x& \vline & x & y & z & w \\
          y& \vline & y & y & w & w \\
          z& \vline & z & w & z & w \\
          w& \vline & w & w & w & w
\end{array}
\]
\begin{enumerate}
\item[a.] Explain how you can tell this operation is commutative.
\item[] {\it Solution:}  The table is symmetric about the ``main diagonal''
from upper left to lower right.  This means that $a * b = b * a$ for all
$a,b\in A$, so the operation is commutative.
\item[b.] Explain why $x$ is an identity element for $*$.
\item[] {\it Solution:}  From the table, $a * x = x * a = a$ for all 
$a \in A$.  
\item[c.] Which elements have inverses and what are the inverses?
\item[] {\it Solution:}  $x$ is the only element with an inverse, and the inverse is $x$ itself.
\item[d.] What is $(y * z) * z$?  Is that the same as $y * (z * z)$?
\item[] {\it Solution:}  $(y * z) * z = w * z = w$.  That is the same
as  $y * (z * z) = y * z = w$.  (This, by itself, does \emph{not} say
that $*$ is associative, though.  Do you see why not?)    
\end{enumerate}
\end{enumerate}

\vskip 10pt
\noindent
{\it `B' Section}
\vskip 10pt
\begin{enumerate}
\item[1.]  Let $f : A \to B$ and $g : B \to A$ be mappings.  Prove
that if $f \circ g$ is onto and $g \circ f$ is one-to-one, then 
$f$ is one-to-one \emph{and} onto.
\item[] {\it Solution:}  If $f \circ g$ is onto, then for every 
$b \in B$, there is some $x \in B$ such that $(f \circ g)(x) = b$.
But that says $f(g(x)) = b$, so for every $b \in B$, there is some
element in $A$ (namely $g(x)$) such that $f(g(x)) = b$.  This 
shows $f$ is onto.  For the other part we will prove the contrapositive
form -- If $f$ is not one-to-one, then $g\circ f$ is not one-to=one
either.  If $f$ is not one-to-one, then there exist $a \ne a'$ in $A$
such that $f(a) = f(a')$.  But then $g(f(a)) = g(f(a'))$ too, so 
$g\circ f$ is not one-to-one either.  
\item[2.]  Let $*$ be an associative binary operation on 
a set $A$ and assume there is an identity element $e$ for $*$.
If $a \in A$ has inverses $b_1$ and $b_2$, show that
$b_1 = b_2$.  Hint: Consider the ``product'' $(b_1 * a) * b_2$.  
\item[] {\it Solution:}  If $b_1$ is an inverse for $*$, then 
$(b_1 * a) * b_2 = e * b_2 = b_2$.  But on the other hand, if 
$*$ is associative we also have
$(b_1 * a) * b_2 = b_1 * (a * b_2)$.  Then since
$b_2$ is also an inverse for $a$, this equals $b_1 * e = b_1$.  
Two things that are equal to the same thing are equal to one another, so
$b_1 = b_2$.   
\item[3.]  Let $A$ be a set and let $\mathcal{P}(A)$ be the power
set of $A$ as defined in \S 1 of the text and on Problem Set 1.  Let 
$*$ be the binary operation on $\mathcal{P}(A)$ defined by 
$S * T = S \cup T$.  Answer the following questions and prove 
your assertions.
\begin{enumerate}
\item[a.]  Is $*$ associative?  Is $*$ commutative? 
\item[] {\it Solution:}  Yes to both.  Commutativity just says 
$S * T = S \cup T = T \cup S = T * S$ and that follows from the 
definition of set union.  Similarly, $*$ is associative since for
any subsets $S,T,U$ of $A$, $(S * T) * U = (S \cup T) \cup U$.
This is the set of all elements of $A$, that are in $S$, or in $T$, or in 
$U$, which is the same as $S \cup (T \cup U) = S * (T * U)$.    
\item[b.]  Is there an identity element in $\mathcal{P}(A)$ for this
operation?  
\item[] {\it Solution:}  Yes, $\emptyset$ (the empty subset of $A$)
is an identity element, since $\emptyset \cup S = S \cup \emptyset = S$
for all $S \subseteq A$.  
\item[c.]  What elements of $\mathcal{P}(A)$ have inverses for this operation?  
\item[] {\it Solution:}  If $S = \emptyset$, then let $T = \emptyset$ too.
Then $S \cup T = \emptyset = T \cup S$.  Therefore $S = \emptyset$ does
have an inverse.  Now, we claim that this is the \emph{only} subset of 
$A$ that does have an inverse for this operation: if $S$ does have
an inverse, then $S = \emptyset$.  We will show the contrapositive form.
Let $S \ne \emptyset$.   An inverse
for $S$ would be a subset $T$ such that $S \cup T = \emptyset$.
But $S \subseteq S \cup T$ for all $T$, so $S\cup T \ne \emptyset$.
Therefore $S = \emptyset$ is the only $S$ that does have an inverse.  
\item[d.]  Make a table like the one in problem 3 of the `A' section 
for the operation in this problem, when $A = \{a,b\}$.  List the elements of
$\mathcal{P}(A)$ in this order on the borders of the table:
$$\emptyset, \{a\}, \{b\}, \{a,b\}.$$ 
Do you notice something?
\item[] {\it Solution:}  The table is:
\[
\begin{array}{rrrrrr}
          *& \vline & \emptyset & \{a\} & \{b\} & \{a,b\} \\ \hline
          \emptyset & \vline & \emptyset & \{a\} & \{b\} & \{a,b\} \\
          \{a\} & \vline & \{a\}  & \{a\} & \{a,b\} & \{a,b\} \\
          \{b\} & \vline & \{b\} & \{a,b\} & \{b\} & \{a,b\} \\
          \{a,b\}& \vline & \{a,b\} & \{a,b\} & \{a,b\} & \{a,b\}
\end{array}
\]
The thing you should notice is that this table has exactly the same
``pattern'' as the table from problem 3 in the `A' section.  If you 
replace $\emptyset \mapsto x$, $\{a\} \mapsto y$, $\{b\} \mapsto z$,
$\{a,b\} \mapsto w$, then you get exactly the other table.   
\end{enumerate}
\item[4.]  Let $\times : \mathbb{R}^3 \times \mathbb{R}^3 \to \mathbb{R}^3$
be the vector \emph{cross product} from multivariable calculus (MATH 241).  
Recall that this operation is defined by the following formula:
$$(a_1,a_2,a_3) \times (b_1,b_2,b_3) = (a_2b_3 - a_3b_2, -(a_1b_3 - a_3b_1), a_1b_2 - a_2b_1).$$
\begin{enumerate}
\item[a.]  Show that $\times$ is not associative and not commutative.
\item[] {\it Solution:}  To show an operation does not have these properties, it suffices
to find specific cases where they do not hold (negation of a ``for all'' 
statement is a ``there exists'' statement).  
Let $\mathbf{a} = (1,0,0)$, $\mathbf{b} = (0,1,0)$, $\mathbf{c} = (1,1,0)$
We have $\mathbf{a} \times \mathbf{b} = (0,0,1)$, but $\mathbf{b} \times \mathbf{a} = (0,0,-1)$,
so $\times$ is not commutative.  Also,
$$(\mathbf{a} \times \mathbf{b}) \times \mathbf{c} = (0,0,1) \times (1,1,0) = (-1,1,0).$$
But 
$$\mathbf{a} \times (\mathbf{b} \times \mathbf{c}) = (1,0,0) \times (0,0,1) = (0,-1,0).$$
Hence $\times$ is not associative.
\item[b.]  Show that $\times$ does satisfy the \emph{Jacobi identity}:
$$(\mathbf{a} \times \mathbf{b}) \times \mathbf{c} = \mathbf{a} \times (\mathbf{b} \times \mathbf{c}) + \mathbf{b} \times (\mathbf{c} \times \mathbf{a})$$
for all $\mathbf{a},\mathbf{b}$, and $\mathbf{c}$ in $\mathbb{R}^3$.  The $+$ in this
formula means the vector sum in ${\bf R}^3$, defined for vectors $\mathbf{d} = (d_1,d_2,d_3)$ and 
$\mathbf{e} = (e_1,e_2,e_3)$ by the rule
$$\mathbf{d} + \mathbf{e} = (d_1,d_2,d_3) + (e_1,e_2,e_3) = (d_1 + e_1, d_2 + e_2, d_3 + e_3).$$
\item[] {\it Solution:}   Since this is a ``for all'' statement, it \emph{does not} suffice
just to give an example where the equation is true.  Instead, we must show that the 
equation holds for all choices of vectors $\mathbf{a}, \mathbf{b}$, and $\mathbf{c}$ in 
$\mathbb{R}^3$.  To see this, we compute as follows:
\begin{align}
\label{Jleft}
(\mathbf{a} \times \mathbf{b}) \times \mathbf{c} &= 
(a_2b_3 - a_3b_2, -(a_1b_3 - a_3b_1), a_1b_2 - a_2b_1) \times (c_1,c_2,c_3) \\ \nonumber
&= ((a_3b_1 - a_1b_3)c_3 - (a_1b_2 - a_2b_1)c_2, (a_3b_2 - a_2b_3)c_3 + (a_1b_2 - a_2b_1)c_1,\\ \nonumber
&\qquad (a_2b_3 - a_3b_2)c_2 + (a_1b_3 - a_3b_1)c_1)\\ \nonumber
&= (a_3b_1c_3 - a_1b_3c_3 - a_1b_2c_2 + a_2b_1c_2, a_3b_2c_3 - a_2b_3c_3 + a_1b_2c_1 - a_2b_1c_1,\\ \nonumber
&\qquad a_2b_3c_2 - a_3b_2c_2 + a_1b_3c_1 - a_3b_1c_1).
\end{align}
Similarly,
\begin{align}
\label{Jright1}
\mathbf{a} \times (\mathbf{b} \times \mathbf{c}) &= 
(a_1,a_2,a_3) \times (b_2c_3 - b_3c_2, -(b_1c_3 - b_3c_1), b_1c_2 - b_2c_1)\\ \nonumber
&= (a_2(b_1c_2 - b_2c_1) + a_3(b_1c_3 - b_3c_1), -a_1(b_1c_2 - b_2c_1) + a_3(b_2c_3 - b_3c_2),\\ \nonumber
&\qquad -a_1(b_1c_3 - b_3c_1) - a_2(b_2c_3 - b_3c_2))\\ \nonumber
&=  (a_2b_1c_2 - a_2b_2c_1 + a_3b_1c_3 - a_3b_3c_1, -a_1b_1c_2 + a_1b_2c_1 + a_3b_2c_3 - a_3b_3c_2,\\ \nonumber
&\qquad -a_1b_1c_3 + a_1b_3c_1 - a_2b_2c_3 + a_2b_3c_2)
\end{align}
and
\begin{align}
\label{Jright2}
\mathbf{b} \times (\mathbf{c} \times \mathbf{a}) &= 
(b_1,b_2,b_3) \times (c_2a_3 - c_3a_2, -(c_1a_3 - c_3a_1), c_1a_2 - c_2a_1) \\ \nonumber
&= (b_2(c_1a_2 - c_2a_1) + b_3(c_1a_3 - c_3a_1), -b_1(c_1a_2 - c_2a_1) + b_3(c_2a_3 - c_3a_2),\\ \nonumber
&\qquad -b_1(c_1a_3 - c_3a_1) - b_2(c_2a_3 - c_3a_2))\\ \nonumber
&= (a_2b_2c_1 - a_1b_2c_2 + a_3b_3c_1 - a_1b_3c_3, -a_2b_1c_1 +  a_1b_1c_2 + a_3b_3c_2 - a_2b_3c_3,\\ \nonumber
&\qquad -a_3b_1c_1 + a_1b_1c_3 - a_3b_2c_2 + a_2b_2c_3)
\end{align}
Adding $\mathbf{a} \times (\mathbf{b} \times \mathbf{c}) + \mathbf{b} \times (\mathbf{c} \times \mathbf{a})$, we see from Eqs. \eqref{Jright1}, \eqref{Jright2} that there are cancellations in every component of the vectors on the right side.  What is left is
\begin{align*} 
&(a_2b_1c_2 + a_3b_1c_3 - a_1b_2c_2  - a_1b_3c_3, 
a_1b_2c_1 + a_3b_2c_3 -a_2b_1c_1 - a_2b_3c_3,\\
&\qquad + a_1b_3c_1 + a_2b_3c_2 -a_3b_1c_1 - a_3b_2c_2),
\end{align*}
which is the same as \eqref{Jleft}.
This proves the Jacobi identity.

\item[c.]  {\it Extra Credit} In a sense, the additional term $\mathbf{b} \times (\mathbf{a} \times \mathbf{c})$ 
on the right in the Jacobi identity measures the failure of associativity.
Using that idea, is $\mathbf{a} \times (\mathbf{b} \times \mathbf{c})$ \emph{ever} equal to 
$(\mathbf{a} \times \mathbf{b}) \times \mathbf{c}$ when all three of the vectors are 
nonzero?  Explain.  Hint:  One way to approach this is to think about the geometric
conditions on the three vectors under which it will be true that
$$\mathbf{b} \times (\mathbf{c} \times \mathbf{a}) = \mathbf{0}.$$
\item[] {\it Solution:}  One condition under which associativity will hold is this:
The cross product of the two vectors $\mathbf{c}$ and 
$\mathbf{c}$ is the zero vector
($\mathbf{c} \times \mathbf{a}) = (0,0,0)$) when $\mathbf{c}$ and $\mathbf{a}$
point along the same line.  If that is true then the associative law does hold for those
$\mathbf{c}$ and $\mathbf{a}$ with any $\mathbf{b}$.  There are other situations too,
for instance if $\mathbf{b}$ points along the same line as $\mathbf{a} \times \mathbf{c}$.  
\end{enumerate}
\end{enumerate}

\end{document}
