\problemdata                                                             
        {T/F about functions/countability of sets} % latex-friendly label for the prob.
        {functions, countability} % The topic(s) of the problem content.  
        {?} % Source (if known)                                          
        {S01 Quiz 2, 6} % Usage (list ones you are aware of). 
        {Tina Wang, S02} % Last revision info (author, date).   
                                                                         
                                                                         
\begin{problem}           
Circle T or F for all questions, even if you have to guess.

\begin{tabbing}
123\=456\=789\=012\=\kill

\\
    \> T \> F \>  There is a surjection $f:\naturals \rightarrow \reals$.\\
\solution{ 
   \> \> \>  {\bf FALSE}  $\reals$ are uncountable, $\naturals$ are countable so no surjection can exist. \\ }
\\
    \> T \> F \>  Any binary relation on the natural numbers is countable.
\\
\solution{
   \> \> \>  {\bf TRUE}, since $\naturals$ is countable, we know
$\naturals\times\naturals$ is countable and a binary
relation \\
   \> \> \> on $\naturals$ is by definition a subset of $\naturals\times
\naturals$. \\}
\\
%    \> T \> F \>  If a set $A$ contains an uncountable subset $B$, then $A$ is
% uncountable.\\
%\solution{
%   \> \> \>  {\bf TRUE}\\}
%%\\
    \> T \> F \>  If an uncountable set $A$ contains a countable subset $B$,
               then $A-B$ is uncountable.\\
\solution{
   \> \> \>  {\bf TRUE}; if $A-B$ were countable, then $A\subseteq B\cup (A-B)$ would
be a union\\
   \> \> \>  of two countable sets and therefore countable.\\}
\\
    \> T \> F \>  If $f:A\rightarrow B$ is a surjection,  
          $f^{-1}:B\rightarrow A$ is an injection.\\
\solution{
   \> \> \>  {\bf FALSE}, $f^{-1}$ may not even be a function (if $f$ maps
two elements of $A$ to\\
   \> \> \>  the same element of $B$) \\}
\\
    \> T \> F \>  If an uncountable set $A$ contains an uncountable subset $B$,
               then $A-B$ is countable.\\
\solution{
   \> \> \>  {\bf FALSE}, consider $B=\reals^{+}$, $A=\reals$. \\}
\\
    \> T \> F \>  The set of functions from $\{0,1\}$ to $\naturals$ is uncountable.\\
\solution{
   \> \> \>  {\bf FALSE} since it is the set of all fourtuples $(0, a, 1, b)$ where $a,b \in \naturals$\\}
\\
    \> T \> F \>  The set of functions from $\naturals$ to $\{0,1\}$ is uncountable.\\
\solution{
   \> \> \>  {\bf TRUE} since it is equinumerous to ${\cal P}(\naturals)$\\}
\\
    \> T \> F \>  The expansion of $(x - 1)^{120}$ has three identical nonzero
coefficients.\\
\solution{
   \> \> \>  {\bf FALSE}, looking at Pascal's triangle binomial coefficients
 \\
   \> \> \> increase to a maximum and then decrease. The coeffs. of $(x-1)^{120}$\\
   \> \> \> are binomial coeffs. and their negatives, so at most two can be equal.\\
}
%    \> T \> F \>  If $p > 5$ is prime, then $p \mid {p \choose {p-4}}$.\\
%\solution{
%   \> \> \>  {\bf TRUE} $p \choose {p-4}$ = $\frac{p!}{(p-4)!4!} = \frac{p \cdot (p-1) \cdot (p-2) \cdot (p-3)}{4 \cdot 3 \cdot 2}$ \\
%\text{Since p is not 0 mod 2, or 0 mod 3, or 0 mod 4, (p-1) and (p-3)
%must be both 0 mod 2.  
%Likewise, either (p-1) or (p-2) must be 0 mod 3 and 
%either (p-1) or (p-3) is 0 mod 4.  If (p-1) is 0 mod 3 and 0 mod 4, then
%it must be also 0 mod 12, and since (p-3) is 0 mod 2, we know the equation
%must be 0 mod p.  In any other case, we have one number each that is
%0 mod 2,3, and 4, so again, the equation is 0 mod p.}\\}
\end{tabbing}

{\bf Comments:}

There's not too much to say about this problem since we didn't ask for
justification. Numbers 6 and 7, about countability of sets of functions,
seemed to trip up many people.

\end{problem}
                                 


