\documentclass[11pt]{article}

\usepackage{homework}

\begin{document}

\dotitle{7}{Wednesday, October 10}


\begin{list1}

\item Finish reading Section 1.5 in van Dalen. Then read Sections 1.6,
  2.1, and 2.2. Note that the midterm exam is in class on Wednesday,
  October 17.

\item Do problem 3 on page 39 of van Dalen.
  
\item \addstar Do problem 4 on page 39. Hints: For 4a, remember that
  if $\alpha$ and $\beta$ are any formulas, from $\beta$ you can
  conclude $\alpha \limplies \beta$. 4b is tricky, because it is not
  classically valid; you will need to use RAA. Note that from $\lnot
  \alpha$ you can conclude $\alpha \limplies \beta$ using \emph{ex
    falso} (show how).

\item Do problems 5, 7, and 8 on pages 39--40.
 
% \item \addstar Do the following part of problem 8 on page 40: Prove
% \[
% (\psi \land \theta)[\varphi_1/p] \liff
% (\psi \land \theta)[\varphi_2/p]
% \]
% from hypotheses
% \[
% \psi[\varphi_1/p] \liff \psi[\varphi_2/p]
% \]
% and 
% \[
% \theta[\varphi_1/p] \liff \theta[\varphi_2/p].
% \]
% (See the comment after item 4 above.)

\item Do problem 1 on page 47. 
If you claim the set is
inconsistent, show that you can prove a contradiction from those
assumptions. If you claim the set is consistent, demonstrate this by
providing a valuation under which all the formulas are true. (Note
that the completeness theorem implies that if a set of formulas is
consistent, there will always be such a valuation.)

\item \addstar Do problem 2 on page 47.

\item \addstar Do problem 3 on page 47.
  
\item \addstar A formula $\ph$ is said to be {\em independent} of a
  set of formulas $\Gamma$ if $\Gamma \not \proves \ph$ and $\Gamma
  \not \proves \lnot \ph$. Suppose $\Gamma$ is a consistent set of
  formulas, $\varphi$ is independent of $\Gamma$, and $\psi$ is
  independent of $\Gamma \cup \{\varphi\}$. Show that there are at
  least three different maximally consistent sets containing $\Gamma$.
  
\item Find a consistent set $\Gamma$ that is not maximally
  consistent, but has the property that there is only one maximally
  consistent set containing it. In fact, show that there is a fixed
  natural number $k$, such that we can assume that every formula in
  $\Gamma$ has length at most $k$.

\item \addcirc Do problem 4 on page 47 of van Dalen.
  
\item \addcirc Do problem 5 on page 48. In effect, you will be
  describing a computer program that prints out propositional formulas
  ad infinitum, in such a way that every propositional formula is
  printed sooner or later.

\item \addstar Do problem 6 on page 48. Van Dalen's wording is
  awkward. What you need to prove is this: Suppose $\Gamma$ is a
  consistent set of formulas with the property that for every formula
  $\ph$, either $\ph \in \Gamma$ or $\lnot \ph \in \Gamma$. Then
  $\Gamma$ is maximally consistent.

\item \addstar Show that if $\Gamma$ is any consistent set, and
  $\varphi$ is any formula, then either $\Gamma \cup \{\varphi\}$ or
  $\Gamma \cup \{ \lnot \varphi \}$ is consistent. (Hint: suppose they
  are both inconsistent\ldots)

\end{list1}

\end{document}