\documentclass[11pt]{article}

\usepackage{homework,amssymb,eufrak}

\begin{document}

\homeworkhead 
\bigskip\bigskip
\begin{center}
{\sc Homework 14} \\ {\small (Entirely optional)}
\end{center}
\bigskip\bigskip

\begin{list1}

\item This homework assignment is designed to keep you busy for a
  while after the course is over. Some of the problems are very hard;
  none are required for the course.

\item \addcirc Show that addition {\em is} definable in the structure
  $\la \mathbb N, \times, < \ra$.

\item \addcirc Show that exponentiation (and, in fact, any primitive
  recursive function) is definable in the structure $\la \mathbb N, +,
  \times \ra$.
 
\item \addcirc Use the suggestion in the notes to show that $<$
  is not definable in $\la \mathbb N, S \ra$.

\item \addcirc Show that addition is not definable in $\la N, S, <
  \ra$.

\item \addcirc Do problem 10 on page 134.

\item \addcirc Do problem 11 on page 134.

\item \addcirc Fill in some of the details left out of the notes, and verify
  that there is a categorical description of the structure $\la
  \mathbb N, 0, S, +, \times, < \ra$ in second-order logic. (For this
  problem and the ones that follow, you can assume that we are using
  the full second-order semantics.)


\item \addcirc Show how to define the class of finite structures such that the
  cardinality of the universe is a multiple of 5.

\item \addcirc Find a second-order formula $\ph(x,y)$ in the language
  of graphs, which defines the relation ``there is a path from $x,y$''
  in any graph.

\item \addcirc (Hard!)
\begin{list2}
\item Provide a categorical description of $\la \mathbb R, 0,
  1, +, \times, < \ra$

\item \addcirc Find a formula $\ph$ which is valid in full
  second-order semantics if and only if the continuum hypothesis is
  true. (Hint: $\ph$ should assert that there exist appropriate
  functions on relations on the universe, making it isomorphic to the
  structure in (a), and that every subset of the universe is either
  countable or has the same cardinality as the entire universe.)
\end{list2}

\item \addcirc Come up with simple Kripke model to show that each of
  the following propositional formulas is not intuitionistically
  valid:
\begin{list2}
\item $(p \limplies q) \lor (q \limplies p)$
\item $\lnot (p \land q) \limplies (\lnot p \lor \lnot q)$
\end{list2}
Note that they {\em are} classically valid.

\item \addcirc (Hard!) A linear order $\gmdl P = \la P, < \ra$ is {\em
    dense} if between any two elements, there is another element. The
  ``theory of dense linear orderings'' is $Th(\mathcal K)$, where
  $\mathcal K$ is the class of dense-linear orderings. This theory can
  be axiomatized by the axioms for linear orderings, together with the
  axiom
\[
\fa {x,y} (x < y \limplies \ex z (x < z \land z < y)).
\]
\begin{list2}
\item Show that any two countable dense linear orders with no greatest
  or least element are isomorphic. (Hint: Cantor was the first to
  prove this, using a ``back-and-forth'' argument. Build the
  isomorphism in stages.)
\item Using the Los-Vaught test, show that the theory of dense linear
  orders with no greatest or least element is complete, and hence
  decidable.
\item Show that there are exactly four complete theories containing
  the theory of dense linear orderings, and that each one of these is
  decidable.
\item Show that the theory of dense linear orderings is decidable.
\item Show that the theory of dense linear orderings is not
  categorical in the cardinality of $\mathbb R$.
\end{list2}

\end{list1}

\end{document}