% AUTOGENERATED FILE; you probably want to edit the .tex.in file, not this.
\documentclass[a4paper]{article}
\pagestyle{headings}
\usepackage{amssymb,amsmath,enumerate,amsthm,url}
\usepackage[all,cmtip]{xy}
\usepackage{graphicx}
\usepackage[numbers]{natbib}
\usepackage{bibentry}
\providecommand{\Dashv}{\mathrel{\text{\reflectbox{$\vDash$}}}}
\providecommand{\eqnref}[1]{(\ref{e:#1})}
\providecommand{\secref}[1]{\S\ref{s:#1}}
\bibliographystyle{alpha}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}{Lemma}
\newtheorem*{lemma*}{Lemma}
\newtheorem{proposition}{Proposition}
\newtheorem{conjecture}{Conjecture}
\newtheorem{fact}{Fact}
\newtheorem*{fact*}{Fact}
\newtheorem{corollary}{Corollary}
\newtheorem*{corollary*}{Corollary}
\newtheorem{claim}{Claim}
\newtheorem*{claim*}{Claim}
\theoremstyle{definition}
\newtheorem{definition}{Definition}
\newtheorem*{definition*}{Definition}
\newtheorem{notation}{Notation}
\newtheorem*{notation*}{Notation}
\theoremstyle{remark}
\newtheorem{remark}{Remark}
\newtheorem*{remark*}{Remark}
\newtheorem{example}{Example}
\newtheorem*{example*}{Example}
\newtheorem{note}{Note}
\newtheorem*{note*}{Note}
\newtheorem{question}{Question}
\newtheorem*{question*}{Question}
\begin{document}
\providecommand{\G}{\mathcal{G}}
\providecommand{\U}{\mathcal{U}}
\providecommand{\ftup}{\overline{f}}
\providecommand{\gtup}{\overline{g}}
\providecommand{\cf}{\operatorname{cf}}
\providecommand{\dom}{\operatorname{dom}}
\providecommand{\fin}{\operatorname{fin}}
\providecommand{\lcf}{\operatorname{lcf}}
\providecommand{\FI}{\operatorname{FI}}

\providecommand{\ns}{{ }^*}
\providecommand{\powerset}{\mathcal{P}}
\newcommand{\bv}[1]{ [[{ #1 }]] }

{\it Notes from a seminar on the Keisler order; primarily an exposition of the 
proof of VI.3.12 in Shelah ``Classification Theory''}

\subsection{Statements}

\begin{definition*}
  For $\U$ an ultrafilter on $\lambda$,
  \[ \mu(\U) := \min_{\alpha \in \omega^\U \setminus \omega} \left|{\{ \beta \in \omega^\U 
  : \beta < \alpha \}}\right| ,\]
  \[ \lcf(\U) := \min \{ |A| : A \subseteq  \omega^\U \setminus \omega,\; \forall \beta \in 
  \omega^\U \setminus \omega.\; \exists \alpha \in A.\; \alpha < \beta \} .\]

  %(Note: cardinality here is in the ordinary standard sense -- we do not work 
  %in a non-standard model of set theory!)
\end{definition*}

\begin{fact*}
  \begin{enumerate}[(i)]\item The nfcp theories form the minimal class in the Keisler order.
  \item Let $T$ be a countable stable fcp theory.
  Then a regular ultrafilter $\U$ on $\lambda\geq \aleph_0$ saturates $T$ iff 
  $\mu(\U) > \lambda$.
  \end{enumerate}
\end{fact*}

\begin{theorem}[Shelah VI.4.8]
  \label{t:lcfNonSat}
  Let $T$ be a countable unstable theory.
  Let $\U$ be a regular ultrafilter on $\lambda\geq \aleph_0$ with $\lcf(\U) \leq  
  \lambda$. Then $\U$ does not saturate $T$.
\end{theorem}

\begin{theorem}[Shelah VI.3.12]
  \label{t:lcfuf}
  For any $\lambda \geq  \aleph_0$, there is a regular ultrafilter $\U$ on 
  $\lambda$ with
  \[ \lcf(\U) \leq  \alpha_1,\; \mu(\U) > \lambda .\]
\end{theorem}

\begin{corollary*}
  If $T_1$ is stable and $T_2$ is unstable, then $T_1 < T_2$ in the Keisler 
  order.
\end{corollary*}
\begin{proof}
  If $T_1$ is nfcp, we are done by the minimality of nfcp and the fact that 
  nfcp $\Rightarrow $ stable. So suppose $T_1$ is stable fcp.

  By Theorem~\ref{t:lcfuf}, there is a regular ultrafilter $\U$ on $\lambda := 
  \aleph_1$ such that
  \begin{itemize}\item $\lcf(\U) \leq  \lambda$, hence $\U$ does not saturate $T_2$;
  \item $\mu(\U) > \lambda$, hence $\U$ saturates $T_1$.
  \end{itemize}
\end{proof}

\subsection*{Proof of Theorem~\ref{t:lcfNonSat}}
By instability, there is a countable $M \vDash  T$ and tuples $b_i \in M^{<\omega}$ 
for $i \in \omega$ and a formula $\phi(x,y)$ such that
\[ M \vDash  \phi(b_i,b_j) \Leftrightarrow  i \leq  j .\]

For $\alpha \in \omega^\U$, let $b_\alpha := (t \mapsto  b_{f(t)}) / \U$
where $f \in \omega^\lambda$, $\alpha = f/\U$.
Then by \L{}os,
\[ M^\U \vDash  \phi(b_\alpha,b_\beta) \Leftrightarrow  \alpha \leq  \beta .\]

Now suppose $M^\U$ is $\lambda^+$-saturated.
Since $\cf(\U) \leq  \lambda$, there is a coinitial subset $\{ \alpha_j : j \in 
\lambda \} \subseteq  \omega^\U \setminus \omega$.
Let $a \in M^\U$ realise
$\{ \phi(b_i, x) : i \in \omega \} \cup \{ \neg \phi(b_{\alpha_j},x) : j \in 
\lambda \}$.
So \[ \{ i \in \omega^\U : \forall j < i.\; M^\U \vDash  \phi(b_j,a) \} = \omega .\]

This contradicts the overspill lemma of non-standard analysis, which states 
that there is no infinite internal set of standard elements.

Alternatively (pointed out by Martin Hils): regularity of $\U$ implies 
$\aleph_1$-saturation, so there can't be a countable internal set.

Alternatively: if $a = g/\U$, $g \in M^\lambda$, then by \L{}os, $\omega = 
\prod_{t \in \lambda} \{ i \in \omega : \forall j < i.\; M \vDash  \phi(b_j,a(t)) 
\}$. But any subset of $\omega$ has the property that if it is bounded then it 
has a maximal element, so by \L{}os this also holds of any ultraproduct of 
subsets of $\omega$ (apply \L{}os to $\exists x. \forall y. (P(y) \rightarrow  y<x) \rightarrow  
\exists x. (P(x) \wedge \forall y. (P(y) \rightarrow  y<x)$). But $\omega \subseteq  \omega^\U$ is 
bounded and has no maximal element.
\qed

\subsection*{Proof of Theorem~\ref{t:lcfuf}.}

Let $\alpha := 2^\lambda\cdot\aleph_1$, so $|\alpha| = 2^\lambda$ and 
$\cf(\alpha) = \aleph_1$.

\begin{notation*}
  For $\sigma = \phi(g_1,\ldots ,g_k)$ a (possibly infinitary) $\{<\}$-sentence 
  with parameters $g_1,\ldots ,g_k \in \omega^\lambda$,
  define $\bv{\sigma} := \{ t : \omega \vDash  \phi(\gtup(t)) \}$.
  For $D$ a filter on $\lambda$, write $\omega^D \vDash  \sigma$ to mean 
  $\bv{\sigma} \in D$.

  Note that for any $A \subseteq  \lambda$, $A = \bv{\chi_A = 1}$.

  {\it (So really this is just a convenient substitute for talking about 
  subsets of $\lambda$, letting us use the notation of propositional logic.)}

  For $\Sigma$ a set of sentences,
  let $D\left<{\Sigma}\right>$ be the filter generated by $D \cup \{\bv{\sigma} : 
  \sigma \in \Sigma\}$.

  For a sentence $\sigma$, let $D\left<{\sigma}\right> := D\left<{\{ \sigma \}}\right>$.
\end{notation*}

\begin{lemma*}
  For $D$ a filter and $\sigma,\tau$ sentences,
  $\omega^{D\left<{\sigma}\right>} \vDash  \tau$ iff $\omega^D \vDash  \sigma \rightarrow  \tau$.
\end{lemma*}
\begin{proof}
  $\omega^{D\left<{\sigma}\right>} \vDash  \tau$ iff $\bv{\tau} \in D\left<{\sigma}\right>$ \\
  iff $\bv{\tau} \supseteq A \cap \bv{\sigma}$ for some $A \in D$ \\
  iff $(\lambda \setminus \bv{\sigma}) \cup \bv{\tau} \supseteq A$ for some $A \in D$ \\
  iff $\bv{\sigma \rightarrow  \tau} \in D$ \\
  iff $\omega^D \vDash  \sigma \rightarrow  \tau$.
\end{proof}

\begin{definition*}
  Say sentences $(\tau_i)_i$ \underline{partition} modulo a filter $D$ if
  $\omega^D \vDash  \neg (\tau_i \wedge \tau_j)$ for $i\neq j$
  and for any sentence $\sigma$,
  \[ \left({\forall i.\; \omega^D \vDash  \tau_i \rightarrow  \sigma}\right) \Rightarrow  \omega^D \vDash  \sigma 
  .\]
\end{definition*}

\begin{claim} \label{c:chain}
  There exist $f_i \in \omega^\lambda$ and regular filters $D_i$ for $i \leq  
  \alpha$ such that
  \begin{enumerate}[(1)]\item $(D_i)_i$ is an increasing chain;
  \item if $i < j < \alpha$ and $n \in \omega$, then $\omega^{D_j} \vDash  f_i \neq  
  n$;
  \item if $j \leq  i < \alpha$, then $(f_i = n)_{n \in \omega}$ partitions mod 
  $D_j$.
  \item $\U := \cup_{i<\alpha} D_i$ is an ultrafilter.
  \end{enumerate}
\end{claim}

\begin{claim*}
  \begin{enumerate}[(i)]\item Then $f_i/\U$ are strictly decreasing, i.e.\ $i<j\leq \alpha \Rightarrow  f_j/\U < 
  f_i/\U$.
  \item
    If $g \in \omega^\lambda$ and $g/\U \in \omega^\U \setminus \omega$,
    then for some $i < \alpha$ we have
    $f_j/\U < g/\U$ for all $i \leq  j < \alpha$.
  \end{enumerate}
\end{claim*}
\begin{proof}
  \begin{enumerate}[(i)]\item
    $\forall n \in \omega.\; \omega^{D_j} \vDash  f_i \neq  n$,
    so $\forall n \in \omega.\; \omega^{D_j} \vDash  f_i > n$,
    so $\forall n \in \omega.\; \omega^{D_j} \vDash  (f_j = n \rightarrow  f_i > f_j)$.
    But $(f_j = n)_n$ partitions mod $D_j$,
    so $\omega^{D_j} \vDash  f_i > f_j$.
    Then also $\omega^\U \vDash  f_i > f_i$,
    i.e.\ $f_i/\U > f_j/\U$, as required.
  \item
    We have $\forall n \in \omega.\; \omega^\U \vDash  g > n$.
    Since $\cf(\alpha) = \aleph_1 > \aleph_0$,
    already $\forall n \in \omega.\; \omega^{D_i} \vDash  g > n$
    for some $i < \alpha$.
    We then conclude exactly as in (i).
  \end{enumerate}
\end{proof}

So if $g/\U \in \omega^\U \setminus \omega$,
for some $\beta<\alpha$ we have $f_i/\U \in g/\U$ for $\beta<i<\alpha$,
so
\[ \left|{\{ \beta \in \omega^\U : \beta < g/\U \}}\right|
  \geq  \left|{\{ i : \beta < i < \alpha = 2^\lambda\cdot\aleph_1 \}}\right| = 2^\lambda > 
  \lambda .\]
So $\mu(\U) > \lambda$.

Furthermore, by the Claim, $(f_i/\U)_{i<\alpha}$ is a coinitial decreasing 
sequence in $\omega^\U \setminus \omega$,
so
\[ \lcf(\U) \leq  \cf(\alpha) = \aleph_1 ,\]
as required.

This concludes the proof of Theorem~\ref{t:lcfuf} modulo Claim~\ref{c:chain}.

\subsection*{Proof of Claim~\ref{c:chain}}

\begin{definition*}
  For $\G \subseteq  \omega^\lambda$,
  define $\FI(\G) := \{ h : G_0 \rightarrow  \omega \;|\; G_0 \subseteq_{\operatorname{fin}} \G \}$.

  For $h \in \FI(\G)$, let $\sigma_h$ be the sentence $\bigwedge_{g \in \dom(h)} g = 
  h(g)$. We write just $h$ for $\sigma_h$.

  For $D$ a filter and sentences $\tau,\sigma$,
  say $\tau$ {\bf decides} $\sigma$ mod $D$
  if either $\omega^D \vDash  h_i \rightarrow  \sigma$ or $\omega^D \vDash  h_i \rightarrow  \neg\sigma$.

  Say $\sigma$ is {\bf supported} by $\G$ mod $D$ if there are $h_i \in \FI(\G)$ 
  for $i \in \omega$ such that each $h_i$ decides $\sigma$ mod $D$ and 
  $(h_i)_i$ partitions mod $D$.

  Say $\G$ is {\bf independent} modulo $D$
  if for all $h \in \FI(\G)$,
  \[ \omega^D \not\vDash  \neg h .\]
\end{definition*}

We build $D_i$ such that (1) and (2) hold and also
\begin{enumerate}[(i)]\item $D_i = D_0\left<{\Sigma_i}\right>$ where each $\sigma \in \Sigma_i$ is supported 
by $f_{<i}$ mod $D_0$;
\item $f_{\geq i}$ is independent mod $D_i$;
\item $D_i$ is maximal such that (i) and (ii) hold.
\end{enumerate}
(3) and (4) will then follow.


First we find the $f_i$ and $D_0$.

\begin{lemma*}
  There are functions $g_i : \lambda \rightarrow  \lambda$ for $i \in 2^\lambda$
  such that for any $I_0 \subseteq_{\operatorname{fin}} 2^\lambda$ and $h : I_0 \rightarrow  \lambda$,
  there exists $\gamma \in \lambda$ such that $\forall i \in I_0.\; g_i(\gamma) 
  = h(i)$.
\end{lemma*}
\begin{proof}
  Enumerate the pairs $(A_\gamma,F_\gamma)_{\gamma \in \lambda}$ of finite 
  subsets $A \subseteq  \lambda$ and functions $F : \powerset(A) \rightarrow  \lambda$. For $B 
  \subseteq  \lambda$, let $g_B(\gamma) := F_\gamma(B \cap A_\gamma)$.
  Now given $h : I_0 \rightarrow  \lambda$, for some finite $A \subseteq  \lambda$ the $(B \cap 
  A)_{B \in I_0}$ are distinct, and so for some $\gamma$ we have $A_\gamma = A$ 
  and $\forall B \in I_0.\; F_\gamma(B \cap A) = h(B)$, as required.
\end{proof}

Applying this lemma, we can find $(f_i : \lambda \rightarrow  \omega)_{i < \alpha}$ and 
$g : \lambda \rightarrow  S_{\aleph_0}(\lambda)$ such that any finite set of values for 
$((f_i)_i,g)$ occurs somewhere on $\lambda$. Let $D_0'$ be the filter 
generated by $R:=\{ \{ t \in \lambda : i \in g(t) \} : i \in \lambda \}$. Then 
$D_0'$ is regular since $R$ is a regularising family, and $f_{<\alpha}$ is 
independent mod $D_0'$.
Extend $D_0$ to a maximal filter $D_0$ such that $f_{<\alpha}$ is independent 
mod $D_0$.
Then (i)-(iii) hold for $D_0$.

Let $\FI := \FI(f_{<\alpha})$.

\begin{lemma} \label{l:independent}
  Suppose $\G \subseteq  \omega^\lambda$ is independent modulo a filter $D$,
  and $\G' \subseteq  \G$,
  and $h \in \G$,
  and $\tau$ is supported by $\G'$ mod $D$,
  and $\omega^D \vDash  h \rightarrow  \tau$.
  Then $\omega^D \vDash  h|_{\G'} \rightarrow  \tau$.
\end{lemma}
\begin{proof}
  Say $h_i \in \FI(\G')$, $i \in \omega$, partition mod $D$ and each $h_i$ 
  decides $\tau$ mod $D$.

  Let $i \in \omega$.
  If $\omega^D \vDash  h_i \rightarrow  \tau$ then
  clearly $\omega^D \vDash  h_i \rightarrow  (h|_{\G'} \rightarrow  \tau)$.
  If $\omega^D \vDash  h_i \rightarrow  \neg \tau$ then
  $\omega^D \vDash  h_i \rightarrow  \neg h$,
  so $\omega^D \vDash  \neg (h_i \wedge h)$,
  so by independence $h_i \cup h \notin \FI(\G)$,
  but then already $h_i \cup h|_{\G'} \notin \FI(\G)$,
  so $\omega^D \vDash  h_i \rightarrow  \neg h|_{\G'}$,
  so again $\omega^D \vDash  h_i \rightarrow  (h|_{\G'} \rightarrow  \tau)$.

  We conclude since the $h_i$ partition mod $D$.
\end{proof}

\begin{lemma*}
  For any $\sigma$, if $\omega^{D_0} \not\vDash  \neg \sigma$ then
  $\omega^{D_0} \vDash  h \rightarrow  \sigma$ for some $h \in \FI$.
\end{lemma*}
\begin{proof}
  Otherwise $f_{\geq 0}$ is independent modulo $D_0\left<{\neg \sigma}\right>$, 
  contradicting the maximality of $D_0$.
\end{proof}

\begin{fact*}
  If $C \subseteq  S_{\aleph_0}(\lambda) := \{ A : A \subseteq_{\operatorname{fin}} \lambda \}$ and $|C| > 
  \aleph_0$,
  there exists $C' \subseteq  C$ with $|C'| > \aleph_0$
  and $A_0 \subseteq_{\operatorname{fin}} \lambda$
  such that $\forall A_1,A_2 \in C'.\; (A_1 \neq  A_2 \Rightarrow  A_1 \cap A_2 = A_0)$.
\end{fact*}
\begin{proof}
  Omitted. See [Shelah-classificationTheory Appendix Theorem~1.4].
\end{proof}

\begin{lemma} \label{l:support}
  For any $\sigma$ there is $\beta < \alpha$
  such that $\sigma$ is supported by $f_{<\beta}$ mod $D_0$.
\end{lemma}
\begin{proof}
  Let $H = \{ h_i \}_i \subseteq  \FI$ be maximal such that each $h_i$ decides 
  $\sigma$ mod $D_0$ and $i\neq j \Rightarrow  \omega^{D_0} \vDash  \neg (h_i \wedge h_j)$.

  Suppose $|H| > \aleph_0$. By the previous Fact, uncountably many have 
  domains intersecting pairwise in a fixed finite set, so in particular there 
  exist $h \neq  h' \in H$ with $h\cup h' \in \FI$. But then $\omega^{D_0} \vDash  \neg 
  (h \wedge h')$ contradicts independence.

  So $|H| = \aleph_0 < \cf(\alpha)$,
  so there exists $\beta<\alpha$ such that each $h_i \in \FI(f_{<\beta})$.
  It remains to show that $H$ partitions mod $D_0$.

  Suppose $\forall h \in H.\; \omega^{D_0} \vDash  h \rightarrow  \tau$
  but $\omega^{D_0} \not\vDash  \tau$.
  Then
  $\omega^{D_0} \not\vDash  \sigma^\epsilon \rightarrow  \tau$ for some $\epsilon$,
  i.e.\ 
  $\omega^{D_0} \not\vDash  \neg (\sigma^\epsilon \wedge \neg \tau)$.

  Applying the previous Lemma to $\sigma^\epsilon \wedge \neg\tau$
  yields $h' \in \FI$ which decides $\sigma$ and $\omega^{D_0} \vDash  h' \rightarrow  
  \neg\tau$ so $h'$ is inconsistent with each $h \in H$, contradicting 
  maximality of $H$.
\end{proof}

Given $D_i$,
let $D_{i+1}' := D_i\left<{\{ f_i \neq  n : n < \omega \}}\right>$.
Then $D_{i+1}'$ satisfies (i) since $D_i$ does,
and satisfies (ii) since $D_i$ does and by Lemma~\ref{l:independent}.
Extend $D_{i+1}'$ to $D_{i+1}$ satisfying the maximality condition (iii).

For $\beta < \alpha$ a limit ordinal, $D_\beta' := \cup_{i<\beta} D_i$ clearly 
satisfies (i) and (ii).
Extend it to $D_\beta$ satisfying the maximality condition (iii).

(1) and (2) are clear from the construction.

We check (4).
To show that $\U$ is an ultrafilter, let $\sigma$ be arbitrary,
suppose $\omega^\U \not\vDash  \sigma$, and we show $\omega^\U \vDash  \neg\sigma$.

By Lemma~\ref{l:support}, say $\sigma$ is $f_{<\beta}$-supported mod $D_0$.
Now $\omega^{D_\beta} \not\vDash  \sigma$,
so by (iii) for $D_\beta$,
$f_{\geq \beta}$ is not independent modulo $D_\beta\left<{\sigma}\right>$.
But then say $h \in \FI(f_{\geq \beta})$ and $\omega^{D_\beta\left<{\sigma}\right>} \vDash  \neg 
h$.
Then $\omega^{D_\beta} \vDash  \sigma \rightarrow  \neg h$,
so $\omega^D \vDash  (\tau \wedge \sigma) \rightarrow  \neg h$ for some 
$f_{<\beta}$-supported $\tau$ with $\omega^{D_\beta} \vDash  \tau$.
So $\omega^D \vDash  h \rightarrow  \neg (\tau \wedge \sigma)$,
and supportedness is closed under boolean combinations (exercise),
so by Lemma~\ref{l:independent} $\omega^D \vDash  \neg (\tau \wedge \sigma)$,
so $\omega^{D_\beta} \vDash  \neg\sigma$,
so $\omega^\U \vDash  \neg\sigma$.

Finally, we check (3).
Suppose $\beta\leq \gamma<\alpha$, let $f := f_\gamma$, and suppose
$\forall n \in \omega.\; \omega^{D_\beta} \vDash  (f = n \rightarrow  \sigma)$.
Say $\omega^{D_\beta} \vDash  \tau_n$
and $\omega^{D_0} \vDash  \tau_n \rightarrow  (f = n \rightarrow  \sigma)$
and $\tau_n$ is supported by $f_{<\beta}$ mod $D_0$.

By Lemma~\ref{l:support},
say $h_i^\epsilon \in \FI$, $i \in \omega$, $\epsilon \in \{\top,\bot\}$, 
partition mod $D_0$ and $\omega^{D_0} \vDash  h_i^\epsilon \rightarrow  \sigma^\epsilon$.

Let $h^\bot_{i,\beta} := h^\bot_i |_{f_{<\beta}}$.
Now $\omega^{D_0} \vDash  \neg \sigma \rightarrow  (f=n \rightarrow  \neg\tau_n)$
so $\omega^{D_0} \vDash  (h^\bot_i \wedge f=n) \rightarrow  \neg\tau_n$.

Now $\omega^{D_\beta} \vDash  h^\bot_i \rightarrow  f\neq n$ for all $n$, so clearly $f \notin 
\dom(h^\bot_i)$, so $h^\bot_i \cup (f \mapsto  n) \in \FI$,
and so by Lemma~\ref{l:independent}, $\omega^D \vDash  h^\bot_{i,\beta} \rightarrow  \neg\tau_n$.

Let $\theta := \bigvee_i h^\bot_{i,\beta}$.
Then $\omega^{D_0} \vDash  h_i^\epsilon \rightarrow  (\neg \theta \rightarrow  \sigma)$ for all 
$i,\epsilon$,
so $\omega^{D_0} \vDash  \neg\theta \rightarrow  \sigma$.

Let $H$ be a maximal antichain in $\{ h \in \FI
: ( \exists i. h \supseteq h^\bot_{i,\beta} ) \vee ( \forall i. h \cup h^\bot_{i,\beta} 
\notin \FI) \}$.

\begin{claim*}
  $H$ partitions mod $D_0$.
\end{claim*}
\begin{proof}
  % |TODO: clean
  By Lemma~\ref{l:support},
  it suffices to show that for $h' \in \FI$,
  if $\forall h \in H.\; \omega^{D_0} \vDash  h \rightarrow  \neg h'$
  then $\omega^D \vDash  \neg h'$.
  Suppose not.
  Now either $\forall i.\; h' \cup h^\bot_{i,\beta} \notin \FI$,
  or $h'$ extends to some $h'' = h' \cup h^\bot{i,\beta} \in \FI$.
  Then by maximality, $h'$ resp.\ $h'' \in H$.
  But then $\omega^D \vDash  \neg h'$, contradiction.
\end{proof}

If $\forall i. h \cup h^\bot_{i,\beta} \notin \FI$ then $\omega^D \vDash  h \rightarrow  \neg 
\theta$, and meanwhile $\omega^D \vDash  h^\bot_{i,\beta}$ for each $i$,
so for $h \in H$,
% |TODO: explain
$\omega^{D_0} \vDash  h \rightarrow  (\theta \rightarrow  \neg \tau_n)$,
so $\omega^{D_0} \vDash  \theta \rightarrow  \neg \tau_n$.

So $\omega^{D_\beta} \vDash  \sigma$ as required.
\qed


-- Martin Bays 2019
\end{document}
