\magnification = \magstep1
\centerline{Mathematics 243, section 3 -- Algebraic Structures}
\centerline{Solutions for Exam 1 -- September 28, 2012}
\bigskip
\noindent
I.  Let $A, B, C$ be any subsets of a universal set $U$.
\item{A)}  Show that if $A \subseteq B$, then $A \cap C \subseteq B \cap C$.
\item{} {\it Solution:}  Let $x \in A\cap C$.  Then 
$x \in A$ and $x \in C$.  It follows from $A \subseteq B$ and $x \in A$ that $x \in B$ as well.
Hence $x \in B$ and $x \in C$, so $x \in B \cap C$.  This shows $A\cap C \subseteq B \cap C$. 
\item{B)}  Is it true that $A - B = A - C$ implies $B = C$?  If you think 
the statement is true, illustrate with a Venn diagram.  If you think the statement
is false, give a counterexample. 
\item{} {\it Solution:}  This statement is false because $A - B = A \cap B'$ and $A - C = A \cap C'$.
To make a counterexample, we just need to think of sets $B$ and $C$ whose complements intersect
$A$ in the same set, but which have different elements.  Here's a 
simple example.  In $U = \{1,2,3\}$, let $A = \{1\}$, $B = \{2,3\}$ and $C = \{2\}$.
Then $B' = \{1\} = A \cap B'$ and $C' = \{1,3\}$, so $A \cap C' = \{1\}$.  But clearly $B \ne C$.  
\bigskip
\noindent
II. Consider the following statement, where $A$ is a nonempty set.
``If $f : A \to B$ is an onto mapping, then for all $b\in B$, the
set $f^{-1}(\{b\})$ is nonempty.''
Give the contrapositive form of this statement.
Are the given statement and its contrapositive true or false?  Explain.
\bigskip
\noindent
{\it Solution:}  The contrapositive form is:  ``If for some $b \in B$ the set $f^{-1}(\{b\})$ 
is empty, then $f$ is not an onto mapping.''  This statement and the original form are
equivalent and both true.  By definition, $f$ is onto if for all $b \in B$, there exist
$a \in A$ such that $f(a) = b$.  Those $a$ are precisely the elements of $f^{-1}(\{a\})$,
so that set must be nonempty.  That is the given form of the statement.   
\bigskip
\noindent
III. 
Let $f,g : {\bf Z} \to {\bf Z}$ be the mappings given by
$$f(x) = \cases{2x - 1 & if $x$ is even\cr
             x + 1 & if $x$ is odd\cr}
  \qquad
  g(x) = \cases{x & if $x$ is even\cr
             x + 1 & if $x$ is odd\cr}$$
\item{A)} Let $S = \{1,2,3\}$ and 
$T = \{0,3,6\}$.  What is $g^{-1}(T) \cap f(S)$?
\item{} {\it Solution:}  We have $f(S) = \{f(1),f(2),f(3)\} = \{2,3,4\}$.
Then $g^{-1}(T) = \{x\in {\bf Z}\mid g(x) \in T\} = \{0,-1,6,5\}$. (Note that 
$g(x)$ is even for all $x$, so there are no $x$ that map to $3 \in T$.)  So 
$g^{-1}(T) \cap f(S) = \emptyset$.  
\item{B)} What is the mapping $f\circ g$?  
\item{}  {\it Solution:}  By the observation about $g$, given in the previous
part, in computing $(f\circ g)(x)$, we never use the part of the definition
of $f$ for odd $x$, and:
$$(f\circ g)(x) = \cases{2x - 1 & if $x$ is even\cr
                         2(x+1) - 1 = 2x + 1 & if $x$ is odd\cr}$$
%\item{C)} (5) Is $f$ a permutation of ${\bf Z}$?  Why or why not?
%\item{} {\it Solution:}  The answer is no, since $f$ is not onto.  For instance,
%consider $y = 5$ which is an odd number.  This says that $5 \ne f(x)$ for 
%any odd $x$, since $x$ odd implies $f(x)$ even.  Moreover, $5 = 2x - 1$ only when $x = 3$.  But we do not use
%the ``even'' part of the definition of $f$ to get $f(3)$.  So there is no 
%$x$ with $f(x) = 5$.  
\bigskip
\noindent         
IV.  Consider the binary operation on ${\bf Z}$ defined by $x * y = x + xy + y$.
\item{A)} Is $*$ associative?   
\item{} {\it Solution:}  Let $x,y,z$ be any three integers.  We have 
$$
\eqalign{
(x * y) * z &= (x + xy + y)*z\cr 
&= x + xy + y + (x + xy + y)z + z \cr
&= x + y + z + xy + xz + yz + xyz \cr
}$$
On the other hand, we have 
$$
\eqalign{
x * (y * z) &= x*(y + yz + z)\cr 
&= x + x(y + yz + z) + y + yz + z \cr
&= x + y + z + xy + xz + yz + xyz \cr
}$$
These are always the same, so $*$ is associative.
\item{B)}  There is an identity element for $*$.  Find it and justify your claim. 
\item{} {\it Solution:}  By inspection $e = 0$ acts as an identity for $*$.
%\item{C)} (5)  Which $x \in {\bf Z}$ have inverses for $*$?
\bigskip
\noindent
V. (15) Let $A \in M_{2\times 2}({\bf Z})$ be the matrix $A = (a_{ij})$ defined by $a_{ij} = i-j$,
and let $B \in M_{3\times 2}({\bf Z})$ be the matrix $B = (b_{ij})$ defined by $b_{ij} = i + 2j$.
Which of the two products $AB, BA$ are defined?  Compute the one(s) that are defined.
\bigskip
\noindent
{\it Solution:}  By the given information, 
$$A = \pmatrix{0&-1\cr 1&0\cr}\qquad {\rm and} \qquad B = \pmatrix{3&5\cr 4&6\cr 5&7\cr}$$
The sizes match to multiply only for $BA$ and 
$$BA = \pmatrix{5&-3\cr 6&-4\cr7&-5}$$
\bigskip
\noindent
{\it Extra Credit}  Which $x \in {\bf Z}$ have inverses for the binary operation $*$
from question IV?
\bigskip
\noindent
\item{} {\it Solution:}  $x$ has an inverse $y$ when $x + xy + y = 0$ (using the identity 
from part B) of IV.  This says $y = {-x\over x+1}$.  But this formula gives integer values
only when $x = 0$ and $x = -2$.  The inverse of $0$ is $0$ and the inverse of $-2$ is $-2$.  
\bye
 
