!newcal G
!newcal U
!newtup f
!newtup g
!newop cf
!newop dom
!newop fin
!newop lcf
!newop 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''}

## Statements

Definition*:
  For $\U$ an ultrafilter on $\lambda$,
  \[ \mu(\U) := \min_{\alpha (- \omega^\U \\ \omega} |{ \{ \beta (- \omega^\U 
  : \beta < \alpha \} }| ,\]
  \[ \lcf(\U) := \min \{ |A| : A (= \omega^\U \\ \omega,\; \forall \beta (- 
  \omega^\U \\ \omega.\; \exists \alpha (- A.\; \alpha < \beta \} .\]

  %(Note: cardinality here is in the ordinary standard sense -- we do not work 
  %in a non-standard model of set theory!)
  .

Fact*:
  ***(i) The nfcp theories form the minimal class in the Keisler order.
  **(ii) Let $T$ be a countable stable fcp theory.
  Then a regular ultrafilter $\U$ on $\lambda>=\aleph_0$ saturates $T$ iff 
  $\mu(\U) > \lambda$.
  *ee*
  .

Theorem[Shelah VI.4.8]:
  \label{t:lcfNonSat}
  Let $T$ be a countable unstable theory.
  Let $\U$ be a regular ultrafilter on $\lambda>=\aleph_0$ with $\lcf(\U) <= 
  \lambda$. Then $\U$ does not saturate $T$.
  .

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

Corollary*:
  If $T_1$ is stable and $T_2$ is unstable, then $T_1 < T_2$ in the Keisler 
  order.
  .
Proof:
  If $T_1$ is nfcp, we are done by the minimality of nfcp and the fact that 
  nfcp $==>$ stable. So suppose $T_1$ is stable fcp.

  By Theorem~{lcfuf}, there is a regular ultrafilter $\U$ on $\lambda := 
  \aleph_1$ such that
  ***) $\lcf(\U) <= \lambda$, hence $\U$ does not saturate $T_2$;
  ** $\mu(\U) > \lambda$, hence $\U$ saturates $T_1$.
  *e)*
  .

##* Proof of Theorem~{lcfNonSat}
By instability, there is a countable $M |= T$ and tuples $b_i (- M^{<\omega}$ 
for $i (- \omega$ and a formula $\phi(x,y)$ such that
\[ M |= \phi(b_i,b_j) <==> i <= j .\]

For $\alpha (- \omega^\U$, let $b_\alpha := (t |-> b_{f(t)}) / \U$
where $f (- \omega^\lambda$, $\alpha = f/\U$.
Then by Łos,
\[ M^\U |= \phi(b_\alpha,b_\beta) <==> \alpha <= \beta .\]

Now suppose $M^\U$ is $\lambda^+$-saturated.
Since $\cf(\U) <= \lambda$, there is a coinitial subset $\{ \alpha_j : j (- 
\lambda \} (= \omega^\U \\ \omega$.
Let $a (- M^\U$ realise
$\{ \phi(b_i, x) : i (- \omega \} \cup \{ \neg \phi(b_{\alpha_j},x) : j (- 
\lambda \}$.
So \[ \{ i (- \omega^\U : \forall j < i.\; M^\U |= \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 (- M^\lambda$, then by Łos, $\omega = 
\prod_{t (- \lambda} \{ i (- \omega : \forall j < i.\; M |= \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 Łos this also holds of any ultraproduct of 
subsets of $\omega$ (apply Łos to $\exists x. \forall y. (P(y) --> y<x) --> 
\exists x. (P(x) /\ \forall y. (P(y) --> y<x)$). But $\omega (= \omega^\U$ is 
bounded and has no maximal element.
\qed

##* Proof of Theorem~{lcfuf}.

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

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

  Note that for any $A (= \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<{ \Sigma }>$ be the filter generated by $D \cup \{\bv{\sigma} : 
  \sigma (- \Sigma\}$.

  For a sentence $\sigma$, let $D<{ \sigma }> := D<{ \{ \sigma \} }>$.
  .

Lemma*:
  For $D$ a filter and $\sigma,\tau$ sentences,
  $\omega^{D<{ \sigma }>} |= \tau$ iff $\omega^D |= \sigma --> \tau$.
  .
Proof:
  $\omega^{D<{ \sigma }>} |= \tau$ iff $\bv{\tau} (- D<{ \sigma }>$ \\\
  iff $\bv{\tau} =) A \cap \bv{\sigma}$ for some $A (- D$ \\\
  iff $(\lambda \\ \bv{\sigma}) \cup \bv{\tau} =) A$ for some $A (- D$ \\\
  iff $\bv{\sigma --> \tau} (- D$ \\\
  iff $\omega^D |= \sigma --> \tau$.
  .

Definition*:
  Say sentences $(\tau_i)_i$ _partition_ modulo a filter $D$ if
  $\omega^D |= \neg (\tau_i /\ \tau_j)$ for $i/=j$
  and for any sentence $\sigma$,
  \[ ({ \forall i.\; \omega^D |= \tau_i -> \sigma }) ==> \omega^D |= \sigma 
  .\]
  .

Claim{chain}:
  There exist $f_i (- \omega^\lambda$ and regular filters $D_i$ for $i <= 
  \alpha$ such that
  ***(1) $(D_i)_i$ is an increasing chain;
  **(2) if $i < j < \alpha$ and $n (- \omega$, then $\omega^{D_j} |= f_i /= 
  n$;
  **(3) if $j <= i < \alpha$, then $(f_i = n)_{n (- \omega}$ partitions mod 
  $D_j$.
  **(4) $\U := \cup_{i<\alpha} D_i$ is an ultrafilter.
  *ee*
  .

Claim*:
  ***(i) Then $f_i/\U$ are strictly decreasing, i.e. $i<j<=\alpha ==> f_j/\U < 
  f_i/\U$.
  **(ii)
    If $g (- \omega^\lambda$ and $g/\U (- \omega^\U \\ \omega$,
    then for some $i < \alpha$ we have
    $f_j/\U < g/\U$ for all $i <= j < \alpha$.
  *ee*
  .
Proof:
  ***(i)
    $\forall n (- \omega.\; \omega^{D_j} |= f_i /= n$,
    so $\forall n (- \omega.\; \omega^{D_j} |= f_i > n$,
    so $\forall n (- \omega.\; \omega^{D_j} |= (f_j = n -> f_i > f_j)$.
    But $(f_j = n)_n$ partitions mod $D_j$,
    so $\omega^{D_j} |= f_i > f_j$.
    Then also $\omega^\U |= f_i > f_i$,
    i.e. $f_i/\U > f_j/\U$, as required.
  **
    We have $\forall n (- \omega.\; \omega^\U |= g > n$.
    Since $\cf(\alpha) = \aleph_1 > \aleph_0$,
    already $\forall n (- \omega.\; \omega^{D_i} |= g > n$
    for some $i < \alpha$.
    We then conclude exactly as in (i).
  *ee*
  .

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

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

This concludes the proof of Theorem~{lcfuf} modulo Claim~{chain}.

##* Proof of Claim~{chain}

Definition*:
  For $\G (= \omega^\lambda$,
  define $\FI(\G) := \{ h : G_0 --> \omega \;|\; G_0 (=f \G \}$.

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

  For $D$ a filter and sentences $\tau,\sigma$,
  say $\tau$ #decides# $\sigma$ mod $D$
  if either $\omega^D |= h_i -> \sigma$ or $\omega^D |= h_i -> \neg\sigma$.

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

  Say $\G$ is #independent# modulo $D$
  if for all $h (- \FI(\G)$,
  \[ \omega^D |/= \neg h .\]
  .

We build $D_i$ such that (1) and (2) hold and also
***(i) $D_i = D_0<{ \Sigma_i }>$ where each $\sigma (- \Sigma_i$ is supported 
by $f_{<i}$ mod $D_0$;
**(ii) $f_{>=i}$ is independent mod $D_i$;
**(iii) $D_i$ is maximal such that (i) and (ii) hold.
*ee*
(3) and (4) will then follow.


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

Lemma*:
  There are functions $g_i : \lambda --> \lambda$ for $i (- 2^\lambda$
  such that for any $I_0 (=f 2^\lambda$ and $h : I_0 --> \lambda$,
  there exists $\gamma (- \lambda$ such that $\forall i (- I_0.\; g_i(\gamma) 
  = h(i)$.
  .
Proof:
  Enumerate the pairs $(A_\gamma,F_\gamma)_{\gamma (- \lambda}$ of finite 
  subsets $A (= \lambda$ and functions $F : \powerset(A) --> \lambda$. For $B 
  (= \lambda$, let $g_B(\gamma) := F_\gamma(B \cap A_\gamma)$.
  Now given $h : I_0 --> \lambda$, for some finite $A (= \lambda$ the $(B \cap 
  A)_{B (- I_0}$ are distinct, and so for some $\gamma$ we have $A_\gamma = A$ 
  and $\forall B (- I_0.\; F_\gamma(B \cap A) = h(B)$, as required.
  .

Applying this lemma, we can find $(f_i : \lambda --> \omega)_{i < \alpha}$ and 
$g : \lambda --> 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 (- \lambda : i (- g(t) \} : i (- \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})$.

Lemma{independent}:
  Suppose $\G (= \omega^\lambda$ is independent modulo a filter $D$,
  and $\G' (= \G$,
  and $h (- \G$,
  and $\tau$ is supported by $\G'$ mod $D$,
  and $\omega^D |= h --> \tau$.
  Then $\omega^D |= h|_{\G'} --> \tau$.
  .
Proof:
  Say $h_i (- \FI(\G')$, $i (- \omega$, partition mod $D$ and each $h_i$ 
  decides $\tau$ mod $D$.

  Let $i (- \omega$.
  If $\omega^D |= h_i --> \tau$ then
  clearly $\omega^D |= h_i --> (h|_{\G'} --> \tau)$.
  If $\omega^D |= h_i --> \neg \tau$ then
  $\omega^D |= h_i --> \neg h$,
  so $\omega^D |= \neg (h_i /\ h)$,
  so by independence $h_i \cup h (/- \FI(\G)$,
  but then already $h_i \cup h|_{\G'} (/- \FI(\G)$,
  so $\omega^D |= h_i --> \neg h|_{\G'}$,
  so again $\omega^D |= h_i --> (h|_{\G'} --> \tau)$.

  We conclude since the $h_i$ partition mod $D$.
  .

Lemma*:
  For any $\sigma$, if $\omega^{D_0} |/= \neg \sigma$ then
  $\omega^{D_0} |= h --> \sigma$ for some $h (- \FI$.
  .
Proof:
  Otherwise $f_{>=0}$ is independent modulo $D_0<{ \neg \sigma }>$, 
  contradicting the maximality of $D_0$.
  .

Fact*:
  If $C (= S_{\aleph_0}(\lambda) := \{ A : A (=f \lambda \}$ and $|C| > 
  \aleph_0$,
  there exists $C' (= C$ with $|C'| > \aleph_0$
  and $A_0 (=f \lambda$
  such that $\forall A_1,A_2 (- C'.\; (A_1 /= A_2 ==> A_1 \cap A_2 = A_0)$.
  .
Proof:
  Omitted. See [Shelah-classificationTheory Appendix Theorem~1.4].
  .

Lemma{support}:
  For any $\sigma$ there is $\beta < \alpha$
  such that $\sigma$ is supported by $f_{<\beta}$ mod $D_0$.
  .
Proof:
  Let $H = \{ h_i \}_i (= \FI$ be maximal such that each $h_i$ decides 
  $\sigma$ mod $D_0$ and $i/=j ==> \omega^{D_0} |= \neg (h_i /\ 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 /= h' (- H$ with $h\cup h' (- \FI$. But then $\omega^{D_0} |= \neg 
  (h /\ h')$ contradicts independence.

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

  Suppose $\forall h (- H.\; \omega^{D_0} |= h --> \tau$
  but $\omega^{D_0} |/= \tau$.
  Then
  $\omega^{D_0} |/= \sigma^\epsilon --> \tau$ for some $\epsilon$,
  i.e.
  $\omega^{D_0} |/= \neg (\sigma^\epsilon /\ \neg \tau)$.

  Applying the previous Lemma to $\sigma^\epsilon /\ \neg\tau$
  yields $h' (- \FI$ which decides $\sigma$ and $\omega^{D_0} |= h' --> 
  \neg\tau$ so $h'$ is inconsistent with each $h (- H$, contradicting 
  maximality of $H$.
  .

Given $D_i$,
let $D_{i+1}' := D_i<{ \{ f_i /= n : n < \omega \} }>$.
Then $D_{i+1}'$ satisfies (i) since $D_i$ does,
and satisfies (ii) since $D_i$ does and by Lemma~{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 |/= \sigma$, and we show $\omega^\U |= \neg\sigma$.

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

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

By Lemma~{support},
say $h_i^\epsilon (- \FI$, $i (- \omega$, $\epsilon (- \{\top,\bot\}$, 
partition mod $D_0$ and $\omega^{D_0} |= h_i^\epsilon --> \sigma^\epsilon$.

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

Now $\omega^{D_\beta} |= h^\bot_i --> f/=n$ for all $n$, so clearly $f (/- 
\dom(h^\bot_i)$, so $h^\bot_i \cup (f |-> n) (- \FI$,
and so by Lemma~{independent}, $\omega^D |= h^\bot_{i,\beta} --> \neg\tau_n$.

Let $\theta := \\//_i h^\bot_{i,\beta}$.
Then $\omega^{D_0} |= h_i^\epsilon --> (\neg \theta --> \sigma)$ for all 
$i,\epsilon$,
so $\omega^{D_0} |= \neg\theta --> \sigma$.

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

Claim*:
  $H$ partitions mod $D_0$.
  .
Proof:
  % |TODO: clean
  By Lemma~{support},
  it suffices to show that for $h' (- \FI$,
  if $\forall h (- H.\; \omega^{D_0} |= h --> \neg h'$
  then $\omega^D |= \neg h'$.
  Suppose not.
  Now either $\forall i.\; h' \cup h^\bot_{i,\beta} (/- \FI$,
  or $h'$ extends to some $h'' = h' \cup h^\bot{i,\beta} (- \FI$.
  Then by maximality, $h'$ resp. $h'' (- H$.
  But then $\omega^D |= \neg h'$, contradiction.
  .

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

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


-- Martin Bays 2019
