\documentstyle[12pt,twoside,amstex,macpsfig]{article}
\input{macros-course}
\begin{document}

\handout{notes6}{\mbox{}}{September 28, 1995}

\begin{center}
\Large \bf 
Lecture Notes 6 \\

Functions, Pigeonhole Principle.

\end{center}

\section{Functions}

\begin{defin}
A {\em function} $f:A\rightarrow B$ is a way of relating {\em every} item
in a set, $A$, with {\em precisely one} item in a set, $B$.
\end{defin}

The set $A$ is called the {\em domain} of $f$, and the set $B$ is called
the {\em range} of $f$.

\begin{figure}[h]
\center{\mbox{\psfig{figure=H18-fig1.ps}}}
\end{figure}

To be a function, every item in $A$ must be related to just one item
in $B$.
Note that every item in $B$ need not be hit.
The image of $f$ is the set of points that are hit.
Formally, the image of $f$, denoted by $f(A)$, is
$\{ b\in B| \exists a\in A \mbox{ s.t. } f(a)=b\}$.

You should be familiar with many functions such as $f:\reals
\rightarrow \reals$ where $f(x)=|x|$ and $g:\reals \rightarrow
\integers$ where $g(x)=\lfloor x \rfloor$.  

An example of a non-function is $f:\reals \rightarrow \reals$ where
$f(x)=\sqrt{x}$.  This is not a function because $\sqrt{-1}$ is not a
real.  Even if we extend the range to the complex numbers, we still
have the problem that $\sqrt{1}=\pm 1$.  If we only take the positive 
root, then square root is no longer distributive over negative
numbers.


Functions can also be defined recursively.
The Fibonacci function, $f:\naturals \rightarrow \naturals$ can be defined as

\[
f(n) = \left\{ \begin{array}{ll}
		0 & \mbox{if $n=0$,} \\
		1 & \mbox{if $n=1$,} \\
		f(n-1)+f(n-2) & \mbox{if $n>1$.} \\
	       \end{array}
   	\right.	 
\]

The factorial function can be similarly defined as
\[
f(n) = \left\{ \begin{array}{ll}
		1 & \mbox{if $n=0$,} \\
		nf(n-1) & \mbox{if $n>0$.} \\
	       \end{array}
   	\right.	 
\]

Three important classifications of functions are surjections, injections,
and bijections.

\begin{defin}
A function $f:A \rightarrow B$ is a {\em surjection} (aka as onto)
if $\forall b \in B, \exists a \in A$ such that $f(a)=b$.
\end{defin}

In a surjection, every element in $B$ is hit by at least one element.

\begin{figure}[h]
\center{\mbox{\psfig{figure=H18-fig2.ps}}}
\end{figure}

\begin{defin}
A function $f:A \rightarrow B$ is an {\em injection} (aka as 1-1)
if $f(a_1)=f(a_2)$, then $a_1=a_2$.
\end{defin}

In an injection, no two elements in $A$ point to the same element.

\begin{figure}[h]
\center{\mbox{\psfig{figure=H18-fig3.ps}}}
\end{figure}

\begin{defin}
A function $f:A \rightarrow B$ is a {\em bijection} if it is both
an injection and a surjection.
\end{defin}

In a bijection, there is a one-to-one correspondence between elements in $A$
and elements in $B$.

For example, 
$f:\naturals \rightarrow \naturals$ where $f(x)=2x$ is one-to-one, but
not onto, and thus not a bijection.  However, if we modify the range,
so $f:\naturals \rightarrow 2\naturals(\mbox{``even numbers''})$,
then we have a bijection.

If there is a bijection between two sets, then the two sets have
the same size.

\begin{theorem}
If $A$ and $B$ are finite sets and $f:A \to B$ is a bijection, then
$|A| = |B|$.
\end{theorem}

The idea is intuitive from the picture of a bijection.  However, picture
proofs can often be wrong.  So, let's do a more formal proof.

\begin{proof}
Let $A= \{ a_1, a_2, a_3, \ldots, a_n \}$ where $n=|A|$.
where the $a_i$ are distinct.
We actually haven't proved you can write the set this way, but
we won't go into that in this class.

{\bf Claim:}  $B=\{f(a_1),f(a_2),f(a_3),\ldots,f(a_n)\}$

We need to show these two sets are equal.  We do this by showing they
are subsets of each other.  Let $b\in B$.  Since $f$ is a bijection,
there exists $a_i \in A$ such that $f(a_i)=b$.  
Thus, $B\subseteq \{f(a_1),f(a_2),f(a_3),\ldots,f(a_n)\}$.
By definition of a
function, each $a_i$ maps into an element of B.  Therefore,
$B\supseteq \{f(a_1),f(a_2),f(a_3),\ldots,f(a_n)\}$.
We have shown
they are subsets of each other, thus
$B=\{f(a_1),f(a_2),f(a_3),\ldots,f(a_n)\}$.

Also, note the $f(a_i)$ are distinct, since $f$ is a bijection (hence,
an injection).  Therefore, $|B|=n$.
\end{proof}

The converse of the theorem is also true.  If two finite sets have
the same size, then there is a bijection between the two.
Let $A=\{ a_1, a_2, a_3, \ldots, a_n \}$ and $B=\{b_1,b_2,b_3,\dots,b_n\}$,
then let $f(a_i)=b_i$ and we have a bijection.
Thus, bijections show that two sets have the same size (cardinality).

Formally, cardinality is defined by a bijection.

\begin{defin}
A set $A$ has cardinality $n$, $|A|=n$, if there exists a bijection
$f:A \to \{1,2,3,\ldots,n\}$.
\end{defin}

A seemingly immediate result is that any set $A$  with more items than
another set $B$ cannot have a bijection between the two.
This is true for finite sets.  However, it is not true for {\em infinite}
sets.

Consider $f: \naturals \to \{0,2,4,6,8,\ldots\}$ where $f(n)=2n$.
This is a bijection, yet the natural numbers contain more elements
than the evens.  Infinite sets have special properities.
In the next lecture, we will discuss them further.

\section{Pigeonhole principle}
The principle can be simply stated as: ``If $n+1$ pigeons are put in 
$n$ holes, then at least one hole has two or more pigeons.''
One easy way to see this is that if each hole only had one or zero pigeons,
then there are at most $n$ pigeons.  This simple fact allows us
to prove many things.  An immediate result is that if three people are 
in a room, then at least two have the same sex.

Here's a slightly more complicated example.

\begin{theorem}
  $\forall m<n$, every set with $n$ numbers must
contain two numbers whose difference is a multiple of $m$.
(e.g., every set with 1000 numbers must contain two whose difference
is a multiple of 573.)
\end{theorem}

\begin{proof}
The proof is easy once you see how to apply the pigeonhole principle.

Let the $n$ numbers be the pigeons.  The holes are congruencies mod $m$
(i.e.  0 mod $m$, 1 mod $m$, 2 mod $m$, ... , $m-1$ mod $m$).
Thus, we can map pigeons into holes.  Every pigeon will
get mapped to some hole.  Since there are more pigeons than holes,
two pigeons get mapped to the same hole.

If two pigeons (say $x$ and $y$) are in the same hole, they are
congruent mod $m$.  Thus, $x\equiv y (\mod m) \implies m|x-y$.
\end{proof}

Another example is the following.  
\begin{theorem}
Let ``friendship'' be a reflexive
and symmetric relation.  Then, any set of $n$ people has two people with
the same number of friends.
\end{theorem}

\begin{proof}
We again use the pigeonhole principle.
Let the pigeons be the $n$ people.  Now, we want to choose the holes
so that there are $n-1$ holes, and every person gets mapped to a hole.
The number of possible friends is 1 to $n$, which is $n$ possibilites.
Apparently, we can't directly apply the pigeonhole principle.
However, if we do a little extra work, we can.
If a person has $n$ friends, then every person has at least two friends --
himself and the very friendly person.  Thus, the set of possible
friendships is either $[1,n-1]$ or $[2,n]$.  Each of these sets has
$n-1$ elements, so we can apply the pigeonhole in either situation.
Therefore, two people must have the same number of friends.
\end{proof}

The
{\em Strong Pigeonhole Principle} is as follows.
If $n(r-1)+1$ pigeons are put in $n$ holes, then there is at least
one hole with
$r$ pigeons.

We can prove this by contradiction.  Assume all holes have  $r-1$ or fewer
pigeons,  Then, the total number of pigeons is at most $n(r-1)$, which
is a contradiction.  Note the simple pigeonhole priciple is a special case
when $r=2$.

We can use the strong pigeonhole principle to prove some interesting facts.
The expression ``you're one in a million'' is sometimes used to
say a person is very special.  Let's take its meaning literally.
There are exactly one million different personalities any person can have.
Beyond that, the differences are insignificant.
In the country of China, there are well over a billion people.
Thus, the strong pigeonhole principle implies there is one personality
where at least 1000 people have that same personality.
I guess those people aren't so special after all.

\end{document}
