\problemdata                                                             
        {Sets} % latex-friendly label for the prob.
        {Property of Group Sets} % The topic(s) of the problem content.  
        {Spring 00} % Source (if known)                                    
        {S01 Tutorial 1, 3} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
A {\em group} is a set $G$ together with a binary operation $\cdot: G      
\times G \rightarrow G$ that satisfies the following axioms.               
                                                                           
                                                                           
Identify at least two ``normal'' sets and operations on them               
  that satisfy the group axioms.                                           
                                                                           
\begin{enumerate}                                                          
                                                                           
\item $\forall a,b,c \in G,(a \cdot b) \cdot c = a \cdot (b \cdot          
  c)$.\label{axiom:associativity}                                          
                                                                           
\item $\exists e \in G$ (called the {\em identity}) such that $\forall     
  a \in G, a \cdot e = e \cdot a = a$.\label{axiom:identity}               
                                                                           
\item $\forall a \in G, \exists a^{-1} \in G$ (called the {\em 
    inverse} of $a$), such that $a \cdot a^{-1} = a^{-1} \cdot a =        
  e$.\label{axiom:inverse}                                                
                                                                          
\end{enumerate}                                                           
                                                                          
\solution{%                                                               
  Addition defines a group on the integers, and multiplication a group    
  on the positive rationals.                                              
                                                                          
  As an example of a finite group, let $G$ be the set of truth values,    
  i.e., $G = \{T, F\}$, and the binary operation~$\cdot$ be~XOR. In       
  this group, $F$~is the identity and $T$~is its own inverse.             
                                                                          
  (The above group can be generalized: Consider for instance all 8-bit    
  binary numbers and let the group operation be bit-wise XOR. This         
  gives a group with 256~elements where 0 is the identity and every        
  element is its own inverse.)}                                            
                                                                           
Using the three group axioms prove the following propositions.             
                                                                           
\begin{problemparts}                                                       
                                                                           
\ppart Show, by contradiction, that the identity element is unique.        
                                                                           
\solution{%                                                                
  \begin{proof}[Proof by contradiction]                                    
    Suppose there are two identities $e_1$ and~$e_2$ such that $e_1        
    \neq e_2$. Then, by axiom~\ref{axiom:identity}, $e_1 e_2 = e_1$        
    since $e_2$~is an identity, but, according to the same axiom, $e_1     
    e_2 = e_2$ since $e_1$~is an identity. Thus $e_1 = e_2$, which         
    contradicts our assumption that $e_1 \neq e_2$.                        
  \end{proof}}                                                             
                                                                           
\ppart Show that for every $g \in G$, the inverse of~$g$ is unique.        
We can therefore write the inverse element as $g^{-1}$ with no fear of     
ambiguity.                                                                 
                                                                           
\solution{%                                                                
  \begin{proof}[Proof by contradiction]                                    
    Consider an arbitrary $g \in G$.  Suppose there are two different      
    inverses of~$g$; we denote them by $g^{-1}$ and~$g^*$. According       
    to axiom~\ref{axiom:inverse}, $g^{-1}g = e$ and $gg^* = e$ since       
    we assumed that $g^{-1}$ and~$g^*$ are inverses of~$a$. Thus,          
    $(g^{-1}g)g^* = eg^* = g^*$, where the second equality follows         
    from axiom~\ref{axiom:identity}. Similarly, $g^{-1}(gg^*) =            
    g^{-1}e = g^{-1}$. But by axiom~\ref{axiom:associativity},             
    $(g^{-1}g)g^* = g^{-1}(gg^*)$. To conclude,                            
    \begin{displaymath}                                                    
      g^* = eg^* = (g^{-1}g)g^* = g^{-1}(gg^*) = g^{-1}e = g^{-1},         
    \end{displaymath}                                                      
    which contradicts our assumption that $g^{-1}$ and~$g^*$ are              
    different.                                                                
  \end{proof}}                                                                
                                                                              
\ppart Show $\forall (g \in G) (g^{-1})^{-1} = g$                             
                                                                              
\solution{%                                                                   
  \begin{proof}[Direct proof]                                                 
    Consider an arbitrary $g \in G$. By axiom~\ref{axiom:inverse} we          
    know that $g^{-1} \in G$. If we can find some $h \in G$ satisfying        
    axiom~\ref{axiom:inverse} where $a$ is instantiated with~$g^{-1}$ and     
    $a^{-1}$~is instantiated with~$h$, i.e., some $h \in G$ such that         
    $g^{-1}h = hg^{-1} = e$, we know---since we proved above that the         
    inverse is unique---that $h$~is the inverse of~$g^{-1}$. However,         
    the choice $h = g$ satisfies axiom~\ref{axiom:inverse}. Thus,             
    $g$~is the inverse of~$g^{-1}$.                                            
  \end{proof}}                                                                 
                                                                               
\ppart Show $\forall g,h \in G, (g \cdot h)^{-1} = h^{-1} \cdot g^{-1}$        
                                                                               
\solution{%                                                                    
  \begin{proof}[Direct proof]                                                  
    As in the above proof, it suffices to verify that                          
    axiom~\ref{axiom:inverse} where $a$~is instantiated with~$gh$ and          
    $a^{-1}$~is instantiated with~$h^{-1}g^{-1}$ holds. We have                
    \begin{displaymath}                                                        
      (gh)(h^{-1}g^{-1}) = \bigl((gh)h^{-1}\bigr)g^{-1} =                      
      \bigl(g(hh^{-1})\bigr)g^{-1} = (ge)g^{-1} = gg^{-1} = e,                 
    \end{displaymath}                                                          
    where the first two equalities follow from                                 
    axiom~\ref{axiom:associativity}, the third and fifth from                  
    axiom~\ref{axiom:inverse}, and the fourth from                             
    axiom~\ref{axiom:identity}. Similarly                                      
    \begin{displaymath}                                                              (h^{-1}g^{-1})(gh) = \bigl((h^{-1}g^{-1})g\bigr)h =       
      \bigl(h^{-1}(g^{-1}g)\bigr)h = (h^{-1}e)h = h^{-1}h = e,  
    \end{displaymath}                                           
    which completes the proof.                                  
  \end{proof}}                                                  
                                                                
\end{problemparts}                                              
\end{problem}            
                                 
