% LaTex2e
\documentclass[12pt]{article}
\usepackage{amssymb,latexsym}

\def\moda{{\frak A}}
\def\rr{{\mathbb R}}
\def\aa{{\mathbb A}}
\def\cc{{\mathbb C}}
\def\qq{{\mathbb Q}}
\def\nn{{\mathbb N}}
\def\zz{{\mathbb Z}}
\def\famf{{\mathcal F}}

\def\disj{\vee}
\def\conj{\wedge}
\def\implies{\to}
\def\iff{\leftrightarrow}

\newcount\probno
\probno=0
\def\prob{\advance\probno by 1  \par\bigskip
    \noindent\the\probno . }




\pagestyle{empty}
\newcount\probno

% save paper style
\oddsidemargin 5pt \evensidemargin 5pt \marginparwidth 68pt
\marginparsep 10pt \topmargin -40pt \headheight 10pt
\headsep 15pt \footskip 35pt
\textheight = 645pt  \textwidth 440pt \columnsep 10pt \columnseprule 5pt
\probno=0
\def\prob{\advance\probno by 1
 \par\bigskip\noindent\the\probno . }

%\def\prob{\par\bigskip\noindent}
\def\nn{{\mathcal N}}

\begin{document}

\begin{flushright}
A.Miller\\
M571\\
Spring 2002\\
Final Exam\\

\end{flushright}

Answer any four of the following questions plus one more.  The fifth problem
can be another one taken from below or if you prefer you can do a homework
exercise of your choice (state the exercise fully and pick one that is as
hard as you are able to do).

\bigskip

Answer each of the five questions as fully as you can and as if you were
telling it to another student not necessarily in this course.

\bigskip
{\bf Please use a separate sheet or sheets of paper for each problem.}
\bigskip

\prob Define theory, complete theory, axioms of a theory, and decidable
theory.  Prove that a complete theory with a computable set of axioms is
decidable.  Give an example of such a theory.

\prob  Let $\nn=(\omega,+,\cdot,\leq,S,0)$.
Give a sketch of the proof that Th$(\nn)$ is undecidable.
What is the relationship between
primitive recursive functions, recursive functions, computable functions,
computably enumerable sets, and arithmetic sets? (Define all of these.)

\prob Deduce as a corollary that for any computable set
$\Sigma\subseteq$Th$(\nn)$ that there is a sentence of arithmetic $\theta$
which is true in $\nn$ but $\Sigma$ does not prove $\theta$.

\prob What is an interpretation of a theory $T$ into another theory $T'$?
Prove in this case that if $T$ is undecidable, then $T'$ is undecidable.

Prove:

\noindent (a) Th$(\nn)$ is interpretable into Th$(\omega,+,\cdot)$

\noindent (b) Th$(\omega,+,\cdot)$ is undecidable.

\noindent (c) Th$(\omega,+,\cdot)$ is interpretable in the
Th$(\omega,\cdot,S)$.

\noindent (d) Th$(\omega,\cdot,S)$ is undecidable.


\prob  What does the {\L}os-Vaught test say?  How is it proved? Give an
example using it.

\prob  What is the completeness theorem of first-order logic? Give a sketch
of its proof.

\prob What is the Lowenheim-Skolem theorem?  How is it proved?

\prob What is a well-formed formula of propositional logic?  Give the formal
definition.

\prob What is the compactness theorem for propositional logic? Give a sketch
of its proof.  Give an example using it.

\prob Is the compactness theorem true for first-order logic? Does it have
anything to do with the completeness theorem?


\end{document}