\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 3}
%\date{April 27, 2007}
\maketitle

\setcounter{section}{5}

\begin{hw}[Rothmaler 12.1.7]
Suppose $\st{M}$ is $\kappa$-saturated,
$A \subset M$ with $|A| < \kappa$ and
$n > 1$ is a natural number.
Prove that all $n$-types of $\st{M}$ over $A$ are realized in $\st{M}$.
\end{hw}

\begin{proof}
Assume $|A| < \kappa$ and
all $(n-1)$-types of $\st{M}$ over $A$ are realized in $\st{M}$.
If $p \in S_n(A)$ then
\[
p = \left\{ \varphi(\obar{v}) \Big|
|\obar{v}|=n \text{ and } \st{M} \models \varphi(\obar{v})\right\}.
\]
Let $\obar{v} = \{v_i\}_{i=1}^n$ and define
\[
q = \left\{\exists v_n \varphi(v_n) \Big| \varphi \in p \right\}.
\]
Note that $q$ is a consistent set of $L_{n-1}$ formulas.
If $\varphi \in L_{n-1}, \symnot\varphi \not \in q$ and $\varphi \not \in q$
then neither $\exists v_n \varphi(v_n)$ nor $\exists v_n \symnot\varphi(v_n)$
(which is logically equivalent to
$\symnot \exists v_n \varphi(v_n) \in q$) are in $p$.
This contradicts the completeness of $p$.
Therefore $q \in S_{n-1}(A)$ and is realized in $\st{M}$ by,
say, $m_q \in M^{n-1}$ according to the induction hypothesis.
If $m_q$ realizes $p$ then the proof is finished.
If $m \in M^n$ is not a realization of $p$
then there is a formula $\varphi(\obar{v}) \in p$
such that $\st{M} \models \symnot\varphi(m)$.
Then define
\[
p' = \left\{\varphi(m,v) \in L_1 \Big|
\varphi(\obar{v})\in p \text{ and } |\obar{v}|=n \right\}.
\]
If $\varphi \in L_1, \varphi(v_n) \not \in p'$
and $\symnot\varphi(v_n) \not \in p'$
then $\varphi(m,v_n) \not \in p$ and $\symnot\varphi(m,v_n) \not \in p$
which contradicts the completeness of $p$.
Therefore $p'$ is complete, hence $p' \in S_1(A)$ is realized by
$m_{p'} \in \st{M}$ by the saturation of $\st{M}$.
Thus $m = m_{q}\union m_{p'}$ is a realization of $p$,
and the result follows.
\begin{comment}
Let $\st{N}$ be a model where $\st{M} \prec \st{N}$ and $p$ is realized
By the consistency of $p$,
for each $\varphi$ there exists a tuple $m_\varphi \in M$
such that $m_\varphi$ is a witness of $\varphi$, that is,
$\st{M} \models \varphi(m_\varphi)$.
Therefore for all $\varphi \in p$ and tuples $\obar{v}$
such that $|\obar{v}|<n,
p \models \exists \obar{v}\varphi(\obar{v})$.
Further
$\Phi = \{\exists \obar{v}\varphi(\obar{v}) | \varphi \in p\} \subset p$
is consistent, and therefore $\st{M}\models \Phi$,
in particular $\Phi[\st{M}]$ is nonempty. 
The conclusion holds if one of these elements is a realization of $p$.
If no $m \in \Phi[\st{M}]$ is realized
then for all $\varphi \in p$  $p \models \symnot\exists\varphi(m,x)$
\end{comment}
\end{proof}

\begin{hw}
If $\st{M}$ is a homogeneous structure
then every partial elementary map $f:\st{M}\to\st{M}$
where $|\!\Dom(f)| < |M|$
can be extended to an $F \in \Aut(\st{M})$.
\end{hw}
\begin{proof}
Let $A = \Dom(f)$ and $B = f[\st{M}]$.
Let $|A| = \kappa < |\st{M}|$.
Then well-order $A$ and $B$ as
$A = \{a_i\}_{i<\kappa}$ and
$B = \{b_i = f(a_i)\}_{i<\kappa}$, respectively.
This gives rise to an elementary chain $\{\st{M}_i\}_{i < \kappa}$ such that
\[
\st{M}(A) = \st{M}_0 \prec \st{M}_1 \prec \cdots
\prec \st{M}_i \prec \cdots
\]
By homogeneity $f$ can be extended
by picking $a_{\kappa+1} \in M \minus A$
and finding $b_{\kappa+1} \in M$ such that $\tp(a/A) = \tp(b/B)$.

Therefore by the elementary chain lemma
$\st{M}_{\kappa^+} = \union_{i<\kappa^+} \st{M}_i \prec \st{M}$.
This argument works for every $\kappa < \st{M}$, and therefore
if $\kappa$ is such that $\kappa^+ = |\st{M}|$
we have that $\st{M}_{\kappa^+} = \st{M}$.
Otherwise, one can form another elementary chain indexed by all $\kappa < \st{M}$,
and the union of these will be $\st{M}$.
Further, this model is defined as the image of $F$, the extension of $f$.
Hence $F$ is a (total) elementary map such that $F(A) = f(A)$.
Therefore $F \in \Aut(\st{M})$ is an automorphism of $\st{M}$ extending $f$.
\end{proof}
\end{document}
