\documentclass[11pt,twoside]{article}
\usepackage{amsmath}
\input{macros-course}

\newcommand{\range}[1]{\text{range}(#1)}
\newcommand{\domain}[1]{\text{domain}(#1)}
\newcommand{\intersect}{\cap}
\newcommand{\union}{\cup}
\newcommand{\cross}{\times}

\newcommand{\solution}[1]{}
%\newcommand{\solution}[1]{\bigskip {\bf Solution:}\\ #1\bigskip}

\begin{document}

\tutprobn{4}{Thursday, 9/23/99}{September 23, 1999}

\begin{problems}
\problem

Let $f$ be a function from a nonempty set $A$ to itself, that is, $f:A \to
A$.  Although $f$ may not be a bijection, we can try to identify ``parts''
of $f$ which are bijections.  For example, if $A = \set{1, 2, 3, 4, 5, 6}$
and $f(1)=2, f(2)=3, f(3)=2, f(4)=6, f(6)=5, f(5)=4$, then the part of $f$
which is defined on the set $\set{2,3}$ is a bijection.  So is the part of
$f$ defined on $\set{4,5,6}$, as well as the part of $f$ defined on their
union $\set{2,3,4,5,6}$.

So let's say that a subset $B \subseteq A$ is \emph{OK for $f$} providing
that, restricting the domain of $f$ to $B$ yields a bijection from $B$ to
$B$.  For the $f$ in the example above, the OK sets are the empty set and
the three sets mentioned.\footnote{The empty set is OK for any function because
by convention, there is a unique \emph{empty function} with empty domain
and codomain, and this function automatically satisfies the conditions for
being a bijection.}

For any $f$, we'd like to find as large an OK set as possible.  We'll call
such a set a \emph{core} of $f$.  To be precise, a core of $f$ is an OK set
which contains all the sets which are OK for $f$.  There can be at most one
core for $f$: if there were two, then by definition each would have contain
the other, so they would be equal.  The core of $f$ in the example above is
$\set{2,3,4,5,6}$.

\bparts

\ppart Prove by strong induction on $\card{A}$, the size of $A$, that if
$A$ is finite and nonempty, then $f$ has a nonempty core.

\solution{\begin{proof}
The induction hypothesis $P(n)$ will be $\forall f:A \to A
(\card{A} = n \implies f \mbox{ has a core})$.  The base case is $n=1$, in
which case $A$ is obviously the core of $f$.
Induction case: Suppose $\card{A}=n+1$, we must show that $f$ has a
nonempty core.  There are two cases:

case 1: $\card{\range{f}} = n+1$.  This implies that $\range{f} = A$
(because $\range{f} \subseteq A$ and $\range{f}$ is the same size as $A$),
so $f$ must be a bijection and $A$ is the core.

case 2: $\card{\range{f}} = k < n+1$.  In that case, let $g: \range{f} \to
\range{f}$ be the restriction of $f$ to its range.  That is, $g(r)::=f(r)$
for all $r \in \range{f}$.  Now we observe that any set that is OK for $f$
must be a subset of $\range{f}$ and therefore must be OK for $g$.
Conversely, any set that is OK for $g$ must also be OK for $f$ because any
restriction of $g$ is also a restriction of $f$.  In other words, $f$ and
$g$ have exactly the same OK sets.  This immediately implies that they
have the same core, if any.  But by the strong induction hypothesis
$P(k)$, the function $g$ has a nonempty core, and therefore so does $f$.
\end{proof}}

\ppart Let $s: \naturals \to \naturals$ be the successor function, namely,
$s(n) = n+1$.  Prove that the core of $s$ is empty.  \hint Assume there is
a nonempty OK set for $s$, and use the Well-ordering Principle to obtain a
contradiction.

\solution{Suppose there is a nonempty set, $B$, which is OK
for $s$.  Since $B \subseteq \domain{f} = \naturals$, by the Well-ordering
Principle, there is a least element $k \in B$.  So every element of $s(B)$
is $\geq s(k) > k$.  In particular, $k \not\in s(B)$, contradicting
the fact that $s$ is supposed to define a bijection from $B$ to $B$.}

\ppart Let $A$ consist of the natural numbers $\naturals$ and two copies of
the negative integers---a ``red'' copy and a ``blue''
copy.\footnote{Formally, $A = \naturals \union (\set{\mbox{red}} \cross M)
\union (\set{\mbox{blue}} \cross M)$ where $M = \set{ n \in \integers \mid
n < 0}$ and the ``red'' and ``blue'' tags may be anything at all, as long
as they are different from each other.}  Define $f$ to act like the
successor function but preserving colors, as illustrated in the attached
figure.  %/pub/www/classes/6.042/fall99/figures/no-core.jpg

That is,
\begin{eqnarray*}
f((\mbox{red},n)) & = & (\mbox{red},n+1),\\
f((\mbox{blue},n))& = & (\mbox{blue},n+1),\\
f((\mbox{red},-1)) & = & 0 = f((\mbox{blue},-1)),\\
f(m) & = & m +1,
\end{eqnarray*}
for $n < -1$ and $m \geq 0$.

What sets are OK for $f$?  Conclude that $f$ does not have a core.

\solution{The only OK sets are the empty set, $\naturals \union
\set{\mbox{red integers}}$, and $\naturals \union \set{\mbox{blue
integers}}$.  Since none of these sets contains all the others, there is
no core.}

\eparts

\end{problems}

\end{document}
