\documentclass[11pt]{article}

\usepackage{homework,amssymb,eufrak,amsmath}


\begin{document}

\soltitle{14}{Thursday, December 4}

\begin{list1} 

\item[5.\hfill] If $T$ is inconsistent, the problem is trivial: every
  sentence is in $T$.

  Otherwise, given a sentence $\ph$, to determine whether or not
  $\ph$ is a theorem of $T$, do the following two things in parallel:
  search for a proof of $\ph$ from the axioms of $T$, and search for a
  proof of $\lnot \ph$. Since $T$ is complete, one of these searches
  is bound to succeed. In the first case, the answer is yes; in the
  second case, the answer is no.

\item[7.\hfill]
\begin{list2}
\item I really botched this problem. I should have listed the axioms
  as follows:
\begin{itemize}
\item $\;\; \fa x (\lnot S(x) = 0)$
\item $\;\; \fa {x,y} (S(x) = S(y) \limplies x = y)$
\item $\;\; \fa x (x \neq 0 \limplies \ex y (S(y) = x)$
\end{itemize}
As well as, for each $n$, an axiom
\[
S(S(\ldots(S(x)))) \neq x,
\]
where there are $n$ $S$'s in this expression.

Any structure satisfying these axioms ``looks'' as
  follows. First of all, there are a single chain that is isomorphic
  to the natural numbers (call these $\mathbb N$-strips):
\\
\\
\\
   and then there may be some chains that are isomorphic to the
   integers (call these $\mathbb Z$-strips):
\\
\\
\\
Without the third axiom, there may be more than one $\mathbb N$-strip.
Without the fourth batch of axioms, there may also be loops:
\\
\\
\\
\\

\item There are countable models with one $\mathbb N$-strip only; and
  there are countable models with an $\mathbb N$-strip and a $\mathbb
 Z$-strip only, etc.
 
\item For the axioms above, every uncountable model has one $\mathbb
  N$-strip and uncountably many $\mathbb Z$-strips.
\end{list2}

\item[9.\hfill] 
\begin{list2}
\item The formula
\[
\begin{split}
\ex R (& \fa x \ex y R(x,y) \land \\
& \fa {x,x',y} (R(x,y) \land R(x',y)
\limplies x=x') \land \\
& \ex y \fa x \lnot R(x,y))
\end{split}
\]
works. After all, if there is such a relation on the universe of the
model, there has to be some $a_0$ such that nothing is related to it;
and a value $a_1$, such that $R(a_0,a_1)$; and a value $a_2$, such
that $R(a_1,a_2)$, and so on. This gives us a sequence of elements
\[
a_0, a_1, a_2, \ldots
\]
in the universe of the model. By induction, let us show that for each
$i$, $a_i$ is not equal to any other $a_j$. This is true when $i = 0$.
So suppose it is true for $i$, and let us show that it is true for
$i+1$.  By induction, let us show that $a_{i+1}$ is not equal to
$a_j$. Note that we have $R(a_i,a_{i+1})$. So $a_{i+1}$ cannot be
$a_0$; and if it is equal to $a_{j+1}$, we have $R(a_i,a_{j+1})$ and
$R(a_j,a_{j+1})$, which implies $i=j$, contrary to the induction
hypothesis.

So the universe of any such model is infinite. Conversely, it isn't
hard to see (assuming the axiom of choice!) that given an infinite
model there is a relation of this form: pick out any countable subset,
and let each element in the subset be related to the ``next''; and
let every other element of the model be related to itself.

\item Let $\ph$ be the statement above. Then $\lnot \ph$ defines the
  class of finite models.

\item For each natural number $i$, let $\psi_i$ be the sentence in the
  language of equality, which ``says'' that there are at least $i$
  elements in the universe. Consider the set of sentences
\[
\lnot \ph, \psi_0, \psi_1, \psi_2, \ldots
\]
  Then every finite subset has a model, but the entire set doesn't
  have a model.
\end{list2}

\item[10.\hfill]
We know that we can define the set of linear orders (in fact, in
first-order logic). Take those axioms, and add the following
sentence, which ``says'' every nonempty set has a least
element:
\[
\fa R (\ex x R(x) \limplies \ex x (R(x) \land \fa y (R(y) \limplies x
\leq y))).
\]

\item [14.\hfill] The following structure provides a counterexample
  for both problems.

\end{list1}

\end{document}