\documentclass[11pt]{article}

\usepackage{homework,amssymb,eufrak}

\begin{document}

\dotitle{13}{Wednesday, December 5}

\begin{list1}

\item Read Chapter 4 of van Dalen, and as much of Chapter 5 as you
  can.
  
\item Note that this is the last homework assignment to be turned in!
  The final exam is on Friday, December 14, from 1-3 PM. Next week, I
  will announce extra office hours. On the exam, I will only test you
  directly on material covered since the midterm. But note that this
  includes, implicitly, a lot of material from the first half of the
  course, such as the notion of a maximally consistent set, proof
  rules for the propositional connectives, etc.

\item Do problems 7--10 on page 119.
  
\item \addstar Do problem 13 on page 119. (Note that saying that
  $Mod(T_1 \cup T_2)=\emptyset$ is equivalent to saying that $T_1 \cup
  T_2$ is inconsistent. Use the compactness theorem.)
  
\item \addstar Show that if $T_1$ and $T_2$ are consistent theories,
  and $T_1 \neq T_2$, then $Mod(T_1) \neq Mod(T_2)$. In other words,
  if $T_1 \neq T_2$, then there is a structure that is a model of one
  but not the other. (Hint: show that if $T_1 \neq T_2$, there is a
  sentence $\ph$ in one but not the other. Without loss of generality,
  say $\ph$ is in $T_1$ but not $T_2$. Using the fact that $T_2$ is a
  theory, show $T_2 \cup \{ \lnot \ph \}$ is consistent.)

\item \addcirc Do problem 3 on page 133. This is a nice application of
compactness.

\item Do problem 5 on page 134.

\item \addstar Do problem 6 on page 134. Note that $\mathcal A
\subseteq \mathcal B$ means that $\mathcal A$ is a substructure of
$\mathcal B$, and $\mathcal A \prec \mathcal B$ means that $\mathcal
A$ is an {\em elementary} substructure of $\mathcal B$.

\item What subsets of the real numbers are first-order definable in
  the structure $\la \mathbb R, < \ra$?
  
\item \addstar Show that multiplication (that is, the relation $x
  \times y = z$) is not definable in $\la \mathbb{R}, 0, +, < \ra$.
  (Hint: find an automorphism $f$ of this structure, such that for
  some $a$ and $b$ $f(a \times b)$ is not equal to $f(a) \times
  f(b)$.)

\item Show that addition is not definable in the structure
   $\la \mathbb N, \times \ra$. (Hint: consider an automorphism that
   switches two primes.)

\item Explain Skolem's paradox, and why it isn't really a paradox.
  
\item \addstar Let $T$ be a complete theory with an effective set of
  axioms (in other words, there is an algorithm which determines if a
  given string of symbols is an axiom of $T$). Show that $T$ is
  decidable (that is, there is an algorithm which determines whether
  or not a given string of symbols is in $T$, i.e.\ provable from the
  axioms).
  
\item The ``theory of a successor operation'' is the theory
  in the language $0, S$ axiomatized by the following sentences:
\begin{myitemize}
\item $\fa x (\lnot S(x) = 0)$
\item $\fa {x,y} (S(x) = S(y) \limplies x = y)$
\item For each $i$, the sentence $\fa x \lnot S^i(x) = x$
\end{myitemize}
The last item is a schema; the notation $S^i(x)$ means $S(S(\ldots
S(x)))$ where $S$ occurs $i$ times.
\begin{list2}
\item What does a model of this theory look like?
\item Show that this theory is not categorical for countable
  structures.
\item \addcirc Show that this theory {\em is} categorical for uncountable
  structures, and hence, by the Los-Vaught test, complete.
\end{list2}

\item \addstar Let $L$ be the language with a single binary relation
  $<$. Show the the class of well-orderings is definable in
  second-order logic.

\item \addcirc
\begin{list2}
\item Let $L$ be the language with no ``built-in'' function and
  relation symbols other than equality. Find a formula $\ph$ in the
  language of second-order logic, such that for every (full) structure
  $\gmdl A$, $\gmdl A \models \ph$ if and only if $|\gmdl A|$ is
  infinite. In other words, show that the class of infinite structures
  is definable by a single formula in second-order logic.  (Hint: use
  the suggestions in the notes to express the assertion that there is
  an injective map from the universe to a proper subset of itself.)
\item Show that the class of finite structures is definable in
  second-order logic.
\item Show that compactness does not hold for second-order logic, by
  exhibiting a set of sentences which is finitely satisfiable, but not
  satisfiable.
\end{list2}

\end{list1}

\end{document}