\documentclass[12pt]{amsart}
\usepackage{amsmath, amsthm, amssymb, amsfonts}
\usepackage{enumerate}
\usepackage{verbatim}
%\numberwithin{equation}{section}

%%%Document Configuration
\pagestyle{headings}
%\addtolength{\topmargin}{-.5in}
\textwidth = 6in 
\oddsidemargin = .25in
\evensidemargin = .25in
\voffset = -1in
\textheight = 9.5 in
%\textwidth = 6in
%\parindent = 0in
%\headsep = 0in
\relpenalty = 9999
\binoppenalty = 9999
%linespacing
\renewcommand{\baselinestretch}{1.25}
\reversemarginpar     
%%%

%%%Theorem Configuration
\theoremstyle{plain}
\newtheorem*{main}{Main~Theorem}
\newtheorem{thm}{Theorem}[section]
\newtheorem{cor}[thm]{Corollary}
\newtheorem{exer}[thm]{Exercise}
\newtheorem{fact}[thm]{Fact}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{prop}[thm]{Proposition}
\newtheorem{remark}[thm]{Remark}
\newtheorem{hw}[section]{}
%\newtheorem{hw}[section]{HW}
\newtheorem{dfn}{Definition}[section]
%%%

%%%Bibliography Configuration
\bibliographystyle{plain}
%%%

%%%semantic definitions
\DeclareMathOperator*{\Aut}{Aut}
\DeclareMathOperator*{\Dom}{Dom}
\DeclareMathOperator*{\Mod}{Mod}
\DeclareMathOperator*{\Th}{Th}
\DeclareMathOperator*{\tp}{tp}
\renewcommand{\div}{\mid}
\renewcommand{\emptyset}{\varnothing}
\renewcommand{\implies}{\Rightarrow}
\renewcommand{\natural}{\mathbb{N}}
\newcommand{\Acl}[1]{\obar{#1}}
\newcommand{\assign}{\leftarrow}
\newcommand{\caseif}{\Rightarrow}
\newcommand{\caseonlyif}{\Leftarrow}
\newcommand{\cantprove}{\nvdash}
\newcommand{\complex}{\mathbb{C}}
\newcommand{\field}{\mathbb{F}}
\newcommand{\minus}{\setminus}
\newcommand{\power}[1]{{\mathcal{P}}({#1})}
\newcommand{\nonnegative}{\mathbb{N}}
\newcommand{\integer}{\mathbb{Z}}
\newcommand{\intersect}{\cap}
\newcommand{\isomorphic}{\simeq}
\newcommand{\obar}[1]{\overline{#1}}
\newcommand{\proves}{\vdash}
\newcommand{\rational}{\mathbb{Q}}
\newcommand{\real}{\mathbb{R}}
\newcommand{\union}{\cup}
\newcommand{\units}[1]{{\left(#1\right)}^{\times}}
%%%

%%%local definitions
\newcommand{\eleq}{\equiv}
\newcommand{\elleq}{\preccurlyeq}
\newcommand{\lang}[1]{{\mathcal{#1}}}
\newcommand{\Los}{{\L o\'s}}
\newcommand{\LS}{{L\"{o}wenheim-Skolem }}
\newcommand{\mathscr}[1]{{\mathcal{#1}}}
\newcommand{\st}[1]{{\mathcal{#1}}}
\newcommand{\structure}[1]{{\mathcal{#1}}}
\newcommand{\struct}[1]{\left\langle#1\right\rangle}
\newcommand{\symAnd}{\mathop{\bigwedge}}
\newcommand{\symand}{\wedge}
\newcommand{\symimply}{\rightarrow}
\newcommand{\symiff}{\leftrightarrow}
\newcommand{\symnot}{\neg}
\newcommand{\symor}{\vee}
\newcommand{\WFF}{well-formed formula}
\newcommand{\0}{\textbf{0}}
\newcommand{\suc}{\textbf{S}}
\newcommand{\A}{\mathfrak{A}}
\newcommand{\B}{\mathfrak{B}}
\newcommand{\D}{\mathcal{D}}
\newcommand{\F}{\mathcal{F}}
\newcommand{\NNN}{\mathfrak{N}}
\newcommand{\E}{\textbf{E}}
\newcommand{\Cn}{\textrm{Cn}}
\newcommand{\res}{\upharpoonright}
%%%

\begin{document}

\title{Model Theory II Homework 4}
%\date{April 27, 2007}
\maketitle

\setcounter{section}{8}

\begin{hw}
Let $(\st{N},\st{M})$ be an elementary pair
of $L$-structures with predicate $P$
such that $\st{N} \isomorphic \st{M}$
and $f$ a unary function symbol specifying the isomorphism.
The statement ``$f$ is an isomorphism between $\st{N}$ and $\st{M}$''
is a first-order statement.
\end{hw}

\begin{proof}
Since $f$ is an isomorphism, it is injective, surjective and a homomorphism.
These can be said as follows:
\begin{itemize}
\item Injective: $I_{x,y} = (f(x) = f(y) \symimply x = y)$
%\item Surjective: $\forall y \in \st{M} \exists x \in \st{N} f(x)=y$
\item Surjective: $S_{y} = (P(y) \symimply \exists x (f(x)=y))$.
\item Homomorphism: $H_{x,y,g}$ = $f(g(x,y)) = g(f(x),f(y))$.
\end{itemize}
Thus
\[
T =
\{\symnot \exists (x,y) \symnot I{x,y}\}
\union \{\symnot \exists y \symnot S_{y}\}
\union \{\symnot \exists (x,y) \symnot H_{x,y,g} |
g \text{ is a function symbol in } L\}
\]

is a first-order axiomatization of the statement
``$f$ is an isomorphism between $\st{N}$ and $\st{M}$.''
\end{proof}

\begin{lem}[Lemma 12 (i)]
Every countable theory $T$ has a countable homogeneous model.
\end{lem}

\begin{lem}[Lemma 15]
Let $L$ be countable.
Then every elementary pair is elementarily quivalent to some
$(\st{N},\st{M})$ where $\st{N} \isomorphic \st{M}$,
and both $\st{N}$ and $\st{M}$ are countable and homogeneous.
\end{lem}

\begin{hw}
Check the $\omega$-homogeneity of $\st{M}''$ and $\st{N}''$
in the last sentence of the proof of Lemma 15.
\end{hw}

\begin{proof}
Note that $T = \Th(\st{N},\st{M})$ is a countable theory.
In the proof, $(\st{N}',\st{M}')$ is an arbitrary elementary pair
of models of $T$.
The first conclusion of Lemma 12 ensures
the existence of a homogeneous model of $T$
In particular we have that
$(\st{N}'',\st{M}'',f'') \equiv (\st{N'},\st{M'},f)$
is a countable, homogeneous elementary pair in $L(P'',f'')$,
but homogeneity is preserved in reducts, in particular in $L$.
Therefore $\st{N''}$ is countable and homogenous,
and $\st{M''} \preceq \st{N''}$ is as well.
\end{proof}

\end{document}
