\documentclass[11pt]{article}

\usepackage{hw}

\begin{document}

\dotitle{5}{Thursday 2 November}


\begin{enumerate}

\item In section 1.6 of van Dalen, do problems 1 and 5 (using the intro and elim rules for disjunction).

\item Consider a first-order language, with relation symbols
  $<$ and $=$, and constant symbol $0$. The intended interpretation is
  the natural numbers, with ``less-than'' and ``equality.''  Formalize
  the following statements:
\begin{enumerate}
\item ``$x$ is less than or equal to $y$''
\item ``0 is the smallest number''
\item ``there is a smallest number''
\item ``there is no largest number''
\item ``every number has an immediate successor'' (in other words, for
every number, there is another one that is the ``next largest'')
\item ``every number is greater than some (other) number''
\item ``there is some number that every (other) number is greater than''
\item ``3 is greater than 2"
\end{enumerate}

\item Consider a first-order language, with predicate symbols
  $M$ and $G$, and constant symbol $s$. The intended interpretation is
  all people, living or dead, with $M(x)$ meaning ``$x$ is mortal'',
  $G(x)$ meaning ``$x$ is Greek'', and $s$ meaning Socrates. Formalize
  the following statements:
\begin{enumerate}
\item ``if $x$ is Greek, then $x$ is mortal''
\item ``all Greeks are mortal''
\item ``some Greeks are mortal''
\item ``no Greeks are mortal''
\item ``no Greeks are immortal''
\item ``Socrates is a mortal Greek, but there are some who are immortal''
\item ``if anyone is mortal, Socrates is''
\item ``if all Greeks are mortal, and Socrates is Greek, then Socrates
  is mortal''
 \item ``if some mortals are Greeks, then some Greeks are not Mortal''
\end{enumerate}

\item Consider a first-order language, with a constant symbol $a$, a predicate symbol $P$, and a binary relation symbol $R$.  Consider the two different interpretations:
\begin{enumerate}
\item[] $\mathcal{A}$\ :  $|\mathcal{A}|$ = all natural numbers, $a^{\mathcal{A}} = 0$,  $P^{\mathcal{A}}$ = the even numbers, $R^{\mathcal{A}}$ = the ``less than'' relation.
\item[] $\mathcal{B}$\ :  $|\mathcal{B}|$ = all people, $a^{\mathcal{B}}$ = Socrates,  $P^{\mathcal{B}}$ = Greeks, $R^{\mathcal{B}}$ = the ``teacher of'' relation.
\end{enumerate}
Find simple formulae which are: (i) true under both interpretations, (ii) under neither, (iii) under  $\mathcal{A}$  only, (iv) under  $\mathcal{B}$  only.

\item Do problem 1 on page 60 of van Dalen.

\item Do problem 4 on page 68 of van Dalen. 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 2 on page 60.

\end{enumerate}

\end{document}