\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{\subst}{\preceq}
\newcommand{\symAnd}{\mathop{\bigwedge}}
\newcommand{\symand}{\wedge}
\newcommand{\symimply}{\rightarrow}
\newcommand{\symiff}{\leftrightarrow}
\newcommand{\symnot}{\neg}
\newcommand{\symor}{\vee}
\newcommand{\tuple}[1]{\obar{#1}}
\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 6}
\author{Dakota Blair}
\maketitle

\setcounter{section}{12}

\begin{hw}
Prove the following are equivalent for an $L$-theory $T$:
\begin{enumerate}
\item The quantifier $Q_\alpha$ may be eliminated in $T_\alpha$
for some $\alpha > 0$. \label{r.13.elimin}
\item The theory $T$ has no Vaughtian Pairs. \label{r.13.nvp}
\item For each formula $\varphi(x,\tuple{y}) \in L$
there exists a $n_\varphi$ such that\\
$T_\alpha \models \forall \tuple{y}
\left(\exists^{\geq n_\varphi} x \varphi(x,\tuple{y})
\symimply Q_\alpha x \varphi(x, \tuple{y})\right)$. \label{r.13.uniform}
\end{enumerate}
\end{hw}

\begin{proof}
$(\ref{r.13.elimin} \implies \ref{r.13.uniform})$
Consider the contrapositive.
If there is no uniform bound $n_\varphi$
for a formula $\varphi(x,y)$, then
\[
\left\{ \symnot Q_\alpha x\varphi(x,y) \right\} \union
\left\{ \exists^{\geq n}x\varphi(x,y) \big| n < \omega \right\}
\]
is finitely consistent, and hence by compactness consistent.
Therefore $Q_\alpha$ may not be eliminated in $T_\alpha$ in this circumstance.

$(\ref{r.13.uniform} \implies \ref{r.13.elimin})$
This follows trivially from the definition of $Q_\alpha$.

$(\ref{r.13.elimin} \implies \ref{r.13.nvp})$
Again proceed by proving the contrapositive.
By Vaught's two-cardinal theorem, if $T$ has a Vaughtian pair,
it has an $(\aleph_1,\aleph_0)$ model, say $(\st{N}_1,\st{M}_0)$.
By \LS we can find $\st{N}_\alpha \eleq \st{N}_1$
such that $|\st{N}_\alpha| = \aleph_\alpha$ and $\st{M}_0\subset\st{N}_\alpha$,
so using isomorphic correction
we may construct an $(\aleph_\alpha, \aleph_0)$ model of $T$.
Let $(\st{N},\st{M})$ be an $(\aleph_\alpha, \aleph_0)$ Vaughtian pair such that
$(\st{N},\st{M}) \models T$.
Then there exists a formula $\varphi$ such that
$\varphi(\st{M})$ is infinite and $\varphi(\st{M}) = \varphi(\st{N})$.
Therefore $\varphi(\st{M}) \subset \st{M}$ and is hence countable,
so $\aleph_\alpha$ may not be eliminated.

$(\ref{r.13.nvp} \implies \ref{r.13.uniform})$
This follows from the proof of Lemma 20(i)
by replacing countable with $\aleph_\alpha$ and uncountable
by $> \aleph_\alpha$, again proceeding by the contrapositive.
If there are no uniform bounds, then one can
construct a structure for any $n < \omega$, say $\st{N}_n$,
such that $\st{N}_n \models T$
and there exists $\varphi(x,\tuple{y}), \tuple{a_n} \in \st{N}_n$
such that $n < \left| \varphi(\st{N}_n, \tuple{a_n}) \right| < \omega$.
Further one may take $|\st{N}_n| > \aleph_\alpha$
as if the original choice is not large enough,
by \LS we may take an elementary extension $\st{N}_n'$
where $|\st{N}_n| > \aleph_\alpha$
and $\varphi(\st{N}_n, \tuple{a_n}) = \varphi(\st{N}_n', \tuple{a_n})$.
Now take $\st{M}_n$ such that
$\varphi(\st{N}_n, \tuple{a_n}) \union \tuple{a_n} \subset M_n$,
$|\st{M}_n| = \aleph_\alpha$ and $\st{M}_n \subst \st{N}_n$.
Then $\st{M}_n$ and $\st{N}_n$ form an elementary chain, so define
$\st{M} = \union_{n<\omega} \st{M}_n$ and 
$\st{N} = \union_{n<\omega} \st{N}_n$.
Therefore $(\st{N},\st{M})$ in $L(P)$ forms an elementary pair.
\pagebreak
But here we may construct
\begin{align*}
T_P = & \{
\exists \tuple{y}(
 \forall x(\varphi(x,\tuple{c}) \symimply P(x))
 \symand P(\tuple{c})
)\} \union
\{ \text{Tarski-Vaught for } P(\st{N}) \subst \st{N} \} \\
& \union \{ \forall \tuple{y}(
 (P(\tuple{y}) \symand \exists x \psi(x,\tuple{y})) \symimply
 \exists x P(x) \symand \psi(x,\tuple{y})
)\}.
\end{align*}
Hence if $\tuple{a}$ is a realization of $T_P$
then $\st{M} \subst \st{N}$ and $\varphi(\st{N},\tuple{a}) \subset M$.
Therefore we may consider the theory
\[
T_P' = T_P \union \{ \exists^{\geq n} x \varphi(x,\tuple{c}) | n < \omega \}
\]
which is finitely consistent since
$(\st{N}_n, \st{M}_n, \tuple{a_n}) \models T_P'$.
But every model of this theory is a Vaughtian pair.
Therefore if a theory has no uniform bounds then it has Vaughtian pairs.
Hence no Vaughtian pairs implies that the theory admits uniform bounds.
\end{proof}

\begin{hw}
If $Q_1$ may be eliminated in a complete theory $T$, then so is $Q_0$.
\end{hw}

\begin{proof}
Since $Q_1$ may be eliminated, $T$ has uniform bounds.
Then $T$ has no Vaughtian pairs and hence no $2$-cardinal models.
Thus any formula $\varphi(x)$ such that
$|\varphi(\st{M})| \geq \aleph_0$
is consistent with $Q_\alpha x \varphi(x)$.
Hence $|\varphi(\st{M})| = \aleph_\alpha$.
Therefore the same uniform bound that implies $Q_\alpha x \varphi(x)$
implies $Q_0 x \varphi(x)$.
Hence $Q_0$ may be eliminated in $T$.
\end{proof}

\end{document}
