\documentclass[10pt]{amsart}


\newcommand{\from}{\colon}
\newcommand{\naturals}{{\mathbb N}}

\begin{document}

\centerline{\bf Sample \LaTeX Code}

\bigskip

\begin{enumerate}

\item
Let $S=\{1,2,3\}$ and $f\from S\to {\rm Power}(S)$ be given by
$$
f(1) = \{1,2\},
\ f(2) = \{1,3\},
\ f(3) = \{2,3\}.
$$
What is $T = \{ s \ | \ s\notin f(s) \}$ ?

\bigskip


\item
Let $S=\{1,2,3\}$ and $f\from S\to {\rm Power}(S)$ satisfy
$f(1) = \{1,2\}$.  Let  $T = \{ s \ | \ s\notin f(s) \}$.
\begin{enumerate}
\item
Without using Cantor's theorem,
give a direct argument to show
that $T\ne \{1,2\}$ (knowing only that $f(1) = \{1,2\}$).
\item
Without any additional information, can you determine whether or 
not $2\in T$ ?
To answer this question, you should either (1) prove that $2\in T$,
(2) prove that $2\notin T$, or (3) give an example of an $f$ such that
$2\in T$ and another example where $2\notin T$.
\end{enumerate}
% What else can you assert about $T$ (without knowning the values of
% $f(2),f(3)$) ?

\bigskip

\item
Let $S=\{a,b,c\}$ and let $f\from S\to {\rm Power}(S)$ any function
such that
$$
a\notin f(a), \quad b\notin f(b), \quad c\notin f(c).
$$
\begin{enumerate}
\item 
Explain why $f(a)$ cannot be all of $S$ (argue directly, without
appealing to Cantor's theorem).
\item
Similarly, explain why none of $f(b),f(c)$ equal $S$.
\item
What is the set
$$
T = \{ s\in S \ | \ s\notin f(s) \} ?
$$
\end{enumerate}

\bigskip

\item
Let $S=\{a,b,c\}$ and let $f\from S\to {\rm Power}(S)$ any function
such that
$$
a\notin f(a), \quad b\in f(b), \quad c\notin f(c).
$$
\begin{enumerate}
\item 
Explain why $f(b)$ cannot equal $\{a,c\}$ (argue directly, without
appealing to Cantor's theorem).
\item
Similarly, explain why none of $f(a),f(c)$ can equal $\{a,c\}$.
\item
What is the set
$$
T = \{ s\in S \ | \ s\notin f(s) \} ?
$$
\end{enumerate}

\bigskip 

\item
Let $S=\{1,2,3\}$ and $f\from S\to {\rm Power}(S)$ be given some
map.  Can it be that
$$
T = \{ s \ | \ s\in f(s) \}
$$
lies in the image of $f$?
[Either give an example of such an $f$, or explain why it doesn't 
exist.  You should give an explanation ``from scratch,'' without
relying on Cantor's theorem or any other result from class or these
notes.]

% ----------------------------------------------------------- 
% Assigned to here for Oct 12
% -----------------------------------------------------------

\bigskip

\item
Let $f\from A\to B$ and $g\from B\to C$ be functions on sets
$A,B,C$.
Consider the composition $gf\from A\to C$ of $f$ and $g$
(you may have seen $gf$ written as $g\circ f$ for clarity).
\begin{enumerate}
\item Say that $gf$ is injective.  Is $f$ necessarily injective?  Explain
(give a proof that $f$ is injective or give examples of $f,g$
where $f$ is not injective).
\item Say that $gf$ is injective.  Is $g$ necessarily injective?  
\item Say that $gf$ is injective and, in addition, $|B|\le |A|$.
Is $g$ necessarily injective?
\item Say that $gf$ is surjective.  Is $f$ necessarily surjective?  
\item Say that $gf$ is surjective.  Is $g$ necessarily surjective?  
\end{enumerate}

\bigskip


\item
Let $f\from \naturals\to{\rm Power}(\naturals)$ be given by
$$
f(n) = \{ m\in\naturals \ | \ \mbox{$m + n/2$ is a perfect square} \}
=\{ m\in\naturals \ | \ \mbox{$m + n/2=k^2$ for some $k\in\naturals$} \}
$$
What is $T = \{ s \ | \ s\notin f(s) \}$ ?

\bigskip

\item
A department has 3 profs, $P=\{A,B,C\}$.  It is given that
\begin{description}
\item[Prof.~A] thinks that no one in the department works too much, 
and
\item[Prof.~C] thinks that everyone in the department works too much.
\end{description}
For $x\in P$, let
$$
f(x) = \{ y\in P \ | \ \mbox{$x$ thinks that $y$ works too much.} \}
$$
\begin{enumerate}
\item
What does the above information tell you about $f$ ?
\item
What can you say about
$$
T = \{ s\in P \ | \ \mbox{$s$ thinks that $s$ does not work too much}  \} ,
$$
and how do you know that $T\ne f(A)$ and $T\ne f(C)$?
% $ is not the subset of profs whom either
% Prof.~A or Prof.~C think is working too much?
\item
Now say that, in addition, you know that
\begin{description}
\item[Prof.~B] thinks that Profs.~A and C work too much, but not themself.
\end{description}
What is
$$
T = \{ s\in P \ | \ \mbox{$s$ thinks that $s$ does not work too much}  \} ?
$$
\end{enumerate}

\bigskip

\item
A department has 3 profs, $P=\{A,B,C\}$.  It is given that
\begin{description}
\item[Prof.~A] thinks that Prof.~B works too much, 
\item[Prof.~B] thinks that Prof.~C works too much, 
and
\item[Prof.~C] thinks that Prof.~A does not work too much.
\end{description}
Find a bijection $g\from P\to P$ such that
$$
T = \{ s\in P \ | \ \mbox{$s$ thinks that $g(s)$ does not work too much}  \} 
$$
can be determined.  
Then state this as an instance of generalized Cantor's theorem.

\end{enumerate}

\end{document}