\input amstex
\documentstyle{amsppt}
\loadeufm\parskip=6 pt
\centerline{Quiz 5 Math 302, Spring 1996}

Work two of the three problems below.

\roster
\item Let $A:=\{1,2,3,4\}$ and $B:=\{1,2,3\}$. Let $\frak A$ denote the set of all functions from $A$ {onto} $A$, and let $\frak A\frak B$ denote the set of all functions from $A$ {onto} $B$.  

\itemitem {}How many functions are there in $\frak A$?
\itemitem {}How many functions are there in $\frak A\frak B$?
\itemitem {}Let $f\in \frak A$, with $f(1)=2, f(2)=3, f(3)=4$, and $f(4)=1$. Find $f\circ f$, and find $f^{-1}$, the inverse function to $f$. 

\item How many numbers $r$ can be selected from the interval $\{1,2,3,\dots 20\}$ so that no two of them differ by exactly 7? [Prove by the pigeonhole principle that it is impossible to select $r+1$, and give an example showing how $r$ numbers can be selected.]

\item Let $C:=\{1,2,\dots n\}$, and let $\frak C$ denote the set of all one-to-one functions from $C$ to $C$. Let $e$ denote the identity function on $C$, so that $e(k)=k$ for all $k$. The paragraphs below make an assertion, and give a (flawed) proof. What is wrong with the logic? Is the assertion true despite the flaw in the proof? How should the proof and/or the assertion be modified to repair the error? \endroster

\proclaim{Proposition 1.0} Every function $f\in\frak C$ has the property that there exists $k$, $1\le k\le n$, so that if $g$ is the k-fold composition $f\circ f\circ \dots f$ of $f$ with itself, then $g=e$.\endproclaim

Proof. (Remember, there is an error!) Let $x\in\{1,2,\dots n\}$. Consider the sequence $x_0,x_1,x_2,x_3\dots$ defined by $x_0=x$, and $x_j:=f(x_{j-1})$ for $j\ge 1$. The numbers $x_0,x_1,\dots x_n$ cannot all be distinct, by the pigeonhole principle. Therefore, there exist integers $a$ and $b$, with $0\le a\le b\le n$, so that $x_a=x_b$. But then $f(f(\dots x_a))=x_b$, where $f$ has been applied $b-a$ times to $x_a$ to give $x_b=x_a$. But that means that the $b-a$-fold composition of $f$ is the identity function, as claimed. QED.

\enddocument