\documentstyle[12pt,twoside,macpsfig,amssymb]{article}
\input{macros-course}
%	\addtolength{\topmargin}{-.35in}
%	\setlength{\textheight}{9in}

\begin{document}

\psol{4}{October 05, 1995}

\bigskip

\begin{problems}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
\bparts
\ppart By ``reachable
by at most two
intermediate connections'' we meant using at most two flights. Some people interpreted this to mean using at most two intermediate airports or using at most three flights. We are accepting both interpretations.

Using at most two flights:  
\[ \left( \begin{array}{ccccc}
1 & 1 & 1 & 0 & 0\\
1 & 1 & 1 & 0 & 1\\
1 & 1 & 1 & 1 & 1\\
1 & 1 & 1 & 1 & 1\\
1 & 1 & 1 & 1 & 1
	\end{array} \right) \]

Using at most three flights:
\[ \left( \begin{array}{ccccc}
1 & 1 & 1 & 0 & 1\\
1 & 1 & 1 & 1 & 1\\
1 & 1 & 1 & 1 & 1\\
1 & 1 & 1 & 1 & 1\\
1 & 1 & 1 & 1 & 1
	\end{array} \right) \]

\ppart 
\vspace*{1in}

The above is a counterexample. $R^2 = R$ but it is not reflexive.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
\bparts
\ppart 
\begin{itemize}
\item sin$(x)$ - neither injective nor surjective.
\item $x^{1994}$ - neither injective nor surjective.
\item $x^{1995}$ - bijective. Inverse: $x^{\frac{1}{1995}}.$
\item $x/(x^2+5)$ - neither injective nor surjective.
\end{itemize}
\ppart $f\circ g : 2x+1; \ g\circ h : 2x^2; f\circ g\circ h : 2x^2 + 1.$ 
\ppart Let the two surjective functions be $f: B \rightarrow C$ and $g: A \rightarrow B$. Then $f\circ g$ is also surjective. To prove that $f\circ g$ is surjective we need to show that every element in the range of $f\circ g$ has a preimage in the domain of $f\circ g$. Consider any element $a$ in the range of $f\circ g$. It is also in the range of $f$. Since $f$ is surjective there exists an element $b$ in the domain of $f$ such that $f(b) = a$. Since $g$ is surjective there exists an element $c$ in the domain of $g$ such that $g(c) = a$. Hence, for any element $a$ in the range of $g$ there is an element $c$ in the domain of $g$ such that $f(g(c)) = a$. Thus $f\circ g$ is surjective.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem
We claim that there is a number in the set $\{2^1 - 1, 2^2 -
1, \ldots, 2^{m+1}-1\}$ divisible by $m$. Since there are $m+1$ numbers in the set and only $m$ possible different remainders on being divided by $m$, by the pigeonhole principle, some two numbers in this set must leave the same remainder on being divided by $m$. So there exist $i$ and $j, 1 \leq i< j \leq m$ such that $2^i-1$ and $2^j -1$ leave the same remainder on being divided by $m$, i.e. $m| (2^j - 1) - (2^i - 1)$ or $ m | 2^i(2^{j-i} - 1)$. But $m$ is odd and hence $m$ must divide $2^{j-i} - 1$. Thus we have found a number in the set $\{2^1 - 1, 2^2 -
1, \ldots, 2^{m+1}-1\}$ which is divisible by $m$.
 
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
Consider the set  
\[\{i | \mbox{$\exists$ player who has played exactly $i$ games when the light went out.} \}\] Note that the numbers in the set range between $1$ and $n-1$ or between $0$ and $n-2$. This is because if there is a player who has played $0$ games then there can be no player who has played $n-1$ games. Remember that each player plays any other player at most once. Since the set has cardinality at most $n-1$ and there are $n$ players, by the pigeon-hole principle, there must be two players who have played exactly the same number of games when the lights went out.

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem

\bparts 
\ppart Let $S$ be the set and $A$ an infinite subset of $S$. (If $A$ is finite then by definition it is countable and there is nothing to prove.) Since $S$ is countable there exists a listing $S = \{s_1, s_2, \ldots \}$. We can construct a listing for $A$ by just going through the list and picking up the elements in $A$. This is a valid listing because this way we are guaranteed to get every element in $A$. Hence $A$ is countable.

\ppart We have a listing of each of the sets $S_i$. Let $s_{ik}$ be the $kth$ element in the listing of $S_i$. We combine them, using the idea of dove-tailed interleaving shown in class, to get the listing for their union. The resulting list is $\{ s_{11}, s_{12}, s_{21}, s_{13}, s_{22}, s_{31}, \ldots \}$. It is easy to see $s_{ik}$ will occur before position $(i+k)^2$ in our listing. Of course, we also drop repeat elements from our listing but that does not affect anything. Since we have been able to give a valid listing, $ {\displaystyle \bigcup}^\infty_{i=1} {\cal S}_i $
is countable.


\ppart No $\reals - \rationals$ cannot be countable because if it were then, since the countable union of countable sets is countable by part (b), $(\reals - \rationals) \cup \rationals = \reals$ would be countable, a contradiction.
\eparts

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem 
\bparts
\ppart Suppose ${\cal P}(\naturals)$ is countable. Then there exists a bijection $f: \naturals \rightarrow {\cal P}(\naturals)$. Represent this by a matrix $M$ where $M_{ij} = 1$ if $j \in f(i)$, and $M_{ij} = 0$ otherwise. Now create a new set $S$ by considering the diagonal elements $M_{ii}$ of the matrix. $S = \{ i | M_{ii} = 0 \}$. This is a valid subset of $\naturals$ and $f^{-1}(S)$ must exist. But observe that $f^{-1}(S) \in S \Rightarrow f^{-1}(S) \not \in S$ and $f^{-1}(S) \not\in S \Rightarrow f^{-1}(S) \in S$. Thus, either way, we have a contradiction. Hence ${\cal P}(\naturals)$ cannot be countable.

\ppart Consider the function $f: x \rightarrow e^x$. This is a bijection from $\reals$ to $\reals^{+}$. The inverse is $\ln x$.

\eparts
\end{problems}

\end{document}





