\documentclass[11pt]{article}

\usepackage{homework,amssymb}


\begin{document}

\begin{center}

{\sc Prerequisites for 80-310/610}

\bigskip\bigskip

\end{center}

{\bf Mathematical Prerequisites}

\medskip

You should have some familiarity reading and writing rigorous
proofs. A course in abstract mathematics or {\em Arguments and
Inquiry} (80-211) should be sufficient preparation.

\bigskip

{\bf Logical Prerequisites}

\medskip

You should be comfortable with propositional and predicate logic and
their semantics, and have worked with at least one deductive system.

\bigskip

{\bf Self test}

\medskip

Answering the following questions should be routine.

\medskip

\begin{list1}

\item Is the propositional formula $(A \limplies B) \lor (B \limplies
A)$ valid? Justify your answer.

\item Put the formula $\ex x A(x) \land \fa y (B(y) \limplies \ex z
  C(y,z))$ in prenex form, i.e.\ write down an equivalent formula in
  which all the quantifiers are in front.

\item Is the formula $\fa x \fa y (x < y \limplies \ex z (x < z \land z < y))$ 
true in the structure $M$,
\begin{list2}
\item if $M$ is the real numbers?
\item if $M$ is the natural numbers?
\item if $M$ is the set of all subsets of the natural numbers, and $<$
is interpreted as proper set inclusion ($\subsetneq$)?
\end{list2}

\item Prove, by induction, that every natural number other than 1 can be 
factored into primes.

\item Define the sequence $a_n$ recursively taking $a_0 = 1$ and
$a_{n+1} = 3 a_n$. Find a formula for $S_n$, where
\[
S_n = \Sigma_{i=1}^n a_i
\]
and use induction to prove that your formula is correct. (Hint: try
doubling each $S_n$.)
 
\item Prove that there are infinitely many primes. (Hint: suppose
$p_0, p_1, \ldots, p_k$ is a list of all the primes, and consider $N =
p_1 p_2 \ldots p_k + 1$. Show that $N$ is either prime or is divisible
by a prime different from any of the $p_i$.)

\end{list1}

\end{document}