\documentclass[11pt]{article}

\usepackage{homework,amssymb,eufrak}

\begin{document}

\dotitle{9}{Wednesday, October 31}

\begin{list1} 

\item Read through section 2.6 in van Dalen.
  
\item \addstar (Repeated from last assignment.) Do problem 4 on page
  68. In each case, just indicate whether the term is ``free'' or
  ``not free'' for the specified variable in the specified term, and
  carry out the substitution either way.
  
\item \addstar Do problem 1 on page 72. Use the symbols $P$, $T$, $S$,
  and $c$ to denote addition, multiplication, successor (``+1''), and
  0 respectively.

\item Do problems 2 and 3 on page 72.

\item \addcirc Prove unique readability for terms and formulas in a
given first-order language (and/or write a parser).

\item \addstar Consider the equivalence
\[
\ex x (\varphi(x) \land \psi(x)) \liff (\ex x \varphi(x) \land \ex x
\psi(x)).
\]
\begin{list2}
\item Show that one direction of this equivalence is valid (i.e.\ true
in every structure). Prove this carefully; you can use Lemma 2.4.5.
\item Find examples of $\ph$ and $\psi$ where the other direction is
  not valid (and justify this claim).
\end{list2}

\item \addstar Fix a language, $L$, which has one binary relation
symbol, $R$. Which of the following statements are true and which are
false? Justify your answers.
\begin{list2}
\item If $\varphi$ is any sentence, either $\models \varphi$ or
$\models \lnot \varphi$.
\item If $\varphi$ is any sentence and $\gmdl{A}$ is any structure,
either $\gmdl{A} \models \varphi$ or $\gmdl{A} \models \lnot
\varphi$.
\item If $\varphi$ is any sentence and $\Gamma$ is any set of
sentences, then either $\Gamma \models \varphi$ or $\Gamma \models
\lnot \varphi$.
\end{list2}

\item Do problems 6 and 7 on page 72.

\end{list1}

\end{document}