% LaTex2e
\documentclass[12pt]{article}
\usepackage{amssymb,latexsym}
\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
\end{flushright}

\begin{center}
  Review questions for Final
\end{center}

\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?

\bigskip
\bigskip \noindent
Final exam - B105 Van Vleck (usual classroom) - Monday May 13 2:45-4:45pm.

\end{document}