\documentclass[11pt]{article}

\usepackage{homework,amssymb}

\begin{document}

\dotitle{12}{Wednesday, November 28}

\begin{list1} 
  
\item Continue reading sections 3.2 and 3.3 in van Dalen, in
  conjunction with the class notes.

\item \addstar Assuming $\theta(x)$ and $\eta$ are any formulas and
  $x$ is not free in $\eta$, prove $\ex x \theta(x) \limplies \eta$
  from $\fa x (\theta (x) \limplies \eta)$.
  
\item \addstar Suppose $\ph$ and $\psi(x)$ are any formulas, and $x$
  is not free in $\varphi$. Prove 
\[
(\varphi \limplies \ex x \psi(x))
  \liff \ex x (\varphi \limplies \psi(x))
\]
using the following steps:
\begin{list2}
\item First prove the $\leftarrow$ direction.
\item From $\ex x \psi(x)$, prove $\ex x (\varphi \limplies \psi(x))$.
\item From $\lnot \ex x \psi(x)$ and $\varphi \limplies \ex x
\psi(x)$, conclude $\ex x (\varphi \limplies \psi(x))$. (Hint: from
the hypotheses, show that $\varphi$ implies {\em anything}.)
\item Put parts (b) and (c) together with a proof of $\ex x \psi(x)
\lor \lnot \ex x \psi(x)$ (you don't have to write out the latter) to
obtain a proof the $\limplies$ direction.
\end{list2}
Note that this $\limplies$ direction of this problem, together with
problem 11, are used in the proof of van Dalen's Lemma 3.1.7.

\item Show that any maximally consistent set of sentences is
  a theory.
  
\item \addstar Suppose $T$ is a maximally consistent theory. Prove
  that $\varphi$ is in $T$ if and only if $\lnot \varphi$ is not in
  $T$.
  
\item Suppose $T$ is a maximally consistent theory. Prove
  that $\ph \limplies \psi$ is in $T$ if and only if either $\ph$ is
  not in $T$, or $\psi$ is in $T$. You may use the previous two problems.

\item \addcirc Do problem 1 on page 112.

\item Do problem 2 on page 112.

\item \addcirc Do problems 3 and 4 on page 112.

\item Consider the following two statements of the
  completeness theorem:
\begin{quote}
\emph{Version A:} If $\Gamma$ is any consistent set of sentences, then
$\Gamma$ has a model.

\emph{Version B:} If $\Gamma$ is any set of sentences, $\ph$ is any
sentence, and $\Gamma \models \ph$, then $\Gamma \proves \ph$.
\end{quote}
Show \emph{directly} that these two statements are equivalent, i.e.\ 
that each one implies the other. (Hint: to show that B implies A, take
$\ph$ to be $\bot$.)

\item \addstar Let $L_1$, $L_2$, and $L_3$ be languages, with $L_1
  \supseteq L_2 \supseteq L_3$. (In other words, $L_1$ has all the
  constant, function, and relation symbols of $L_2$, and possibly
  more; and similarly for $L_2$ and $L_3$.) Suppose $T_1$, $T_2$, and
  $T_3$ are theories in the languages $L_1$, $L_2$, and $L_3$
  respectively. Show that if $T_1$ is a conservative extension of
  $T_2$, and $T_2$ is a conservative extension of $T_3$, then $T_1$ is
  a conservative extension of $T_3$. (You can find the definition of
  ``conservative extension'' on page 106 in van Dalen, Definition
  3.1.5.)

\item Do problems 1 through 5 on page 118--119.

\item \addstar Let $(0,1)$ denote the open interval of real numbers
  between 0 and 1:
\[
(0,1) = \{ x \in \mathbb R \st 0 < x < 1 \}.
\]
Let $[0,1]$ denote the closed interval
\[
[0,1] = \{ x \in \mathbb R \st 0 \leq x \leq 1 \}.
\]
Let $(0,\infty)$ denote the positive real numbers,
\[
(0,\infty) = \{ x \in \mathbb R \st x > 0 \}.
\]
\begin{list2}
\item Show that $\la (0,1), < \ra$ is isomorphic to $\la (0,1), >
  \ra$, by exhibiting a bijective function from $(0,1)$ to $(0,1)$ and
  proving that it is an isomorphism of the two structures. Note that
  the underlying language has a single binary relation $r$ that is
  interpreted as $<$ in the first structure and $>$ in the second.
\item Show that $\la (0,1), < \ra$ is isomorphic to $\la (0, \infty),
  < \ra$. (Hint: consider the function $f(x) = \frac{x}{1-x}$.)
\item Show that $\la (0,1), < \ra$ is {\em not} isomorphic to $\la
  [0,1], < \ra$. (Hint: use Lemma 3.3.3 in van Dalen, and find a
  sentence that is true in one structure but false in the other.)
\end{list2}

\item \addstar Let $\mdl P = \la P, < \ra$ be a linear ordering.
  $\mdl P$ is said to be a {\em well-ordering} if every nonempty
  subset of $P$ has a least (minimum) element. Note that $\la \mathbb
  N, < \ra$ has this property, so you can think of elements of a
  well-ordering as ``generalized numbers'' (a.k.a.\ ``ordinals'').
\begin{list2}
\item Show that the structure $\mdl B$ in exercise 14 on page 91 of
  van Dalen is a well-ordering.
\item Do problem 6 on page 119. In other words, use the suggestion to
  show that there is no set of sentences $\Gamma$ such that the models
  of $\Gamma$ are exactly the well-orderings.
\end{list2}

\end{list1}

\end{document}