% HW 9 for 80-310-610
% Autumn 2006

\documentclass[11pt]{article}
\usepackage{hw}
\begin{document}
\dotitle{9}{Thursday, November 30}

\begin{enumerate}

\item Determine whether each of the following arguments is valid.  Justify your answer either way.

\begin{enumerate}

\item \begin{quote}
All whales are fish.\\
Some mammals are not fish.\\
No mammals that are whales are fish.\\
Therefore, no mammals are whales.
\end{quote}

\item \begin{quote}
If you serve in the National Guard, you get paid.\\
W got paid for serving in the National Guard.\\
Therefore, W served in the National Guard.
\end{quote}

\end{enumerate}

%\item In the language $\mc{L}=\{<\}$ consider the theory $\mathbf{\Delta}$  of the ordering of the Real numbers $\R$,
%\[
%\Delta = \{ \sigma\ |\ \R\models\sigma\}.
%\]
%Use the downward L{\"owenheim}-Skolem theorem to show that $\Delta$ has a countable model $\mc{M}$  (i.e.\ the set $|\mc{M}|$ is isomorphic to the natural numbers $\N$).  Infer that there is no hope of \emph{fully} axiomatizing the ordering of the Reals in first-order logic (i.e.\ so that any two models are isomorphic).  Would it help to add more relation, function, and constant symbols?  Why?

\item In the language $\mc{L}=\{0, S, +, \cdot \}$ of Arithmetic (see van Dalen, 2.7, example 6) consider the set $\mathbf{T}$  of sentences satisfied by the Natural Numbers $\N$,
\[
\mathbf{T} = \{ \sigma\ |\ \N\models\sigma\}.
\]
Is $\mathbf{T}$  a Henkin theory?  Justify your answer!

\item Does the theory $\mathbf{T}$ above have any finite models?  Does it have any models other than the natural numbers?  Justify your answers!

\item Consider the language $\mathcal{L} = \{0, S, \leq \}$ with a constant symbol, a unary function symbol and a binary relation symbol.  \begin{enumerate}
\item Can you give a finite axiom set for a theory having only finite models of a given size?  If so, do so; if not, say why.
\item Can you give a finite axiom set for a theory having only infinite models? If so, do so; if not, say why.
\item\addstar Can you write down an axiom set for a theory having finite models of every finite size, but no infinite models? If so, do so; if not, say why.

\end{enumerate}

%Use the upward L{\"owenheim}-Skolem theorem to show that $\mathbf{T}$ has an uncountable model $\mc{N}$  (i.e.\ the infinite set $|\mc{N}|$ is not isomorphic to the natural numbers $\N$).  Infer that there is no hope of \emph{fully} axiomatizing the arithmetic of the Naturals in first-order logic (i.e.\ so that any two models are isomorphic).  Would it help to add more relation, function, and constant symbols?  Why?

%\item In the language $\mc{L}=\{0, S, +, \cdot \}$ of Arithmetic consider the theory $\mathbf{PA}$  of Peano Arithmetic (see van Dalen, 2.7.7).  Show that the model $\mc{N}$ from the foregoing problem is a ``non-standard" model of $\mathbf{PA}$, in the sense that (it models $\mathbf{PA}$ and) there are elements $n\in |\mc{N}|$ satisfying all of the infinitely many sentences in the following set $\Gamma$:
%\[
%\Gamma = \{ 0<n, S(0)<n, S(S(0))<n, \ldots \}
%\]
%Infer that the set of elements $\{0, S(0), S(S(0)), \ldots\}$ in this model of $\mathbf{PA}$ is not definable in first-order logic (hint: consider the induction axiom).

%\item Use compactness to show that there is a \emph{countable}, non-standard model of $\mathbf{PA}$ (i.e.\ one also satisfying $\Gamma$ above).  Can the same line of reasoning be used to find a non-standard model of the theory $\mathbf{T}$ of ``true arithmetic" from problem 3 in place of $\mathbf{PA}$?  Justify your answer!

%\item\addstar Do problem 4 on page 134.

\end{enumerate}

\end{document}