\magnification=\magstep1
\centerline{Mathematics 243, section 1 -- Algebraic Structures}
\centerline{Selected Solutions, Problem Set 3}
\centerline{October 1, 2003}
\bigskip
\noindent
1.4/9  Let $a\in A$, and assume $b,c$ are both inverses of $a$ for $*$.
Consider the ``product'' $(b*a)*c$.  First, since 
$b$ is an inverse for $a$, $(b*a)*c = e*c = c$ (where the 
last equality comes since $e$ is the identity element for $*$).  But we 
also know $*$ is associative, so 
$(b*a)*c = b*(a*c) = b*e = b$.  Hence $b = c$, so the inverse
of $a$ is unique (if it exists).
\bigskip
\noindent
1.4/13  The problem says show that $f : A \to A$ has
a left inverse (for composition) if and only if $f^{-1}(f(S)) = S$
for all subsets $S \subseteq A$.  From Discussion 2, or 
Lemma 1.23 in the text, we know that $f$ has a left inverse
if and only if $f$ is injective.  Hence it suffices to prove
that $f$ is injective if and only if $f^{-1}(f(S)) = S$ for 
all $S \subseteq A$.  

\bigskip
\noindent
$\Rightarrow$:  We show that $f$ injective implies $f^{-1}(f(S)) = S$
for all $S$.  The inclusion $S\subseteq f^{-1}(f(S))$ is automatic
from the definitions of the direct and inverse images (if you don't
see why, work this out from the definitions(!)).  So the key
point is the other inclusion.  Let $x \in f^{-1}(f(S))$.  By 
definition, this means $f(x) \in f(S)$, so $f(x) = f(a)$ for 
some $a\in S$.  But we are assuming $f$ is injective, so 
$x = a \in S$.  Hence $x \in S$ and $f^{-1}(f(S)) \subseteq S$,
which finishes this part of the proof.

\bigskip
\noindent
$\Leftarrow$:  Now we assume that $f^{-1}(f(S)) = S$ for all $S$, and use
that to show $f$ is injective.  Let $x \in A$, and consider the 
subset $S = \{x \}$.  By hypothesis in this part, 
$f^{-1}(f(\{x \})) = \{x \}$.  If $f(a) = f(x)$ for some $a \in A$,
then by the definition of the direct image, $f(a) \in f(S)$.
Then by the definition of the inverse image, $a \in f^{-1}(f(S))$.
But then $a \in S = \{x\}$, so the only possibility is $a = x$.
Hence $f$ is injective.  This concludes the proof.

\bigskip
\noindent
1.4/13  The problem says show that $f : A \to A$ has
a right inverse (for composition) if and only if $f(f^{-1}(T)) = T$
for all subsets $T \subseteq A$.  From Discussion 2, or 
Lemma 1.24 in the text, we know that $f$ has a right inverse
if and only if $f$ is surjective.  Hence it suffices to prove
that $f$ is surjective if and only if $f(f^{-1}(T)) = T$ for 
all $T \subseteq A$.

\bigskip
\noindent
$\Rightarrow$:  We show that $f$ surjective implies $f(f^{-1}(T)) = T$
for all $T$.  The inclusion $f(f^{-1}(T))\subseteq T$ is automatic
from the definitions of the direct and inverse images (if you don't
see why, work this out from the definitions(!)).  So the key
point is the other inclusion.  Let $x \in T$.  Since $f$ is surjective,
there is some $a \in A$ such that $f(a) = x$.  By definition 
$a \in f^{-1}(T)$, so $x = f(a) \in f(f^{-1}(T))$.  Hence
$T \subset f(f^{-1}(T))$.

\bigskip
\noindent
$\Leftarrow$:  Now we assume that $f(f^{-1}(T)) = T$ for all subsets, and use
that to show $f$ is surjective.  As in problem 13 above,
the ``action'' all goes on with one-element subsets(!)
Let $x \in A$ be arbitrary, and consider $T = \{x \}$.
Since $T = f(f^{-1}(T))$, $x = f(a)$ for some $a \in f^{-1}(T)$.
But $x$ was arbitrary in $A$, so
this shows that all $x$ in $A$ are in the range of $f$.  Hence
$f$ is surjective. This concludes the proof.

\bigskip
\noindent
1.6/19.  Let $\{A_\lambda\}$, $\lambda \in {\cal L}$ be a collection
of subsets of $A$ defining a partition
of $A$.  That is we are given:
$$\cases{A = \bigcup_{\lambda\in {\cal L}} A_\lambda & and \cr
         A_\lambda \cap A_\mu = \emptyset & if $\lambda\ne\mu$\cr}$$
The problem is to show that if we define a relation $R$ on $A$ 
by 
$$x R y \Leftrightarrow x, y \in {\rm the\ same\ } A_\lambda$$
then $R$ is an equivalence relation.  (Note: by the second property
of a partition, $x$ and $y$ cannot be in more than one of the 
$A_\lambda$.) 
To show that $R$ is an equivalence relation, we check that $R$
is reflexive, symmetric, and transitive.

\bigskip
\noindent
reflexive:  $x R x$ is true for all $x$ since there is just one 
subset $A_\lambda$ such that $x \in A_\lambda$ (the different 
subsets in the partition do not overlap).

\bigskip
\noindent
symmetric:  If $x R y$ is true, then $x,y \in A_\lambda$.
But that says $y,x \in A_\lambda$ also, so $y R x$ follows.

\bigskip
\noindent
transitive:  If $x R y$ and $y R z$, then $x,y$ are in the 
same $A_\lambda$, and $y, z$ are in the same $A_\lambda$.
Hence $x,z$ are in the same $A_\lambda$, so $x R z$ follows.
\bye
           