Notation 2.1.

1. (1) For any structure M in some language, we denote its universe by $|M|$ , and its cardinality by $\|M\|$ .

2. (2) For cardinals $\lambda $ and $\mu $ , $[\lambda ,\mu ):=\{\kappa \in \text {Card}\mid \lambda \leq \kappa <\mu \}$ . $[\lambda ,\infty ):=\{\kappa \in \text {Card}\mid \lambda \leq \kappa \}$ .

3. (3) $K_{[\lambda ,\mu )}:=\{M\in K\mid \|M\|\in [\lambda ,\mu )\}$ . $K_\lambda :=K_{[\lambda ,\lambda ^+)}$ .

Fact 2.9 [Reference Baldwin1, Theorem 11.3(1)].

Let $\delta $ be a limit ordinal and $\langle M_i\in K\mid i\leq \delta \rangle $ increasing continuous, and $\langle p_i\in gS(M_i)\mid i<\delta \rangle $ a coherent sequence of types. Then there is $p\in gS(M_\delta )$ an upper bound of $\langle p_i\in gS(M_i)\mid i<\delta \rangle $ , where the order is the one from Definition 2.5(5).

Fact 2.10 [Reference Baldwin1, Theorem 11.3(2)].

Let $\delta $ be a limit ordinal, $\langle M_i\in K\mid i\leq \delta \rangle $ increasing continuous, and $\langle p_i\in gS(M_i)\mid i<\delta \rangle $ a sequence of types with upper bound ${p\in gS(M_\delta )}$ . Then there are $\langle N_i\mid i\leq \delta \rangle $ and $\langle f_{j,i}\mid j<i\rangle $ that witness $\langle p_i\in gS(M_i)\mid i\leq \delta \rangle $ being a coherent sequence.

Fact 2.13 [Reference Shelah23, Lemma 0.26(1)].

Let $\mu>\lambda $ . If $K_\lambda $ has AP then $M\in K_{\mu }$ is saturated over $\mu $ for $\lambda $ if and only if M is homogeneous over $\mu $ for $\lambda $ .

Fact 2.15 [Reference Shelah20, Theorem II.4.11].

Let T be a complete first order theory and $\phi $ a formula in its language. $\lambda $ is an infinite cardinal such that $2^\lambda>\text {ded } \lambda $ . The following are equivalent:

1. (1) $\phi $ has the independence property.

2. (2) $|S_\phi (A)|> \text {ded } |A|$ for some infinite set A, $|A|=\lambda $ .

3. (3) $|S_\phi (A)|=2^{|A|}$ for some infinite set A, $|A|=\lambda $ .

Fact 2.16 [Reference Shelah20, Theorem II.4.12].

Let T be a complete theory in countable language, and $f_T(\lambda ):=\sup \{|S(M)|\mid M\models T$ , $\|M \|=\lambda \}$ . Then $f_T(\lambda )$ is exactly one of: $\lambda $ , $\lambda +2^{\aleph _0}$ , $\lambda ^{\aleph _0}$ , $\text {ded } \lambda $ , $(\text {ded } \lambda )^{\aleph _0}$ or $2^\lambda $ (see also [Reference Jerome Keisler12]).

Question 2.18. Is there an equivalent notion which does not rely on extra set theoretic assumptions (at least for AECs K with $LS(K)=\aleph _0$ which are also $PC_{\aleph _0}$ )?

Question 2.19. Is there a global characterization of NIP?

Fact 2.20 [Reference Jarden and Shelah11, Theorem 2.5.8].

Assume K has JEP, AP, and NMM. Suppose there is $S^{bs}\subseteq gS$ family of types on K satisfying only (Density), (Invariance), and for all $M\in K_\lambda $ , $|S^{bs}(M)|\leq \lambda ^+$ (see Definitions 3.1 and 3.3).

1. (1) If $\langle M_\alpha \in K_\lambda \mid \alpha <\lambda ^+ \rangle $ is increasing and continuous, and there is a stationary set $S\subseteq \lambda ^+$ such that for every $\alpha \in S$ and every model N, with $M_\alpha \leq _K N$ , there is a type $p\in S^{bs}(M_\alpha )$ which is realized in $M_{\lambda ^+}:=\bigcup _{i<\lambda ^+} M_i$ and in N, then $M_{\lambda ^+}$ is saturated in $\lambda ^+$ above $\lambda $ .

2. (2) For all $M\in K_\lambda $ , $|gS(M)|\leq \lambda ^+$ .

Question 2.23. Are there other (perhaps more interesting than the previous two) examples of NIP that arise naturally in algebra or analysis?

Fact 2.30 [Reference Shelah27, Claim VI.2.18].

( $2^{\lambda } < 2^{\lambda ^+}$ ) Assume K has amalgamation and no maximal model in $\lambda $ . If

1. (1) $S_*$ is $\leq _{K_\lambda }$ -type-kind and hereditary;

2. (2) $S_*\subseteq gS^{<\lambda ^+-min}$ , and

3. (3) there is $M \in K_\lambda $ such that:

   1. (a) $|gS_*(M)|\geq \lambda ^+$ , and

   2. (b) if $M \leq _K N\in K_\lambda $ , no subset of $S_*(N)$ of size $\leq \lambda $ is $S_*$ -inevitable,

then $I(\lambda ^+,K)=2^{\lambda ^+}$ .

Fact 2.31 [Reference Shelah27, Claim VI.2.11(2)].Footnote ²

For every $M\in K_\lambda $ we have $|S_*(M)|\leq \lambda $ when:

1. (1) K has AP in $\lambda $ , and

2. (2) $S_*$ is a hereditary $\leq _{K_\lambda }$ -type-kind in $gS$ , and

3. (3) for every $M\in K_\lambda $ there is an $S_*$ -inevitable $\Gamma _M\subseteq gS(M)$ of cardinality $\leq \lambda $ .

Hypothesis 3.7 ( $2^{\lambda ^+}>2^\lambda $ ).

We fix K an AEC and a cardinal $\lambda \geq LS(K)$ such that K is categorical in $\lambda $ . Furthermore $1\leq I(\lambda ^+,K)<2^{\lambda ^+}$ , and $K_\lambda $ has NIP.

Fact 3.8 [Reference Shelah21, Theorem 3.5] ( $2^\lambda <2^{\lambda ^+}$ ).

If $I(\lambda , K)=1\leq I(\lambda ^+,K)<2^{\lambda ^+}$ , then K has the $\lambda $ -AP.

Fact 3.11 [Reference Shelah27, Claim VI.2.5(2B)].

If $K_\lambda $ has AP and $\lambda \geq LS(K)$ , $\textbf {gtp}(a,M,N)$ has $\geq \lambda ^+$ realizations in some extension of M (necessarily in $K_{\geq \lambda ^+})$ if and only if $ \textbf {gtp} (a/M,N)$ has the extension property.

Proof. Suppose not, i.e., $|S^{\lambda -al}(M)|\geq \lambda ^+$ .

Claim. There is no $\Gamma \subseteq S^{\lambda -al}(M)$ , $|\Gamma |\leq \lambda $ that is inevitable.

Otherwise, suppose there exists such $\Gamma $ . By Fact 2.31, taking $S_*$ to be $gS$ , and $\Gamma _M$ to be $\Gamma $ , we have $|gS(M)|\leq \lambda $ , so in particular $|S^{\lambda -al}(M)|\leq \lambda $ , contradiction.

Now by the claim and Fact 2.30, taking $S_*$ there to be $S^{\lambda -al}$ and $\mu $ there to be $\lambda ^+$ , we have $I(\lambda ^+,K)=2^{\lambda ^+}$ , contradiction.

Proof. Easy. We prove (Transitivity) as an example. Suppose $p\in S^{bs}(N)$ does not fork over $M_1\leq _K N$ , and $p\restriction _{M_1}$ does not fork over $M_0\leq _K M_1$ . Then $(p\restriction _{M_1})\restriction _{M_0}$ is $\lambda $ -unique, i.e., $p\restriction _{M_0}$ is. Thus p does not fork over $M_0$ .

Proof. It suffices to show that there is a $\lambda $ -unique type above any basic type. By Fact 2.20 let $\mathfrak C\in K_{\lambda ^+}$ be saturated in $\lambda ^+$ over $\lambda $ . It is also homogeneous in $\lambda ^+$ over $\lambda $ by Fact 2.13. Let $(a,M,N)\in K^3_\lambda $ such that $\textbf {gtp}(a/M,N)$ has the extension property and there is no $\lambda $ -unique type above $\textbf {gtp}(a/M,N)$ . Build $(a_\eta ,M_\eta ,N_\eta )\in K^3_\lambda $ for $\eta \in {}^{<\lambda }2$ and $h_{\eta ,\nu }$ for $\eta <\nu \in {}^{<\lambda }2$ such that:

1. (1) $(a_{\langle \rangle },M_{\langle \rangle },N_{\langle \rangle })=(a,M,N)$ .

2. (2) $(a_\eta ,M_\eta ,N_\eta )\leq _{h_{\eta ,\nu }} (a_\nu ,M_\nu ,N_\nu )$ for $\eta < \nu $ .

3. (3) $h_{\eta ,\rho }=h_{\nu ,\rho }\circ h_{\eta ,\nu }$ for $\eta <\nu <\rho $ .

4. (4) , , and .

5. (5) , both having $\lambda ^+$ -many realizations.

6. (6) If $\eta \in {}^\delta 2$ for $\delta $ a limit ordinal, take $M_\eta $ and $N_\eta $ to be directed colimits.

Construction: Base case and limit case are clear. At successor stage use non- $\lambda $ -uniqueness to get two distinct extensions, each having $\lambda ^+$ -many realizations.

Enough: Let $M\leq _K \mathfrak C\in K_{\lambda ^+}$ be saturated over $\lambda $ . Build $g_\eta :M_\eta \to \mathfrak C$ for $\eta \in {}^{\leq \lambda } 2$ such that:

1. (1) $g_\eta \circ h_{\eta ,\nu }=g_\nu $ for $\nu < \eta $ .

2. (2) .

Sub-Construction: We carry out the construction by induction on the $\ell (\eta )$ , the length of $\eta $ . For the base case take $g_{\langle \rangle }$ to be inclusion $M\leq _K \mathfrak C$ . At limit use the universal property of $M_\eta $ as a directed colimit. For the successor case, for $\eta $ of length $\alpha =\beta +1$ , suppose we have $g_\eta $ .

(1)

Use basic extension to obtain the right square and g, and then obtain the middle square and h. Finally the left triangle is by saturation of $\mathfrak C$ . Now define to be the composition of the top row from right to left.

Sub-construction is enough: For each branch $\eta \in {}^{\lambda }2$ , take directed colimit to obtain $(a_\eta ,M_\eta ,N_\eta )$ . Obtain $f_\eta :M_\eta \to \mathfrak C$ by the universal property of colimits such that $f_\eta \circ h_{\nu ,\eta }=g_\nu $ for all $\nu <\eta $ , and obtain $f^{\prime }_\eta :N_\eta \to \mathfrak C$ extending $f_\eta $ by saturation over $\lambda $ . Since each $f^{\prime }_\eta (a_\eta )\in |\mathfrak C|$ , but $\|\mathfrak C\|=\text {ded } \lambda <2^\lambda $ , there must be $\eta \neq \nu \in {}^\lambda 2$ such that $f^{\prime }_\eta (a_\eta )=f^{\prime }_\nu (a_\nu )$ . Let $\alpha <\lambda $ be the least such that $\eta (\alpha )\neq \nu (\alpha )$ . Without loss of generality say $\eta (\alpha )=0$ and $\nu (\alpha )=1$ . Then the following diagram commutes:

(2)

with since $f^{\prime }_\eta (a_\eta )=f^{\prime }_\nu (a_\nu )$ , contradicting requirement (5) of the construction.

Question 3.18. Lemma 3.16 is a weaker form of (Existence of Non-Forking Extension). Is it possible to obtain (Existence of Non-Forking Extension) in its full strength, by perhaps considering another family of basic types and non-forking relation? One could imitate the w-good $\lambda $ -frame in [Reference Mazari-Armida15] and use $\lambda $ -unique types as basic ones, and then Lemma 3.16 gives a proof of (Weak Density). However, then it is hard to show that having such a frame implies NIP.

Proof. Let $M_i$ , $i<\delta $ be increasing continuous. $p_i\in S^{bs}(M_i)$ increasing and for $i<j<\delta $ we have $p_j\restriction _{M_i}=p_i$ , all non-forking over $M_0$ and $p_\delta $ upper bound. Suppose $p_\delta $ has $\leq \lambda $ -many realizations. Then there is a set S of cardinality $\lambda ^+$ of realizations of $p_0$ , such that for each $a\in S$ , by locality there is $i< \delta $ such that a realizes $p_i$ but not $p_{i+1}$ . By pigeonhole principle for some $i<\delta $ there are $\lambda ^+$ -many realizations of $p_i$ that are not realizations of $p_{i+1}$ . Since there are $\leq \lambda $ -many types in $S(M_{i+1})$ that have $\leq \lambda $ -many realizations, there must be another type in $S(M_{i+1})$ with $\lambda ^+$ realizations distinct from $p_{i+1}$ , which contradicts $\lambda $ -uniqueness of $p_{i+1}$ .

For the moreover part, if $p_0$ does not fork over $M_0$ , so $p_0=p_\delta \restriction _{M_0}$ is $\lambda $ -unique, i.e., $p_\delta $ does not fork over $M_0$ .

Proof. The moreover part follows from Lemma 3.16.

Question 3.22. Are there other positive consequences of NIP that rely on weaker assumptions?

Hypothesis 4.1. Let $\kappa $ be an infinite cardinal and K an AEC. Let $\tau =L(K)$ be its underlying language.

Fact 4.7 [Reference Vasey30, Corollary 3.18(2)].

Under the notation of the previous definition, K is $(<\kappa )$ -tame if and only if for each ordinal $\alpha $ , $M\in K$ , $A\subseteq M$ , $\textbf {gtp}(\bar b/A,M)\mapsto \textbf {tp}_{\text {qf-} L_{\kappa ,\kappa }(\hat \tau )}(\bar b/A,M)$ from $gS^\alpha (A;M)$ to $S^\alpha _{\text {qf}-L_{\kappa ,\kappa }(\hat \tau )}(A;M)$ is bijective.

Notation 4.8. For any formula $\varphi $ and a condition i, $\varphi ^i$ means $\varphi $ itself when i holds, and $\neg \varphi $ otherwise. For example, at the end of the proof of the next theorem, the formula is $\phi (c_i,x)$ and the condition is $i\in w$ . When $i\in w$ holds, $\phi (c_i,x)^{i\in w}$ is $\phi (c_i,x)$ . When $i\notin w$ , $\phi (c_i,x)^{i\in w}$ is $\neg \phi (c_i,x)$ .

Proof. Let $\hat K$ be the $(<\aleph _0)$ Galois Morleyization of K. Note that both classes have the same Galois types. By Shelah’s Presentation Theorem $\hat K=PC(T,\Gamma , \hat \tau )$ with $|T|\leq 2^{LS(K)}$ , with the language of T containing $\hat \tau $ . Then by tameness and the previous fact $|S^{1}_{\text {qf}-L_{\omega ,\omega }(\hat \tau )}(C;M)|>\text {ded } \lambda $ , so for some quantifier-free formula $\phi (\bar y,x)$ in $ L_{\omega ,\omega }(\hat \tau )$ with $|S_\phi (C;M)|> \text {ded } \lambda $ , since there are $\leq 2^{LS(K)}$ -many quantifier-free $L_{\omega ,\omega }(\hat \tau )$ -formulas.

Without loss of generality $C=\lambda =|C|$ . Let $\mu :=(\text {ded } \lambda )^+$ . For notational simplicity we view $S_{\phi }(C; M)$ as S, a family of subsets of $ ^{\ell (\bar y)}C$ , where

$$ \begin{align*}A\in S\iff \{\phi(\bar a, x)\mid \bar a\in A\}\in S_\phi(C;M). \end{align*} $$

We also assume $\bar y$ has length $1$ . The proof for other cases is similar.

Claim. For all $\alpha <\lambda $ , if $|\{A\cap \alpha \mid A\in S\}|\geq \mu $ , then $\alpha \geq (\beth _2(LS(K)))^+$ .

Proof of Claim.

Suppose there is $\alpha < \lambda $ , $|\{A\cap \alpha \mid A\in S\}|\geq \mu $ . Since $\{A\cap \alpha \mid A\in S\}$ is the set of branches of the a subtree of $^{<\alpha }2$ , $\text {ded } \lambda < \mu \leq \text {ded } |^{<\alpha } 2|\leq \text {ded } 2^{|\alpha |}$ , so $2^{|\alpha |}>\lambda \geq \beth _3(LS(K))$ , so $|\alpha |> \beth _2(LS(K))$ . Thus the claim holds.

Proof. We fix $\hat K$ and $\phi $ as in the proof of the previous theorem. Let $\lambda =(2^{LS(K)})^+$ . Suppose K can encode subsets of $\mu :=\beth _{(2^{LS(K)})^+}$ . That is, there are $M\in K$ , $\{a_i\mid i<\mu \}\subseteq |M|$ , $\{b_w\mid w\subseteq \mu \}\subseteq |M|$ such that for all $w\subseteq \mu $ ,

$$ \begin{align*}i\in w\iff \phi(a_i,b_w).\end{align*} $$

For each $i_0<\ldots <i_{n-1}<\mu $ and $u\subseteq n$ , choose some subset $w\subseteq \mu $ such that $i_j\in w \iff \phi (a_{i_j},b_w)\iff j\in u$ , and let $b_{u,n}^{i_0,\ldots ,i_{n-1}}:=b_w$ . We build $\langle F_n\subseteq \mu \mid n<\omega \rangle $ , $\langle X_{\xi ,n}\subseteq \mu \mid \xi \in F_n, n<\omega \rangle $ and $p_n\in S^{n+2^n}_T(\emptyset )$ such that:

1. (1) for all $n<\omega $ , $|F_n|=\lambda $ ;

2. (2) $|X_{\xi ,n}|>\beth _\beta (2^{LS(K)})$ when $\xi $ is the $\beta $ -th element of $F_n$ ;

3. (3) .

Let $F_0=\lambda $ and $X_{\xi ,0}:=\mu $ for all $\xi $ . Suppose we have constructed everything for stage n. Fix $g:\lambda \to F_n$ an increasing enumeration. Let $G_n:=\{g(\beta +n+1)\mid \beta <\lambda \}$ . For each $\xi =g(\beta +n+1)\in G_n$ , consider the map from $[X_{\xi ,n}]^{n+1}$ (increasing $(n+1)$ -tuples from $X_{\xi ,n}$ ) to $S_T^{n+2^n}(\emptyset )$ . Since $|X_{\xi ,n}|>\beth _{\beta +n+1}((2^{LS(K)})^+)$ , by the Erdős–Rado theorem, there is a monochromatic subset $X_{\xi , n+1}\subseteq X_{\xi ,n}$ such that $|X_{\xi ,n+1}|>\beth _\beta ((2^{LS(K)})^+)$ . That is, there is a type $p_{\xi ,n+1}$ such that for all $i_0<\ldots <i_n$ , . By the pigeonhole principle there is $F_{n+1}\subseteq G_n$ of cardinality $\lambda $ and $p_{n+1}$ such that for all $\xi \in F_{n+1}$ , $p_{\xi ,n+1}=p_{n+1}$ .

Then

is consistent for any cardinal $\kappa $ . By Morley’s method we are done.

Proof. Let M be a model of $T^*$ and without loss of generality $M=EM(\{c_i\mid i<\alpha \})$ . We show that M omits all types from $\Gamma $ . Suppose not, i.e., $a\in |M|$ realizes some $q\in \Gamma $ . Write a as $\tau ^M(c_{i_0},\ldots , c_{i_k})$ for some term $\tau $ in the language of T. Let $S:=\{c^M_{i_0},\ldots , c^M_{i_k}\}$ and $\langle b_0,\ldots , b_k\rangle \subseteq N^*\in EC(T,\Gamma )$ realizing $p_S$ . Then for some $\varphi (y)\in q$ , $N^*\models \neg \varphi (\tau (b_0,\ldots ,b_k))$ . As $p_S$ is complete, $\neg \varphi (\tau (x_0,\ldots ,x_k))\in p_S$ . Thus $M\not \models \varphi (\tau (c_{i_0},\ldots ,c_{i_k}))$ , i.e., $M\models \neg \varphi (a)$ , so a does not realize q.