\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 1}
\centerline{{\bf due:} September 7, 2012}
\vskip 10pt
\noindent
{\it 'A' Section}
\bigskip
\begin{enumerate}
\item[1.]  Let 
\begin{align*}
U &= \{1,2,3,\ldots,12\}\\
A &= \{1,3,5,7,9,11\}\\
B &= \{4,6,8\}\\
C &= \{7,8,9,10\}
\end{align*}
Find each of the following sets:
\begin{enumerate}
\item[a.] $A' \cap C$
\item[b.] $A \cup C'$
\item[c.] $A \cap (B \cup C)$
\item[d.] $(A - B) \cup (B - C)$
\end{enumerate}
\item[2.]  Let $S = \{a,b,c,d\}$
\begin{enumerate}
\item[a.]  List all elements of $\mathcal{P}(S)$ (the power set)
\item[b.]  Write out all of the \emph{partitions} of $S$.  
\end{enumerate}
\item[3.]  Let $A = \{1,2\}$.  For each pair of subsets $S,T \subset A$ (including
the cases where $S$ or $T$ is $\emptyset$ or $A$ itself), define $S + T = (S \cup T) - (S \cap T)$.  Make a chart with rows labeled with the possibilities for $S$, columns labeled with
the possibilities for $T$, and entries showing which subset of $A$ is produced as
$S + T$.  (For example, in the row for $S = \{1\}$ and the column for $T = \{1,2\}$, your 
chart will contain the entry $S + T = \{1,2\} - \{1\} = \{2\}$.) 
\item[4.]  Let $A = \{1,2,3,4,5\}$, $B = \{a,b,c,d,e\}$ and let $f : A \to B$
be defined by $f(1) = a$, $f(2) = e$, $f(3) = c$, $f(4) = a$, and $f(5) = e$.
Find the following:
\begin{enumerate}
\item[a.]  $f(A)$
\item[b.]  $f(S)$ for $S = \{3,4,5\} \subset A$
\item[c.]  $f^{-1}(f(S))$ for $S = \{1,2,3\} \subset A$
\item[d.]  $f^{-1}(T)$ for $T = \{c,d,e\} \subset B$
\item[e.]  $f(f^{-1}(T))$  for $T = \{a,b,c\} \subset B$
\end{enumerate}  
\item[5.]  Let $P$ be the set of positive integers and 
let $f : P \to P$ be defined by 
$$f(x) = \begin{cases}
         3x + 1 & \text{if } x \text{ is odd}\\
         x/2 & \text{if } x \text{ is even}
         \end{cases}$$
\begin{enumerate}
\item[a.] Compute $f(7)$, $f(f(7))$, $f(f(f(7)))$, etc.  What happens eventually if
you continue this long enough?  Try the same thing with $f(9)$, $f(f(9))$, $f(f(f(9)))$, etc.
\item[b.] Show by example that $f$ is \emph{not} one-to-one.
\item[c.] Explain why $f$ \emph{is} onto.  
\end{enumerate}
\end{enumerate}
\vskip 10pt
\noindent
{\it 'B' Section}
\vskip 10pt
\begin{enumerate}
\item[1.] Let $A,B$ be any two subsets of a universal set $U$. 
\begin{enumerate}
\item[a.]  Prove that $(A \cap B)' = A' \cup B'$.
\item[b.]  Prove that $(A \cup B) - (A \cap B) = (A \cap B') \cup (A' \cap B)$.
\end{enumerate}
\item[2.] Let $A$ and $B$ be finite sets with $|A| = m$ and $|B| = n$.
\begin{enumerate}
\item[a.]  Show that if $m > n$, there are no one-to-one mappings $f : A \to B$.
\item[b.]  Show that if $n > m$, there are no onto mappings $f : A \to B$.
\item[c.]  Assume $n \ge m$.  How many different one-to-one mappings 
$f : A \to B$ are there?  Prove your assertion.  
\end{enumerate}
\item[3.] Refer back to Problem 4 in the 'A' section for some examples of the 
patterns described in this exercise.
\begin{enumerate}
\item[a.]  Show that if $f$ is not one-to-one, then there is some $S \subset A$
such that $f^{-1}(f(S)) \ne S$.  
\item[b.]  Conversely, show that if $f$ is one-to-one, then $f^{-1}(f(S)) = S$
for all $S \subset A$.
\item[c.]  Show that if $f$ is not onto, then there is some $T \subset B$
such that $f(f^{-1}(T)) \ne T$
\item[d.]  Conversely, show that if $f$ is onto, then $f(f^{-1}(T)) = T$ for 
all $T \subset B$.    
\end{enumerate}
\end{enumerate}

\end{document}
