%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
%%   LAST REVISION 4/05/2000

\documentclass[psamsfonts, 11pt]{amsart}                    

\usepackage{amssymb, enumerate}


%%%%%%%%%% proclamations %%%%%%%%%%%%%%%%%%%%%%%%%%%%

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{subclaim}[theorem]{Subclaim}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{claim}[theorem]{Claim}
\newtheorem{question}[theorem]{Question}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{remark}[theorem]{Remark}

\theoremstyle{remark}


%%%%%%%%%% definitions%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\newcommand{\cf}{\operatorname{cf}}
\newcommand{\ec}{\operatorname{EC}}
\newcommand{\dom}{\operatorname{dom}}
\def\rge{\operatorname{rge}}
\newcommand{\tp}{\operatorname{tp}}
\newcommand{\Min}{\operatorname{Min}}
\newcommand{\conc}{\Hat{\ }}
\newcommand{\aut}[1]{\operatorname{Aut}_{#1}(\mathfrak{C})}
\newcommand{\sq}[2]{\sideset{^{#1}}{}{\operatorname{#2}}}
\newcommand{\av}{\operatorname{Av}}
\newcommand{\con}{\operatorname{Con}}

\renewcommand{\qedsymbol}{\ensuremath{\dashv}}
\renewcommand{\phi}{\varphi}
\renewcommand{\labelitemi}{$\cdot$}
\renewcommand{\labelenumi}{(\theenumi)}
\renewcommand{\labelenumiii}{(\theenumiii)}
\newcommand{\Union}{\bigcup}
\newcommand{\initial}\lessdot
 \newcommand{\infinity}{\infty}
\def\x{\mathbf{x}}
\def\y{\mathbf{y}}
\def\z{\mathbf{z}}
\def\a{\mathbf{a}}
\def\b{\mathbf{b}}
\def\c{\mathbf{c}}


%%%%%%%%%%a list environment with empty label %%%%%%%%%%

\newenvironment{nolabels}
{\begin{list}{}{\leftmargin 15pt}}
{\end{list}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%



\begin{document}

\begin{lemma}
Suppose $\theta (\x;\a)$ is $\Delta$-stable, where $\Delta $ 
is closed under Boolean operations. Suppose 
$\lambda \ge \aleph _1$. Then 
$Deg[\theta (\x;\a), \Delta, \lambda]=
 D[\theta (\x;\a), \Delta, \lambda]$.
\end{lemma}

\begin{proof}
The non-trivial part is to show that for all $\alpha $
$$
D[\theta (\x;\a), \Delta, \lambda]\geq \alpha \quad\textrm{implies}
\quad Deg[\theta (\x;\a), \Delta, \lambda]\geq \alpha.
$$
We prove that by induction on $\alpha$. The base case $\alpha=0$ and 
the limit steps follow by definition. 

Suppose 
$D[\theta (\x;\a), \Delta, \lambda]\geq \alpha+1$ for $\alpha \ge 0$.
By the definition, for all $\aleph _0\le \mu<\lambda $, $\mu$ limit, 
there is a formula $\phi(\x;\c)$ with
$\models \phi(\x;\c)\to \theta(\x;\a)$, there are $\psi \in \Delta$ and
$\{\a_i \mid i<\mu\}$ such that for some $n<\omega$
\begin{enumerate}
\item $D[\phi(\x;\c)\land \psi(\x;\a_i),\Delta,\lambda]\ge\alpha$ and
\item $\{\psi (\x;\a_i)\mid i<\mu\}$ is $n$-contradictory over 
$\phi(\x;\c)$.
\end{enumerate}

By monotonicity for the $D$-rank and the induction hypothesis, 
$$Deg[\theta(\x;\a)\land \psi (\x;\a_i), \Delta,\lambda]\ge
\alpha\quad\text{for all }i<\mu.$$
 If $\{\psi (\x;\a_i)\mid i<\mu\}$ is
$k$-contradictory over 
$\theta(\x;\a)$ for some $k<\omega$, then we are done. Otherwise,
the set $\{\theta(\x;\a)\}\cup \{\psi (\x;\a_i)\mid i<\omega\}$  is
consistent. Since $\{\psi (\x;\a_i)\mid i<\mu\}$ is 
$n$-contradictory over $\phi(\x;\c)$, we have 
$$\models \phi(\x;\c)\to \phi(\x;\c)\land 
 \lnot\bigwedge_{j<n} \psi(\x;\a_j).$$
Hence $D[\phi(\x;\c)\land \lnot[\bigwedge_{j<n} \psi(\x;\a_j)]
 \land \psi(\x;\a_i),\Delta,\lambda ]\ge \alpha$ for $i<\mu$.
By the Ultrametric property for the $D$-rank and the pigeon-hole 
principle, we may assume that 
$$
D[\phi(\x;\c)\land \lnot \psi(\x;\a_0)\land \psi(\x;\a_i),
 \Delta,\lambda] \ge \alpha \ \textrm{for } 1\le i<\mu. \qquad (*_0)
$$
By monotonicity for the $D$-rank and the induction hypothesis, 
$$Deg[\theta(\x;\a)\land \lnot \psi(\x;\a_0)\land \psi (\x;\a_i), 
 \Delta,\lambda]\ge \alpha \text{ for }1\le i<\mu.$$
If $\{\psi (\x;\a_i)\mid 1\le i<\mu\}$ is $k$-contradictory over 
$\theta(\x;\a)\land \lnot \psi(\x;\a_0)$
for some $k<\omega$, then we are done.\\
 Otherwise, 
$\{\theta(\x;\a)\land \lnot \psi(\x;\a_0)\}
  \cup \{\psi (\x;\a_i)\mid 1\le i<\omega\}$ is consistent.
Now we replace $\phi(\x;\c)$ in $(*_0)$ by 
$\phi(\x;\c)\land \lnot\bigwedge_{1\le i<n+1} \psi(\x;\a_i)$, and get
as above
$$
D[\phi(\x;\c)\land \lnot \psi(\x;\a_0)\land \lnot \psi(\x;\a_1)\land 
 \psi(\x;\a_i),\Delta,\lambda]\ge \alpha \ \textrm{for } 2\le i<\mu. 
\qquad (*_1)
$$

Repeat this process.

\begin{subclaim}
The above process terminates in finitely many steps, i.e., there is
$l<\omega$ and a sequence $\{\a_i\mid i<\mu \}$ such that
$$
D[\phi(\x;\c)\land \bigwedge_{j\le l}\lnot \psi(\x;\a_j)\land 
 \psi(\x;\a_i),\Delta,\lambda]\ge \alpha \ \text{for } l+1\le i<\mu. 
\qquad (*_l)
$$
and $\{\psi(\x;\a_i)\mid l+1\le i<\mu \}$ are $k$-contradictory over
$\theta(\x;\a)$ for some $k$.
\end{subclaim}

\begin{proof}
Since $\theta$ is $\Delta$-stable, the formula $\psi \in \Delta$ does 
not have the order property over $\theta(\x;\a)$. Let $N<\omega $ 
witnes failure of the order property for $\psi$. We claim that the 
above process terminates after at most $N$ steps. Indeed, otherwise 
we would have a sequence $\{\a_i\mid i<\mu\}$ such that 
$$
\models\exists\x[ \theta(\x;\a)\land 
 \bigwedge_{j\le l }\lnot \psi(\x;\a_j)\land 
 \bigwedge _{l<i<N}\psi(\x;\a_i)] \textrm{ for all
} l<N,
$$
which contradicts the choice of $N$.
\end{proof}

Let $\{\a_i\mid i<\mu \}$, $l<\omega$ and $k$ be as in the subclaim, let
$$\bar \psi (\x;\y_0,\dots,\y_l,\y_{l+1}):=
 \bigwedge_{j\le l }\lnot \psi(\x;\y_j)\land \psi(\x;\y_{l+1}),$$
and let $\b_i:=\a_0\conc \a_1\conc \dots \conc \a_l\conc \a_{l+1+i}$ for
$i<\mu$. Since $\Delta $ is closed under Boolean operations, 
$\bar\psi\in \Delta$. By $(*_l)$, monotonicity and induction hypothesis
$Deg[\theta(\x;\a)\land \bar\psi(\x;\b_i),\Delta,\lambda]\ge \alpha$,
and clearly $\{\bar\psi(\x;\b_i)\mid i<\mu \}$ is $k$-contradictory over
$\theta(\x;\a)$. Thus, $Deg[\theta(\x;\a),\Delta,\lambda]\ge \alpha+1$.
\end{proof}



\end{document}



