\documentclass[12pt]{article}

\begin{document}

\centerline{Homework 4, MORALLY Due Feb 25}
\newcommand{\implies}{\Rightarrow}

\centerline{\bf WARNING: THIS HW IS TWO PAGES LONG!!!!!!!!!!!!!!!!!}

\newif{\ifshowsoln}
\showsolntrue % comment out to NOT show solution inside \ifshowsoln and \fi blocks.

\begin{enumerate}
\item
(20 points)
Simplify the following formula so that its of the form QUANTIFIER QUANTIFIER then stuff.
In other words, there is no negation on the outside or between the quantifiers.


$$\neg (\forall x)(\exists y)[ R(x,y) \wedge \neg S(x,y)].$$


\item
(30 points)
The domain is $N$ which includes 0.
\begin{enumerate}
\item
(5 points)
Write an expression $SQ(x)$ which will mean that $x$ is a square.
\item
(5 points)
Write an expression $SUMSQ2(x)$ which will mean that $x$ is the sum of
two squares.
\item
(5 points)
For all $n$ show how you can write
an expression $SUMSQn(x)$ which will mean that $x$ is the sum of
$n$ squares. Use $SQ$.
\item
(5 points)
Write a sentence that means that every natural is the sum of 1, 2, or 3 squares.
Use the predicates you have defined above.
\item
(0 points but you will need this for the next part).
Write a program that will, for all $0\le x\le 1000$ determine the smallest number of 
squares such that $x$ is the sum of that many squares.
(For this part do not hand anything in.)
\item
(15 points)
Based on the data you produces make TWO conjectures along the lines of:
\begin{itemize}
\item
Every number is the sum of at most BLAH squares.
\item
The infinite set X is such that every number in X can be written as the sum
of BLAH squares but NOT BLAH-1 squares.
(NOTE- X should be a nice set-- its okay if some elements NOT in X also need BLAH squares.)
\end{itemize}
\end{enumerate}


\centerline{\bf GOTO NEXT PAGE}

\newpage

\item
(20 points)
For the following sentences find both (a) an infinite domain where it is true,
and (b) an infinite domain where it is false. All domains should be subsets of $R$.

$(\forall x)(\exists y)[x=y^2]$ but DO NOT use $R$ or any closed or open or clopen interval.

\item
(30 points)
(Recall that $Q$ is the rationals.)
\begin{enumerate}
\item
Prove that $\sqrt{5}\notin Q$ using the mod method.
(Hint: First prove a lemma about mods.)
\item
Prove that $\sqrt{5}\notin Q$ using unique factorization.
\end{enumerate}

\end{enumerate}

\end{document}