\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 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[] {\it Solution:}  $A'$ is the complement of $A$ in the universal
set $U$, so $A' = \{2,4,6,8,10\}$, and $A' \cap C = \{8,10\}$.
\item[b.] $A \cup C'$
\item[] {\it Solution:}  Similarly, $C' = \{1,2,3,4,5,6,11,12\}$ so 
$A \cup C' = \{1,2,3,4,5,6,7,9,11,12\} = U - \{8,10\}$.
\item[c.] $A \cap (B \cup C)$
\item[] {\it Solution:}  $B \cup C = \{4,6,7,8,9,10\}$ so $A \cap (B \cup C) = \{7,9\}$.  
\item[d.] $(A - B) \cup (B - C)$
\item[] {\it Solution:}  $A - B = \{1,3,5,7,9,11\} = A$ since $A \cap B = \emptyset$.  
Then, $B - C = \{4,6\}$.  So $(A - B) \cup (B - C) = \{1,3,4,5,6,7,9,11\}$.  
%\item[] {\it Grading:}  2 points for each part -- take off one point for ``essentially OK''
%but some small error.  
\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[] {\it Solution:}  There are $2^4 = 16$ subsets of $S$:
\begin{align*}
\text{one of cardinality } 0 &: \emptyset\\
\text{four of cardinality } 1 &: \{a\}, \{b\}, \{c\}, \{d\}\\
\text{six of cardinality } 2 &: \{a,b\}, \{a,c\}, \{a,d\}, \{b,c\}, \{b,d\}, \{c,d\}\\
\text{four of cardinality } 3 &: \{a,b,c\}, \{a,b,d\}, \{a,c,d\}, \{b,c,d\}\\
\text{one of cardinality } 4 &: \{a,b,c,d\}
\end{align*}
The power set $\mathcal{P}(S)$ is the set whose elements are these 16 subsets.   
%\item[] {\it Grading:}  4 points for this part.  
\item[b.]  Write out all of the \emph{partitions} of $S$.  
\item[] {\it Solution:}  A partition is a collection of nonempty, pairwise disjoint subsets
whose union is $S$.  Up to the labeling of the individual subsets the possible partitions are
\begin{align*}
\text{cardinalities 1,1,1,1} &: \{a\}, \{b\}, \{c\}, \{d\}\\
\text{cardinalities 1,1,2} &:  \{a\}, \{b\}, \{c,d\}\\
                           &     \{a\}, \{c\}, \{b,d\}\\
                           &     \{a\}, \{d\}, \{b,c\}\\
                           &     \{b\}, \{c\}, \{a,d\}\\
                           &     \{b\}, \{d\}, \{a,c\}\\
                           &     \{c\}, \{d\}, \{a,b\}\\ 
\text{cardinalities 1,3} &: \{a\}, \{b,c,d\}\\
                                   &  \{b\}, \{a,c,d\}\\
                                   &  \{c\}, \{a,b,d\}\\
                                   &  \{d\}, \{a,b,c\}\\
\text{cardinalities 2,2} &: \{a,b\}, \{c,d\}\\
                         &          \{a,c\}, \{b,d\}\\
                         &         \{a,d\}, \{b,c\}\\
\text{cardinality 4} &: \{a,b,c,d\}.
\end{align*}
%\item[] {\it Grading:}  Any equivalent form is OK, 6 points total.  Take off one point
%if they miss a whole category, and add a comment.                                  
\end{enumerate}
\item[3.]  Let $A = \{1,2\}$.  For each pair of subsets $S,T \subseteq 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[] {\it Solution:}  The table looks like this:
\[
\begin{array}{cccccc}
          +& \vline & \emptyset & \{1\} & \{2\} & \{1,2\} \\ \hline
          \emptyset& \vline & \emptyset & \{1\} & \{2\} & \{1,2\} \\
          \{1\}& \vline & \{1\} & \emptyset & \{1,2\} & \{2\} \\
          \{2\}& \vline & \{2\} & \{1,2\} & \emptyset & \{1\} \\
          \{1,2\}& \vline & \{1,2\} & \{2\} & \{1\} & \emptyset
\end{array}
\]
%\item[] {\it Grading:}  16 points, one for each table entry.
\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[] {\it Solution:}  $f(A) = \{a,c,e\}$.
\item[b.]  $f(S)$ for $S = \{3,4,5\} \subset A$
\item[] {\it Solution:}  $f(S) = \{f(3),f(4),f(5)\} = \{a,c,e\}$
\item[c.]  $f^{-1}(f(S))$ for $S = \{1,2,3\} \subset A$
\item[] {\it Solution:}  We have $f(S) = \{a,c,e\}$, and $f^{-1}(f(S)) = \{1,2,3,4,5\}$
since every image under $f$ is contained in the set $\{a,c,e\}$.
\item[d.]  $f^{-1}(T)$ for $T = \{c,d,e\} \subset B$
\item[] {\it Solution:}  $f^{-1}(T) = \{x \in A \mid f(x) \in T\} = \{2,3,5\}$.
\item[e.]  $f(f^{-1}(T))$  for $T = \{a,b,c\} \subset B$
\item[] {\it Solution:}  Since $T = \{a,b,c\}$, $f^{-1}(T) = \{1,3,4\}$.  So
$f(f^{-1}(T)) = \{f(1),f(3),f(4)\} = \{a,c\}$.  
%\item[] {\it Grading:}  2 points each.  
\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[] {\it Solution:}  To simplify the notation, we write $\to$ for the result of applying $f$.
For instance, since $7$ is odd, $7 \to 3\cdot 7 + 1 = 22$.  Then since $22$ is even, 
$22 \to 11$.  Following this until something ``interesting'' happens:
\begin{align*}
&7 \to 22 \to 11 \to 34 \to 17 \to 52 \to 26 \to 13 \to 40 \to 20 \to \\
&10 \to 5 \to 16 \to 8 \to 4 \to 2 \to 1 \to 4 \cdots
\end{align*}
Note at this point the values will repeat the $4 \to 2 \to 1$ cycle forever.  

Starting from 9, we have 
$$9 \to 28 \to 14 \to 7 \to \cdots$$
so this continues with the pattern for $f(7)$--it also lands in the $4\to 2 \to 1 \to 4$ cycle
eventually.

\noindent
{\it Comment:}  It is an \emph{open question} whether that the same behavior
will happen starting from \emph{any positive} $n$.  This means that there are
lots of people who have worked on this but they have not been able
to solve this problem yet.  (Yes, there are
unsolved problems in mathematics!  A part of what mathematics professors do is to 
try to find solutions to these unsolved problems -- this is what it means to do 
\emph{research} in mathematics.)
In this case, if you can prove that, starting from any $n \in P$, the function $f$ \emph{always} 
takes you into the $4 \to 2 \to 1 \to 4$ cycle \emph{eventually}, you'll be rich and famous (well
famous, anyway!)
\item[b.] Show by example that $f$ is \emph{not} one-to-one.
\item[] {\it Solution:}  For instance, $f(1) = 4$ and $f(8) = 4$.  Since $1 \ne 8$, this
says $f$ is not one-to-one.  (There are infinitely many other cases like this as well, one
for each odd positive integer.
For instance, $f(3) = 10 = f(20)$, etc.  
\item[c.]  Explain why $f$ \emph{is} onto.
\item[] {\it Solution:}  $f$ is an onto mapping since if $n \in P$ is any positive
integer, $f(x) = n$ if $x = 2n$.  Note that $2n$ is always an even number so that
$f(2n) = (2n)/2 = n$.  
%\item[] {\it Grading:}  4 points for part a (minus 1 if they stop before the repeating
%pattern and add a comment) 2 points each for parts b and c.    
\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[] {\it Solution:}  Let $x \in (A \cap B)'$.  This means that $x \notin A \cap B$,
so $x \notin A$ or $x \notin B$.  But by definition of set union that implies
$x \in A' \cup B'$.  Hence $(A \cap B)' \subseteq A' \cup B'$.  Conversely, suppose
$x \in A' \cup B'$.  Then $x \in A'$ or $x \in B'$, or equivalently: $x \notin A$ or 
$x \notin B$.  This implies that $x \notin A \cap B$ so $x \in (A \cap B)'$.  
We have $A' \cup B' \subseteq (A \cap B)'$  Because of the two containments, 
$A' \cup B' = (A \cap B)'$ follows.  
\item[b.]  Prove that $(A \cup B) - (A \cap B) = (A \cap B') \cup (A' \cap B)$.
\item[] {\it Solution:}  By definition of the set difference, 
$(A \cup B) - (A \cap B) = (A\cup B) \cap (A\cap B)'$.
By part a of this problem, this is the same as 
$(A\cup B) \cap (A'\cup B')$.  By the distributive laws for intersection over
union and commutative laws for intersections, we have
\begin{align*}
(A\cup B) \cap (A'\cup B') &= (A \cap A') \cup (B\cap A') \cup (B\cap A') \cup (B\cap B')\\
&= \emptyset \cup (A'\cap B) \cup (A \cap B') \cup \emptyset\\
&= (A' \cap B) \cup (A \cap B').
\end{align*}
This is what we wanted to show.  
\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[] {\it Solution:}  Write the elements in $A$ as 
$A = \{a_1,a_2, \ldots, a_m\}$.  So $B$ must contain the set
$\{f(a_1),\ldots,f(a_m)\}$.
But these cannot be distinct in $B$ since $B$ contains only $n < m$ distinct
elements.  Therefore $f(a_i) = f(a_j)$ for some $i \ne j$ and as a result $f$
is not one-to-one. 
\item[b.]  Show that if $n > m$, there are no onto mappings $f : A \to B$.
\item[] {\it Solution:}  Write $A = \{a_1,\ldots, a_m\}$ again.  By definition,
$f(A) = \{f(a_1),\ldots, f(a_m)\}$.  There are at most $m$ distinct elements
of this set, and $n > m$ elements in $B$.  There is no way $f(A) = B$ can
hold since there are at least $n - m$ elements of $B$ that are not images
of elements in $A$.  Therefore, $f$ is not onto.
\item[c.]  Assume $n \ge m$.  How many different one-to-one mappings 
$f : A \to B$ are there?  Prove your assertion.  
\item[] {\it Solution:}  Write $A = \{a_1,\ldots,a_m\}$ again.  There
are $n$ different possibilities for $f(a_1)$.  Once that element of $B$
is determined, there are $n - 1$ different possibilities for $f(a_2) \ne f(a_1)$, and 
therefore $n\cdot(n-1)$ possible choices for those two images.  Then
once $f(a_1), f(a_2)$ are determined, there are $n - 2$ possibilities for $f(a_3) \ne f(a_1), f(a_2)$,
and $n(n-1)(n-2)$ possible choices for those three images.
Continuing in the same way, we see there are
$$n(n-1)(n-2)\cdot \cdots\cdot (n - (m - 1))$$
different one-to-one mappings $f : A \to B$.  
\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 \subseteq A$
such that $f^{-1}(f(S)) \ne S$.  
\item[] {\it Solution:}  If $f$ is not one-to-one, there are $a_1 \ne a_2 \in A$
such that $f(a_1) = f(a_2) = b$.  So let $S = \{a_1\}$. We have $f(S) = \{b\}$, but
now $a_1, a_2 \in f^{-1}(f(S))$, so $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 \subseteq A$.
\item[] {\it Solution:}  It is true by definition that $S \subseteq f^{-1}(f(S))$ for
all subsets $S \subseteq A$.
So what we must show is that if $f$ is one-to-one, then $f^{-1}(f(S)) \subseteq S$, 
since that will then imply $f^{-1}(f(S)) = S$.  
Suppose $t \in f^{-1}(f(S))$.  Then by definition, this means that $f(t) = f(s)$ for 
some $s \in S$.   Since $f$ is assumed to be one-to-one,
this implies $s = t$, so $t \in S$.  This shows that $f^{-1}(f(S)) \subseteq S$, and
this concludes the proof.
\item[c.]  Show that if $f$ is not onto, then there is some $T \subseteq B$
such that $f(f^{-1}(T)) \ne T$.
\item[] {\it Solution:}  If $f$ is not onto, there is some $y \in B$ such
that $y \ne f(x)$ for all $x \in A$.  Take $T = \{y\}$.  Then 
$f^{-1}(T) = \emptyset$ and $f(f^{-1}(T)) = \emptyset$, so $f(f^{-1}(T)) \ne T$.  
\item[d.]  Conversely, show that if $f$ is onto, then $f(f^{-1}(T)) = T$ for 
all $T \subseteq B$.    
\item[] {\it Solution:}  By the definitions, $f(f^{-1}(T)) \subseteq T$ 
holds for all $T \subseteq B$.  So what we must show is that if $f$ is onto, then
$T \subseteq f(f^{-1}(T))$ for all $T$, since that will imply $f(f^{-1}(T)) = T$.
So assuming that $f$ is onto, consider
any subset $T$.  For each $y \in T$, there exists $x \in A$ such that $f(x) = y$, 
and each of these $x$ is in $f^{-1}(T)$.  But then, $f(f^{-1}(T))$ contains
every $y$ in $T$, since we have $f(x) = y$ for some $x\in f^{-1}(T)$.  It
follows that $T \subseteq f(f^{-1}(T))$.  This concludes the proof.  
\end{enumerate}
\end{enumerate}

\end{document}
