\documentclass[11pt]{article}

\usepackage{homework,amssymb,eufrak}

\begin{document}

\soltitle{13}{Thursday, December 4}

\begin{list1} 

% \item[3.\hfill] This is just the contrapositive to Lemma 3.2.6.

\item[4.\hfill] Suppose $Mod(T_1 \cup T_2) = \emptyset$. By
  compactness, there is a finite subset of $T_1 \cup T_2$ that has no
  model.  In other words, there is a set $\{\varphi_1, \ldots,
  \varphi_k\}$ of sentences in $T_1$, and another set $\{ \psi_1,
  \ldots, \psi_l \}$ of sentences in $T_2$, such that $\{ \varphi_1,
  \ldots, \varphi_k, \psi_1, \ldots, \psi_l\}$ has no model.
  
  Let $\sigma = \varphi_1 \land \ldots \land \varphi_k$. Since each
  $\varphi_i$ is in $T_1$, it is easy to see that $T_1 \models
  \sigma$.  But any structure that satisfies $T_2$ has to satisfy
  $\{\psi_1, \ldots, \psi_l\}$, so it can't satisfy all of the
  $\varphi_i$'s. So $T_2 \models \lnot \sigma$.
  
\item[5.\hfill] Suppose $T_1 \neq T_2$. Then there is a sentence that
  is in one but not the other. Without loss of generality, suppose
  $\ph$ is a sentence in $T_1$ but not $T_2$. Since $T_2$ is a theory,
  $T_2 \not \proves \ph$, and so $T_2 \cup \{ \lnot \ph \}$ is
  consistent.

Let $\mdl A$ be a model of $T_2 \cup \{ \lnot \ph \}$. Since $\mdl A
\models \lnot \ph$, $\mdl A$ is a model of $T_2$ but not $T_1$.

\item[8.\hfill] 
\begin{list2}
\item It is easy to verify that the map $f(x) = x+1$ is an
isomorphism.
\item By Lemma 3.3.3, any two isomorphic structures are elementarily
equivalent.
\item Clearly $|\mathcal{A}| \subseteq |\mathcal{B}|$, and the ordering is
the same on both universes.
\item $\mathcal{A} \models \ex x (x< \bar 1)$, but not $\mathcal{B}$.
\end{list2}

\item[10.\hfill] It is easy to verify that $f(x) = 2x$ is an
  automorphism of this structure. But $1 \times 1 = 1$, while 
\[
f(1) \times f(1) = 2 \times 2 = 4 \neq f(1).
\]

\item[13.\hfill] Here is the algorithm: on input $\ph$, in parallel
  look for a proof of $\ph$ and a proof of $\lnot \ph$ from the axioms
  of $T$. Since $T$ is complete, you are bound to find one or the
  other. If it is a proof of $\ph$, answer ``yes,'' $\ph \in T$;
  otherwise, answer ``no,'' $\ph \not \in T$.

\item[15.\hfill] I cancelled this question because we did not cover
  second-order logic in time. But just FYI, note that being
  well ordered is naturally a second-order property, since we can use
  a second-order variable to range over subsets:
\[
\forall S (\ex x S(x) \limplies \ex x (S(x) \land \fa y (y < x
\limplies \lnot S(y)))).
\]

\end{list1}

\end{document}