

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 2000 Quiz 1
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{25} \textbf{Relations}
\begin{problemparts}

For each relation listed in parts (a) through (e) circle {\em all} terms
listed that apply to it.

\problempart {\bf (5 points)}  $A = \{a, b\}, R = \{(a, a), (a, b)\}$.

\solution{ 
\bigskip {\bf Solution: }
This relation is antisymmetric and transitive.
}

\problempart {\bf (5 points)} $aRb$ whenever $a$ and $b$ are students
and either $a = b$ or $a$ has a GPA greater than or equal to that of
$b$.  (You may assume that all students have different GPAs).

\solution{
\bigskip {\bf Solution: }
This relation is reflexive, transitive and antisymmetric, so it is
a partial order.  Furthermore, since any two different students have
different GPAs, they can be compared with $R$.  Therefore, this 
relation is also a total order.
}

\problempart {\bf (5 points)} $aRb$ whenever $a$ and $b$ are real numbers
and $a = b^x$ for some rational number $x$.

\solution{
\bigskip {\bf Solution: }
This relation is not symmetric, since $1 = 4^0$ but $1^x$ is 1 for any 
rational number $x$.  However, it is not antisymmetric since $2 = 4^{.5}$
and $4 = 2^2$.  Thus is is none of these.
}

\problempart {\bf (5 points)}  $aRb$ whenever $a$ and $b$ are rational
numbers and $ab$ is an integer.

\solution{
\bigskip {\bf Solution: }
This relation is not reflexive (for instance, $\neg(.5R.5)$).
Therefore, it is none of these.
}


\problempart {\bf (5 points)} $aRb$ whenever $a$ and $b$ are integers such
that there is a nonnegative integer $k$ such that $3^k | a$ and $3^k | b$
and $3^{k+1}\not|a$ and $3^{k+1}\not|b$.  

\solution{\bigskip
{\bf Solution: }
This relation is essentially just saying that $3$ divides $a$ and $b$
the same number of times.  This is an equivalence relation, since
the same number of times is reflexive, symmetric and transitive.

} \nextproblem


\end{problemparts}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 1998 Midterm
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\examonly{\newpage}

\problem {\bf (5 points)}  Suppose that we have functions
$f : A \mapsto B$, $g : B \mapsto C$, and $h : C \mapsto A$ such that
for all $a \in A$, $h(g(f(a))) = a$, and for all $b \in B$,
$f(h(g(b))) = b$.  Proofs are not required for any part of this
problem.

\begin{problemparts}
\problempart {\bf (1 points)}  Which of the functions $f$, $g$, and $h$ must be injective?

\examonly{\vspace{1in}}

\solution{
The functions $f$ and $g$ must injective.  }

\problempart {\bf (1 points)}  Which of the functions $f$, $g$, and $h$ must be surjective?

\examonly{\vspace{1in}}

\solution{
The functions $f$ and $h$ must be surjective.  }

\problempart {\bf (2 points)}  Circle the relations that must hold.

\[
\begin{array}{ccccc}
|B| > |C| &\quad& \us{|C| \geq |A|} &\quad& \us{|B| \leq |C|} \\
\\
\us{|A| = |B|}  &\quad& |A| \neq |C|        &\quad& |A| + |B| \geq |C|
\\
\end{array}
\]

\problempart {\bf (1 points)}  If $g$ is surjective, then which of the
functions $f$, $g$, and $h$ must be bijective?

\solution{
If $g$ is surjective, then all of the functions must be bijective.
}

\end{problemparts}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%Fall 2000 Final exam
% Added by George
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%% PROBLEM 3
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\problem\pts{9} \textbf {Lines That Cross and Lines That Don't}

Suppose we have a set $L$ of 26 different lines with equations in the
form $y = mx + b$ for real $m$ and $b$.  Prove that there is either

\begin{itemize}
\item[1.]  A set $S$ of 6 lines that never intersect one another when $x>0$, or
\item[2.]  A set $T$ of 6 lines such that any two of them intersect
one another at some point where $x>0$.
\end{itemize}

Hint:  Use Dilworth's Theorem.

\solution{\bigskip {\bf Solution:}

Let $\preceq$ be the relation on the set of 26 different lines such
that $mx + b \preceq m'x + b'$ if and only if at all points where $x >
0$, the height $mx + b$ is less than or equal to the height $m'x +
b'$.  (This relation is equivalent to the relation that $mx + b
\preceq m'x + b'$ if and only if $m \leq m'$ and $b \leq b'$, but we
won't prove this here.)

This is a partial order.  It is reflexive, since $mx + b \leq mx + b$
for every value of $x$.  If $mx + b \leq m'x + b'$ and $m'x + b' \leq
mx + b$ for all $x > 0$ then $mx + b = m'x + b$ so the two lines must
be the same (thus, the relation is antisymmetric).  Finally, the
relation is transitive since $\leq$ is transitive.

By Dilworth's theorem, there is either a chain in this poset of size
$>5$ or there is an antichain of size $\geq (26/5)$.

If there is a chain of size $6$ or greater, then the first six
elements of it form the set $S$.  If two lines are comparable they don't 
intersect when $x>0$.  If they did, at say $x = a$, then one of them is
higher at $x = 2a$ but the other is higher at $x = a/2$.  Thus, the 
chain forms the set $S$.

If there is an antichain of size $6$ or greater, then the first six
elements of it form the set $T$.  If two lines are not comparable,
there must be some point $x = a > 0$ such that $ma + b < m'a + b$ but
there must then be some point $x = a' > 0$ such that $ma' + b > m'a' +
b'$.  Thus, the function $(m'-m)x + (b'-b)$ has a value $(a)$ that
makes it greater than zero, and a value $(a')$ that makes it less than
zero.  Since this is a line, it must pass through zero at some point
$a''$ between $a$ and $a'$.  Since $a$ and $a'$ are both greater than
zero, $a''$ must also be greater than zero, so the two lines
intersect.
}









