Proof. The first part is trivial. For the second part, let \(\mathcal{F}\subseteq[\theta]^{<\kappa}\) be \(\lambda\)-cofinal, and apply the first part with \(X=\theta\) and \(X_0=\theta_0\). It is clearly still \(\lambda\)-cofinal, and consists of sets of size less than \(\kappa \leq \kappa_0\), so in particular \(\lambda_0\)-cofinal, giving us the desired inequality. ◻

Proof. Fix such a family \(\mathcal{F}\) with a corresponding function \(f:\omega\rightarrow \omega\). consider the two-sorted structure \(\mathcal{M}=(\omega,\mathcal{F},\in)\), where \(\mathord{\in} \subseteq \omega\times\mathcal{F}\) is the incidence relation. Then for every \(n<\omega\), we have that \(\mathcal{M}\models \psi_n\), where: \[\begin{gather} \psi_n:= \;\forall x_0,\ldots,x_{n-1}\in \omega\;\exists y_0,\ldots,y_{f(n)-1}\in\omega\;\exists S\in\mathcal{F}\\ \big\{x_0,\ldots,x_{n-1}\big\}\subseteq S\land \big\{y_0,\ldots,y_{f(n)-1}\big\}=S \end{gather}\]

Assume towards a contradiction that \(\mathop{\mathrm{VC}}(\mathcal{F})=m<\omega\). Let \(\mathcal{N}=(N,\hat{\mathcal{F}})\) be an elementary extension of cardinality \(\aleph_m\). Without loss of generality we have \(N=\aleph_m\). Now, write \(\hat{\mathcal{F}}_{\mathop{\mathrm{fin}}}=\hat{\mathcal{F}}\cap[\aleph_m]^{<\omega}\). Since having VC-dimension \(m\) is a first-order property, we have \(\mathop{\mathrm{VC}}(\mathcal{\hat{F}})=m\), hence \(\mathop{\mathrm{VC}}(\mathcal{\hat{F}}_{\mathop{\mathrm{fin}}})\leq m\). Because \(\mathcal{N}\models \psi_n\) for every \(n<\omega\), we have that \(\hat{\mathcal{F}}_{\mathop{\mathrm{fin}}}\) is cofinal as well, a contradiction to the bound of 13. ◻

Proof. We prove this lemma by induction, where the case \(n=1\) is trivial, as is the case of \(s=\emptyset\). For \(n>1\) and \(s\neq\emptyset\) we write \(x_0=\max_{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_\emptyset}s\). By the induction hypothesis there exists \(t_{k-1}\in[(s\setminus\{x_0\})]^{k-1}\) such that \(s\setminus(\{x_0\}\cup t_{k-1})\subseteq \mathord{\operatorname{dom}}(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^{x_0}_{t_{k-1}})=\mathord{\operatorname{dom}}(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_{t_{k-1}\cup\{x_0\}})\), which shows that setting \(s_k=t_{k-1}\cup\{x_0\}\) finishes the existence proof. For uniqueness, suppose \(s_k,t_k\in[s]^k\) both satisfy the conclusion of the lemma. We will first claim that \(s_k,t_k\) must contain \(x_0\). Indeed, for any nonempty \(t\subseteq s\) we have \(x_0\notin\mathord{\operatorname{dom}}(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_t)\subseteq X_{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_\emptyset \max_{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_\emptyset}t}\subseteq X_{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_\emptyset x_0}\), so the desired inclusion cannot hold otherwise. Write \(s_k'=s_k\setminus\{x_0\}\) and \(t_k'=t_k\setminus \{x_0\}\). Note that we have \(s\setminus\{x_0\}\subseteq \mathord{\operatorname{dom}}(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_{x_0})\), so we have \(s\setminus s_k\subseteq \mathord{\operatorname{dom}}(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^{x_0}_{s_k'})\subseteq X_{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_\emptyset x_0}\) and \(s\setminus t_k\subseteq\mathord{\operatorname{dom}}(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^{x_0}_{t_k'})\). Applying the induction hypothesis proves \(s_k'=t_k'\), which completes the proof of uniqueness. ◻

Proof. Suppose that \(s\subseteq X\) has size \(n+1\). Apply 24 to get \(s'\in[s]^{n-1}\) such that \(s\setminus s'\subseteq \mathord{\operatorname{dom}}(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_{s'})\), and write \(\{a,b\}=s\setminus s'\) As \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_{s'}\) is a linear order, either \(a \prec\mathrel{\mkern-5mu}\mathrel{\cdot}_{s'} b\) or \(b \prec\mathrel{\mkern-5mu}\mathrel{\cdot}_{s'} a\). Assume without loss of generality that the former holds. Then every closed set containing \(s',b\) also contains \(a\) by 21, so \(s\) cannot be shattered. ◻

Proof. Fix such an ordering system \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}\). By 25, the collection of \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}\)-closed sets has VC-dimension at most \(n+1\). By 12 so does \(\mathcal{F}\), and by having \((\lambda,\theta)\)-closures this family is \(\lambda\)-cofinal. ◻

Proof. Given an ordering system \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}\) on a set \(X\) and \(A\subseteq X\), \(x\in X\), write \(A\vdash x\) if any \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}\)-closed set \(S\) which contains \(A\) must contain \(x\).

By induction on \(\alpha<\omega_1\), we will recursively construct a sequence of 2-ordering systems \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^\alpha\) on \(\alpha +1\) for \(\alpha < \omega_1\) such that the following hold:

1. \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^\alpha_\emptyset\) is the usual ordering on \(\alpha+1\).

2. \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^\alpha_{\{\beta\}} = \prec\mathrel{\mkern-5mu}\mathrel{\cdot}^{\alpha'}_{\{\beta\}}\) whenever \(\beta \leq \alpha < \alpha'\).

3. \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^\alpha_{\{\beta\}}\) is of order type \(|\beta|\) for all \(\beta\leq \alpha\).

4. All closed 2-initial segments of \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^\alpha\) are \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^\alpha\)-closed.

5. Given a finite and \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^\alpha\)-closed set \(S\subseteq \alpha\) and \(\beta,\gamma\in \alpha\setminus S\) distinct, either \(S \cup \{\gamma\}\not\vdash\beta\) or \(S\cup \{\beta\}\not\vdash\gamma\).

If we succeed, then define \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}\) on \(\omega_1\) by setting \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_\emptyset\) as the usual ordering on \(\omega_1\) and \(\mathord{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}}_{\{\alpha\}} = \mathord{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}}_{\{\alpha\}}^\alpha\) for \(\alpha<\omega_1\) to conclude: ([IC]) tells us that all closed 2-initial segments are \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}\)-closed.

In the construction, we only explain how to define \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^\alpha_{\{\alpha\}}\) since ([itm:usual32ordering]) and ([itm:increasing]) determine the rest. Thus, to simplify notation, we will write \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_{\{\alpha\}}\) instead of \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^\alpha_{\{\alpha\}}\).

Define \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_{\{0\}}\) to be the empty ordering, then clearly it satisfies this.

We start with the successor step. Assuming we have defined \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^\beta\) for all \(\beta \leq \alpha<\omega_1\) such that the above hold, define \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_{\{\alpha+1\}}=\{(\alpha,\beta):\beta<\alpha\}\cup \mathord{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}}_{\{\alpha\}}\) (i.e., leave the ordering \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_{\{\alpha\}}\) on \(\alpha\) unchanged and add \(\alpha\) as the first element). We claim that our assumptions still hold.

([itm:usual32ordering]) is clear.

([itm:order32type]): We have to show that the order type of \(\prec_{\{\alpha+1\}}\) is \(|\alpha+1|\). This follows directly by the construction and the induction hypothesis.

([IC]): Suppose that \(D\) is a closed 2-initial segment of \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^{\alpha+1}\), i.e., has the form \(\{x<\alpha+2 : x \prec\mathrel{\mkern-5mu}\mathrel{\cdot}_{\{\beta\}} \gamma\} \cup \{\beta,\gamma\}\) for some \(\gamma<\beta<\alpha+2\). If \(\beta<\alpha+1\), then \(D\) is \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^{\alpha}\)-closed by induction, so also \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^{\alpha+1}\)-closed. If \(\gamma = \alpha\) (i.e., the minimal element in \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_{\{\alpha+1\}}\)) then \(D = \{\beta, \gamma\}\) so it is trivially \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^{\alpha+1}\)-closed, so we may assume that \(\beta=\alpha+1,\gamma \neq \alpha\). From this and the definition of \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_{\{\alpha+1\}}\), it follows that \(D \cap (\alpha+1)\) is the closed 2-initial segment of \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^\alpha\) determined by \(\alpha,\gamma\), so it is \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^\alpha\)-closed by induction.

We are given \(\gamma_2,\delta <\gamma_1\leq \alpha+1\) such that \(\gamma_2,\gamma_1\in D\) and \(\delta\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_{\{\gamma_1\}} \gamma_2\) and we have to show that \(\delta \in D\). If \(\gamma_1 = \alpha+1\), this follows directly from the definition of \(D\), so we may assume \(\gamma_1\leq \alpha\). In this case \(\gamma_2,\gamma_1 \in D \cap (\alpha+1)\), so \(\delta \in D \cap (\alpha+1)\) since it is \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^\alpha\)-closed, as required.

([dash]): Suppose \(S\subseteq\alpha+1\) is finite and \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^{\alpha+1}\)-closed, and \(\beta,\gamma\in\alpha+1\setminus S\) are distinct and \(\gamma<\beta\).

If \(S=\emptyset\) then ([dash]) holds since singletons are closed. If \(S\cup\{\beta\}\subseteq\alpha\) then ([dash]) follows from the induction hypothesis. Otherwise, we either have \(\alpha\in S\) or \(\beta=\alpha\).

• If \(\alpha\in S\) and \(\beta,\gamma\in\alpha+1\setminus S\), we must have \(\beta,\gamma<\alpha\). Suppose without loss of generality that \(\beta\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_{\{\alpha\}}\gamma\). Note that as \(S\) is \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^{\alpha+1}\)-closed and \(\beta \notin S\), \(S \subseteq \{x<\alpha : x\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_{\{\alpha\}} \beta\} \cup \{\alpha\}\). Thus, the set \(\{x<\alpha : x\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_{\{\alpha\}} \beta\} \cup \{\alpha,\beta\}\) is a closed 2-initial segment of \(\prec^{\alpha}\) not containing \(\gamma\). By ([IC]) applied to \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^{\alpha}\), this set witnesses that \(S\cup\{\beta\}\not\vdash \gamma\).

• Otherwise we have \(\beta=\alpha\). Take some initial segment \(D\) of \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_{\{\alpha\}}\) which contains \(\gamma\) and \(S\). Note that \(D \cup \{\alpha\}\) is a closed 2-initial segment of \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^\alpha\) so \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^\alpha\)-closed by induction. It follows that \(D\) is also \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^\alpha\)-closed (clearly if \(\gamma_1,\gamma_2 \in D\) and \(\delta \prec\mathrel{\mkern-5mu}\mathrel{\cdot}_{\{\gamma_1\}} \gamma_2\) then \(\delta <\alpha\)). Thus, \(D\) witnesses that \(S\cup \{\gamma\}\not\vdash \beta\).

We are left with the limit stage of the construction. Suppose \(\delta<\omega_1\) is a limit ordinal and we constructed \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^\alpha\) for all \(\alpha<\delta\). As above, we only need to define \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_{\{\delta\}}\) on \(\delta+1\).

Fix a bijection \(f:\omega\rightarrow\delta\). Let \(\mathord{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^*}\) be a 2-ordering system on \(\delta\) determined by \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^*_\emptyset\) being the usual order on \(\delta\) and for each \(\alpha < \delta\), \(\mathord{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^*_{\{\alpha\}}} = \mathord{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^{\alpha}_{\{\alpha\}}}\). Note that ([itm:usual32ordering])–([dash]) hold for \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^*\). Define an increasing union of finite \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^*\)-closed sets \((S_n)_{n<\omega}\) recursively as follows. Take \(S_0=\emptyset\). Suppose we have defined the \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^*\)-closed sets \((S_k)_{k\leq n}\) such that each \(S_k\) contains \(f(0),\ldots,f(k-1)\) and \(S_j\) for \(j<k\). Let \(\alpha < \delta\) be such that \(\alpha+1\) contains \(S_n\). By ([IC]) (and ([itm:order32type]), i.e., the fact that closed 2-initial segments are finite), there is some finite \(S_{n+1} \subseteq \alpha+1\) which is \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^\alpha\)-closed (so also \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^*\)-closed) and contains \(S_n\) and \(f(n)\). Note that we have \(\bigcup_{n<\omega}S_n=\delta\).

Fix some \(n<\omega\). Suppose that \(m = |S_{n+1} \setminus S_n|\). By induction on \(i\leq m\) define a strictly increasing sequence of injective functions (enumerations) \(f_i:i\to S_{n+1} \setminus S_n\) such that for all \(i<m\), \(S_n \cup \mathop{\mathrm{Im}}(f_i)\) is \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^*\)-closed (where \(\mathop{\mathrm{Im}}(f_i)\) is the image of \(f_i\)).

For \(i=0\), this is possible since \(S_n\) is \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^*\)-closed. Given \(f_i\) for \(i<m\), define the following binary relation on \(S_{n+1}\setminus \mathop{\mathrm{Im}}(f_i)\): \(x \preceq y\) if and only if \(S_n \cup \mathop{\mathrm{Im}}(f_i) \cup \{y\} \vdash x\). Note that \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}\) is antisymmetric: if \(x\preceq y\) and \(y \preceq x\) then \(x=y\) by ([dash]) (applied to the \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^*\)-closed set \(S_n \cup \mathop{\mathrm{Im}}(f_i)\)). It is also clearly transitive, so it is a partial order on a finite set and thus has a minimal element \(x_0\), and let \(f_{i+1}(i)=x_0\). Let us show that \(S_n \cup \mathop{\mathrm{Im}}(f_{i+1}) = S_n \cup \mathop{\mathrm{Im}}(f_i) \cup {\{x_0\}}\) is \(\prec^*\)-closed. Indeed, define the closure \(\mathop{\mathrm{cl}}(S_n \cup \mathop{\mathrm{Im}}(f_{i+1}))\) as the intersection of all \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^*\)-closed sets containing it (note that \(S_{n+1}\) is closed, so this closure is finite and contained in \(S_{n+1}\)). Clearly \(\mathop{\mathrm{cl}}(S_n \cup \mathop{\mathrm{Im}}(f_{i+1}))\) is \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^*\)-closed and contains \(S_n \cup \mathop{\mathrm{Im}}(f_{i+1})\). If \(y \in \mathop{\mathrm{cl}}(S_n \cup \mathop{\mathrm{Im}}(f_{i+1})) \setminus (S_n \cup \mathop{\mathrm{Im}}(f_{i+1}))\) then \(y \preceq x_0\) and \(y \neq x_0\), contradicting the minimality of \(x_0\). Thus, \(\mathop{\mathrm{cl}}(S_n \cup \mathop{\mathrm{Im}}(f_{i+1})) = S_n \cup \mathop{\mathrm{Im}}(f_{i+1})\) and the latter is \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^*\)-closed as required.

Being done with the inductive construction, let \(f^n = \bigcup_{i\leq m} f_i\); it is an enumeration of \(S_{n+1} \setminus S_n\). For \(x <\delta\), let \(n_x = \max \{n<\omega : x\notin S_n\}\).

Finally define \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_{\{\delta\}}\) by \(x\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_{\{\delta\}} y\) if and only if \(n_x < n_y\) or \(n=n_x = n_y\) and \((f^{n})^{-1}(x) < (f^{n})^{-1}(y)\) (i.e., \(x\) appears before \(y\) in the enumeration given by \(f^n\)). Note that any initial segment of \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_{\{\delta\}}\) is \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^*\)-closed.

Let us check that ([itm:usual32ordering])–([dash]) hold. ([itm:usual32ordering]), ([itm:increasing]) are clear and ([itm:order32type]) holds since every initial segment of the linear order \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_{\{\delta\}}\) is finite (so that the order type of \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_{\{\delta\}}\) is \(\omega\)).

We show ([IC]). Suppose that \(D = \{x<\delta : x\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_{\{\alpha\}} \beta\} \cup \{\alpha,\beta\}\) for some \(\beta<\alpha\leq \delta\) is a closed 2-initial segment of \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^\delta\). If \(\alpha<\delta\), \(D\) is \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^*\)-closed (so also \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^\delta\)-closed) by the induction hypothesis, so suppose that \(\alpha = \delta\). We are given \(\gamma_2,\varepsilon<\gamma_1 \leq \delta\) such that \(\gamma_1,\gamma_2 \in D\) and \(\varepsilon\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_{\{\gamma_1\}} \gamma_2\) and we have to show that \(\varepsilon \in D\). If \(\gamma_1 = \delta\), this follows directly from the definition of \(D\), so we may assume that \(\gamma_1 < \delta\). But since \(D \cap \delta\) is an initial segment of \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_{\{\delta\}}\), it is \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^*\)-closed, so \(\varepsilon \in D\) as required.

Finally we show ([dash]). Suppose that \(S \subseteq \delta\) is finite and \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^\delta\)-closed, and \(\alpha\neq \beta \in \delta \setminus S\). Then, \(S \cup \{\alpha,\beta\} \subseteq \gamma < \delta\), and hence this follows from the induction hypothesis applied to \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^\gamma\). ◻

Proof. By induction on \(n\). We first set \(\mathord{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}}_\emptyset\) to be some linear order on \(X\) of order type \(|X|\). If \(n=0\) then we are done. Otherwise, since the set \(X_{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_{\emptyset}x_0}\) has cardinality at most \(\theta^{+(n-1)}\) for every \(x_0\in X\), we can apply the induction hypothesis to get an \(n\)-ordering systems \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^{x_0}\) on each of these sets of order type bounded by \((\theta^{+(n-1)},...,\theta)\), and so for \(s\in [X]^{<n}\setminus\{\emptyset\}\) we define \(\mathord{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}}_{s}=\mathord{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}}^{x_0}_{s\setminus \{x_0\}}\), where \(x_0=\max_{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_\emptyset}s\). ◻

Proof. Fix such an ordering system \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}\) and fix \(A\in[\theta^{+n}]^{<\theta}\). Define \(A=A_0\), and given that we have defined \(A_k\) for some \(k<\omega\), define:

\[A_{k+1}=A_k\cup\bigcup\left\{\{x\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_s \alpha\}:\alpha\in \mathord{\operatorname{dom}}\left(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_s\right)\cap A_k,s\in [A_k]^n\right\}.\]

By definition we have \(|A_0|<\theta\), and by induction, the order type bound assumption and the regularity of \(\theta\), it follows that \(|A_{k+1}|<\theta\). Take \(A_\omega=\bigcup_{k<\omega}A_k\) hence \(|A_\omega|<\theta\) by the regularity and uncountability of \(\theta\). Clearly it is \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}\)-closed. Hence \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}\) has \(\theta\)-closures. For the second part, apply 26 [exists] to the first part. ◻

Proof. Assume otherwise. Let \((\kappa_\alpha:\alpha<\lambda)\) be a strictly increasing sequence of cardinals with \(\bigcup_{\alpha<\lambda}\kappa_\alpha=\theta\). Then there are \(A_\alpha\in[\theta]^{<\lambda^+}\) for \(\alpha<\lambda\) such that the minimal cardinality of a set \(B_\alpha\in\mathcal{F}\) with \(A_\alpha\subseteq B_\alpha\) is greater than \(\kappa_\alpha\). Let \(A=\bigcup_{\alpha<\lambda}A_\alpha\), so it is of size \(\leq \lambda\) as well, hence there is some \(B\in\mathcal{F}\) with \(A\subseteq B\). Since \((\kappa_\alpha:\alpha<\lambda)\) is cofinal in \(\theta\) and \(|B|<\theta\), there is some \(\alpha<\lambda\) with \(|B|<\kappa_\alpha\). But \(A_\alpha\subseteq A\subseteq B_\alpha\), a contradiction to our choice of \(A_\alpha\). ◻

Proof. Let \(\mathcal{F}\) be as above. Apply 32 to get some \(\kappa\) and \(\mathcal{F}_0\subseteq\mathcal{F}\) as there. Since \(\theta\) is singular, it is a limit cardinal, and because \(\kappa<\theta\) we get \(\kappa^{+n}<\theta\) for every \(n<\omega\). Let \(\mathcal{F}_0' = \{s \cap \kappa^{+n} : s\in \mathcal{F}_0\}\). Assuming towards a contradiction that \(\mathop{\mathrm{VC}}(\mathcal{F})=n<\omega\), and in particular \(\mathop{\mathrm{VC}}(\mathcal{F}_0')\leq n\) by 12. This gives us \(\mathop{\mathrm{VCcof}}(\omega,\kappa,\kappa^{+n})<n+1\), a contradiction to 13. ◻

Proof. Let \(\theta\) be measurable and let \(\mathbb{P}\) be the forcing notion of 34. Since \(\theta\) is measurable, it is regular, so by 31 for every \(n<\omega\) there is some \(\mathcal{F}_n\) witnessing \(\mathop{\mathrm{VCcof}}(\theta,\theta,\theta^{+n})=n+1\). Let \(G\subseteq\mathbb{P}\) be a generic filter and fix \(n<\omega\). By 34 the cardinal \(\theta\) is singular and of cofinality \(\omega\) in \(V[G]\), and the \(n\)’th successor of \(\theta\) in \(V[G]\) is its \(n\)’th successor in \(V\), so it remains to show that \(\mathcal{F}_n\) is \(\omega\)-cofinal and \(\mathop{\mathrm{VC}}(\mathcal{F}_n)=n+1\). For the first of these, forcing cannot add a new finite subset to an existing set, so by the \(\theta\)-cofinality of \(\mathcal{F}_n\) in \(V\) we get \(\omega\)-cofinality in \(V[G]\). The latter follows from absoluteness, hence we are done. ◻

Proof. We may assume \(t\neq \emptyset\). By the definition of \(\mathord{\operatorname{predom}}\), the lemma would follow once we prove that \(\mathop{\mathrm{MIN}}_{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}}(t\cup\{x_0\})=\mathop{\mathrm{MIN}}_{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^{x_0}}t\). Writing \(m\) for the latter, we get: \[m\in\mathord{\operatorname{dom}}(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^{x_0}_{t\setminus\{m\}})=\mathord{\operatorname{dom}}(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_{(t\cup\{x_0\})\setminus\{m\}}),\] which is the definition of \(\mathop{\mathrm{MIN}}_{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^{x_0}}t\). ◻

Proof. By induction on \(n\), with the case of \(n=1\) being the definition of a 2-ordering system. Suppose \(n>1\) and fix \(x_0\in X\). In order to show that \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}'\) is an \((n+1)\)-ordering system on \(X\), we must show that \((\prec\mathrel{\mkern-5mu}\mathrel{\cdot}')^{x_0}\) is an \(n\)-ordering system on \(\mathord{\operatorname{dom}}(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_{x_0})\).

Now, the assignment \((\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^{x_0})':[\mathord{\operatorname{dom}}(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_{\{x_0\}})]^{<n-1}\rightarrow \mathcal{P}([\mathord{\operatorname{dom}}(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^{x_0})]^2)\) extending \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^{x_0}\) and assigning to each \(t\in[\mathord{\operatorname{dom}}(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_{\{x_0\}})]^{n-1}\) the orderings \(\mathord{<'}_t:=\mathord{<}_{t\cup\{x_0\}}\) on each \(\mathord{\operatorname{predom}}(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_{t\cup \{x_0\}})\) (which is equal to \(\mathord{\operatorname{predom}}(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^{x_0}_t)\) by 40) is an \(n\)-ordering system on \(\mathord{\operatorname{dom}}(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_{\{x_0\}})\) by the induction hypothesis, which is exactly the assignment \((\prec\mathrel{\mkern-5mu}\mathrel{\cdot}')^{x_0}\). Thus the proof is complete. ◻

Proof. By induction on \(n\). We set \(\mathord{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_\emptyset}=\mathord{<^X}\). If \(n=1\) we are done. Otherwise, since the initial segment \(X_{<^X x_0}\) has cardinality at most \(\aleph_{n-1}\geq \aleph_1\) for any \(x_0\in X\), we fix a well-ordering \(<_{x_0}\) of order type at most \(\omega_{n-1}\) on each \(X_{<^X x_0}\), such that \(\omega^{<^X}\cap X_{<^{X} x_0}\) is an initial segment of \((X_{<^{X} x_0},<_{x_0})\) with both \(<^X,<_{x_0}\) agreeing on \(\omega^{<^X}\cap X_{<^{X} x_0}\). Thus, we have that \(\omega^{<_{x_0}}\) is an initial segment of \(\omega^{<^X}\). Applying the induction hypothesis to \((X_{<^X x_0},<_{x_0})\) for every \(x_0\) gives us nice \((n-1)\)-ordering systems \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^{x_0}\) on each of these sets of order type bounded by \((\omega_{n-1},...,\omega_1)\), and so for \(s\in [X]^{<n}\setminus\{\emptyset\}\) we define \(\mathord{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_s}=\mathord{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^{x_0}_{s\setminus\{x_0\}}}\), where \(x_0=\max_{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_\emptyset}s\). ◻

Proof. Fix \(s\in[X]^{\leq n}\setminus\{\emptyset\}\). The case of \(|s|=1\) is immediate, so assume \(|s|>1\) and write \(x_0=\max_{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_\emptyset} s\). We also write \(k=\min\{|\mathord{\operatorname{dom}}(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_{\{x_0\}})|,\omega\}\).

We will prove the lemma by induction on \(n\), where the case \(n=1\) follows from the case \(|s|=1\).

For \(n>1\) we have \(\mathord{\operatorname{predom}}(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^{x_0}_{s\setminus\{x_0\}})=\mathord{\operatorname{predom}}(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_s)\) by 40. By the induction hypothesis and since \(k^{<^X}=k^{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^{x_0}}\) by niceness, we first of all get that if the former is finite then \(\mathord{\operatorname{predom}}(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_s)=\left\{x\in X: x<^X \min((s\setminus\{x_0\})\cap \omega^{<^X})\right\}\) (where here we use that niceness gives \(\mathord{<}^X=\mathord{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}}_{x_0}\) on \(\omega^{<^X}\)). We also get that \(\mathord{\operatorname{predom}}(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_s)\) is finite if and only if \((s\setminus\{x_0\})\cap \omega^{<^X}\neq\emptyset\). We now finish both parts by noting that if \(\mathord{\operatorname{predom}}(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_s)\) is finite then since \(|s|\geq 2\), any \(y\in s\setminus\{x_0\}\) must satisfy \(y\prec\mathrel{\mkern-5mu}\mathrel{\cdot}x_0\) by maximality, implying both that \(\min((s\setminus\{x_0\}\cap\omega^{<^X})=\min(s\cap \omega^{<^X})\) and that if \(s\cap\omega^{<^X}\neq\emptyset\) then \(s\setminus\{x_0\}\cap\omega^{<^X}\neq\emptyset\). This finishes the proofs of both parts of the lemma. ◻

Proof. Write \(y=\mathop{\mathrm{MIN}}_{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}}s\) and \(s'=s\setminus\{y\}\). By definition we have that \(\mathord{\operatorname{predom}}(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_s)\) is an initial segment of the ordering \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_{s'}\) on the set \(\mathord{\operatorname{dom}}(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_{s'})\), which contains \(\omega^{<^X}\) as an initial segment of order type \(\omega\) by niceness. Since any infinite initial segment of a well-order contains its first \(\omega\) elements, the result follows. ◻

Proof. Given \(s\in[\omega_n]^{n}\) we write \(y=\mathop{\mathrm{MIN}}_{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}}s\) and \(s'=s\setminus\{y\}\). By the assumption on the bound of the order type of \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}\) we have \(\mathop{\mathrm{otp}}(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_{s'})\leq \omega_1\) hence every initial segment is at most countable. ◻

Proof. Let \(B,p\) be as above. Let \(G\subseteq\mathcal{Q}\) be a generic filter containing \(p\) and \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^{G}\) the corresponding \((n+1)\)-ordering system as in 55. Suppose \(t\in[B]^n\), \(\alpha,\beta\in\mathord{\operatorname{dom}}(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^G_t)=\mathord{\operatorname{predom}}(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_t)\) and \(\alpha\in B\) satisfy \(\beta\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^G_t\alpha\). Assume first that \(t\notin\mathop{\mathrm{Inf}}_{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}}\), so \(\mathord{\operatorname{predom}}(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_t)\in\omega\) by 45 and the first bullet of 55, \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^G_t\) is the usual ordering on this natural number. Thus, by ([jt1]) we have \(\beta\in B\). Consider now the case \(t\in\mathop{\mathrm{Inf}}_{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}}\), meaning \(g_t(\beta)<g_t(\alpha)\). Since \(\alpha\in \mathord{\operatorname{predom}}(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_t)\cap B\) we have \(\alpha\in\mathord{\operatorname{dom}}(p_t)\) by ([jt2]), and so ([jt3]) and the injectivity part of 53 gives us \(\beta\in \mathord{\operatorname{dom}}(p_t)\) and hence \(\beta\in B\) by ([jt2]). More explicitly, by 53 there is some \(q\in G\) such that \((\beta,t) \in \mathord{\operatorname{dom}}(q)\). Additionally, by ([jt2]) there is some \(\beta'\in \mathord{\operatorname{dom}}(p_t)\) such that \(p_t(\beta')=g_t(\beta)\). Since \(G\) is a filter, \(p\) and \(q\) are compatible, i.e., there is some \(r\in G\) containing both. So \(p_t(\beta') = g_t(\beta) = r_t(\beta)\) so \(\beta = \beta'\) because \(r_t\) is injective. ◻

Proof. Given a condition \(r\in \mathcal{Q}\), write \(\mathop{\mathrm{Inf}}_{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}}^{r}\) for the set of all \(s\in\mathop{\mathrm{Inf}}_{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}}\) such that \(\mathop{\mathrm{Im}}(r_s)\neq\emptyset\). Our proof will, for each \(1\leq i\leq 5\), construct \(q_i\in \mathcal{Q}\) and \(B_i\in[\omega_n]^{<\omega}\) such that the items \((1),...,(i)\) hold, and then \(q=q_5\), \(B=B_5\) will satisfy the conclusion. Assume without loss of generality that \(p\) is not the empty condition. We start by setting \(q_1=p\) and \(B_1=A\). We now set \(q_2=q_1\) and \(B_2=B_1\cup \bigcup(B_1\cap \omega)\), so that ([J1]) and ([J2]) both hold.

To each \(s\in\mathop{\mathrm{Inf}}_{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}}^{q_2}\) we associate the set \(X_s=\max\{\mathop{\mathrm{Im}}(q_2)_s\}\setminus\mathop{\mathrm{Im}}(q_2)_s\) and write \(j_s=|X_s|\). We now write \(X_s=\{m^s_0,...,m^s_{j_{s-1}}\}\). Let \(\{n^s_0,...n^s_{j_{s-1}}\}\) denote the first \(j_s\) elements of \(\omega\setminus\mathord{\operatorname{dom}}(q_2)_s\), and define \(q_3=q_2\cup\{(n^s_i,s;m^s_i):s\in\mathop{\mathrm{Inf}}_{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}}^{q_2},i< j_s\}\) (note that by 46 the elements \(n^s_i\) are elements of \(\mathord{\operatorname{predom}}(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_s)\)) and \(B_3=B_2\). By our choice of \(m_i\) the functions \(q_s\) are still injective, meaning \(q_3\in \mathcal{Q}\) and ([J1]) clearly holds. Trivially ([J2]) still holds. By definition of \(X_s\) and \(q_3\) we have that \(\mathop{\mathrm{Im}}(q_3)_s=\mathop{\mathrm{Im}}(q_2)_s\cup X_s\) is an initial segment of \(\omega\), so ([J3]) holds for all \(s\in\mathop{\mathrm{Inf}}_{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}}^{q_2}=\mathop{\mathrm{Inf}}_{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}}^{q_3}\), and so the same holds for all \(s\in\mathop{\mathrm{Inf}}_{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}}\) (for any \(s\notin\mathop{\mathrm{Inf}}_{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}}^{q_3}\) we trivially have that \(\mathop{\mathrm{Im}}(q_3)_s\) is an initial segment of \(\omega\)).

To every \(s\in\mathop{\mathrm{Inf}}_{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}}^{q_3}\) we set \(\{a^s_0,...,a^s_{l_s-1}\}=\mathord{\operatorname{dom}}(q_3)_s\setminus B_3\) for \(l_s=|\mathord{\operatorname{dom}}(q_3)_s\setminus B_3|\). We now define \(q_4=q_3\), \(B_4'=B_4\cup\{a^s_i:s\in\mathop{\mathrm{Inf}}_{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}}^{q_4},i<l_s\}\) and \(B_4=B_4'\cup \bigcup(B_4'\cap\omega)\). We have that ([J2]) holds by definition of \(B_4\), and since \(q_4=q_3\) we have that ([J1]) and ([J3]) both hold. By choice of \(a^s_i\) we have that ([J4]) holds for all \(s\in\mathop{\mathrm{Inf}}_{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}}^{q_3}\), and so the same holds for all \(s\in\mathop{\mathrm{Inf}}_{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}}\) (for any \(s\notin\mathop{\mathrm{Inf}}_{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}}^{q_3}\) we clearly have \(\mathord{\operatorname{dom}}(q_3)\subseteq\mathord{\operatorname{predom}}(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_s)\cap B\).

Finally, for any \(s\in\mathop{\mathrm{Inf}}_{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}}(B_4)\), write \(\{x^s_0,...,x^s_{m_s -1}\}\) for the elements of the set \((\mathord{\operatorname{predom}}(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}_s)\cap B_4)\setminus\mathord{\operatorname{dom}}(q_4)_s\) and \(\{y^s_0,...,y^s_{m_s -1}\}\) for the first \(m_s-1\) elements of \(\omega\setminus \mathop{\mathrm{Im}}(q_4)_s\), and set \(B_5=B_4\) and \(q_5=q_4\cup\{(x^s_i,s;y^s_i):s\in\inf_{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}}(B),i<m_s-1\}\). We have that ([J1]), ([J2]) hold by induction. For \(s\in\mathop{\mathrm{Inf}}_{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}}\setminus\mathop{\mathrm{Inf}}_{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}}(B_5)\) we have that ([J3]) and ([J4]) hold because \((q_4)_s=(q_5)_s\). and for \(s\in\mathop{\mathrm{Inf}}_{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}}(B_5)\) by choice of \(x^s_i,y^s_i\). To finish, ([J5]) also holds by choice of \(x^s_i\). ◻

Proof of 56. Fix \(A\in[\omega_n]^{<\omega}\). We will show that the set \(D_A\) of conditions which force that \(A\) is contained in a finite \(\dot{\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^G}\)-closed set \(B\in[\omega_n]^{<\omega}\) is dense in \(\mathcal{Q}\). Fix \(p\in\mathcal{Q}\). Let \((B,q)\) be a pair given by applying 59 to \((A,p)\), so in particular it satisfies the conditions of 58, hence \(q\) forces that \(B\) is closed. Since \(B\) is finite and contains \(A\), the result follows. ◻

Proof. Let \(G\subseteq\mathcal{Q}\) be generic, then \(V[G]\) and \(V\) have the same cardinals by 52 and \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^G\) is an \((n+1)\)-ordering system on \(\omega_n\) with finite closures by 56. The collection of finite \(\prec\mathrel{\mkern-5mu}\mathrel{\cdot}^G\)-closed sets has VC-dimension \(n+1\) by 25, so we finish by 26. ◻