\documentclass[11pt]{article}

\usepackage{homework,amssymb,eufrak,bussproofs,mylogic}

\EnableBpAbbreviations

\begin{document}

\soltitle{12}{Thursday, November 20}

\begin{list1} 

\item[2.\hfill] \ 
\begin{prooftree}
\AXM{[\ex x \theta(x)]_2}
\AXM{[\theta(x)]_1}
\AXM{\fa x (\theta(x) \limplies \eta)}
\UIM{\theta(x) \limplies \eta}
\BIM{\eta}
\RL{1}
\BIM{\eta}
\RL{2}
\UIM{\ex x \theta(x) \limplies \eta}
\end{prooftree}

\item[3.\hfill] \ 
\begin{list2}
\item \ 
\begin{prooftree}
\AXM{[\ex x (\ph \limplies \psi(x))]_3}
\AXM{[\ph \limplies \psi(x)]_1}
\AXM{[\ph]_2}
\BIM{\psi(x)}
\UIM{\ex x \psi(x)}
\RL{1}
\BIM{\ex x \psi(x)}
\RL{2}
\UIM{\ph \limplies \ex x \psi(x)}
\RL{3}
\UIM{(\ex x (\ph \limplies \psi(x))) \limplies (\ph \limplies \ex x
  \psi(x))}
\end{prooftree}

\item \ 
\begin{prooftree}
\AXM{\ex x \psi(x)}
\AXM{[\psi(x)]_1}
\UIM{\ph \limplies \psi(x)}
\UIM{\ex x (\ph \limplies \psi(x))}
\RL{1}
\BIM{\ex x (\ph \limplies \psi(x))}
\end{prooftree}

\item \ 
\begin{prooftree}
\AXM{\lnot \ex x \psi(x)}
\AXM{\ph \limplies \ex x \psi(x)}
\AXM{[\ph]_1}
\BIM{\ex x \psi(x)}
\BIM{\bot}
\UIM{\psi(x)}
\RL{1}
\UIM{\ph \limplies \psi(x)}
\UIM{\ex x (\ph \limplies \psi(x))}
\end{prooftree}

\item This is just the $\lor$ elimination rule:
\begin{prooftree}
\AXM{\ex x \psi(x) \lor \lnot \ex x \psi(x)}
\AXM{[\ex x \psi(x)]_1}
\noLine
\UIM{\vdots (b)}
\noLine
\UIM{[\ex x (\ph \limplies \psi(x))]_2}
\AXM{[\lnot \ex x \psi(x)]_1}
\noLine
\UIM{\vdots}
\AXM{\ph \limplies \ex x \psi(x)}
\noLine
\UIM{\vdots (c)}
\noLine
\BIM{\ex x (\ph \limplies \psi(x))}
\RL{1}
\TIM{\ex x (\ph \limplies \psi(x))}
\RL{2}
\UIM{(\ex x (\ph \limplies \psi(x)) \limplies \ex x (\ph \limplies \psi(x)))}
\end{prooftree}
\end{list2}
  
% \item[4.\hfill] Suppose $T$ is maximally consistent, and $T \proves
%   \ph$. I need to show that $\ph$ is in $T$. Aiming for a
%   contradiction, suppose $\ph$ is not in $T$.  Then $T \cup \{ \ph \}$
%   is inconsistent, by the definition of ``maximally consistent''; in
%   other words, $T \cup \{ \ph \}$ proves $\bot$. Using $\limplies$
%   introduction, $T$ proves $\lnot \ph$. But since $T$ also proves
%   $\ph$, it is inconsistent, contrary to our hypothesis.

\item[5.\hfill] Suppose $T$ is a maximally consistent theory.

For the forwards direction, suppose $\ph$ is in $T$. Since $T$ is
consistent, $\lnot \ph$ is not in $T$.

For the other direction, suppose $\lnot \ph$ is not in $T$. By
maxmimality, $T \cup \{ \lnot \ph \}$ is inconsistent. So there is a
proof of $\bot$ from $T$ and $\lnot \ph$. Using RAA, we get a proof of
$\ph$ from $T$. Since $T$ is a theory, $\ph$ is in $T$.

% \item[6.\hfill] Suppose $T$ is a maximally consistent theory.

% For the forwards direction, suppose $\ph \limplies \psi$ is in $T$. If
% $\ph$ is not in $T$, we are done. Otherwise, $\ph$ is in $T$. Since
% $T$ is a theory, $\psi$ is in $T$ as well.

% For the reverse direction, suppose either $\ph$ is not in $T$ or
% $\psi$ is in $T$. In the first case, by problem 6, $\lnot \ph$ is in
% $T$. Since $\ph \limplies \psi$ is derivable from $\lnot \ph$, and $T$
% is a theory, $\ph \limplies \psi$ is in $T$. In the second case, $\psi$
% is in $T$. Since $\ph \limplies \psi$ is derivable from $\psi$ and $T$
% is a theory, $\ph \limplies \psi$ is in $T$. So, in either case, $\ph
% \limplies \psi$ is in $T$.

% \item[9.\hfill] Suppose $\{T_i \; | \; i \in I\}$ is a set of theories
%   linearly ordered by inclusion. This means that for any $T_i$ and
%   $T_j$, either $T_i \subseteq T_j$ or $T_j \subseteq T_i$. If
%   $T_{i_1}, T_{i_2}, \ldots, T_{i_k}$ is any finite set of these
%   theories, by reordering the indices they can be arranged in a
%   sequence of the form
% \[
%   T_{i'_1} \subseteq T_{i'_2} \subseteq \ldots \subseteq T_{i'_k}.
% \]
%   As a result, one of them (in this case $T_{i'_k}$) contains all the
%   others. (More formally, by induction on $k$ show that one of the sets
%   contains all the others.)
%    Let $T$ be the union of the $T_i$. Trivially $T$ contains each
%   $T_i$.  To show that $T$ is a theory, suppose $T \vdash \varphi$.
%   Then there is a proof of $\varphi$ from some hypotheses $\psi_1,
%   \ldots, \psi_k$ in $T$. Since $T$ is the union of the sets $T_i$,
%   for each $l$ the formula $\psi_l$ is in some $T_{i_l}$. By the above
%   we can find $k$ so that all the formulas $\psi_i$ are on $T_{i_k}$.
%   But then $T_{i_k}$ proves $\varphi$. Since $T_{i_k}$ is a theory, it
%   contains $\varphi$.  Since $T_{i_k}$ is a subset of $T$, $T$
%   contains $\varphi$ as well.
 
%   By the same reasoning, if $T$ proves a contradiction, then some
%   $T_i$ proves a contradiction. So if each $T_i$ is consistent, so is
%   $T$.
 
%   Note that this lemma is very similar to parts (ii) and (iv) of Lemma
%   3.1.8. The only difference is that $I$ is an arbitrary set, instead
%   of the natural numbers.
  
% \item[10.\hfill] First, let us suppose $A$ and prove $B$. Suppose
%   $\Gamma$ is any set of sentences and $\ph$ is any sentence, and
%   suppose $\Gamma \not \proves \ph$. Then $\Gamma \cup \{ \lnot \ph
%   \}$ is consistent. By A, it has a model, $\gmdl A$. But then $\gmdl A
%   \models \Gamma$ and $\gmdl A \not \models \ph$, so $\Gamma \not
%   \models \ph$.

% For the other direction, let us suppose $B$ and prove $A$. Suppose
% $\Gamma$ is a set of sentences that has no model. Then $\Gamma
% \models \bot$. By A, $\Gamma \proves \bot$, i.e.\ $\Gamma$ is
% inconsistent.

\item[11.\hfill] Suppose $T_1$ is a conservative extension of $T_2$,
  and $T_2$ is a conservative extension of $T_3$. I need to show that
  $T_1$ is a conservative extension of $T_3$. In other words, I need
  to show that if $\ph$ is any sentence in $L_3$, then $\ph$ is in
  $T_1$ if and only if it is in $T_3$.
  
  Since $T_1$ contains $T_2$ and $T_2$ contains $T_3$, it is clear
  that every sentence $\ph$ in $T_3$ is in $T_1$. For the other
  direction, suppose $\ph$ is some sentence in the language $L_3$ that
  is in $T_1$. Since $L_3$ is a smaller language than $L_2$, $\ph$ is
  also a sentence in $L_2$. Since $T_1$ is a conservative extension of
  $T_2$, $\ph$ is in $T_2$. And since $T_2$ is a conservative
  extension of $T_3$, then $\ph$ is in $T_3$, as required.

\item[13.\hfill]
\begin{list2}
\item Let $f(x) = 1-x$. This is an isomorphism of the two structures,
  as follows. {\em $f$ is injective:} if $1-x = 1-y$ then $x=y$. {\em
    $f$ is surjective:} Given any $z$ in $(0,1)$, $z = f(1-z)$. {\em
    $f$ is an isomorphism:} If $a < b$ then $1-a > 1-b$.
\item Let $f(x) = x/(1-x)$. {\em $f$ is injective:} if $x/(1-x) =
  y/(1-y)$, then (cross multiplying) we have $x-xy = y-xy$ and so
  $x=y$. {\em $f$ is surjective:} if $z$ is any positive real number, let
  $x = z/(1+z)$. Then $x$ is an element of $(0,1)$, and it is easy to
  check that $f(x) = z$. {\em $f$ is an isomorphism:} Assuming $x$ and
  $y$ are in $(0,1)$, $1-x$ and $1-y$ are both positive. So we have
  $x/(1-x) < y/(1-y)$ iff $x-xy < y - xy$ iff $x < y$.
\item $[0,1]$ satisfies ``there is a smallest element,'' $\ex x \fa y
  (x \leq y)$, while $(0,1)$ does not.
\end{list2}

\item[14.\hfill] 
\begin{list2}
\item The structure $\mdl B$ in the problem mentioned ordered the
  natural numbers so that all the even numbers come first, followed by
  the odd numbers:
\[
0,2,4,6,\ldots,1,3,5,7,9\ldots
\]
Let $X$ be any nonempty subset of the universe of $\mdl B$. If $X$
has any even numbers, take the smallest even number in $X$, under the
usual ordering on $\mathbb N$; this is the least element of $X$ in the
ordering on $\mdl B$. Otherwise, if there are no even numbers in $X$,
there is at least one odd number in $X$. In that case, the smallest
odd number in $X$, under the usual ordering on $\mathbb N$, is the
least element of $X$ in the ordering on $\mdl B$.

\item Let $\Gamma$ be a set of sentences, such that every
well-ordering is a model of $\Gamma$. Using compactness, I will show
that there is a structure that is {\em not} a well-ordering, but is
also a model of $\Gamma$.

Add constants $c_0, c_1, c_2, \ldots$ to the language. Let $\Gamma'$
be the set of sentences
\[
\Gamma \cup \{ c_1 < c_0, c_2 < c_1, c_3 < c_2, \ldots \}.
\]
I claim that every finite subset of $\Gamma'$ is consistent. Let
$\Delta$ be any such finite subset, and notice that for some $n$,
$\Delta$ is a subset of
\[
\Gamma \cup \{ c_1 < c_0, c_2 < c_1, c_3 < c_2, \ldots, c_n < c_{n-1}
\}.
\]
In other words, only finitely many of the sentences $c_{i+1} < c_i$
can be in $\Delta$. Since $\la \mathbb{N}, < \ra$ is a model of
$\Gamma$, the structure
\[
\la \mathbb{N}, <, n, n-1, n-2, \ldots, 3, 2, 1, 0, 0, 0, 0 \ldots \ra
\]
is a model of $\Delta$ (that is, the structure that assigns $n$ to
$c_0$, $n-1$ to $c_1$, and so on). Note that the constants from
$c_{n+1}$ don't appear in $\Delta$, so we can just assign 0 to them.

Since every finite subset of $\Gamma'$ has a model, $\Gamma'$ also has
a model $\mathcal{A'}$ (in the language with the new constants). Let
$\mathcal{A}$ be the reduct of $\Gamma'$ to the original
language. Then $\mathcal{A}$ is a model of $\Gamma$, but $\mathcal{A}$
has elements $a_0, a_1, a_2, \ldots$ such that $a_1 < a_0$, $a_2 <
a_1$, and so on. Then the set 
\[
\{ a_0, a_1, a_2, \ldots, \}
\]
doesn't have a least element, so $\mathcal{A}$ is not a well-ordering.
\end{list2}

\end{list1}

\end{document}