\documentclass[11pt]{article}

\usepackage{homework,amssymb,eufrak}

\begin{document}

\dotitle{10}{Wednesday, November 7}

\begin{list1}

\item Finish reading Chapter 2 in van Dalen.

\item Do problems 1, 2, and 3 on page 80.
  
\item Do problems 4 and 6 on page 80. (In each case, show that for
  some formula $\varphi$ in a language of your choosing, the
  equivalence shown is not valid.)

% \item \addstar Show that if $x$ is not a free variable of $\psi$, then
% \[
% (\psi \limplies \ex x \ph) \limplies \ex x (\psi \limplies \ph)
% \]
% is valid. Do this carefully, using the definition of truth in a
% structure (or Lemma 2.4.5).

\item Do problem 5 on page 80. Note that this relies on the convention
that we do not consider structures with empty universes.

% \item Do problem 6 on page 80.

\item Do problem 12 on page 81. You can use any of the lemmas
and theorems in section 2.5 to make your argument as clear as
possible. Note that the barber paradox reads as follows: ``In a
certain town the barber shaves all and exactly those people who do not
shave themselves. Who shaves the barber?''

\item \addstar Do problem 14c on page 81, assuming $\ph$, $\psi$, and
  $\sigma$ are quantifier-free.

\item \addstar Do problem 15 on page 81.
  
\item In the language of arithmetic, with constant symbols 0 and 1,
  functions symbols $+$ and $\times$, and a relation symbol $<$,
  formalize the following:
\begin{list2}
\item the statement, ``$x$ is prime.''
\item the statement, ``There are infinitely many primes.''
\item the principle of induction for a formula $\varphi(x)$
\item the least-element principle for a formula $\varphi(x)$
\end{list2}

\item The language of sets has a single binary relation
  symbol $\in$, where $x \in y$ is meant to denote the fact that $x$
  is an element of $y$. In the intended interpretation, everything is
  a set; that is, every object is a set, whose elements are sets, and
  so on. In this language, formalize the following statements:
\begin{list2}
\item $x$ is a subset of (or equal to) $y$.
\item Two sets are equal if and only if they have the same elements.
\item For any set $z$, there is another set $w$ consisting of all the
subsets of $z$. (You can use the symbol $\subseteq$ to abbreviate the
formula you found in part (a).)
\end{list2}

\item In a language with a binary relation symbol $<$,
  formalize the following statements:
\begin{list2}
\item $<$ is transitive.
\item Between any two things there is another thing.
\item There is a smallest thing.
\item There is no largest thing.
\end{list2}

% \item \addcirc In the language of groups, which has a multiplication
%   symbol $\cdot$ and a constant symbol $i$, formalize the following
%   statements:
% \begin{list2}
% \item $\cdot$ is associative.
% \item $\cdot$ is not commutative.
% \item $i$ is an identity.
% \item Every element has an inverse.
% \end{list2}

\item \addstar Let $\mathcal A$ be the structure consisting of ``all objects on
the planet Earth'' with relations {\em IsCow(x)}, {\em
EatsGrass(x)}, {\em IsCar(x)}, etc. Give reasonable formalizations of
the following sentences:
\begin{list2}
\item All cows eat grass.
\item There is a car that is blue and old.
\item No car is not pink.
\item All cars that are old must be inspected annually.
\end{list2}
% In plain English, express the negation of each of these sentences,
% that is, the assertion that each sentence is false.

% \item \addcirc In a language with unary relation symbols $Red(x)$,
%   $Car(x)$, and $Broken(x)$, come up with a reasonable formalization
%   of the sentence ``The red car is broken.''

\item Consider the language of orderings with a single binary
  relation symbol $\leq$. Use $x < y$ as shorthand for $x \leq y \land
  \lnot (x = y)$. An element $a$ in a partial ordering $\mdl P$ is
  {\em minimal} if there is no element smaller than it; that is,
  $\mdl P \models \fa{x} \lnot (x < \bar a)$. An element $a$ is {\em
    minimum} if it is at least as small as every other element; that
  is, $\mdl P \models \fa{x} (\bar a \leq x)$.
\begin{list2}
\item Describe a partial ordering with a minimal element, but no
minimum element. (You can use a diagram.)
\item Show that in a linear ordering, an element is minimum iff it is
minimal.
\item Describe a linear ordering with no minimal element.
\end{list2}
You can argue informally about what is ``true in $\mdl P$,'' without
having to use Lemma 2.4.5 explicitly; but your argument should be
mathematically rigorous.

\item Do problem 2 on page 90.

\item \addstar Do problem 3 on page 90. Help out the grader by
  explaining, informally, what your formula is supposed to say.

\item \addstar Do problem 4 on page 90.

\item Do problem 5 on page 90.

\item Do problem  6 on page 90.
  
\item Do problem 10 on page 91. This really means, using the
  language of arithmetic on page 87, define the given relations in the
  ``standard'' structure $\la \mathbb{N}, 0, S, +, \times \ra$. Note
  that ``$x$ and $y$ are relatively prime'' means that they have no
  common factor other than 1.
  
\item \addstar In $\la \mathbb{N}, 0, S, +, \times \ra$, define
\begin{list2}
\item the set of primes (i.e.\ the unary relation ``$x$ is a prime'')
\item the set of odd perfect squares
\item the set of numbers with at least 3 different prime factors
\end{list2}
Use the symbol ``0'' to denote the element 0, the symbol ``$S$''
to denote the successor function $S$, and so on.

\item In the structure $\la \mathbb{N}, < \ra$, define
\begin{list2}
\item 0 (i.e.\ the unary relation $x = 0$)
\item 1
\item The relation ``$y$ is the successor of $x$''
\end{list2}

\item Do problem 14 on page 91. Note that the second relation amounts
  to ``reordering'' the natural numbers, so that all the even numbers
  come first, and all the odd ones come next. (This problem is not
  easy! Give it your best shot.)

\item \addcirc Try to define the class of structures with finite
universes in the language of equality, or explain why this is
impossible. Do the same for well orderings in the language with
$\leq$. (In fact, you can add any function or relation symbols you
want to these languages.)

\item \addcirc If you have some background in abstract algebra, do
probems 7, 8, and 9 on page 91.

\item \addcirc Do problem 12 on page 91.

\end{list1}

\end{document}



\end{list1}

\end{document}