Infinite-dimensional Ramsey theory for homogeneous structures with SDAP⁺

Natasha Dobrinen Department of Mathematics
University of Notre Dame
255 Hurley Bldg
Notre Dame, IN 46556 U.S.A. [email protected]

Abstract.

We prove that for any homogeneous structure $\mathbf{K}$ in a language with finitely many relation symbols of arity at most two satisfying SDAP⁺ (or LSDAP⁺), there are spaces of subcopies of $\mathbf{K}$ , forming subspaces of the Baire space, in which all Borel sets are Ramsey. Structures satisfying SDAP⁺ include the rationals, the Rado graph and more generally, unrestricted structures, and generic $k$ -partite graphs, the latter three types with or without an additional dense linear order. As a corollary of the main theorem, we obtain an analogue of the Nash-Williams Theorem which recovers exact big Ramsey degrees for these structures, answering a question raised by Todorcevic at the 2019 Luminy Workshop on Set Theory. Moreover, for the rationals and similar homogeneous structures our methods produce topological Ramsey spaces, thus satisfying analogues of the Ellentuck theorem.

2020 Mathematics Subject Classification:

05D10, 05C55, 05C15, 05C05, 03C15, 03E75

This research was supported by National Science Foundation Grant DMS-1901753

1. Introduction

Ramsey theory was initiated by the following celebrated result.

Theorem 1.1 (Ramsey [13]).

Given a positive integer $k$ , suppose that $[\mathbb{N}]^{k}$ , the collection of all $k$ -element subsets of the natural numbers, is partitioned into finitely many pieces. Then there is an infinite subset $N\subseteq\mathbb{N}$ such that $[N]^{k}$ is contained in one piece of the partition.

Extensions of Ramsey’s Theorem to colorings of infinite subsets of $\mathbb{N}$ have been proved, subject to constraints necessitated by the Axiom of Choice. Considering the set of all infinite subsets of the natural numbers, denoted by $[\mathbb{N}]^{\mathbb{N}}$ , as the Baire space with its metric topology, a set $\mathcal{X}\subseteq[\mathbb{N}]^{\mathbb{N}}$ is called Ramsey if for each $M\in[\mathbb{N}]^{\mathbb{N}}$ , there is an $N\in[M]^{\mathbb{N}}$ such that either $[N]^{\mathbb{N}}\subseteq\mathcal{X}$ or else $[N]^{\mathbb{N}}\cap\mathcal{X}=\emptyset$ . From 1965 through 1974, a beautiful progression of results was obtained using topological properties to guarantee that certain subsets of the Baire space are Ramsey. Nash-Williams proved that clopen sets are Ramsey in [12]; Galvin and Prikry proved that Borel sets are Ramsey in [8]; and Silver extended this to analytic sets in [15]. This line of work culminated in the topological characterization of Ramsey sets found by Ellentuck in [7] in terms of a topology refining the metric topology on $[\mathbb{N}]^{\mathbb{N}}$ , now referred to as the Ellentuck topology.

This paper is focused on developing analogues of the Galvin–Prikry and Ellentuck Theorems for topological spaces of subcopies of a given Fraïssé structure. This line of inquiry was highlighted in Section 11 of [9], by Kechris, Pestov, and Todorcevic. Specifically, they asked for the development of infinite-dimensional Ramsey theory of the form $\mathbf{K}\rightarrow_{*}(\mathbf{K})^{\mathbf{K}}_{\ell,t}$ , where $\mathbf{K}$ is the Fraïssé limit of some Fraïssé class and $\rightarrow_{*}$ means that the partitions of ${\mathbf{K}\choose\mathbf{K}}$ are required to be definable in some sense.

Identifying the universe of $\mathbf{K}$ with $\mathbb{N}$ , one can view the set of all subcopies of $\mathbf{K}$ as the subspace of the Baire space corresponding to the set of universes of subcopies of $\mathbf{K}$ . In [4], the author proved an infinite-dimensional Ramsey theorem for certain topological spaces of subcopies of the Rado graph. At the 2019 Luminy Workshop on Set Theory, Todorcevic asked the author whether the infinite-dimensional Ramsey theorem would directly recover the exact big Ramsey degrees of the Rado graph. The approach in [4] directly recovers exact big Ramsey degrees for vertex, edge, and non-edge colorings, but does not directly recover exact big Ramsey degrees for most graphs with three or more vertices. Thus, the first motivation for this paper was to develop infinite-dimensional Ramsey theory for the Rado graph which would directly recover known exact big Ramsey degrees from a Nash-Williams style corollary. This is done in Corollary 6.5.

The second motivation for this paper was to develop infinite-dimensional Ramsey theory for a large collection of Fraïssé structures for which exact big Ramsey degrees are already known, thus making progress on the question of Kechris, Pestov, and Todorcevic discussed above. The Main Theorem of this paper, Theorem 6.3, develops infinite-dimensional Ramsey theory for all Fraïssé structures with finitely many relations of arity at most two satisfying amalgamation properties called SDAP⁺ and LSDAP⁺, developed by Coulson, Dobrinen, and Patel in [2] and [3] to prove exact big Ramsey degrees with a simple characterization in terms of diagonal antichains in coding trees of $1$ -types (see Theorem 2.24). The class of homogeneous structures satisfying SDAP⁺ includes the rationals and the rationals with an equivalence relation with finitely many dense equivalence classes, as well as the Rado graph, generic $n$ -partite graphs, the generic tournament and digraph, more generally unrestricted structures with finitely many binary relations, as well as versions of these with an additional linear order forming a dense linear order on the Fraïssé limit. The class of LSDAP⁺ structures includes the rationals with a convex equivalence relation and a natural hiearchy of such structures with successively coarser convex equivalence relations. (See Section 5 of [3] for a catalogue of SDAP⁺ and LSDAP⁺ structures and their big Ramsey degree results.)

The infinite-dimensional Ramsey theorem in this paper recovers the big Ramsey degrees proved in [3] for SDAP⁺ and LSDAP⁺ structures in the following manner: For each diagonal antichain $A$ representing a finite substructure $\mathbf{A}$ of $\mathbf{K}$ , Corollary 6.5 shows that given any finite coloring of the copies of $\mathbf{A}$ in $\mathbf{K}$ , there is a subcopy of $\mathbf{K}$ in which all copies of $\mathbf{A}$ represented by the similarity type of $A$ have the same color. Note that the lower bound argument in [3] showing that each diagonal antichain representing $\mathbf{A}$ persists in each subcopy of $\mathbf{K}$ does not follow from the infinite-dimensional Ramsey theory in this paper. Rather, given that result, we can conclude that Corollary 6.5 recovers exact big Ramsey degrees.

We remark on the necessity (in one form or another) of diagonal coding antichains and similarity types for infinite dimensional Ramsey theory. In the context of Countable Choice, one can well-order the vertices of a countably infinite structure $\mathbf{K}$ in order type $\omega$ ; that is, we may assume that the universe of $\mathbf{K}$ is $\mathbf{N}$ . Since our language is countable, we can linearly order its symbols. Taken together, these automatically induce a coding tree of $1$ -types representing $\mathbf{K}$ . Big Ramsey degrees of Fraïssé structures present constraints for the development of infinite-dimensional structural Ramsey theory. A Fraïssé limit $\mathbf{K}$ of a Fraïssé class $\mathcal{K}$ is said to have finite big Ramsey degrees if for each $\mathbf{A}\in\mathcal{K}$ , there is some positive integer $t$ such that for each $\ell\geq 2$ ,

(1)

\mathbf{K}\rightarrow(\mathbf{K})^{\mathbf{A}}_{\ell,t}.

This is the structural analogue of the infinite Ramsey Theorem 1.1. When such a $t$ exists for a given $\mathbf{A}$ , using the conventions in [9], $T(\mathbf{A},\mathcal{K})$ denotes the minimal such $t$ and is called the big Ramsey degree of $\mathbf{A}$ in $\mathbf{K}$ . In all known cases, the big Ramsey degree $T(\mathbf{A},\mathbf{K})$ corresponds to a canonical partition of ${\mathbf{K}\choose\mathbf{A}}$ (the copies of $\mathbf{A}$ in $\mathbf{K}$ ) into $T(\mathbf{A},\mathbf{K})$ many pieces each of which is persistent, meaning that for any member $\mathbf{M}$ of ${\mathbf{K}\choose\mathbf{K}}$ , the set ${\mathbf{M}\choose\mathbf{A}}$ meets every piece in the partition. Through the view of coding trees of $1$ -types, canonical partitions for SDAP⁺ and LSDAP⁺ structures are characterized by finite diagonal coding antichains (see Theorem 2.24 and preceding definitions). It is useful to think of finite big Ramsey degrees as a structural Ramsey theorem where one finds an expanded structure which guarantees one color for all copies of $\mathbf{A}$ in that expansion. Big Ramsey degrees of size two or more present a fundamental constraint to the development of infinite-dimensional structural Ramsey theory: any infinite-dimensional theorem must restrict to a subspace of ${\mathbf{K}\choose\mathbf{K}}$ where all members have the same similarity type in the coding tree of $1$ -types.

Given any Fraïssé structure $\mathbf{K}$ satisfying SDAP⁺ or LSDAP⁺ with universe $\mathbb{N}$ , and given a subcopy $\mathbf{M}$ of $\mathbf{K}$ , let $\mathbf{K}(\mathbf{M})$ denote the collection of all $\mathbf{N}\in{\mathbf{M}\choose\mathbf{K}}$ with the same (induced) similarity type as $\mathbf{M}$ has as an enumerated substructure of $\mathbf{K}$ . (This space will be precisely defined in Section 6.) Note that $\mathbf{K}(\mathbf{M})$ is a topological space, identified with the subspace of the Baire space consisting of the universes of all structures in $\mathbf{K}(\mathbf{M})$ . The following is the main theorem of the paper.

Theorem 6.3.

Let $\mathbf{K}$ be an enumerated Fraïssé structure satisfying SDAP⁺ (or LSDAP⁺) with finitely many relations of arity at most two, and let $\mathbf{D}$ be a subcopy of $\mathbf{K}$ such that the subtree $\mathbb{D}$ of the coding tree of $1$ -types over $\mathbf{K}$ induced by the vertices in $\mathbf{D}$ is a good diagonal antichain. Then each Borel subset of $\mathbf{K}(\mathbf{D})$ is completely Ramsey, and hence Ramsey.

From the methods used in this paper, we immediately obtain the following stronger Ellentuck analogue for certain structures.

Theorem 6.4.

Let $\mathbf{K}$ be any one of the following structures with universe $\mathbb{N}$ : The rationals, $\mathbb{Q}_{n}$ , $\mathbb{Q}_{\mathbb{Q}}$ , and or any Fraïssé structure satisfying SDAP⁺ (or LSDAP⁺) for which the coding tree of $1$ -types $\mathbb{U}(\mathbf{K})$ has the property that on any given level of $\mathbb{U}(\mathbf{K})$ , only the coding node splits. Then the spaces $\mathcal{D}(\mathbb{D})$ , where $\mathbb{D}$ is a diagonal coding antichain for $\mathbf{K}$ , are actually topological Ramsey spaces.

The paper is orginized as follows: Background from [2] and [3] is presented in Section 2. Section 3 defines the spaces of diagonal coding antichains representing subcopies of a given homogeneous structure $\mathbf{K}$ . The pretext for our notation and set-up is Chapter 5 of Todorcevic’s book [16] on topological Ramsey spaces. Theorem 4.5 proves an Extended Pigeonhole Principle, a strong version of Todorcevic’s Axiom A.4. Theorem 5.17 proves a Galvin–Prikry style theorem for spaces of diagonal coding antichains with a metric topology. Theorem 6.3 in Section 6 interprets this back into natural subspaces of the Baire space, proving the main theorem of this paper. Corollary 6.5 answers a question of Todorcevic, showing that the Nash-Williams style corollary of our main theorem recovers big Ramsey degrees. Theorem 6.4 proves Ellentuck analogues for structures which have a certain amount of rigidity.

2. Background

This section reviews Fraïssé theory, amalgamation properties, and coding tree notions from [2].

2.1. Fraïssé theory and substructure amalgamation properties

In this paper, all languages $\mathcal{L}$ will consist of finitely many relation symbols $\{R_{i}:i<n\}$ , with the arity $k_{i}$ of $R_{i}$ being either $1$ or $2$ . An $\mathcal{L}$ -structure is an object $\mathbf{A}=\langle\mathrm{A},R^{\mathbf{A}}_{0},\dots,R^{\mathbf{A}}_{n-1}\rangle$ , where the universe of $\mathbf{A}$ , denoted by $\mathrm{A}$ , is non-empty and $R^{\mathbf{A}}_{i}\subseteq\mathrm{A}^{k_{i}}$ . Finite structures will be denoted by $\mathbf{A},\mathbf{B},\mathbf{C},\dots$ , and their universes by $\mathrm{A},\mathrm{B},\mathrm{C},\dots$ . Infinite structures will typically be denoted by $\mathbf{K},\mathbf{M},\mathbf{N},\dots$ , and their universes by $\mathrm{K},\mathrm{M},\mathrm{N},\dots$ . The elements of the universe of a structure will be called vertices.

With no loss of generality, we make the following assumptions: (a) $\mathcal{L}$ has at least one unary relation symbol. (b) Any structure $\mathbf{A}\in\mathcal{K}$ has the property that each vertex $v\in\mathrm{A}$ satisfies $R^{\mathbf{A}}(v)$ for exactly one unary relation symbol $R$ in $\mathcal{L}$ . (c) For each unary relation symbol $R\in\mathcal{L}$ , there is some $\mathbf{A}\in\mathcal{K}$ and a vertex $v\in\mathrm{A}$ such that $R^{\mathbf{A}}(v)$ . We say that the unary relations are non-trivial exactly when $\mathcal{L}$ has two or more unary relation symbols.

For $\mathcal{L}$ -structures $\mathbf{A}$ and $\mathbf{B}$ , an embedding $e:\mathbf{A}\rightarrow\mathbf{B}$ is an injection on their universes $e:\mathrm{A}\rightarrow\mathrm{B}$ with the property that for all $i<n$ ,

R_{i}^{\mathbf{A}}(a_{1},\dots,a_{n_{i}})\longleftrightarrow R_{i}^{\mathbf{B}}(e(a_{1}),\dots,e(a_{n_{i}}))

The $e$ -image of $\mathbf{A}$ is called a copy of $\mathbf{A}$ in $\mathbf{B}$ . If $e$ is the identity map, then $\mathbf{A}$ is a substructure of $\mathbf{B}$ . If $e$ is onto $\mathbf{B}$ then $e$ is an isomorphism and we say that $\mathbf{A}$ and $\mathbf{B}$ are isomorphic. We write $\mathbf{A}\leq\mathbf{B}$ exactly when there is an embedding of $\mathbf{A}$ into $\mathbf{B}$ , and $\mathbf{A}\cong\mathbf{B}$ exactly when there is an isomorphism from $\mathbf{A}$ onto $\mathbf{B}$ .

A class $\mathcal{K}$ of finite structures is called a Fraïssé class if it is nonempty, closed under isomorphisms, hereditary, and satisfies the joint embedding and amalgamation properties. $\mathcal{K}$ is hereditary if whenever $\mathbf{B}\in\mathcal{K}$ and $\mathbf{A}\leq\mathbf{B}$ , then also $\mathbf{A}\in\mathcal{K}$ . $\mathcal{K}$ satisfies the joint embedding property if for any $\mathbf{A},\mathbf{B}\in\mathcal{K}$ , there is a $\mathbf{C}\in\mathcal{K}$ such that $\mathbf{A}\leq\mathbf{C}$ and $\mathbf{B}\leq\mathbf{C}$ . $\mathcal{K}$ satisfies the amalgamation property if for any embeddings $f:\mathbf{A}\rightarrow\mathbf{B}$ and $g:\mathbf{A}\rightarrow\mathbf{C}$ , with $\mathbf{A},\mathbf{B},\mathbf{C}\in\mathcal{K}$ , there is a $\mathbf{D}\in\mathcal{K}$ and there are embeddings $r:\mathbf{B}\rightarrow\mathbf{D}$ and $s:\mathbf{C}\rightarrow\mathbf{D}$ such that $r\circ f=s\circ g$ . Note that in a finite relational language, there are only countably many finite structures up to isomorphism.

A Fraïssé class $\mathcal{K}$ satisfies the disjoint amalgamation property (DAP) if given $\mathbf{A},\mathbf{B},\mathbf{C}\in\mathcal{K}$ and embeddings $e:\mathbf{A}\rightarrow\mathbf{B}$ and $f:\mathbf{A}\rightarrow\mathbf{C}$ , there is some $\mathbf{D}\in\mathcal{K}$ and embeddings $e^{\prime}:\mathbf{B}\rightarrow\mathbf{D}$ and $f^{\prime}:\mathbf{C}\rightarrow\mathbf{D}$ such that $e^{\prime}\circ e=f^{\prime}\circ f$ , and $e^{\prime}[B]\cap f^{\prime}[C]=e^{\prime}\circ e[A]=f^{\prime}\circ f[A]$ . The DAP is often called the strong amalgamation property and is equivalent to the strong embedding property, which says that for any $\mathbf{A}\in\mathcal{K}$ , $v\in\mathrm{A}$ , and embedding $\varphi:(\mathbf{A}-v)\rightarrow\mathbf{K}$ , there are infinitely many different extensions of $\varphi$ to embeddings of $\mathbf{A}$ into $\mathbf{K}$ . (See [1].) We say that $\mathcal{K}$ satisfies the free amalgamation property (FAP) if it satisfies the DAP and moreover, $\mathbf{D}$ can be chosen so that $\mathbf{D}$ has no additional relations other than those inherited from $\mathbf{B}$ and $\mathbf{C}$ .

The following amalgamation properties, SFAP and SDAP, were first formulated in [2].

Definition 2.1 ([2]).

A Fraïssé class $\mathcal{K}$ has the Substructure Free Amalgamation Property (SFAP) if $\mathcal{K}$ has free amalgamation and given $\mathbf{A},\mathbf{B},\mathbf{C},\mathbf{D}\in\mathcal{K}$ , the following holds: Suppose

(1)

$\mathbf{A}$ is a substructure of $\mathbf{C}$ , where $\mathbf{C}$ extends $\mathbf{A}$ by two vertices, say $\mathrm{C}\setminus\mathrm{A}=\{v,w\}$ ;
(2)

$\mathbf{A}$ is a substructure of $\mathbf{B}$ and $\sigma$ and $\tau$ are $1$ -types over $\mathbf{B}$ with $\sigma\restriction\mathbf{A}=\operatorname{tp}(v/\mathbf{A})$ and $\tau\restriction\mathbf{A}=\operatorname{tp}(w/\mathbf{A})$ ; and
(3)

$\mathbf{B}$ is a substructure of $\mathbf{D}$ which extends $\mathbf{B}$ by one vertex, say $v^{\prime}$ , such that $\operatorname{tp}(v^{\prime}/\mathbf{B})=\sigma$ .

Then there is an $\mathbf{E}\in\mathcal{K}$ extending $\mathbf{D}$ by one vertex, say $w^{\prime}$ , such that $\operatorname{tp}(w^{\prime}/\mathbf{B})=\tau$ , $\mathbf{E}\restriction(\mathrm{A}\cup\{v^{\prime},w^{\prime}\})\cong\mathbf{C}$ , and $\mathbf{E}$ adds no other relations over $\mathrm{D}$ .

SFAP can be stated in terms of embeddings, but its formulation via substructures and $1$ -types is more closely aligned with its uses in the forcing proof in Section 4. In [2] it was remarked that SFAP is equivalent to free amalgamation along with a model-theoretic property that may be termed free 3-amalgamation, which is a special case of the disjoint 3-amalgamation property defined in [10]. Kruckman showed in [10] that if the age of a Fraïssé limit $\mathbf{K}$ has disjoint amalgamation and disjoint 3-amalgamation, then $\mathbf{K}$ exhibits a model-theoretic tameness property called simplicity.

The next amalgamation property extends SFAP to disjoint amalgamation classes.

Definition 2.2 ([2]).

A Fraïssé class $\mathcal{K}$ has the Substructure Disjoint Amalgamation Property (SDAP) if $\mathcal{K}$ has disjoint amalgamation, and the following holds: Given $\mathbf{A},\mathbf{C}\in\mathcal{K}$ , suppose that $\mathbf{A}$ is a substructure of $\mathbf{C}$ , where $\mathbf{C}$ extends $\mathbf{A}$ by two vertices, say $v$ and $w$ . Then there exist $\mathbf{A}^{\prime},\mathbf{C}^{\prime}\in\mathcal{K}$ , where $\mathbf{A}^{\prime}$ contains a copy of $\mathbf{A}$ as a substructure and $\mathbf{C}^{\prime}$ is a disjoint amalgamation of $\mathbf{A}^{\prime}$ and $\mathbf{C}$ over $\mathbf{A}$ , such that letting $v^{\prime},w^{\prime}$ denote the two vertices in $\mathrm{C}^{\prime}\setminus\mathrm{A}^{\prime}$ and assuming (1) and (2), the conclusion holds:

(1)

Suppose $\mathbf{B}\in\mathcal{K}$ is any structure containing $\mathbf{A}^{\prime}$ as a substructure, and let $\sigma$ and $\tau$ be $1$ -types over $\mathbf{B}$ satisfying $\sigma\restriction\mathbf{A}^{\prime}=\operatorname{tp}(v^{\prime}/\mathbf{A}^{\prime})$ and $\tau\restriction\mathbf{A}^{\prime}=\operatorname{tp}(w^{\prime}/\mathbf{A}^{\prime})$ .
(2)

Suppose $\mathbf{D}\in\mathcal{K}$ extends $\mathbf{B}$ by one vertex, say $v^{\prime\prime}$ , such that $\operatorname{tp}(v^{\prime\prime}/\mathbf{B})=\sigma$ .

Then there is an $\mathbf{E}\in\mathcal{K}$ extending $\mathbf{D}$ by one vertex, say $w^{\prime\prime}$ , such that $\operatorname{tp}(w^{\prime\prime}/\mathbf{B})=\tau$ and $\mathbf{E}\restriction(\mathrm{A}\cup\{v^{\prime\prime},w^{\prime\prime}\})\cong\mathbf{C}$ .

It is straightforward to see that SDAP implies SFAP (let $\mathbf{A}^{\prime}=\mathbf{A}$ and $\mathbf{C}^{\prime}=\mathbf{C}$ ), and that SFAP and SDAP are each preserved under free superposition. These two amalgamation properties were formulated by extracting properties of Fraïssé classes for which the forcing partial order in Theorem 4.5 can just be extension, from which simple characterizations of their big Ramsey degrees in [3] follow.

2.2. Coding trees of $1$ -types

This subsection reproduces notions from [2] which will be used throughout this paper. Given a Fraïssé class $\mathcal{K}$ , an enumerated Fraïssé structure is a Fraïssé limit $\mathbf{K}$ of $\mathcal{K}$ with universe $\mathbb{N}=\{0,1,2,\dots\}$ . For the sake of clarity, we use $v_{n}$ (rather than $n$ ) to denote the $n$ -th vertex of $\mathbf{K}$ . We let $\mathbf{K}_{n}$ denote $\mathbf{K}\restriction\{v_{i}:i<n\}$ , the restriction of $\mathbf{K}$ to its first $n$ vertices. All types will be quantifier-free 1-types, with variable $x$ , over some finite initial segment of $\mathbf{K}$ ; the notation “tp” denotes a complete quantifer-free 1-type. For $n\geq 1$ , a type over $\mathbf{K}_{n}$ must contain the formula $\neg(x=v_{i})$ for each $i<n$ . Given a type $s$ over $\mathbf{K}_{n}$ , for any $i<n$ , $s\restriction\mathbf{K}_{i}$ denotes the restriction of $s$ to parameters from $\mathbf{K}_{i}$ .

Definition 2.3 (The Coding Tree of $1$ -Types, [2]).

The coding tree of $1$ -types $\mathbb{S}(\mathbf{K})$ for an enumerated Fraïssé structure $\mathbf{K}$ is the set of all complete $1$ -types over initial segments of $\mathbf{K}$ along with a function $c:\mathbb{N}\rightarrow\mathbb{S}(\mathbf{K})$ such that $c(n)$ is the $1$ -type of $v_{n}$ over $\mathbf{K}_{n}$ . The tree-ordering is inclusion.

We will often write $\mathbb{S}$ and $c_{n}$ in place of $\mathbb{S}(\mathbf{K})$ and $c(n)$ , respectively. Let $\mathbb{S}(n)$ denote the collection of all $1$ -types $\operatorname{tp}(v_{i}/\mathbf{K}_{n})$ , where $i\geq n$ , and note that $c_{n}$ is a node in $\mathbb{S}(n)$ . The set $\mathbb{S}(0)$ consists of the $1$ -types over the empty structure $\mathbf{K}_{0}$ . A level set is a subset $X\subseteq\mathbb{S}(n)$ for some $n$ . For $s\in\mathbb{S}(n)$ , the immediate successors of $s$ are exactly those $t\in\mathbb{S}(n+1)$ such that $s\subseteq t$ . Each set $\mathbb{S}(n)$ is finite, since the language $\mathcal{L}$ has finitely many finitary relation symbols.

A node $s\in\mathbb{S}(n)$ has length $n+1$ , denoted by $|s|$ , and uniquely induces the sequence $\langle s(i):i<|s|\rangle$ defined as follows: $s(0)$ denotes the set of formulas in $s$ involving no parameters, and for $1\leq i<|s|$ , $s(i)$ denotes the set of those formulas in $s\restriction\mathbf{K}_{i}$ in which $v_{i-1}$ appears as the parameter. For $j<|s|$ , note that $\bigcup_{i\leq j}s(i)$ is the predecessor of $s$ in $\mathbb{S}(j)$ . For $\ell\leq|s|$ , we let $s\restriction\ell$ denote $\bigcup_{i<\ell}s(i)$ . Given $s,t\in\mathbb{S}$ , $s\wedge t$ denotes the meet of $s$ and $t$ , which is $s\restriction\mathbf{K}_{m}$ where $m$ is maximal such that $s\restriction\mathbf{K}_{m}=t\restriction\mathbf{K}_{m}$ .

Let $\Gamma$ denote $\mathbb{S}(0)$ , the set of complete $1$ -types over the empty set that are realized in $\mathbf{K}$ . For $\gamma\in\Gamma$ , we write “ $\gamma(v_{n})$ holds in $\mathbf{K}$ ” when $\gamma$ is the 1-type of $v_{n}$ over the empty set. The following modification of Definition 2.3 of $\mathbb{S}(\mathbf{K})$ is useful for Fraïssé classes which have both non-trivial unary relations and a linear order.

Definition 2.4 (The Unary-Colored Coding Tree of $1$ -Types, [2]).

Let $\mathcal{K}$ be a Fraïssé class in language $\mathcal{L}$ and $\mathbf{K}$ be an enumerated Fraïssé structure for $\mathcal{K}$ . For $n\in\mathbb{N}$ , let $c_{n}$ denote the $1$ -type of $v_{n}$ over $\mathbf{K}_{n}$ (exactly as in the definition of $\mathbb{S}(\mathbf{K})$ ). Let $\mathcal{L}^{-}$ denote the collection of all relation symbols in $\mathcal{L}$ of arity greater than one, and let $\mathbf{K}^{-}$ denote the reduct of $\mathbf{K}$ to $\mathcal{L}^{-}$ and $\mathbf{K}_{n}^{-}$ the reduct of $\mathbf{K}_{n}$ to $\mathcal{L}^{-}$ .

The $n$ -th level, denoted $\mathbb{U}(n)$ , is the collection of all $1$ -types $s$ over $\mathbf{K}^{-}_{n}$ in the language $\mathcal{L}^{-}$ such that for some $i\geq n$ , $v_{i}$ satisfies $s$ . Define $\mathbb{U}=\mathbb{U}(\mathbf{K})$ to be $\bigcup_{n<\omega}\mathbb{U}(n)$ . The tree-ordering on $\mathbb{U}$ is simply inclusion. The unary-colored coding tree of $1$ -types is the tree $\mathbb{U}$ along with the function $c:\omega\rightarrow\mathbb{U}$ such that $c(n)=c_{n}$ . Thus, $c_{n}$ is the $1$ -type (in the language $\mathcal{L}^{-}$ ) of $v_{n}$ in $\mathbb{U}(n)$ along with the additional “unary color” $\gamma\in\Gamma$ such that $\gamma(v_{n})$ holds in $\mathbf{K}$ .

Remark 2.5.

If $\mathcal{L}$ has no non-trivial unary relation symbols then $\mathbb{U}(\mathbf{K})=\mathbb{S}(\mathbf{K})$ . If $\mathcal{K}$ satisfies SFAP, it suffices to work in $\mathbb{S}(\mathbf{K})$ . The purpose of $\mathbb{U}(\mathbf{K})$ is to handle cases such as $\mathbb{Q}_{n}$ , the rationals with an equivalence relation with finitely many equivalence classes each of which is dense in the rationals.

2.3. Passing types and similarity

This subsection reproduces definitions from [2], with simplified versions given due to the fact that all relation symbols in this article have arity at most two. Throughout, fix $\mathbf{K}$ and let $\mathbb{S}$ denote $\mathbb{S}(\mathbf{K})$ . All of the instances of $\mathbb{S}$ in this subsection may be substituted with $\mathbb{U}:=\mathbb{U}(\mathbf{K})$ .

Definition 2.6 (Passing Type, [2]).

Given $s,t\in\mathbb{S}$ with $|s|<|t|$ , we call $t(|s|)$ the passing type of $t$ at $s$ . We also call $t(|s|)$ the passing type of $t$ at $c_{n}$ , where $n$ is the integer such that $|c_{n}|=|s|$ .

Note that passing types are partial $1$ -types which contain only binary relation symbols.

Definition 2.7 (Similarity of Passing Types, [2]).

Let $m,n\in\mathbb{N}$ , and let $f:\{v_{m},x\}\to\{v_{n},x\}$ be given by $f(v_{m})=v_{n}$ and $f(x)=x$ . Suppose $s,t\in\mathbb{S}$ are such that $|c_{m}|<|s|$ and $|c_{n}|<|t|$ . We write

(2)

s(c_{m})\sim t(c_{n})

when, given any relation symbol $R\in\mathcal{L}$ of arity two and ordered pair $(z_{0},z_{1})$ such that $\{z_{0},z_{1}\}=\{v_{m},x\}$ , it follows that $R(z_{0},z_{1})\in s(c_{m})$ if and only if $R(f(z_{0}),f(z_{1}))\in t(c_{n})$ . When $s(c_{m})\sim t(c_{n})$ holds, we say that the passing type of $s$ at $c_{m}$ is similar to the passing type of $t$ at $c_{n}$ .

It is clear that $\sim$ is an equivalence relation.

Definition 2.8.

Let $\mathbf{A}$ , $\mathbf{B}$ be finite substructures of $\mathbf{K}$ with universes $\langle v_{j_{i}}:i<n\rangle$ , $\langle v_{k_{i}}:i<n\rangle$ , respectively. Let $s\in\mathbb{S}(\ell)$ and $t\in\mathbb{S}(\ell^{\prime})$ , where $\ell\geq|c_{j_{n-1}}|+1$ and $\ell^{\prime}\geq|c_{k_{n-1}}|+1$ . We say that $s\restriction\mathbf{A}$ and $t\restriction\mathbf{B}$ are similar, and write $s\restriction\mathbf{A}\sim t\restriction\mathbf{B}$ , if and only if for each $i<n$ , $s(c_{j_{i}})\sim t(c_{k_{i}})$ .

Fact 2.9 ([2]).

Let $A=\langle v_{j_{i}}:i<n\rangle$ and $B=\langle v_{k_{i}}:i<n\rangle$ be sets of vertices in $\mathbf{K}$ , and let $\mathbf{A}:=\mathbf{K}\restriction A$ and $\mathbf{B}:=\mathbf{K}\restriction B$ . Then $\mathbf{A}$ and $\mathbf{B}$ are isomorphic as ordered substructures of $\mathbf{K}$ , if and only if

(1)

$c_{j_{i}}$ and $c_{k_{i}}$ contain the same parameter-free formulas, for each $i<n$ ; and
(2)

$c_{j_{i}}\restriction(\mathbf{K}\restriction\{v_{j_{m}}:m<i\})\sim c_{k_{i}}\restriction(\mathbf{K}\restriction\{v_{k_{m}}:m<i\})$ , for all $i<n$ .

A lexicographic order $\prec$ on $\mathbb{S}$ is induced by fixing a linear ordering on the relation symbols in $\mathcal{L}$ and their negations. We may assume that the negated relation symbols appear in the linear order before the relation symbols. Since any node of $\mathbb{S}$ is completely determined by such atomic and negated atomic formulas, this lexicographic order gives rise to a linear order on $\mathbb{S}$ , which we again denote by $\prec$ , with the following properties: If $s\subsetneq t$ , then $s\prec t$ . For any incomparable $s,t\in\mathbb{S}$ , if $|s\wedge t|=n$ , then $s\prec t$ if and only if $s\restriction(n+1)\prec t\restriction(n+1)$ . This order $\prec$ generalizes the lexicographic order for the case of binary relational structures in [14], [11], [6], [5], and [17].

Given $S\subseteq\mathbb{S}$ , let $\langle c^{S}_{i}:i<n\rangle$ enumerate the coding nodes in $S$ in increasing length, where $n\in\mathbb{N}\cup\{\mathbb{N}\}$ .

Definition 2.10 (Similarity Map, [2]).

Let $S$ and $T$ be meet-closed subsets of $\mathbb{S}$ . A function $f:S\rightarrow T$ is a similarity map of $S$ to $T$ if $f$ is a bijection and for all nodes $s,t\in\mathbb{S}$ , the following hold:

(1)

$f$ preserves $\prec$ : $s\prec t$ if and only if $f(s)\prec f(t)$ .
(2)

$f$ preserves meets, and hence splitting nodes: $f(s\wedge t)=f(s)\wedge f(t)$ .
(3)

$f$ preserves relative lengths: $|s|<|t|$ if and only if $|f(s)|<|f(t)|$ .
(4)

$f$ preserves initial segments: $s\subseteq t$ if and only if $f(s)\subseteq f(t)$ .
(5)

$f$ preserves coding nodes and their parameter-free formulas: Given $c_{i}^{S}\in S$ , then $f(c_{i}^{S})=c^{T}_{i}$ ; moreover, for $\gamma\in\Gamma$ , $\gamma(v^{S}_{i})$ holds in $\mathbf{K}$ if and only if $\gamma(v^{T}_{i})$ holds in $\mathbf{K}$ , where $v^{S}_{i}$ and $v^{T}_{i}$ are the vertices of $\mathbf{K}$ represented by coding nodes $c^{S}_{i}$ and $c^{T}_{i}$ , respectively.
(6)

$f$ preserves relative passing types: $s(c^{S}_{i})\sim f(s)(c^{T}_{i})$ , for all coding nodes $c^{S}_{i}$ in $S$ .

When there is a similarity map between $S$ and $T$ , we say that $S$ and $T$ are similar and write $S\sim T$ . Given a subtree $S$ of $\mathbb{S}$ , let $\operatorname{Sim}(S)$ denote the collection of all subtrees $T$ of $\mathbb{S}$ which are similar to $S$ . If $T^{\prime}\subseteq T$ and $f$ is a similarity map of $S$ to $T^{\prime}$ , then $f$ is called a similarity embedding of $S$ into $T$ .

2.4. The properties SDAP⁺ and LSDAP⁺

The property SDAP⁺ is a strengthening of SDAP, and LSDAP⁺ is a ‘labeled’ version of SDAP⁺.

Definition 2.11 (Subtree).

Let $T$ be a subset of $\mathbb{S}$ , and let $L$ be the set of lengths of coding nodes in $T$ and lengths of meets of two incomparable nodes (not necessarily coding nodes) in $T$ . Then $T$ is a subtree of $\mathbb{S}$ if $T$ is closed under meets and closed under initial segments with lengths in $L$ .

Definition 2.12 (Diagonal tree).

A subtree $T\subseteq\mathbb{S}$ is diagonal if each level of $T$ has at most one splitting node, each splitting node in $T$ has degree two (exactly two immediate successors), and coding node levels in $T$ have no splitting nodes.

Subtrees of $\mathbb{S}$ correspond to substructures of $\mathbf{K}$ , and vice versa for diagonal subtrees: Given a subtree $T\subseteq\mathbb{S}$ , let $N^{T}$ denote the set of natural numbers $n$ such that $c_{n}\in T$ ; let $\mathbf{K}\restriction T$ denote the substructure of $\mathbf{K}$ on universe $\{v_{n}:n\in N^{T}\}$ . We call $\mathbf{K}\restriction T$ the substructure of $\mathbf{K}$ represented by the coding nodes in $T$ , or simply the substructure represented by $T$ . In the reverse direction, given a substructure $\mathbf{M}\leq\mathbf{K}$ , let $\mathbb{S}\restriction\mathbf{M}$ denote the subtree of $\mathbb{S}$ induced by the meet-closure of the coding nodes $\{c_{n}:v_{n}\in\mathrm{M}\}$ , and call $\mathbb{S}\restriction\mathbf{M}$ the subtree of $\mathbb{S}$ induced by $\mathbf{J}$ . If $T$ is a diagonal subtree and $\mathbf{M}=\mathbf{K}\restriction T$ , then $\mathbb{S}\restriction\mathbf{M}=T$ , as $T$ being diagonal ensures that the coding nodes in $\mathbb{S}\restriction\mathbf{M}$ are exactly those in $T$ .

Given two substructures $\mathbf{A},\mathbf{B}$ of $\mathbf{K}$ , we write $\mathbf{A}\cong^{\omega}\mathbf{B}$ when there exists an $\mathcal{L}$ -isomorphism between $\mathbf{A}$ and $\mathbf{B}$ that preserves the linear order on their universes. It follows from Fact 2.9 that for any subtrees $S,T\subseteq\mathbb{S}$ , $S\sim T$ implies that $\mathbf{K}\restriction S\cong^{\omega}\mathbf{K}\restriction T$ .

Notation 2.13.

Given a diagonal subtree $T$ , let $\langle c^{T}_{n}:n<N\rangle$ denote the enumeration of the coding nodes in $T$ in order of increasing length, and let $\ell^{T}_{n}$ denote $|c^{T}_{n}|$ , the length of $c^{T}_{n}$ . For a finite subset $A\subseteq T$ , let

(3)

\ell_{A}=\max\{|t|:t\in A\}\mathrm{\ \ and\ \ }\max(A)=\{s\in A:|s|=\ell_{A}\}.

For any subset $A\subseteq T$ , let

(4)

A\restriction\ell=\{t\restriction\ell:t\in A\mathrm{\ and\ }|t|\geq\ell\}

and let

(5)

A\upharpoonleft\ell=\{t\in A:|t|<\ell\}\cup A\restriction\ell.

Thus, $A\restriction\ell$ is a level set, while $A\upharpoonleft\ell$ is the set of nodes in $A$ with length less than $\ell$ along with the truncation to $\ell$ of the nodes in $A$ of length at least $\ell$ . For $A,B\subseteq T$ , $B$ is an initial segment of $A$ if $B=A\upharpoonleft\ell$ for some $\ell$ equal to the length of some node in $A$ . In this case, we also say that $A$ end-extends (or just extends) $B$ . If $\ell$ is not the length of any node in $A$ , then $A\upharpoonleft\ell$ is not a subset of $A$ , but is a subset of $\widehat{A}$ , where $\widehat{A}$ denotes $\{t\restriction n:t\in A\mathrm{\ and\ }n\leq|t|\}$ . Given $t\in T$ at the level of a coding node in $T$ , $t$ has exactly one immediate successor in $\widehat{T}$ , which we denote by $t^{+}$ .

Given a substructure $\mathbf{M}$ of $\mathbf{K}$ , let $\mathbf{M}_{n}$ denote $\mathbf{M}$ restricted to its first $n$ vertices. A tree $T$ is perfect if each node in $T$ has at least two incomparable extensions in $T$ .

Definition 2.14 (Diagonal Coding Subtree).

A subtree $T\subseteq\mathbb{S}$ is called a diagonal coding subtree if $T$ is diagonal, perfect, $\mathbf{M}:=\mathbf{K}\restriction T\cong\mathbf{K}$ , and the following holds:

Suppose $s\in T$ with $|s|=\ell^{T}_{i-1}+1$ for some $i\geq 1$ , or else suppose $s$ is the stem of $T$ and let $i=0$ . Then for each $n>i$ and each $1$ -type $\tau$ over $\mathbf{K}_{n}$ such that $\tau\restriction\mathbf{K}_{i}\sim s$ , there is a $t\in T\restriction(\ell^{T}_{n-1}+1)$ extending $s$ such that $t\restriction\mathbf{M}_{n}\sim\tau$ .

Definition 2.15 (Diagonal Coding Tree Property, [2]).

A Fraïssé class $\mathcal{K}$ in language $\mathcal{L}$ satisfies the Diagonal Coding Tree Property (DCTP) if given any enumerated Fraïssé structure $\mathbf{K}$ for $\mathcal{K}$ , there is a diagonal coding subtree.

Definition 2.16 ( $+$ -Similarity, [2]).

Let $T$ be a diagonal coding tree for the Fraïssé limit $\mathbf{K}$ of a Fraïssé class $\mathcal{K}$ , and suppose $A$ and $B$ are finite subtrees of $T$ . We write $A\stackrel{{\scriptstyle+}}{{\sim}}B$ and say that $A$ and $B$ are $+$ -similar if and only if $A\sim B$ and one of the following two cases holds:

1. Case 1.
  
  If $\max(A)$ has a splitting node in $T$ , then so does $\max(B)$ , and the similarity map from $A$ to $B$ takes the splitting node in $\max(A)$ to the splitting node in $\max(B)$ .

1. Case 2.
  
  If $\max(A)$ has a coding node, say $c^{A}_{n}$ , and $f:A\rightarrow B$ is the similarity map, then $s^{+}(n)\sim f(s)^{+}(n)$ for each $s\in\max(A)$ .

Note that $\stackrel{{\scriptstyle+}}{{\sim}}$ is an equivalence relation, and $A\stackrel{{\scriptstyle+}}{{\sim}}B$ implies $A\sim B$ . When $A\sim B$ ( $A\stackrel{{\scriptstyle+}}{{\sim}}B$ ), we say that they have the same similarity type ( $+$ -similarity type).

Definition 2.17 (Extension Property, [2]).

We say that $\mathbf{K}$ has the Extension Property when the following condition (EP) holds:

(EP)

Suppose $A$ is a finite or infinite subtree of some $T\in\mathcal{T}$ . Let $k$ be given and suppose $\max(r_{k+1}(A))$ has a splitting node. Suppose that $B$ is a $+$ -similarity copy of $r_{k}(A)$ in $T$ . Let $u$ denote the splitting node in $\max(r_{k+1}(A))$ , and let $s$ denote the node in $\max(B)^{+}$ which must be extended to a splitting node in order to obtain a $+$ -similarity copy of $r_{k+1}(A)$ . If $s^{*}$ is a splitting node in $T$ extending $s$ , then there are extensions of the rest of the nodes in $\max(B)^{+}$ to the same length as $s^{*}$ resulting in a $+$ -similarity copy of $r_{k+1}(A)$ which can be extended to a copy of $A$ .

It was shown in Lemma 4.17 of [2] that SFAP implies the Extension Property, and that moreover, any SFAP class with an additional linear order also easily satisfy the Extension Property.

Definition 2.18 (SDAP⁺, [2]).

A Fraïssé class $\mathcal{K}$ satisfies SDAP⁺ if and only if $\mathcal{K}$ satisfies SDAP and any Fraïssé limit $\mathbf{K}$ of $\mathcal{K}$ with universe $\mathbb{N}$ satisfies the Diagonal Coding Tree Property and the Extension Property.

Remark 2.19.

If there exists an enumerated Fraïssé limit $\mathbf{K}$ of $\mathcal{K}$ satisfying DCTP and EP, then every enumerated Fraïssé limit of $\mathcal{K}$ also satisfies DCTP and EP. Thus, the property SDAP⁺ is truly a property of the Fraïssé class $\mathcal{K}$ . This being the case, we will refer to both a Fraïssé class and its Fraïssé limit as satisfying SDAP⁺.

The Labeled Substructure Disjoint Amalgamation Property is a labeled version applicable to structures such as $\mathbb{Q}_{\mathbb{Q}}$ , $\mathbb{Q}_{{\mathbb{Q}}_{\mathbb{Q}}}$ , and so forth (see Subsection 4.4 in [2]). Since the proofs for SDAP⁺ and LSDAP⁺ structures are almost identical, for the sake of space, we will provide proofs for SDAP⁺ structures.

Note that any SDAP⁺ and LSDAP⁺ structures can be encoded inside $\mathbb{U}$ according to the following convention.

Convention 2.20.

There is some $k\geq 1$ , a partition $P_{i}$ ( $i<k$ ) of the unary relation symbols in $\mathcal{L}$ and subtrees $T_{i}\subseteq\mathbb{U}$ so that the following hold:

(1)

$T:=\bigcup_{i<k}T_{i}$ forms a $k$ -rooted diagonal coding tree;
(2)

For each $i<k$ , the coding nodes in $T_{i}$ have only unary relations from $P_{i}$ , and all the unary relation symbols from $P_{i}$ occur densely in $T_{i}$ ;
(3)

Property (2) persists in every coding subtree of $T$ .

In this way, the partition $P_{i}$ , $i<k$ , is optimal and persistent.

For simplicity, though, we will assume the following convention.

Convention 2.21.

Let $\mathcal{K}$ be a Fraïssé class in a language $\mathcal{L}$ and $\mathbf{K}$ a Fraïssé limit of $\mathcal{K}$ . If (a) $\mathcal{K}$ satisfies SFAP, or (b) $\mathbf{K}$ satisfies SDAP⁺ and either has no unary relations or has no transitive relations, then we work inside a diagonal coding subtree $\mathbb{T}$ of $\mathbb{S}$ . Otherwise, we work inside a diagonal coding subtree $\mathbb{T}$ of $\mathbb{U}$ .

Convention 2.21 is a special case of Convention 2.20. We will prove the main theorems assuming Convention 2.21, noting that it is straightforward to recover the general results under Convention 2.20.

We conclude this section with the result on big Ramsey degrees from [3]. A set of incomparable coding nodes $A\subseteq\mathbb{U}$ is called an antichain. An antichain of coding nodes in $\mathbb{U}$ is called a diagonal antichain if the tree induced by the meet closure of the antichain is diagonal.

Definition 2.22 (Diagonal Coding Antichain, [2]).

A diagonal antichain $A\subseteq\mathbb{U}$ is called a diagonal coding antichain (DCA) if $\mathbf{K}\restriction A\cong\mathbf{K}$ and (the tree induced by) $A$ is a Diagonal Coding Subtree.

Lemma 2.23 ([2]).

Suppose $\mathcal{K}$ is a Fraïssé class satisfying SDAP⁺ or LSDAP⁺. Then there is an infinite diagonal antichain of coding nodes $\mathbb{D}\subseteq\mathbb{U}$ so that $\mathbf{K}\restriction\mathbb{D}\cong^{\omega}\mathbf{K}$ .

Theorem 2.24 (Coulson, Dobrinen, Patel, [3]).

Let $\mathcal{K}$ be a Fraïssé class satisfying SDAP⁺ or LSDAP⁺ in a finite relational language with relation symbols of arity at most two. Then for each finite structure $\mathbf{A}\in\mathcal{K}$ , the big Ramsey degree of $\mathbf{A}$ in $\mathbf{K}$ is exactly the number of similarity types of diagonal antichains representing a copy of $\mathbf{A}$ .

3. Baire spaces of diagonal coding antichains

We now set up the subspaces of the Baire space for which we will prove analogues of the Galvin–Prikry and Ellentuck Theorems. Given a Fraïssé structure $\mathbf{K}$ with universe $\mathbb{N}$ , each subcopy of $\mathbf{K}$ can be identified with its universe, an infinite subset of $\mathbb{N}$ . Thus, the collection ${\mathbf{K}\choose\mathbf{K}}$ of all subcopies of $\mathbf{K}$ is naturally identified with a subspace of the Baire space $[\mathbb{N}]^{\mathbb{N}}$ .

The existence of big Ramsey degrees greater than one precludes any simplistic approach to infinite-dimensional Ramsey theorems in terms only of definable sets on the full space ${\mathbf{K}\choose\mathbf{K}}$ of subcopies of $\mathbf{K}$ . At the same time, Theorem 2.24 shows us where to look for viable infinite-dimensional Ramsey theorems: precisely on subspaces of the Baire space determined by collections of coding subtrees which are all similar to each other. While infinite-dimensional Ramsey theorems for all such spaces follow from the methods in this paper, we will concentrate on spaces of antichains similar to some fixed diagonal coding antichain, as such spaces will additionally recover exact big Ramsey degrees.

Definition 3.1 (Spaces of Diagonal Coding Antichains).

Let $\mathcal{K}$ be a Fraïssé class satisfying SDAP⁺, and let $\mathbf{K}$ be a Fraïssé limit of $\mathcal{K}$ with universe $\mathbb{N}$ . Let $\mathbb{D}$ be any diagonal coding antichain; that is, $\mathbb{D}$ is a diagonal antichain of coding nodes in $\mathbb{S}(\mathbf{K})$ or $\mathbb{U}(\mathbf{K})$ representing a subcopy of $\mathbf{K}$ . (Recall Convention 2.21.)

Let $\mathcal{D}(\mathbb{D})$ denote the collection of all subsets $M\subseteq\mathbb{D}$ such that $M\sim\mathbb{D}$ . The partial ordering $\leq$ on $\mathcal{D}(\mathbb{D})$ is simply inclusion. For $M\in\mathcal{D}(\mathbb{D})$ , when we write $N\leq M$ , it is implied that $N\in\mathcal{D}(\mathbb{D})$ . When $\mathbb{D}$ is understood, we simply write $\mathcal{D}$ .

Each diagonal coding antichain $M\in\mathcal{D}$ uniquely determines the substructure $\mathbf{M}:=\mathbf{K}\restriction\{v_{i}:c_{i}\in M\}$ . Since $M\sim\mathbb{D}$ , it follows that $\mathbf{M}\cong^{\omega}\mathbf{K}$ . Let $\mathbf{D}$ denote $\mathbf{K}\restriction\mathbb{D}$ , and let

(6)

\mathbf{K}(\mathbf{D})=\{\mathbf{M}:M\in\mathcal{D}\}.

Then $\mathbf{K}(\mathbf{D})$ is identified with the subspace $\{\{i\in\mathbb{N}:v_{i}\in\mathbf{M}\}:\mathbf{M}\in\mathbf{K}(\mathbf{D})\}$ of the Baire space. These are the spaces for which we will prove infinite-dimensional Ramsey theorems in Section 6.

Each diagonal coding antichain $M\in\mathcal{D}$ can also be identified with the tree induced by its meet-closure. The set of coding and splitting nodes in (the tree induced by) $M$ are called the critical nodes of $M$ , and we let $\langle d^{M}_{n}:n\in\mathbb{N}\rangle$ denote their enumeration in order of increasing length. For $n\in\mathbb{N}$ , $M(n)$ denotes the set of nodes in $M$ of length $|d^{M}_{n}|$ . Given $k\in\mathbb{N}$ , $r_{k}(M)$ denotes the finite subset of $M$ consisting of all nodes in $M$ with length less than $|d^{M}_{k}|$ . Thus, $r_{0}(M)$ is the empty set and

(7)

r_{k}(M)=\bigcup_{n<k}M(n).

We define the following notation in line with topological Ramsey space theory from [16]. For $k\in\mathbb{N}$ , define

(8)

\mathcal{AD}_{k}=\{r_{k}(M):M\in\mathcal{D}\},

the set of all $k$ -th restrictions of members of $\mathcal{D}$ . Let

(9)

\mathcal{AD}=\bigcup_{k=1}^{\infty}\mathcal{AD}_{k},

the set of all finite approximations to members of $\mathcal{D}$ . Note that having identified $M$ with the tree it induces, members of $\mathcal{AD}$ are finite diagonal trees which are initial segments of the diagonal tree $M$ .

For $A,B\in\mathcal{AD}$ we write $A\sqsubseteq B$ if and only if there is some $M\in\mathcal{D}$ and some $j\leq k$ such that $A=r_{j}(M)$ and $B=r_{k}(M)$ . In this case, $A$ is called an initial segment of $B$ ; we also say that $B$ extends $A$ . If $A\sqsubseteq B$ and $A\neq B$ , then we say that $A$ is a proper initial segment of $B$ and write $A\sqsubset B$ . When $A=r_{j}(M)$ for some $j$ , we also write $A\sqsubset M$ and call $A$ an initial segment of $M$ .

The metric topology on $\mathcal{D}$ is the topology induced by basic open cones of the form

(10)

[A,\mathbb{D}]=\{M\in\mathcal{D}:\exists k\,(r_{k}(M)=A)\},

for $A\in\mathcal{AD}$ . The Ellentuck topology on $\mathcal{D}$ is induced by basic open sets of the form

(11)

[A,M]=\{N\in\mathcal{D}:\exists k\,(r_{k}(N)=A)\mathrm{\ and\ }N\leq M\},

where $A\in\mathcal{AD}$ and $M\in\mathcal{D}$ . Thus, the Ellentuck topology refines the metric topology.

Given $A\in\mathcal{AD}$ , let $\ell_{A}$ denote the maximum of the lengths of nodes in $A$ , and let

(12)

\max(A)=\{s\in A:|s|=\ell_{A}\}.

The partial ordering $\leq_{\mathrm{fin}}$ on $\mathcal{AD}$ is defined as follows: For $A,B\in\mathcal{AD}$ , write $A\leq_{\mathrm{fin}}B$ if and only if $A$ is a subtree of $B$ . Define $\operatorname{depth}_{M}(A)$ to be the least integer $k$ such that $A\leq_{\mathrm{fin}}r_{k}(M)$ , if it exists; otherwise, define $\operatorname{depth}_{M}(A)=\infty$ . Lastly, given $j<k$ , $A\in\mathcal{AD}_{j}$ and $M\in\mathcal{D}$ , define

(13)

r_{k}[A,M]=\{r_{k}(N):N\in[A,M]\}.

4. Forcing the Extended Pigeonhole Principle

This section proves an enhanced pigeonhole principle for Baire spaces of diagonal coding antichains which preserves the width in some finite initial segment of the ambient antichain. This is done to prove the pigeonhole principle (axiom A.4 of Todorcevic) while simultaneously overcoming the fact that the amalgamation axiom A.3(2) of Todorcevic does not hold for many spaces of the form $\mathcal{D}(\mathbb{D})$ . The proof will use forcing techniques to do infinitely many unbounded searches for finite objects with some homogeneity properties. Since the objects are finite, they exist in the ground model; no generic extension is needed for the main theorem of this section.

Definition 4.1 (Good Diagonal Coding Antichains).

Fix an enumerated Fraïssé structure $\mathbf{K}$ satisfying SDAP⁺. We call a diagonal coding antichain $M$ good if it satisfies the following:

(1)

For each $n\in\mathbb{N}$ , the longest splitting node in $M$ with length less than $|c^{M}_{n}|$ extends $\prec$ -right to $c^{M}_{n}$ . We call this splitting node the splitting predecessor of $c^{M}_{n}$ and denote it by $\mathrm{sp}_{M}(c^{M}_{n})$ .
(2)

For any $m<n$ , letting $s$ be the $\prec$ -left extension of $\mathrm{sp}_{M}(c^{M}_{m})$ in $M\restriction(|c^{M}_{m}|+1)$ and $t$ be the $\prec$ -left extension of $\mathrm{sp}_{M}(c^{M}_{n})$ in $M\restriction(|c^{M}_{n}|+1)$ , we have $s(c^{M}_{m})\sim t(c^{M}_{n})$ .
(3)

There is a $k\in\mathbb{N}$ such that for all $n\geq k$ , to each $1$ -type $\sigma$ over $\mathbf{K}_{n+1}$ there corresponds a unique node $s\in M\restriction(|c^{M}_{n}|+1)$ such that $\operatorname{tp}(s/\mathbf{M}_{n+1})\sim\sigma$ .

Fix throughout this section a good diagonal coding antichain $\mathbb{D}$ for $\mathbf{K}$ , and let $\mathcal{D}$ denote $\mathcal{D}(\mathbb{D})$ . For any subset $U\subseteq\mathbb{D}$ , finite or infinite, let $L_{U}$ denote $\{|t|:t\in U\}$ , the set of lengths of nodes in $U$ , and let $U^{\wedge}$ denote the meet-closure of $U$ . Define

(14)

\widehat{U}=\{t\restriction\ell:t\in U\mathrm{\ and\ }\ell\leq|t|\},

the tree of all initial segments of members of $U$ , and

(15)

\operatorname{tree}({U})=\{t\in\widehat{U}:|t|\in L_{U^{\wedge}}\},

the tree induced by the meet-closure of $U$ . We will abuse notation an identify $U$ with tree $(U)$ .

Let

(16)

\widehat{\mathcal{AD}}=\{A\upharpoonleft\ell:A\in\mathcal{AD}\mathrm{\ and\ }\ell\leq\ell_{A}\}.

Given $M\in\mathcal{D}$ , let $\mathcal{AD}(M)$ denote the members of $\mathcal{AD}$ which are contained in $M$ . For $k\in\mathbb{N}$ , let $\mathcal{AD}_{k}(M)$ denote the set of those $A\in\mathcal{AD}_{k}$ such that $A$ is a subtree of $M$ . Define

(17)

\widehat{\mathcal{AD}}(M)=\{A\upharpoonleft\ell:A\in\mathcal{AD}(M)\mathrm{\ and\ }\ell\in L_{M}\}.

Note that for any $M\in\mathcal{D}$ , there are members of $\widehat{\mathcal{AD}}(M)$ which are not similar to $r_{n}(\mathbb{D})$ for any $n$ , and hence are not members of $\mathcal{AD}(M)$ .

Definition 4.2.

Given $M\in\mathcal{D}$ and $B\in\widehat{\mathcal{AD}}(M)$ , letting $m$ be the least integer for which there exists $B^{\prime}\in\mathcal{AD}_{m}$ such that $\max(B)\sqsubseteq\max(B^{\prime})$ , define

(18)

[B,M]^{*}=\{N\in\mathcal{D}:\max(B)\sqsubseteq\max(r_{m}(N))\mathrm{\ and\ }N\leq M\}.

For $n\geq m$ , define

(19)

r_{n}[B,M]^{*}=\{r_{n}(N):N\in[B,M]^{*}\},

and let

(20)

r[B,M]^{*}=\bigcup_{m\leq n}r_{n}[B,M]^{*}.

Given $B\in\widehat{\mathcal{AD}}$ and $M\in\mathcal{D}$ , notice that the set $[B,M]^{*}$ from Definition 4.2 is open in the Ellentuck topology on $\mathcal{D}$ : If $B$ is in $\mathcal{AD}_{k}$ for some $k$ , then the set $[B,M]^{*}$ is the union of $[B,M]$ along with all $[C,M]$ , where $C\in\mathcal{AD}_{k}$ and $\max(C)$ end-extends $\max(B)$ . If $B$ is in $\widehat{\mathcal{AD}}$ but not in $\mathcal{AD}$ , then letting $k$ be the least integer for which there is some $C\in\mathcal{AD}_{k}$ with $\max(C)\sqsupset\max(B)$ , we see that $[B,M]^{*}$ equals the union of all $[C,M]$ , where $C\in\mathcal{AD}_{k}$ and $B\sqsubseteq C$ . For the same reasons, the set $[B,\mathbb{D}]^{*}$ is open in the metric topology on $\mathcal{D}$ . Notice also that $r_{n}[B,M]^{*}$ defined in equation (19) is equal to $\{C\in\mathcal{AD}_{n}(M):\max(B)\sqsubseteq\max(C)\}$ .

Given $M\in\mathcal{D}$ , a splitting node $s\in M$ is called a splitting predecessor of a coding node in $M$ (or just splitting predecessor if $M$ is understood) if and only if there is a coding node $c\in M$ such that $s\subset c$ and $|c|$ is minimal in $L_{M}$ above $|s|$ . Given a coding node $c$ in $M$ , we write $\operatorname{sp}_{M}(c)$ to denote the splitting predecessor of $c$ in $M$ . Note that $s=\operatorname{sp}_{M}(c)$ if and only if the minimal node in $M$ extending the $\prec$ -right extension of $s$ is a coding node. When $M=\mathbb{D}$ , we will usually write $\operatorname{sp}(c)$ in place of $\operatorname{sp}_{\mathbb{D}}(c)$ .

Given $A\in\widehat{\mathcal{AD}}(M)$ , let $A^{+}$ denote the union of $A$ with the set of immediate successors in $\widehat{M}$ of the members of $\max(A)$ ; thus,

(21)

A^{+}=A\cup\{t\in M\restriction(\ell_{A}+1):t\restriction\ell_{A}\in A\}

and $\max(A^{+})$ is the set of all nodes in $A^{+}$ with length $\ell_{A}+1$ .

A set of nodes is called a level set if all nodes in the set have the same length. For level sets $X,Y\subseteq\mathbb{D}$ , we say that $Y$ end-extends $X$ and write $X\sqsubset Y$ if and only if $X$ and $Y$ have the same cardinality, $\ell_{X}<\ell_{Y}$ , and $Y\restriction\ell_{X}=X$ . More generally, for $A,B\in\widehat{\mathcal{AD}}$ , write $A\sqsubseteq B$ if and only if $A=B\upharpoonleft\ell_{A}$ ; in this case, write $A\sqsubset B$ if also $\ell_{A}<\ell_{B}$ .

Assumption 4.3.

Fix a good diagonal coding antichain $\mathbb{D}$ and let $\mathcal{D}:=\mathcal{D}(\mathbb{D})$ . We will be working with triples $(A,B,k)$ , where $A\in\widehat{\mathcal{AD}}$ , $B\subseteq\widehat{\mathbb{D}}$ , and $A\sqsubset B\subseteq A^{+}$ . Assume that all splitting nodes in $A$ , $B$ , and $D$ are not splitting predecessors in $\mathbb{D}$ . We consider the following combinations of one of Cases (a) or (b) with one of Cases (i) or (ii).

1. Case (a).
  
  $\max(r_{k+1}(\mathbb{D}))$ has a splitting node.

1. Case (b).
  
  $\max(r_{k+1}(\mathbb{D}))$ has a coding node.

1. Case (i).
  
  $k\geq 1$ , $A\in\mathcal{AD}_{k}$ , and $B=A^{+}$ .

1. Case (ii).
  
  $k\geq 0$ , $A$ has at least one node, each member of $\max(A)$ has exactly one extension in $\max(B)$ (that is, $\max(A)\sqsubset\max(B)$ ), and $A=C\upharpoonleft\ell$ for some $C\in\mathcal{AD}_{k+1}$ and $\ell<\ell_{C}$ such that $r_{k}(C)\sqsubseteq A$ and $B\sqsubseteq C$ .

We point out that in Case (ii), $A$ may or may not be a member of $\mathcal{AD}$ .

The following theorem of Erdős and Rado will be used in the proof of Theorem 4.5.

Theorem 4.4 (Erdős-Rado).

For $r<\omega$ and $\mu$ an infinite cardinal,

\beth_{r}(\mu)^{+}\rightarrow(\mu^{+})_{\mu}^{r+1}.

We are now set up to prove the theorem which will form the basis of the result that all Borel sets in $\mathcal{B}(\mathbb{D})$ are Ramsey.

Theorem 4.5 (Extended Pigeonhole Principle).

Let $\mathbb{D}$ , $(A,B,k)$ , $D$ , $d$ be as in Assumption 4.3, where $(A,B,k)$ satisfies one of Cases (i) or (ii) and one of Cases (a) or (b). Let $h:r_{k+1}[D,\mathbb{D}]^{*}\rightarrow 2$ be a coloring. Then there is an $N\in[D,\mathbb{D}]^{*}$ such that $h$ is monochromatic on $r_{k+1}[B,N]^{*}$ .

Proof.

Assume the hypotheses. Let $\mathbf{i}+1$ be the number of nodes in $\max(B)$ , and fix an enumeration $s_{0},\dots,s_{\mathbf{i}}$ of the nodes in $\max(B)$ with the property that for any $C\in r_{k+1}[B,\mathbb{D}]^{*}$ , the critical node in $\max(C)$ extends $s_{\mathbf{i}}$ . Note that in Case (b), $\mathbf{i}$ must be at least two. Let $d$ denote the integer such that $D\in\mathcal{AD}_{d}$ , and let $I$ denote the set of all $n>d$ such that for some (equivalently, all) $M\in[D,\mathbb{D}]$ there is a member $C\in r_{k+1}[B,M]^{*}$ with $\operatorname{depth}_{M}(C)=n$ . Let $L$ denote the set $\{\ell_{r_{n}(M)}:M\in[D,\mathbb{D}]$ and $n\in I\}$ . In Case (b), for $\ell\in L$ we let $\ell^{\prime}$ denote the length of the splitting predecessor in $\mathbb{D}$ of the coding node in $\mathbb{D}$ of length $\ell$ , and let $L^{\prime}=\{\ell^{\prime}:\ell\in L\}$ .

Given $U\in\mathcal{AD}\cup\mathcal{D}$ with $D\sqsubseteq U$ , define the set $\operatorname{Ext}_{U}(B)$ as follows: In Case (a), let $\operatorname{Ext}_{U}(B)$ consist of those level sets $X\subseteq U$ such that $X=\max(C)$ for some $C\in r_{k+1}[B,\mathbb{D}]^{*}$ , where the splitting node in $X$ is not a splitting predecessor in $\mathbb{D}$ . In Case (b), let $\operatorname{Ext}_{U}(B)$ consist of those sets $X\subseteq U$ such that $X$ consists of the non-coding nodes in $\max(C)$ along with the splitting predecessor in $\mathbb{D}$ of the coding node in $\max(C)$ , for some $C\in r_{k+1}[B,\mathbb{D}]^{*}$ . We will simply write $\operatorname{Ext}(B)$ to mean $\operatorname{Ext}_{\mathbb{D}}(B)$ .

The coloring $h$ induces a coloring $h^{\prime}:\operatorname{Ext}(B)\rightarrow 2$ as follows: For $X\in\operatorname{Ext}(B)$ , in Case (a) define $h^{\prime}(X)=h(C)$ , where $C$ is the member of $r_{k+1}[B,\mathbb{D}]^{*}$ such that $X=\max(C)$ . In Case (b), define $h^{\prime}(X)=h(C)$ , where $C$ is the member of $r_{k+1}[B,\mathbb{D}]^{*}$ such that $X=(\max(C)\setminus\{c\})\cup\{\operatorname{sp}(c)\}$ , where $c$ denotes the coding node in $\max(C)$ .

For $i\leq\mathbf{i}$ , let $T_{i}=\{t\in\widehat{\mathbb{D}}:t\supseteq s_{i}\}$ . Let $\kappa=\beth_{2\mathbf{i}}$ , so that the partition relation $\kappa\rightarrow(\aleph_{1})^{2\mathbf{i}}_{\aleph_{0}}$ holds by the Erdős-Rado Theorem 4.4. The following forcing notion adds $\kappa$ many paths through each $T_{i}$ , $i<\mathbf{i}$ , and one path through $T_{\mathbf{i}}$ .

In both Cases (a) and (b), define $\mathbb{P}$ to be the set of finite partial functions $p$ such that

(1)

$\operatorname{dom}(p)=\{\mathbf{i}\}\times\vec{\delta}_{p}$ , where $\vec{\delta}_{p}$ is a finite subset of $\kappa$ ;
(2)

$p(\mathbf{i})\in T_{\mathbf{i}}$ and $\{p(i,\delta):\delta\in\vec{\delta}_{p}\}\subseteq T_{i}$ for each $i<\mathbf{i}$ ;
(3)

For any choices of $\delta_{i}\in\vec{\delta}_{p}$ , $i<\mathbf{i}$ , the set $\{p(i,\delta_{i}):i<\mathbf{i}\}\cup\{p(\mathbf{i})\}$ is a member of $\operatorname{Ext}(B)$ .

Let $\ell_{p}$ denote the maximal length of nodes in $\operatorname{ran}(p)$ . All nodes in $\operatorname{ran}(p)$ will have length $\ell_{p}$ except in Case (b), where the splitting predecessor $p(\mathbf{i})$ will have length $\ell_{p}^{\prime}$ .

The partial ordering on $\mathbb{P}$ is just reverse inclusion: $q\leq p$ if and only if $\ell_{q}\geq\ell_{p}$ , $\vec{\delta}_{q}\supseteq\vec{\delta}_{p}$ , $q(\mathbf{i})\supseteq p(\mathbf{i})$ , and $q(i,\delta)\supseteq p(i,\delta)$ for each $(i,\delta)\in\mathbf{i}\times\vec{\delta}_{p}$ . It is routine to check that $(\mathbb{P},\leq)$ is a separative, atomless partial order.

We point out that condition (3) in the definition of $\mathbb{P}$ is easy to satisfy since $\mathbf{K}$ has SDAP⁺: Let $C$ be any member of $r_{k+1}[B,\mathbb{D}]^{*}$ and let $\langle t_{i}:i\leq\mathbf{i}\rangle$ enumerate $\max(C)$ so that so that each $t_{i}$ extends $s_{i}$ . In Case (a), each $p(i,\delta)$ only need be a node in $T_{i}$ of length $\ell_{p}$ . If (1) of the Extension Property holds for $\mathbf{K}$ , then $p(\mathbf{i})$ just needs to be a splitting node in $T_{\mathbf{i}}$ which is not a splitting predecessor; if (2) of the Extension Property holds, it suffices for $p(\mathbf{i})$ to additionally satisfy $\psi(p(\mathbf{i}))=\psi(t_{\mathbf{i}})$ . In Case (b), $p(\mathbf{i})$ need only be the splitting predecessor of some coding node $c$ in $T_{\mathbf{i}}$ , and each $p(i,\delta)$ need only be a node in $T_{i}$ of length $\ell_{p}$ such that $p(i,\delta)^{+}(c)\sim t_{i}^{+}(t_{\mathbf{i}})$ .

Given $p\in\mathbb{P}$ , the range of $p$ is the set

\operatorname{ran}(p)=\{p(i,\delta):(i,\delta)\in\mathbf{i}\times\vec{\delta}_{p}\}\cup\{p(\mathbf{i})\}.

If also $q\in\mathbb{P}$ and $q\leq p$ , then we let

(22)

\operatorname{ran}(q)\restriction\operatorname{dom}(p)=\{q(i,\delta):(i,\delta)\in\mathbf{i}\times\vec{\delta}_{p}\}\cup\{q(\mathbf{i})\}.

For $(i,\alpha)\in\mathbf{i}\times\kappa$ , let

(23)

\dot{b}_{i,\alpha}=\{\langle p(i,\alpha),p\rangle:p\in\mathbb{P}\mathrm{\ and\ }\alpha\in\vec{\delta}_{p}\},

a $\mathbb{P}$ -name for the $\alpha$ -th generic branch through $T_{i}$ . Let

(24)

\dot{b}_{\mathbf{i}}=\{\langle p(\mathbf{i}),p\rangle:p\in\mathbb{P}\},

a $\mathbb{P}$ -name for the generic branch through $M_{\mathbf{i}}$ . Given a generic filter $G\subseteq\mathbb{P}$ , notice that $\dot{b}_{\mathbf{i}}^{G}=\{p(\mathbf{i}):p\in G\}$ , which is a cofinal path in $T_{\mathbf{i}}$ . We point out that given $p\in\mathbb{P}$ ,

(25)

p\Vdash\forall(i,\alpha)\in\mathbf{i}\times\vec{\delta}_{p}\,(\dot{b}_{i,\alpha}\restriction\ell_{p}=p(i,\alpha)).

Furthermore, in Case (a), $p\Vdash(\dot{b}_{\mathbf{i}}\restriction\ell_{p}=p(\mathbf{i}))$ , while in Case (b), $p\Vdash(\dot{b}_{\mathbf{i}}\restriction\ell^{\prime}_{p}=p(\mathbf{i}))$ .

Let $\dot{G}$ be the $\mathbb{P}$ -name for a generic filter, and let $\dot{L}_{G}$ be a $\mathbb{P}$ -name for the set of lengths $\{\ell_{p}:p\in\dot{G}\}$ . Note that $\mathbb{P}$ forces that $\dot{L}_{G}\subseteq L$ . Let $\dot{\mathcal{U}}$ be a $\mathbb{P}$ -name for a non-principal ultrafilter on $\dot{L}_{G}$ .

We will write sets $\{\alpha_{i}:i<\mathbf{i}\}$ in $[\kappa]^{\mathbf{i}}$ as vectors $\vec{\alpha}=\langle\alpha_{0},\dots,\alpha_{\mathbf{i}-1}\rangle$ in strictly increasing order. For $\vec{\alpha}\in[\kappa]^{\mathbf{i}}$ , let

(26)

\dot{b}_{\vec{\alpha}}=\langle\dot{b}_{0,\alpha_{0}},\dots,\dot{b}_{\mathbf{i}-1,\alpha_{\mathbf{i}-1}},\dot{b}_{\mathbf{i}}\rangle.

For $\ell\in L$ , in Case (a) let

(27)

\dot{b}_{\vec{\alpha}}\restriction\ell=\langle\dot{b}_{0,\alpha_{0}}\restriction\ell,\dots,\dot{b}_{\mathbf{i}-1,\alpha_{\mathbf{i}-1}}\restriction\ell,\dot{b}_{\mathbf{i}}\restriction\ell\rangle;

and in Case (b), let

(28)

\dot{b}_{\vec{\alpha}}\restriction\ell=\langle\dot{b}_{0,\alpha_{0}}\restriction\ell,\dots,\dot{b}_{\mathbf{i}-1,\alpha_{\mathbf{i}-1}}\restriction\ell,\dot{b}_{\mathbf{i}}\restriction\ell^{\prime}\rangle.

Note that $h^{\prime}$ is a coloring on $\dot{b}_{\vec{\alpha}}\restriction\ell$ whenever this is forced to be a member of $\operatorname{Ext}_{M}(B)$ . Given $\vec{\alpha}\in[\kappa]^{\mathbf{i}}$ and $p\in\mathbb{P}$ with $\vec{\alpha}\subseteq\vec{\delta}_{p}$ , let

(29)

X(p,\vec{\alpha})=\{p(i,\alpha_{i}):i<\mathbf{i}\}\cup\{p(\mathbf{i})\}.

For each $\vec{\alpha}\in[\kappa]^{\mathbf{i}}$ , choose a condition $p_{\vec{\alpha}}\in\mathbb{P}$ satisfying the following:

(1)

$\vec{\alpha}\subseteq\vec{\delta}_{p_{\vec{\alpha}}}$ .
(2)

There is an $\varepsilon_{\vec{\alpha}}\in 2$ such that $p_{\vec{\alpha}}\Vdash$ “ $h^{\prime}(\dot{b}_{\vec{\alpha}}\restriction\ell)=\varepsilon_{\vec{\alpha}}$ for $\dot{\mathcal{U}}$ many $\ell$ in $\dot{L}_{G}$ ”.
(3)

$h^{\prime}(X(p_{\vec{\alpha}},\vec{\alpha}))=\varepsilon_{\vec{\alpha}}$ .

Such conditions can be found as follows: Fix some $X\in\operatorname{Ext}(B)$ and let $x_{i}$ denote the node in $X$ extending $s_{i}$ , for each $i\leq\mathbf{i}$ . For $\vec{\alpha}\in[\kappa]^{\mathbf{i}}$ , define

p^{0}_{\vec{\alpha}}=\{\langle(i,\delta),x_{i}\rangle:i<\mathbf{i},\ \delta\in\vec{\alpha}\}\cup\{\langle\mathbf{i},x_{\mathbf{i}}\rangle\}.

Then (1) will hold for all $p\leq p^{0}_{\vec{\alpha}}$ , since $\vec{\delta}_{p_{\vec{\alpha}}^{0}}=\vec{\alpha}$ . Next, let $p^{1}_{\vec{\alpha}}$ be a condition below $p^{0}_{\vec{\alpha}}$ which forces $h^{\prime}(\dot{b}_{\vec{\alpha}}\restriction\ell)$ to be the same value for $\dot{\mathcal{U}}$ many $\ell\in\dot{L}_{G}$ . Extend this to some condition $p^{2}_{\vec{\alpha}}\leq p_{\vec{\alpha}}^{1}$ which decides a value $\varepsilon_{\vec{\alpha}}\in 2$ so that $p^{2}_{\vec{\alpha}}$ forces $h^{\prime}(\dot{b}_{\vec{\alpha}}\restriction\ell)=\varepsilon_{\vec{\alpha}}$ for $\dot{\mathcal{U}}$ many $\ell$ in $\dot{L}_{G}$ . Then (2) holds for all $p\leq p_{\vec{\alpha}}^{2}$ . If $p_{\vec{\alpha}}^{2}$ satisfies (3), then let $p_{\vec{\alpha}}=p_{\vec{\alpha}}^{2}$ . Otherwise, take some $p^{3}_{\vec{\alpha}}\leq p^{2}_{\vec{\alpha}}$ which forces $\dot{b}_{\vec{\alpha}}\restriction\ell\in\operatorname{Ext}(B)$ and $h^{\prime}(\dot{b}_{\vec{\alpha}}\restriction\ell)=\varepsilon_{\vec{\alpha}}$ for some $\ell\in\dot{L}_{G}$ with $\ell_{p^{2}_{\vec{\alpha}}}<\ell\leq\ell_{p^{3}_{\vec{\alpha}}}$ ; then $h^{\prime}(X(p^{3}_{\vec{\alpha}}\restriction\ell,\vec{\alpha}))=\varepsilon_{\vec{\alpha}}$ . Thus, letting $p_{\vec{\alpha}}$ be $p^{3}_{\vec{\alpha}}\restriction\ell$ , we see that $p_{\vec{\alpha}}$ satisfies (1)–(3).

Let $\mathcal{I}$ denote the collection of all functions $\iota:2\mathbf{i}\rightarrow 2\mathbf{i}$ such that for each $i<\mathbf{i}$ , $\{\iota(2i),\iota(2i+1)\}\subseteq\{2i,2i+1\}$ . For $\vec{\theta}=\langle\theta_{0},\dots,\theta_{2\mathbf{i}-1}\rangle\in[\kappa]^{2\mathbf{i}}$ , $\iota(\vec{\theta}\,)$ determines the pair of sequences of ordinals $\langle\iota_{e}(\vec{\theta}\,),\iota_{o}(\vec{\theta}\,)\rangle$ , where

(30)		$\displaystyle\iota_{e}(\vec{\theta}\,)$	$\displaystyle=\langle\theta_{\iota(0)},\theta_{\iota(2)},\dots,\theta_{\iota(2\mathbf{i}-2))}\rangle$
(31)		$\displaystyle\iota_{o}(\vec{\theta}\,)$	$\displaystyle=\langle\theta_{\iota(1)},\theta_{\iota(3)},\dots,\theta_{\iota(2\mathbf{i}-1)}\rangle.$

We now proceed to define a coloring $f$ on $[\kappa]^{2\mathbf{i}}$ into countably many colors. Let $\vec{\delta}_{\vec{\alpha}}$ denote $\vec{\delta}_{p_{\vec{\alpha}}}$ , $k_{\vec{\alpha}}$ denote $|\vec{\delta}_{\vec{\alpha}}|$ , $\ell_{\vec{\alpha}}$ denote $\ell_{p_{\vec{\alpha}}}$ , and let $\langle\delta_{\vec{\alpha}}(j):j<k_{\vec{\alpha}}\rangle$ denote the enumeration of $\vec{\delta}_{\vec{\alpha}}$ in increasing order. Given $\vec{\theta}\in[\kappa]^{2\mathbf{i}}$ and $\iota\in\mathcal{I}$ , to reduce subscripts let $\vec{\alpha}$ denote $\iota_{e}(\vec{\theta}\,)$ and $\vec{\beta}$ denote $\iota_{o}(\vec{\theta}\,)$ , and define

(32)	$\displaystyle f(\iota,\vec{\theta}\,)=\,$	$\displaystyle\langle\iota,\varepsilon_{\vec{\alpha}},k_{\vec{\alpha}},p_{\vec{\alpha}}(\mathbf{i}),\langle\langle p_{\vec{\alpha}}(i,\delta_{\vec{\alpha}}(j)):j<k_{\vec{\alpha}}\rangle:i<\mathbf{i}\rangle,$
(33)		$\displaystyle\langle\langle i,j\rangle:i<\mathbf{i},\ j<k_{\vec{\alpha}},\ \mathrm{and\ }\delta_{\vec{\alpha}}(j)=\alpha_{i}\rangle,$
(34)		$\displaystyle\langle\langle j,k\rangle:j<k_{\vec{\alpha}},\ k<k_{\vec{\beta}},\ \delta_{\vec{\alpha}}(j)=\delta_{\vec{\beta}}(k)\rangle\rangle.$

Fix some ordering of $\mathcal{I}$ and define

(35)

f(\vec{\theta}\,)=\langle f(\iota,\vec{\theta}\,):\iota\in\mathcal{I}\rangle.

By the Erdős-Rado Theorem 4.4, there is a subset $K\subseteq\kappa$ of cardinality $\aleph_{1}$ which is homogeneous for $f$ . Take $K^{\prime}\subseteq K$ so that between each two members of $K^{\prime}$ there is a member of $K$ . Then take $K_{i}\subseteq K^{\prime}$ satisfying $K_{0}<\dots<K_{\mathbf{i}-1}$ , where $K_{i}<K_{i+1}$ means that each ordinal in $K_{i}$ is less than each ordinal in $K_{i+1}$ . Let $\vec{K}$ denote $\prod_{i<\mathbf{i}}K_{i}$ .

Fix some $\vec{\gamma}\in\vec{K}$ , and define

(36)			$\displaystyle\varepsilon_{}=\varepsilon_{\vec{\gamma}},\ \ k_{}=k_{\vec{\gamma}},\ \ t_{\mathbf{i}}=p_{\vec{\gamma}}(\mathbf{i}),$
(37)		$\displaystyle t_{i,j}$	$\displaystyle=p_{\vec{\gamma}}(i,\delta_{\vec{\gamma}}(j))\mathrm{\ for\ }i<\mathbf{i},\ j<k_{*}.$

The next three lemmas show that the values in equation (36) are the same for any choice of $\vec{\gamma}$ in $\vec{K}$ .

Lemma 4.6.

For all $\vec{\alpha}\in\vec{K}$ , $\varepsilon_{\vec{\alpha}}=\varepsilon_{*}$ , $k_{\vec{\alpha}}=k_{*}$ , $p_{\vec{\alpha}}(\mathbf{i})=t_{\mathbf{i}}$ , and $\langle p_{\vec{\alpha}}(i,\delta_{\vec{\alpha}}(j)):j<k_{\vec{\alpha}}\rangle=\langle t_{i,j}:j<k_{*}\rangle$ for each $i<\mathbf{i}$ .

Proof.

Let $\vec{\alpha}$ be any member of $\vec{K}$ , and let $\vec{\gamma}$ be the set of ordinals fixed above. Take $\iota\in\mathcal{I}$ to be the identity function on $2\mathbf{i}$ . Then there are $\vec{\theta},\vec{\theta}^{\prime}\in[K]^{2\mathbf{i}}$ such that $\vec{\alpha}=\iota_{e}(\vec{\theta}\,)$ and $\vec{\gamma}=\iota_{e}(\vec{\theta}^{\prime}\,)$ . Since $f(\iota,\vec{\theta}\,)=f(\iota,\vec{\theta}^{\prime}\,)$ , it follows that $\varepsilon_{\vec{\alpha}}=\varepsilon_{\vec{\gamma}}$ , $k_{\vec{\alpha}}=k_{\vec{\gamma}}$ , $p_{\vec{\alpha}}(\mathbf{i})=p_{\vec{\gamma}}(\mathbf{i})$ , and $\langle\langle p_{\vec{\alpha}}(i,\delta_{\vec{\alpha}}(j)):j<k_{\vec{\alpha}}\rangle:i<\mathbf{i}\rangle=\langle\langle p_{\vec{\gamma}}(i,\delta_{\vec{\gamma}}(j)):j<k_{\vec{\gamma}}\rangle:i<\mathbf{i}\rangle$ . ∎

Let $\ell_{*}$ denote the length of the nodes $t_{i,j}$ , $(i,j)\in d\times k_{*}$ . In Case (a), $|t_{\mathbf{i}}|$ also equals $\ell_{*}$ ; in Case (b), let $\ell_{*}^{\prime}$ denote $|t_{\mathbf{i}}|$ .

Lemma 4.7.

Given any $\vec{\alpha},\vec{\beta}\in\vec{K}$ , if $j,k<k_{*}$ and $\delta_{\vec{\alpha}}(j)=\delta_{\vec{\beta}}(k)$ , then $j=k$ .

Proof.

Let $\vec{\alpha},\vec{\beta}$ be members of $\vec{K}$ and suppose that $\delta_{\vec{\alpha}}(j)=\delta_{\vec{\beta}}(k)$ for some $j,k<k_{*}$ . For $i<\mathbf{i}$ , let $\rho_{i}$ be the relation from among $\{<,=,>\}$ such that $\alpha_{i}\,\rho_{i}\,\beta_{i}$ . Let $\iota$ be the member of $\mathcal{I}$ such that for each $\vec{\theta}\in[K]^{2\mathbf{i}}$ and each $i<\mathbf{i}$ , $\theta_{\iota(2i)}\ \rho_{i}\ \theta_{\iota(2i+1)}$ . Fix some $\vec{\theta}\in[K^{\prime}]^{2\mathbf{i}}$ such that $\iota_{e}(\vec{\theta})=\vec{\alpha}$ and $\iota_{o}(\vec{\theta})=\vec{\beta}$ . Since between any two members of $K^{\prime}$ there is a member of $K$ , there is a $\vec{\zeta}\in[K]^{\mathbf{i}}$ such that for each $i<\mathbf{i}$ , $\alpha_{i}\,\rho_{i}\,\zeta_{i}$ and $\zeta_{i}\,\rho_{i}\,\beta_{i}$ . Let $\vec{\mu},\vec{\nu}$ be members of $[K]^{2\mathbf{i}}$ such that $\iota_{e}(\vec{\mu})=\vec{\alpha}$ , $\iota_{o}(\vec{\mu})=\vec{\zeta}$ , $\iota_{e}(\vec{\nu})=\vec{\zeta}$ , and $\iota_{o}(\vec{\nu})=\vec{\beta}$ . Since $\delta_{\vec{\alpha}}(j)=\delta_{\vec{\beta}}(k)$ , the pair $\langle j,k\rangle$ is in the last sequence in $f(\iota,\vec{\theta})$ . Since $f(\iota,\vec{\mu})=f(\iota,\vec{\nu})=f(\iota,\vec{\theta})$ , also $\langle j,k\rangle$ is in the last sequence in $f(\iota,\vec{\mu})$ and $f(\iota,\vec{\nu})$ . It follows that $\delta_{\vec{\alpha}}(j)=\delta_{\vec{\zeta}}(k)$ and $\delta_{\vec{\zeta}}(j)=\delta_{\vec{\beta}}(k)$ . Hence, $\delta_{\vec{\zeta}}(j)=\delta_{\vec{\zeta}}(k)$ , and therefore $j$ must equal $k$ . ∎

For each $\vec{\alpha}\in\vec{K}$ , given any $\iota\in\mathcal{I}$ , there is a $\vec{\theta}\in[K]^{2\mathbf{i}}$ such that $\vec{\alpha}=\iota_{o}(\vec{\alpha})$ . By the second line of equation (32), there is a strictly increasing sequence $\langle j_{i}:i<\mathbf{i}\rangle$ of members of $k_{*}$ such that $\delta_{\vec{\gamma}}(j_{i})=\alpha_{i}$ . By homogeneity of $f$ , this sequence $\langle j_{i}:i<\mathbf{i}\rangle$ is the same for all members of $\vec{K}$ . Then letting $t^{*}_{i}$ denote $t_{i,j_{i}}$ , one sees that

(38)

p_{\vec{\alpha}}(i,\alpha_{i})=p_{\vec{\alpha}}(i,\delta_{\vec{\alpha}}(j_{i}))=t_{i,j_{i}}=t^{*}_{i}.

Let $t_{\mathbf{i}}^{*}$ denote $t_{\mathbf{i}}$ .

Lemma 4.8 (Homogeneity of $\{p_{\vec{\alpha}}:\vec{\alpha}\in\vec{K}\,\}$ ).

For any finite subset $\vec{J}\subseteq\vec{K}$ , $p_{\vec{J}}:=\bigcup\{p_{\vec{\alpha}}:\vec{\alpha}\in\vec{J}\,\}$ is a member of $\mathbb{P}$ which is below each $p_{\vec{\alpha}}$ , $\vec{\alpha}\in\vec{J}$ .

Proof.

Given $\vec{\alpha},\vec{\beta}\in\vec{J}$ , if $j,k<k_{*}$ and $\delta_{\vec{\alpha}}(j)=\delta_{\vec{\beta}}(k)$ , then $j$ and $k$ must be equal, by Lemma 4.7. Then Lemma 4.6 implies that for each $i<\mathbf{i}$ ,

(39)

p_{\vec{\alpha}}(i,\delta_{\vec{\alpha}}(j))=t_{i,j}=p_{\vec{\beta}}(i,\delta_{\vec{\beta}}(j))=p_{\vec{\beta}}(i,\delta_{\vec{\beta}}(k)).

Hence, for all $\delta\in\vec{\delta}_{\vec{\alpha}}\cap\vec{\delta}_{\vec{\beta}}$ and $i<\mathbf{i}$ , $p_{\vec{\alpha}}(i,\delta)=p_{\vec{\beta}}(i,\delta)$ . Thus, $p_{\vec{J}}:=\bigcup\{p_{\vec{\alpha}}:\vec{\alpha}\in\vec{J}\}$ is a function with $\vec{\delta}_{p_{\vec{J}}}=\bigcup\{\vec{\delta}_{\vec{\alpha}}:\vec{\alpha}\in\vec{J}\,\}$ ; hence, $p_{\vec{J}}$ is a member of $\mathbb{P}$ . Since for each $\vec{\alpha}\in\vec{J}$ , $\operatorname{ran}(p_{\vec{J}}\restriction\vec{\delta}_{\vec{\alpha}})=\operatorname{ran}(p_{\vec{\alpha}})$ , it follows that $p_{\vec{J}}\leq p_{\vec{\alpha}}$ for each $\vec{\alpha}\in\vec{J}$ . ∎

We now proceed to build an $N\in[D,\mathbb{D}]$ so that the coloring $h^{\prime}$ will be monochromatic on $\operatorname{Ext}_{N}(B)$ , from which it will follow that $h$ is monochromatic in $r_{k+1}[B,N]^{*}$ . Set

(40)

U^{*}=\{t^{*}_{i}:i\leq\mathbf{i}\}\cup\{u^{*}:u\in\max(D)^{+}\setminus B\},

where for each $u$ in $\max(D)^{+}\setminus B$ , $u^{*}$ is some extension of $u^{*}$ in $\mathbb{D}\restriction\ell_{*}$ . Then $U^{*}$ end-extends $\max(D)^{+}$ . One may take each $u^{*}$ to be the $\prec$ -leftmost extension of $u$ to be deterministic, but SDAP implies that any extensions will suffice. (Since $t^{*}_{\mathbf{i}}$ is either a splitting node or a splitting predecessor, all possible choices of $u^{*}$ for $u\in\max(D)^{+}\setminus B$ are are automatically never splitting nodes nor splitting predecessors nor coding nodes in $\mathbb{D}$ .)

Let $\{n_{j}:j\in\mathbb{N}\}$ be the strictly increasing enumeration of $I$ , and note that $n_{0}>d$ . From now on, Cases (a) and (b) are different enough to warrant separate treatment.

Case (a). If $n_{0}=d+1$ , then $D\cup U^{*}$ is a member of $r_{n_{0}}[D,\mathbb{D}]$ . In this case, we let $U_{n_{0}}=D\cup U^{*}$ , and let $U_{n_{1}-1}$ be any member of $r_{n_{1}-1}[U_{n_{0}},\mathbb{D}]$ , noting that $U^{*}$ is the only member of $\operatorname{Ext}_{U_{n_{0}}}(B)$ and that $h^{\prime}(U^{*})=\varepsilon_{*}$ . Otherwise, $n_{0}>d+1$ . In this case, take some $U_{n_{0}-1}\in r_{n_{0}-1}[D,\mathbb{D}]$ such that $\max(U_{n_{0}-1})$ end-extends $U^{*}$ , and notice that $\operatorname{Ext}_{U_{n_{0}-1}}(B)$ is empty.

Now assume that $j\geq 0$ and we have constructed $U_{n_{j}-1}\in r_{n_{j}-1}[D,\mathbb{D}]$ so that every member of $\operatorname{Ext}_{U_{n_{j}-1}}(B)$ has $h^{\prime}$ -color $\varepsilon_{*}$ . Fix some $E\in r_{n_{j}}[U_{n_{j}-1},\mathbb{D}]$ and let $Y=\max(E)$ . We will extend the nodes in $Y$ to construct $U_{n_{j}}\in r_{n_{j}}[U_{n_{j}-1},\mathbb{D}]$ with the property that all members of $\operatorname{Ext}_{U_{n_{j}}}(B)$ have the same $h$ -value $\varepsilon_{*}$ . This will be achieved by constructing the condition $q\in\mathbb{P}$ , below, and then extending it to some condition $r\leq q$ which decides that all members of $\operatorname{Ext}(B)$ coming from the nodes in $\operatorname{ran}(r)$ have $h$ -color $\varepsilon_{*}$ .

Let $q(\mathbf{i})$ denote the splitting node in $Y$ and let $\ell_{q}=\ell_{Y}$ . For each $i<\mathbf{i}$ , let $Y_{i}$ denote $Y\cap T_{i}$ , and let $J_{i}\subseteq K_{i}$ be a set of the same cardinality as $Y_{i}$ and label the members of $Y_{i}$ as $\{z_{\alpha}:\alpha\in J_{i}\}$ . Let $\vec{J}$ denote $\prod_{i<\mathbf{i}}J_{i}$ , and note that for each $\vec{\alpha}\in\vec{J}$ , the set $\{z_{\alpha_{i}}:i<\mathbf{i}\}\cup\{q(\mathbf{i})\}$ is a member of $\operatorname{Ext}(B)$ . By Lemma 4.8, the set $\{p_{\vec{\alpha}}:\vec{\alpha}\in\vec{J}\}$ is compatible, and $p_{\vec{J}}:=\bigcup\{p_{\vec{\alpha}}:\vec{\alpha}\in\vec{J}\}$ is a condition in $\mathbb{P}$ .

Let $\vec{\delta}_{q}=\bigcup\{\vec{\delta}_{\vec{\alpha}}:\vec{\alpha}\in\vec{J}\}$ . For $i<\mathbf{i}$ and $\alpha\in J_{i}$ , define $q(i,\alpha)=z_{\alpha}$ . It follows that for each $\vec{\alpha}\in\vec{J}$ and $i<\mathbf{i}$ ,

(41)

q(i,\alpha_{i})\supseteq t^{*}_{i}=p_{\vec{\alpha}}(i,\alpha_{i})=p_{\vec{J}}(i,\alpha_{i}),

and

(42)

q(\mathbf{i})\supseteq t^{*}_{\mathbf{i}}=p_{\vec{\alpha}}(\mathbf{i})=p_{\vec{J}}(\mathbf{i}).

For $i<\mathbf{i}$ and $\delta\in\vec{\delta}_{q}\setminus J_{i}$ , let $q(i,\delta)$ be any node in $\mathbb{D}\restriction\ell_{q}$ extending $p_{\vec{J}}(i,\delta)$ . Define

(43)

q=\{q(\mathbf{i})\}\cup\{\langle(i,\delta),q(i,\delta)\rangle:i<\mathbf{i},\ \delta\in\vec{\delta}_{q}\}.

This $q$ is a condition in $\mathbb{P}$ , and $q\leq p_{\vec{J}}$ .

Take an $r\leq q$ in $\mathbb{P}$ which decides some $\ell$ in $\dot{L}_{G}$ for which $h^{\prime}(\dot{b}_{\vec{\alpha}}\restriction\ell)=\varepsilon_{*}$ , for all $\vec{\alpha}\in\vec{J}$ . Without loss of generality, we may assume that $\ell_{r}=\ell$ . Since $r$ forces $\dot{b}_{\vec{\alpha}}\restriction\ell=X(r,\vec{\alpha})$ for each $\vec{\alpha}\in\vec{J}$ , and since the coloring $h^{\prime}$ is defined in the ground model, it follows that $h^{\prime}(X(r,\vec{\alpha}))=\varepsilon_{*}$ for each $\vec{\alpha}\in\vec{J}$ . Let

(44)

Y^{\prime}=\{q(\mathbf{i})\}\cup\{q(i,\alpha):i<\mathbf{i},\ \alpha\in J_{i}\},

and let

(45)

Z^{\prime}=\{r(\mathbf{i})\}\cup\{r(i,\alpha):i<\mathbf{i},\ \alpha\in J_{i}\}.

Let $Z$ be the level set consisting of the nodes in $Z^{\prime}$ along with a node $z_{y}$ in $\mathbb{D}\restriction\ell$ extending $y$ , for each $y\in Y\setminus Y^{\prime}$ . Then $Z$ end-extends $Y$ , and moreover, letting $U_{n_{j}}=U_{n_{j}-1}\cup Z$ , we see that $U_{n_{j}}$ is a member of $r_{n_{j}}[U_{n_{j}-1},\mathbb{D}]$ such that $h^{\prime}$ has value $\varepsilon_{*}$ on $\operatorname{Ext}_{U_{n_{j}}}(B)$ .

Case (b). Notice that in this case, $n_{0}$ must be at least $d+2$ and that $t^{*}_{\mathbf{i}}$ is the splitting predecessor of the coding node in $\mathbb{D}\restriction\ell_{*}$ , which we shall denote by $c^{*}$ . Let $U^{*}$ be as in equation (40). In Case (b), all nodes in $U^{*}$ have length $\ell_{*}$ except for $t^{*}_{\mathbf{i}}$ , which has length $\ell^{\prime}_{*}$ . There is exactly one non-terminal (i.e. non-coding) node in $\mathbb{D}\restriction\ell_{*}$ extending $t^{*}_{\mathbf{i}}$ ; denote this node by $u^{*}_{\mathbf{i}}$ . If $n_{0}=d+2$ , let $U_{n_{0}}$ be the tree induced by $D\cup U^{*}\cup\{u_{\mathbf{i}}^{*},c^{*}\}$ . Then let $U_{n_{1}-2}$ be any member of $r_{n_{1}-2}[U_{n_{0}},\mathbb{D}]$ .

If $n_{0}>d+2$ , the same argument will handle the base case and the induction step. For the base case, let $E$ be a member of $r_{n_{0}}[D,\mathbb{D}]$ such that $E\restriction\ell_{*}$ equals $(U^{*}\setminus\{t^{*}_{\mathbf{i}}\})\cup\{u^{*}_{\mathbf{i}}\}$ . (In particular, $\ell_{*}<\ell_{r_{d+1}(U_{n_{0}})}$ .) For $j\geq 1$ , supposing we have constructed $U_{n_{j}-2}\in r_{n_{j}-2}[U_{n_{j-1}},\mathbb{D}]$ so that every member of $\operatorname{Ext}_{U_{n_{j}-2}}(B)$ has $h^{\prime}$ -color $\varepsilon_{*}$ , let $E$ be any member of $r_{n_{j}}[U_{n_{j}-2},D]$ . In each of these two cases, let $c^{E}$ denote the coding node in $\max(E)$ , and let $Y$ denote the set $\max(E)$ but with the two extensions of $\operatorname{sp}(c^{E})$ in $\max(E)$ deleted and replaced by $\operatorname{sp}(c^{E})$ .

Let $\ell_{q}=\ell_{E}$ , and let $q(\mathbf{i})$ denote $\operatorname{sp}(c^{E})$ . For each $i<\mathbf{i}$ , let $Y_{i}$ denote the set of nodes $y\in Y\cap T_{i}$ such that $y$ is a member of some $X\in\operatorname{Ext}_{E}(B)$ . Equivalently, $Y_{i}$ is the set of those $y\in Y\cap T_{i}$ such that $y^{+}(c^{E})\sim(t^{*}_{i})^{+}(c^{*})$ . For each $i<\mathbf{i}$ , take a set $J_{i}\subseteq K_{i}$ of the same cardinality as $Y_{i}$ and label the members of $Y_{i}$ as $\{z_{\alpha}:\alpha\in J_{i}\}$ . Let $\vec{J}$ denote $\prod_{i<\mathbf{i}}J_{i}$ , noting that for each $\vec{\alpha}\in\vec{J}$ , $\{z_{\alpha_{i}}:i<\mathbf{i}\}\cup\{q(\mathbf{i})\}$ is a member of $\operatorname{Ext}(B)$ . By Lemma 4.8, the set $\{p_{\vec{\alpha}}:\vec{\alpha}\in\vec{J}\}$ is compatible, and $p_{\vec{J}}:=\bigcup\{p_{\vec{\alpha}}:\vec{\alpha}\in\vec{J}\}$ is a condition in $\mathbb{P}$ .

(46)

q(i,\alpha_{i})\supseteq t^{*}_{i}=p_{\vec{\alpha}}(i,\alpha_{i})=p_{\vec{J}}(i,\alpha_{i}),

and

(47)

q(\mathbf{i})\supseteq t^{*}_{\mathbf{i}}=p_{\vec{\alpha}}(\mathbf{i})=p_{\vec{J}}(\mathbf{i}).

For $i<\mathbf{i}$ and $\delta\in\vec{\delta}_{q}\setminus J_{i}$ , let $q(i,\delta)$ be an extension of $p_{\vec{J}}(i,\delta)$ in $T_{i}$ of length $\ell_{q}$ satisfying

(48)

q(i,\delta)^{+}(c_{q})\sim p_{\vec{J}}(i,\delta)^{+}(c^{*}),

where $c_{q}$ denotes the coding node in $\mathbb{D}\restriction\ell_{q}$ . Such nodes $q(i,\delta)$ exist by SDAP. Define

(49)

q=\{q(\mathbf{i})\}\cup\{\langle(i,\delta),q(i,\delta)\rangle:i<\mathbf{i},\ \delta\in\vec{\delta}_{q}\}.

This $q$ is a condition in $\mathbb{P}$ , and $q\leq p_{\vec{J}}$ .

Now take an $r\leq q$ in $\mathbb{P}$ which decides some $\ell$ in $\dot{L}_{G}$ for which $h^{\prime}(\dot{b}_{\vec{\alpha}}\restriction\ell)=\varepsilon_{*}$ , for all $\vec{\alpha}\in\vec{J}$ . Without loss of generality, we may assume that $\ell_{r}=\ell$ . Since $r$ forces $\dot{b}_{\vec{\alpha}}\restriction\ell=X(r,\vec{\alpha})$ for each $\vec{\alpha}\in\vec{J}$ , and since the coloring $h^{\prime}$ is defined in the ground model, it follows that $h^{\prime}(X(r,\vec{\alpha}))=\varepsilon_{*}$ for each $\vec{\alpha}\in\vec{J}$ . Let

(50)

Z_{0}=\{r(\mathbf{i})\}\cup\{r(i,\alpha):i<\mathbf{i},\ \alpha\in J_{i}\}.

Recall that $\operatorname{ran}(q)\subseteq Y$ , and note that $Z_{0}$ end-extends $\operatorname{ran}(q)$ .

Let $c_{r}$ denote the coding node in $\mathbb{D}$ of length $\ell_{r}$ . For each $y\in Y\setminus\operatorname{ran}(q)$ , choose a member $z_{y}\supset y$ in $\mathbb{D}\restriction\ell_{r}$ so that

(51)

z_{y}^{+}(c_{r})\sim y^{+}(c_{q}).

Again, SDAP ensures the existence of such $z_{y}$ . Let $Z$ be the level set consisting of the nodes $z_{y}$ for $y\in Y\setminus\operatorname{ran}(q)$ , the nodes in $Z_{0}\setminus\{r(\mathbf{i})\}$ , and the two nodes in $\mathbb{D}\restriction\ell_{r}$ extending $r(\mathbf{i})$ . Let

(52)

U_{n_{j}}=U_{n_{j}-2}\cup Z\cup(Z\restriction\ell^{\prime}_{r}).

Then $U_{n_{j}}$ is a member of $r_{n_{j}}[U_{n_{j}-2},\mathbb{D}]$ .

Now that we have constructed $U_{n_{j}}$ , let $U_{n_{j+1}-2}$ be any member of $r_{n_{j+1}-2}[U_{n_{j}},\mathbb{D}]$ . This completes the inductive construction. Let $N=\bigcup_{j<\omega}U_{n_{j}}$ . Then $N$ is a member of $[D,\mathbb{D}]^{*}$ and for each $X\in\operatorname{Ext}_{N}(B)$ , $h^{\prime}(X)=\varepsilon_{*}$ . Thus, $N$ satisfies the theorem. ∎

Remark 4.9.

A simple modification of the proof yields the same theorem for structures with LSDAP⁺. (See proof of Theorem 5.4 in [2].)

5. Borel sets of $\mathcal{D}(\mathbb{D})$ are completely Ramsey

The main result of this section is Theorem 5.17: For any enumerated Fraïssé structure $\mathbf{K}$ satisfying SDAP⁺, for each good diagonal coding antichain $\mathbb{D}$ representing $\mathbf{K}$ , the space $\mathcal{D}(\mathbb{D})$ of all diagonal antichains $M\subseteq\mathbb{D}$ similar to $\mathbb{D}$ has the property that all Borel subsets are Ramsey. The proof generally follows the outline of the Galvin–Prikry Theorem in [8] with the following exceptions: The proof of the Nash-Williams-style Theorem 5.5 uses an asymmetric version of combinatorial forcing as well as applications of the Extended Pigeonhole Principle. This Principle is also needed to show that countable unions of completely Ramsey sets are completely Ramsey. Finally, working with diagonal coding antichains requires extra care.

Fix a Fraïssé structure $\mathbf{K}$ with universe $\mathbb{N}$ satisfying SDAP⁺. Fix a good diagonal coding antichain $\mathbb{D}$ representing $\mathbf{K}$ , and let $\mathcal{D}$ denote $\mathcal{D}(\mathbb{D})$ . We hold to the following convention:

Convention 5.1.

Given $M\in\mathcal{D}$ and $A\in\mathcal{AD}(M)$ , when we write $[A,M]$ , it is assumed that $\max(A)$ does not contain a splitting predecessor in $M$ . When we write $B\in r[A,M]^{*}$ , if $\max(B)$ has a splitting node then it is assumed that that splitting node is not a splitting predecessor in $M$ .

Definition 5.2.

A family $\mathcal{F}\subseteq\mathcal{AD}$ has the Nash-Williams property if for any two distinct members in $\mathcal{F}$ , neither is an initial segment of the other.

Nash-Williams families correspond to metrically open sets in $\mathcal{D}$ .

Definition 5.3.

Suppose $M\in\mathcal{D}$ and $B\in\widehat{\mathcal{AD}}(M)$ . A Nash-Williams family $\mathcal{F}\subseteq r[B,M]^{*}$ is a front on $[B,M]^{*}$ if for each $N\in[B,M]^{*}$ , there is some $C\in\mathcal{F}$ such that $C\sqsubset N$ .

A front $\mathcal{F}$ on $[B,M]^{*}$ determines a collection of disjoint (Ellentuck) basic open sets $[C,M]$ , $C\in\mathcal{F}$ , whose union is exactly $[B,M]^{*}$ .

Recall that for level sets $X,Y\subseteq\mathbb{D}$ , we write $X\sqsubset Y$ exactly when $X$ and $Y$ have the same cardinality, $\ell_{X}<\ell_{Y}$ , and $Y\restriction\ell_{X}=X$ . More generally, for $B,F\in\widehat{\mathcal{AD}}$ , write $B\sqsubseteq F$ exactly when $B=F\upharpoonleft\ell_{B}$ ; in this case, write $B\sqsubset F$ if also $\ell_{B}<\ell_{F}$ . Given $\mathcal{F}\subseteq\mathcal{AD}$ and $B\in\widehat{\mathcal{AD}}$ , define

(53)

\mathcal{F}_{B}=\{F\in\mathcal{F}:B\sqsubset F\}.

In particular, if $\mathcal{F}\subseteq r[B,\mathbb{D}]^{*}$ , then $\mathcal{F}_{B}=\mathcal{F}$ . If $\mathcal{F}$ is a Nash-Williams family, then $B\in\mathcal{F}$ if and only if $\mathcal{F}_{B}=\{B\}$ .

Given $M\in\mathcal{D}$ , let

(54)

\mathcal{F}|M=\{F\in\mathcal{F}:F\in\mathcal{AD}(M)\}.

With this notation, $\mathcal{F}_{B}|M=\mathcal{F}\cap r[B,M]^{*}$ , for any $B\in\widehat{\mathcal{AD}}$ . For $F\in\mathcal{AD}$ , let $|F|$ denote the $k$ for which $F\in\mathcal{AD}_{k}$ . Given a set $\mathcal{F}\subseteq\mathcal{AD}$ , let

(55)

\widetilde{\mathcal{F}}=\{r_{k}(F):F\in\mathcal{F}\mathrm{\ and\ }k\leq|F|\}.

If $\mathcal{F}$ is a Nash-Williams family, then $\mathcal{F}$ consists of the $\sqsubseteq$ -maximal members of $\widetilde{\mathcal{F}}$ .

We now prove an analogue of the Nash-Williams Theorem for our spaces of good diagonal coding antichains.

Assumption 5.4.

Recall that we are under Convention 5.1. Given $M\in\mathcal{D}$ and $A\in\widehat{\mathcal{AD}}(M)$ , let $d=\operatorname{depth}_{M}(A)$ and $D=r_{d}(M)$ . Recall that $A^{+}$ denotes the union of $A$ with the set of immediate extensions in $\widehat{M}$ of the members of $\max(A)$ . Let $B$ be a member of $\widehat{\mathcal{AD}}(M)$ such that $A\sqsubset B\subseteq A^{+}$ . In what follows we consider simultaneously the two pairs of cases for triples $(A,B,k)$ , from Section 4:

1. Case (a).
  
  $\max(r_{k+1}(\mathbb{D}))$ has a splitting node.

1. Case (b).
  
  $\max(r_{k+1}(\mathbb{D}))$ has a coding node.

1. Case (i).
  
  $k\geq 1$ , $A\in\mathcal{AD}_{k}$ , and $B=A^{+}$ .

1. Case (ii).
  
  $k\geq 0$ , $A$ has at least one node, $\max(A)\sqsubset\max(B)$ , and $A=C\upharpoonleft\ell$ for some $C\in\mathcal{AD}_{k+1}$ and $\ell<\ell_{C}$ such that $r_{k}(C)\sqsubseteq A$ and $B\sqsubseteq C$ .

Theorem 5.5.

Given $M\in\mathcal{D}$ , $(A,B,k)$ , $d=\operatorname{depth}_{M}(A)$ , and $D=r_{d}(M)$ as in Assumption 5.4, let $\mathcal{F}\subseteq r[B,M]^{*}$ be a Nash-Williams family. Then there is an $N\in[D,M]$ such that either $\mathcal{F}|N$ is a front on $[B,N]^{*}$ or else $\mathcal{F}|N=\emptyset$ .

Proof.

Since $A$ and $B$ are fixed, we shall use lower case $a,b,c,\dots$ to denote members of $\mathcal{AD}$ in this proof. Recall that the notation $N\leq M$ means that $N\in[\emptyset,M]$ . We say that $N\leq M$ accepts $a\in r[B,N]^{*}$ if $\mathcal{F}_{a}|N$ is a front on $[a,N]$ . We say that $N$ widely-rejects (w-rejects) $a$ if either

(a)

$a\not\in r[B,N]^{*}$ ; or
(b)

$a\in r[B,N]^{*}$ and $\forall P\in[\operatorname{depth}_{N}(a),N]\ \exists Q\in[a,P]\ \forall n(r_{n}(Q)\not\in\mathcal{F})$ .

We say that $N$ decides $a$ if either $N$ accepts $a$ or else $N$ w-rejects $a$ .¹¹1After the author had developed this proof, it was pointed out that a similar asymmetric version of combinatorial forcing was developed by Todorcevic in notes for a graduate course in Ramsey theory. However, those notes do not directly apply to sets of the form $[B,M]^{*}$ , nor do they include the concluding argument in our proof after Lemma 5.10. For $n\in\omega$ , let $[n,N]$ denote $[r_{n}(N),N]$ .

Fact 5.6.

If $N$ accepts $a$ , then so does each $P\leq N$ with $a\in\mathcal{AD}(P)$ . If $N$ w-rejects $a$ , then either $a\not\in r[B,N]^{*}$ and every $P\leq N$ also rejects $a$ , or else $a\in r[B,N]^{*}$ and every $P\in[\operatorname{depth}_{N}(a),N]$ w-rejects $a$ .

Proof.

Suppose $N$ accepts $a$ and $P\leq N$ with $a\in\mathcal{AD}(P)$ . Since $\mathcal{F}_{a}|N$ is a front on $[a,N]$ , it follows that $\mathcal{F}_{a}|P$ is a front on $[a,P]$ . Hence $P$ accepts $s$ .

Suppose $N$ w-rejects $a$ . If $a\not\in\mathcal{AD}(N)$ , then also for each $P\leq N$ , $a\not\in\mathcal{AD}(P)$ and hence $P$ w-rejects $a$ . Otherwise, $a\in\mathcal{AD}(N)$ . Let $n=\operatorname{depth}_{N}(a)$ and suppose $P\in[n,N]$ . Since $N$ w-rejects $a$ , for each $Q\in[n,N]$ there is an $R\in[n,Q]$ such that for all $m$ , $r_{m}(R)\not\in\mathcal{F}$ . Note that $P\in[n,N]$ implies $[n,P]\subseteq[n,N]$ ; so for each $Q\in[n,P]$ there is an $R\in[a,Q]$ such that for all $m$ , $r_{m}(Q)\not\in\mathcal{F}$ . Therefore, $P$ w-rejects $a$ . ∎

Lemma 5.7.

Given $a\in r[B,N]^{*}$ and $n=\operatorname{depth}_{N}(a)$ , either $\exists P\in[n,N]$ which w-rejects $a$ , or else $\forall P\in[n,N]\ \exists Q\in[n,P]$ which accepts $a$ .

Proof.

Suppose there is no $P\in[n,N]$ which w-rejects $a$ . Then $\forall P\in[n,N]$ ,

(56)

\exists Q\in[n,P]\ \forall X\in[a,Q]\ \exists m(r_{m}(X)\in\mathcal{F}).

Thus, for all $P\in[n,N]$ there is a $Q\in[n,P]$ such that $\mathcal{F}_{a}|Q$ is a front on $[a,Q]$ ; that is, $Q$ accepts $a$ . ∎

Fact 5.8.

(a)

For each $a\in r[B,M]^{*}$ , there is an $N\in[\operatorname{depth}_{M}(a),M]$ which decides $a$ .
(b)

If $a\in r[B,M]^{*}$ , then $N\in[B,M]^{*}$ with $a\in\mathcal{AD}(N)$ accepts $a$ if and only if $N$ accepts each $b\in r_{|a|+1}[a,N]$ .

Proof.

For (a), let $n=\operatorname{depth}_{M}(a)$ . By Lemma 5.7, either there is an $N\in[n,M]$ which w-rejects $a$ , or else there is an $N\in[n,M]$ which accepts $a$ .

For (b), given the hypotheses, $N$ accepts $a$ iff $\mathcal{F}_{a}|N$ is a front on $[a,N]$ iff for each $b\in r_{|a|+1}[a,N]$ , $\mathcal{F}_{a}|N$ is a front on $[b,N]$ iff $N$ accepts each $b\in r_{|a|+1}[a,N]$ . ∎

Recall that $B\in\widehat{\mathcal{AD}}$ , but is not necessarily a member of $\mathcal{AD}$ . We shall say that $N$ accepts $B$ if $N$ accepts $a$ for all $a\in r_{k+1}[B,N]^{*}$ .

Fact 5.9.

If $N\in[B,M]^{*}$ accepts $B$ , then $\mathcal{F}_{B}|N$ is a front on $[B,N]^{*}$ .

Proof.

For each $a\in r_{k+1}[B,N]^{*}$ , $N$ accepts $a$ implies that $\mathcal{F}_{a}|N$ is a front on $[a,N]$ . Since $[B,N]^{*}=\bigcup\{[a,N]:a\in r_{k+1}[B,N]^{*}\}$ , it follows that $\mathcal{F}|N=\bigcup\{\mathcal{F}_{a}|N:a\in r_{k+1}[B,N]^{*}\}$ , which is a front on $[B,N]^{*}$ . ∎

Lemma 5.10.

There is an $N\in[d,M]$ which decides each $a$ in $r[B,N]^{*}$ .

Proof.

By finitely many applications of Fact 5.8, we obtain an $M_{1}\in[d+1,M]$ such that $M_{1}$ decides each $a\in r[B,M]^{*}$ with $a\leq_{\mathrm{fin}}r_{d+1}(M)$ . Given $M_{i}$ , by finitely many applications of Fact 5.8, we obtain an $M_{i+1}\in[d+i+1,M_{i}]$ such that $M_{i+1}$ decides each $a\in r[B,M_{i}]^{*}$ with $a\leq_{\mathrm{fin}}r_{d+i+1}(M_{i})$ . Let $N=\bigcup_{i=1}^{\infty}r_{d+i}(M_{i})$ , which is the same as $\bigcup_{i=1}^{\infty}r_{d+i+1}(M_{i})$ . Then $N\in[d,M]$ (in fact, $N\in[d+1,M]$ ) and for $a\in r[B,N]^{*}$ , $M_{i}$ decides $a$ , where $i$ is the index satisfying $a\leq_{\mathrm{fin}}r_{d+i}(M_{i})$ . Since $N\in[d+i,M_{i}]$ , it follows that $N$ decides $a$ in the same way that $M_{i}$ does. Thus, $N$ decides all $a\in r[B,N]^{*}$ . ∎

Now we finish the proof of the theorem. Take $N$ as in Lemma 5.10 and define a coloring $f:r[B,N]^{*}\rightarrow 2$ by $f(a)=0$ if $N$ accepts $a$ and $f(a)=1$ if $N$ w-rejects $a$ . By the Extended Pigeonhole Principle, Theorem 4.5, there is a $P\in[d,N]$ for which $f$ is monochromatic on $r_{k+1}[B,P]^{*}$ . Now if $f$ has color $0$ on this set, then $P$ accepts $B$ and by Fact 5.9, $\mathcal{F}|P$ is a front on $[B,P]^{*}$ .

Otherwise, $f$ has color $1$ on $r_{k+1}[B,P]^{*}$ so $P$ w-rejects each member of $r_{k+1}[B,P]^{*}$ . Let $P_{0}=P$ . Apply Theorem 4.5 finitely many (possibly $0$ ) times, to obtain some $P_{1}\in[d+1,P_{0}]$ such that for each $a\in r[B,P_{1}]^{*}$ with $a\subseteq r_{d+1}(P_{0})$ , all members of $r_{|a|+1}[B,P_{1}]^{*}$ have the same $f$ -color. Since such an $a$ is necessarily in $r_{k+1}[B,P_{0}]^{*}$ and $P_{0}$ w-rejects $a$ , Fact 5.8 implies that this $f$ -color must be $1$ .

For $i\geq 1$ , we have the following the induction hypothesis: $P_{i}\in[d+i,P_{i-1}]$ and for each $a\in r[B,P_{i-1}]^{*}$ with $a\subseteq r_{d+i}(P_{i-1})$ , $P_{i}$ w-rejects all members of $r_{|a|+1}[a,P_{i}]$ . Apply Theorem 4.5 finitely many times to obtain a $P_{i+1}\in[d+i+1,P_{i}]$ such that $f$ is monochromatic on $r_{|a|+1}[a,P_{i+1}]$ for each $a\in r[B,P_{i}]^{*}$ with $a\subseteq r_{d+i+1}(P_{i})$ . Fix an $a\in r[B,P_{i}]^{*}$ with $a\subseteq r_{d+i+1}(P_{i})$ . If $|a|=k+1$ then $P_{i+1}$ w-rejects $a$ , since $a\in r_{k+1}[B,P]^{*}$ and $P_{i+1}\in[B,P]^{*}$ . Suppose now that $|a|>k+1$ . By the induction hypothesis, $P_{i}$ w-rejects $a$ since $a\in r_{|b|+1}[b,P_{i}]$ , where $b=r_{|a|-1}(a)\subseteq r_{d+i}(P_{i-1})$ . Now if the $f$ -color on $r_{|a|+1}[a,P_{i+1}]$ is $0$ , then $P_{i+1}$ accepts $a$ by Fact 5.8, a contradiction. Hence, $f$ has color $1$ on $r_{|a|+1}[a,P_{i+1}]$ ; in particular, $P_{i+1}$ w-rejects each member of $r_{|a|+1}[a,P_{i+1}]$ .

Let $Q=\bigcup_{i=1}^{\infty}r_{d+i}(P_{i})$ . Then $Q$ w-rejects each member of $r[B,Q]^{*}$ . By definition of w-rejects, for each $a\in r[B,Q]^{*}$ ,

(57)

\forall R\in[\operatorname{depth}_{Q}(a),Q]\ \exists X\in[a,R]\ \forall n(r_{n}(X)\not\in\mathcal{F})

Suppose toward a contradiction that there is an $a\in\mathcal{F}|Q$ . Then for all $X\in[a,Q]$ , $r_{|a|}(X)=a\in\mathcal{F}$ . So $Q\in[\operatorname{depth}_{Q}(a),Q]$ and for all $X\in[a,Q]$ , $\exists n(r_{n}(X)\in\mathcal{F})$ . But this contradicts (57). Thus $\mathcal{F}|Q$ must be empty. ∎

Definition 5.11.

Let $\mathcal{X}$ be a subset of $\mathcal{D}$ . We say that $\mathcal{X}$ is Ramsey if for each $M\in\mathcal{D}$ there is an $N\leq M$ such that either $\mathcal{X}\subseteq[\emptyset,N]$ or else $\mathcal{X}\cap[\emptyset,N]=\emptyset$ . $\mathcal{X}$ is said to be completely Ramsey (CR) if for each $C\in\mathcal{AD}$ and each $M\in\mathcal{D}$ , there is an $N\in[C,M]$ such that either $[C,N]\subseteq\mathcal{X}$ or else $[C,N]\cap\mathcal{X}=\emptyset$ . We shall say that $\mathcal{X}$ is CR^∗ if given $M\in\mathcal{D}$ and $(A,B)$ as in Assumption 5.4, there is an $N\in[D,M]$ such that either $[B,N]^{*}\subseteq\mathcal{X}$ or else $[B,N]^{*}\cap\mathcal{X}=\emptyset$ .

Remark 5.12.

Since metrically open sets correspond to Nash-Williams families, Theorem 5.5 implies that metrically open sets are not only completely Ramsey but moreover CR^∗, even when relativized below some $M\in\mathcal{D}$ .

Lemma 5.13.

Complements of CR^∗ sets are CR^∗.

Proof.

Suppose $\mathcal{X}\subseteq\mathcal{D}$ is CR^∗, and $M\in\mathcal{D}$ , $(A,B,k)$ , $d=\operatorname{depth}_{M}(A)$ , and $D=r_{d}(M)$ are as in Assumption 5.4. By definition of CR^∗, there is an $N\in[D,M]$ such that either $[B,N]^{*}\subseteq\mathcal{X}$ or else $[B,N]^{*}\cap\mathcal{X}=\emptyset$ . Letting $\mathcal{Y}=\mathcal{D}\setminus\mathcal{X}$ , we see that either $[B,N]^{*}\cap\mathcal{Y}=\emptyset$ or else $[B,N]^{*}\subseteq\mathcal{Y}$ . ∎

In the rest of this section, given $M\in\mathcal{D}$ , endow $[\emptyset,M]$ with the subspace topology inherited from $\mathcal{D}$ with the metric topology. The next two lemmas build up to Lemma 5.16, which will show that countable unions of CR^∗ sets are CR^∗.

Lemma 5.14.

Suppose $\mathcal{X}\subseteq\mathcal{D}$ is CR^∗. Then for each $M\in\mathcal{D}$ and each $C\in\mathcal{AD}(M)$ , there is an $N\in[C,M]$ such that $\mathcal{X}\cap[\emptyset,N]$ is metrically open in $[\emptyset,N]$ .

Proof.

Fix $M\in\mathcal{D}$ and $C\in\mathcal{AD}(M)$ . Notice that $[\emptyset,M]=\bigcup_{j<\tilde{j}}[B_{j},M]^{*}$ , where $\langle(A_{j},B_{j}):j<\tilde{j}\rangle$ enumerates all pairs $(A,B)$ with $\operatorname{depth}_{M}(A)=\operatorname{depth}_{M}(C)$ satisfying Assumption 5.4.

Let $M_{-1}=M$ . Given $M_{j-1}$ for $j<\tilde{j}$ , $\mathcal{X}$ being CR^∗ implies there is an $M_{j}\in[C,M_{j-1}]$ such that either $[B_{j},M_{j}]^{*}\subseteq\mathcal{X}$ or else $\mathcal{X}\cap[B_{j},M_{j}]^{*}=\emptyset$ . Let $N=M_{\tilde{j}-1}$ . Then $N\in[C,M]$ and for each $j<\tilde{j}$ , $[B_{j},N]^{*}\subseteq[B_{j},M_{j}]^{*}$ . Since $[\emptyset,N]=\bigcup_{j<\tilde{j}}[B_{j},N]^{*}$ , it follows that

(58)

\mathcal{X}\cap[\emptyset,N]=\bigcup_{j<\tilde{j}}(\mathcal{X}\cap[B_{j},N]^{*}).

For $j<\tilde{j}$ , if $[B_{j},M_{j}]^{*}\subseteq\mathcal{X}$ then $\mathcal{X}\cap[B_{j},N]^{*}=[B_{j},N]^{*}$ ; and if $\mathcal{X}\cap[B_{j},M_{j}]^{*}=\emptyset$ then $\mathcal{X}\cap[B_{j},N]^{*}=\emptyset$ . Thus,

(59)

\mathcal{X}\cap[\emptyset,N]=\bigcup_{j\in J}[B_{j},N]^{*},

where $J=\{j<\tilde{j}:[B_{j},M_{j}]^{*}\subseteq\mathcal{X}\}$ . As each $[B_{j},N]^{*}$ is metrically open in the subspace $[\emptyset,N]$ , $\mathcal{X}\cap[\emptyset,N]$ is also metrically open in the subspace $[0,N]$ . ∎

Lemma 5.15.

Suppose $\mathcal{X}_{n}$ , $n\in\mathbb{N}$ , are CR^∗ sets. Then for each $M\in\mathcal{D}$ and each $C\in\mathcal{AD}(M)$ , there is an $N\in[C,M]$ such that for each $n\in\mathbb{N}$ , $\mathcal{X}_{n}\cap[\emptyset,N]$ is metrically open in $[\emptyset,N]$ .

Proof.

Assume the hypotheses and let $d=\operatorname{depth}_{M}(C)$ and $D=r_{d}(M)$ . Since $\mathcal{X}_{0}$ is CR^∗, Lemma 5.14 implies there is an $M_{0}\in[D,M]$ and a metrically open set $\mathcal{O}_{0}\subseteq\mathcal{D}$ satisfying $\mathcal{X}_{0}\cap[\emptyset,M_{0}]=\mathcal{O}_{0}\cap[\emptyset,M_{0}]$ . In general, given $M_{i}$ , by Lemma 5.14 there is some $M_{i+1}\in[r_{d+i+1}(M_{i}),M_{i}]$ and some metrically open $\mathcal{O}_{i}\subseteq\mathcal{D}$ satisfying $\mathcal{X}_{i}\cap[\emptyset,M_{i}]=\mathcal{O}_{i}\cap[\emptyset,M_{i}]$ . Let $N=\bigcup_{i=0}^{\infty}r_{d+i}(M_{i})$ . Then $N$ is a member of $[D,M]$ .

Letting $M_{-1}=M$ , note that $N\in[r_{d+i}(M_{i}),M_{i-1}]$ for each $i\in\mathbb{N}$ . It follows that for each $i\in\mathbb{N}$ , $\mathcal{X}_{i}\cap[\emptyset,N]=\mathcal{O}_{i}\cap[\emptyset,N]$ . Hence $\mathcal{X}_{i}\cap[\emptyset,N]$ is metrically open in $[\emptyset,N]$ . ∎

Lemma 5.16.

Countable unions of CR^∗ sets are CR^∗.

Proof.

Suppose $\mathcal{X}_{n}$ , $n\in\mathbb{N}$ , are CR^∗ subsets of $\mathcal{D}$ , and let $\mathcal{X}=\bigcup_{n=0}^{\infty}\mathcal{X}_{n}$ . Let $(M,A,B,k)$ be as in Assumption 5.4, and let $d=\operatorname{depth}_{M}(A)$ and $D=r_{d}(M)$ . By Lemma 5.15, there is a $M^{\prime}\in[D,M]$ such that for each $n$ , $\mathcal{X}_{n}\cap[\emptyset,M^{\prime}]$ is metrically open in $[\emptyset,M^{\prime}]$ . Thus, $\mathcal{X}\cap[\emptyset,M^{\prime}]$ is metrically open in $[\emptyset,M^{\prime}]$ , so $\mathcal{X}\cap[\emptyset,M^{\prime}]=\mathcal{O}\cap[\emptyset,M^{\prime}]$ for some metrically open set $\mathcal{O}\subseteq\mathcal{D}$ .

Theorem 5.5 implies that $\mathcal{O}$ is CR^∗ in $[\emptyset,M^{\prime}]$ . Hence, there is some $N\in[D,M^{\prime}]$ such that either $[B,N]^{*}\subseteq\mathcal{O}$ or else $[B,N]^{*}\cap\mathcal{O}=\emptyset$ . Therefore, either

(60)

[B,N]^{*}=[B,N]^{*}\cap[\emptyset,M^{\prime}]\subseteq\mathcal{O}\cap[\emptyset,M^{\prime}]=\mathcal{X}\cap[\emptyset,M^{\prime}],

or else

(61)	$\displaystyle[B,N]^{*}\cap\mathcal{X}$	$\displaystyle=[B,N]^{*}\cap[\emptyset,M^{\prime}]\cap\mathcal{X}$
(62)		$\displaystyle\subseteq[B,N]^{*}\cap[\emptyset,M^{\prime}]\cap\mathcal{O}$
(63)		$\displaystyle\subseteq[B,N]^{*}\cap\mathcal{O}=\emptyset.$

Thus, $\mathcal{X}$ is CR^∗. ∎

Theorem 5.17.

Let $\mathbf{K}$ be an enumerated Fraïssé structure satisfying SDAP⁺, with finitely many relations of arity at most two. Let $\mathbb{D}$ be a good diagonal coding antichain representing $\mathbf{K}$ . Then the collection of CR^∗ subsets of $\mathcal{D}(\mathbb{D})$ contains all Borel subsets of $\mathcal{D}(\mathbb{D})$ . In particular, Borel subsets of the space $\mathcal{D}(\mathbb{D})$ are completely Ramsey, and hence Ramsey.

Proof.

This follows from Theorem 5.5 and Lemmas 5.13 and 5.16. ∎

Remark 5.18.

A simple modification of the proof yields the same result for LSDAP⁺ structures.

6. Main Theorems

This section contains the main theorem that Borel sets in our spaces of subcopies of a given structure $\mathbf{K}$ are Ramsey, conditions under which analogues of the Ellentuck theorem hold, and a Nash-Williams-style corollary recovering exact big Ramsey degrees.

6.1. Borel sets are Ramsey

We now prove the Main Theorem. Fix an enumerated Fraïssé structure $\mathbf{K}$ satisfying SDAP⁺ and a good diagonal coding antichain $\mathbb{D}\subseteq\mathbb{U}(\mathbf{K})$ representing a subcopy of $\mathbf{K}$ . Recall that the universe of $\mathbf{K}$ is $\mathbb{N}$ . Each substructure $\mathbf{M}$ of $\mathbf{K}$ is uniquely identified with its universe $\mathrm{M}\subseteq\mathbb{N}$ , which in turn, is uniquely identified with the set of coding nodes $\{c_{n}:n\in\mathrm{M}\}$ . To avoid any ambiguity, we will use $T_{\mathbf{M}}$ (rather than $M$ ) to denote the subtree of $\mathbb{D}$ induced by the set of coding nodes $\{c_{n}:n\in\mathrm{M}\}$ . Define

(64)

\mathcal{B}(\mathbb{D})=\{\mathrm{M}\in[\mathbb{N}]^{\mathbb{N}}:T_{\mathbf{M}}\in\mathcal{D}(\mathbb{D})\}.

That is, $\mathrm{M}\subseteq\mathbb{N}$ is a member of $\mathcal{B}(\mathbb{D})$ if and only if $\{c_{n}:n\in\mathrm{M}\}\subseteq\mathbb{D}$ and the tree induced by $\{c_{n}:n\in\mathrm{M}\}$ is similar to the tree induced by $\mathbb{D}$ . Note that $\mathcal{B}(\mathbb{D})$ is a subspace of the Baire space.

Let $\mathbf{D}$ denote the substructure $\mathbf{K}\restriction\mathbb{D}$ , and let $\langle d_{n}:n\in\mathbb{N}\rangle$ be the increasing enumeration of the universe $\mathrm{D}$ of $\mathbf{D}$ . Notice that $\langle c_{d_{n}}:n\in\mathbf{N}\rangle$ enumerates the coding nodes in $\mathbb{D}$ . Define

(65)

\mathbf{K}(\mathbf{D})=\{\mathbf{M}\leq\mathbf{D}:\mathrm{M}\in\mathcal{B}(\mathbb{D})\}.

That is, $\mathbf{K}(\mathbf{D})$ is the subspace of ${\mathbf{K}\choose\mathbf{K}}$ consisting of all substructures $\mathbf{M}$ of $\mathbf{D}$ with universe $\mathrm{M}\in\mathcal{B}(\mathbb{D})$ . Notice that $\mathbf{K}(\mathbf{D})$ is identified with a subspace of the Baire space via its identification with $\mathcal{B}(\mathbb{D})$ . For $\mathbf{M}\in\mathbf{K}(\mathbf{D})$ , we will let $\mathbf{K}(\mathbf{M})$ denote the cube of all substructures of $\mathbf{M}$ in $\mathbf{K}(\mathbf{D})$ .

For $\mathbf{M}\in\mathbf{K}(\mathbf{D})$ , let $\langle m_{i}:i\in\mathbb{N}\rangle$ be the increasing enumeration of $\mathrm{M}$ . Then increasing bijection $m_{i}\mapsto d_{i}$ induces an isomorphism from $\mathbf{M}$ to $\mathbf{D}$ , and $c_{m_{i}}\mapsto c_{d_{i}}$ induces a similarity map from $T_{\mathbf{M}}$ to $\mathbb{D}$ . Given $n\in\mathbb{N}$ , define $\mathbf{M}_{n}=\mathbf{M}\restriction\{m_{i}:i<n\}$ . Let

(66)

\mathcal{A}\mathbf{K}(\mathbf{D})=\{\mathbf{M}_{n}:\mathbf{M}\in\mathbf{K}(\mathbf{D})\mathrm{\ and\ }n\in\mathbb{N}\}.

For $\mathbf{A}\in\mathcal{A}\mathbf{K}(\mathbf{D})$ and $\mathbf{M}\in\mathbf{K}(\mathbf{D})$ , write $\mathbf{A}\sqsubset\mathbf{M}$ if and only if $\mathbf{A}=\mathbf{M}_{n}$ for some $n$ . Define

(67)

[\mathbf{A},\mathbf{M}]=\{\mathbf{N}\in\mathbf{K}(\mathbf{D}):\mathbf{A}\sqsubset\mathbf{N}\}.

These are the basic open sets for the Ellentuck topology on $\mathbf{K}(\mathbf{D})$ corresponding to the basic Ellentuck open sets $[\mathrm{A},\mathrm{M}]$ in the Baire space, where $\mathrm{A}$ and $\mathrm{M}$ are the universes of $\mathbf{A}$ and $\mathbf{M}$ , respectively. The basic open sets for the metric topology on $\mathbf{K}(\mathbf{D})$ are those of the form $[\mathbf{A},\mathbf{D}]$ , where $\mathbf{A}\in\mathcal{A}\mathbf{K}(\mathbf{D})$ .

Let $\theta:\mathbf{K}(\mathbf{D})\rightarrow\mathcal{D}(\mathbb{D})$ denote the map which sends each $\mathbf{M}\in\mathbf{K}(\mathbf{D})$ to the tree $T_{\mathbf{M}}$ in $\mathcal{D}(\mathbb{D})$ . This map is certainly a bijection. We will show that $\theta$ is in fact a homeomorphism between these two spaces with their metric topologies.

For $n\in\mathbb{N}$ , let $k_{n}$ denote the least integer such that $c^{\mathbb{D}}_{n-1}\in r_{k_{n}}(\mathbb{D})$ . Since each $T\in\mathcal{D}(\mathbb{D})$ is similar to $\mathbb{D}$ , it follows that $k_{n}$ is the least integer such that the $(n-1)$ -st coding node of $T$ is in $r_{k_{n}}(T)$ . In particular, $k_{n}$ is least such that $\mathbf{D}_{n}=\mathbf{K}\restriction r_{k_{n}}(\mathbb{D})$ . For the following lemma, recall that since $\mathbb{D}$ is a good diagonal coding antichain, there is some $n_{\mathbb{D}}$ such that for each $n\geq n_{\mathbb{D}}$ , there is a one-to-one correspondence between the nodes in $\max(r_{k_{n}}(\mathbb{D}))^{+}$ and the $1$ -types over $\mathbf{D}_{n}$ .

Lemma 6.1.

Suppose $\mathbf{M}\in\mathbf{K}(\mathbf{D})$ and $\mathbf{A}=\mathbf{M}_{n}$ , where $n\geq n_{\mathbb{D}}$ . Then $\theta([\mathbf{A},\mathbf{M}])=[r_{k_{n}}(T_{\mathbf{M}}),T_{\mathbf{M}}]$ .

Proof.

Since $n\geq n_{\mathbb{D}}$ , there is a one-to-one correspondence between the nodes in $\max(r_{k_{n}}(T_{\mathbf{M}}))^{+}$ and the $1$ -types over $\mathbf{A}$ . For $\mathbf{N}\in[\mathbf{A},\mathbf{M}]$ , $\mathbf{N}$ extends $\mathbf{A}$ to some isomorphic subcopy of $\mathbf{M}$ , and $T_{\mathbf{N}}$ is a subtree of $T_{\mathbf{M}}$ . In order for $\mathbf{N}$ to be isomorphic to $\mathbf{M}$ , each $1$ -type over $\mathbf{A}$ must be represented by a node in $\max(r_{k_{n}}(T_{\mathbf{N}}))^{+}$ . The only way this is possible is if $r_{k_{n}}(T_{\mathbf{N}})=r_{k_{n}}(T_{\mathbf{M}})$ . Thus, letting $A=r_{k_{n}}(T_{\mathbf{M}})$ ,

(68)	$\displaystyle\theta([\mathbf{A},\mathbf{M}])$	$\displaystyle=\{T_{\mathbf{N}}:\mathbf{N}\in[\mathbf{A},\mathbf{M}]\}$
(69)		$\displaystyle=\{T_{\mathbf{N}}:\mathbf{N}\in[\mathbf{A},\mathbf{M}]\mathrm{\ and\ }r_{k_{n}}(T_{\mathbf{N}})=r_{k_{n}}(T_{\mathbf{M}})\}$
(70)		$\displaystyle=\{T_{\mathbf{N}}:A\sqsubset T_{\mathbf{N}}\mathrm{\ and\ }T_{\mathbf{N}}\leq T_{\mathbf{M}}\}$
(71)		$\displaystyle=[A,T_{\mathbf{M}}].$

∎

Thus, $\theta$ takes the basic Ellentuck open set $[\mathbf{M}_{n},\mathbf{M}]$ to the basic Ellentuck open set $[r_{k_{n}}(T_{\mathbf{M}}),T_{\mathbf{M}}]$ whenever $n\geq n_{\mathbb{D}}$ . Furthermore, $\theta$ is a homeomorphism from $\mathbf{K}(\mathbf{D})$ with its metric topology to $\mathcal{D}(\mathbb{D})$ with its metric topology, as follows from the next lemma.

Lemma 6.2.

The map $\theta$ takes each basic metrically open set in $\mathbf{K}(\mathbf{D})$ to a metrically open set in $\mathcal{B}(\mathbb{D})$ , and $\theta^{-1}$ takes each basic metrically open set in $\mathcal{B}(\mathbb{D})$ to a metrically open set in $\mathbf{K}(\mathbf{D})$ .

Proof.

Let $[\mathbf{A},\mathbf{D}]$ be a basic open set in the metric topology on $\mathbf{K}(\mathbf{D})$ , and let $n$ be the number of vertices in $\mathbf{A}$ . Then

(72)		$\displaystyle\theta([\mathbf{A},\mathbf{D}])$	$\displaystyle=\bigcup\{[r_{k_{n}}(T_{\mathbf{M}}),\mathbb{D}]:\mathbf{A}\sqsubset\mathbf{M}\}$
(73)			$\displaystyle=\bigcup\{[B,\mathbb{D}]:B\in\mathcal{AD}_{k_{n}}\mathrm{\ and\ }\mathbf{D}\restriction B=\mathbf{A}\}$

which is a countable union of metrically open sets in $\mathcal{D}(\mathbb{D})$ . Conversely, given a basic open set $[A,\mathbb{D}]$ in the metric topology on $\mathcal{D}(\mathbb{D})$ , we may without loss of generality assume that $A\in\mathcal{AD}_{k_{n}}$ for some $n$ . Let $n^{\prime}$ denote the least integer such that for each $\mathbf{M}\in\mathbf{K}(\mathbf{D})$ ,

(74)

r_{k_{n}}(T_{\mathbf{M}_{n^{\prime}}})=r_{k_{n}}(T_{\mathbf{M}}).

Then

(75)		$\displaystyle\theta^{-1}([A,\mathbb{D}])$	$\displaystyle=\{\mathbf{M}\in\mathbf{K}(\mathbf{D}):T_{\mathbf{M}}\in[A,\mathbb{D}]\}$
(76)			$\displaystyle=\bigcup\{[\mathbf{B},\mathbf{D}]:\mathbf{B}\in\mathcal{A}\mathbf{K}(\mathbf{D})_{n^{\prime}}\mathrm{\ and\ }r_{k_{n}}(T_{\mathbf{B}})=A\},$

which is a countable union of basic metrically open sets in $\mathbf{K}(\mathbf{D})$ . ∎

A set $\mathcal{X}\subseteq\mathbf{K}(\mathbf{D})$ is Ramsey if for any $\mathbf{M}\in\mathbf{K}(\mathbf{D})$ , there is some $\mathbf{N}\leq\mathbf{M}$ in $\mathbf{K}(\mathbf{D})$ such that either $\mathbf{K}(\mathbf{N})\subseteq\mathcal{X}$ or else $\mathbf{K}(\mathbf{N})\cap\mathcal{X}=\emptyset$ . A set $\mathcal{X}\subseteq\mathbf{K}(\mathbf{D})$ is completely Ramsey if for any $\mathbf{A}\in\mathcal{A}\mathbf{K}(\mathbf{D})$ and $\mathbf{M}\in\mathbf{K}(\mathbf{D})$ , there is some $\mathbf{N}\in[\mathbf{A},\mathbf{M}]$ such that either $[\mathbf{A},\mathbf{N}]\subseteq\mathcal{X}$ or else $[\mathbf{A},\mathbf{N}]\cap\mathcal{X}=\emptyset$ .

Theorem 6.3.

Let $\mathbf{K}$ be an enumerated Fraïssé structure satisfying SDAP⁺ (or LSDAP⁺) with finitely many relations of arity at most two, let $\mathbb{D}$ be a good diagonal coding antichain, and let $\mathbf{D}=\mathbf{K}\restriction\mathbb{D}$ . Then every Borel subset $\mathcal{X}\subseteq\mathbf{K}(\mathbf{D})$ is completely Ramsey, and hence Ramsey.

Proof.

Let $\mathcal{X}$ be a Borel subset of $\mathbf{K}(\mathbf{D})$ , and suppose $\mathbf{A}\in\mathcal{A}\mathbf{K}(\mathbf{D})$ and $\mathbf{M}\in\mathbf{K}(\mathbf{D})$ . If $[\mathbf{A},\mathbf{M}]=\emptyset$ then we are done, so assume that $[\mathbf{A},\mathbf{M}]$ is non-empty. By shrinking $\mathbf{M}$ if necessary, we may assume that $\mathbf{A}$ is an initial segment of $\mathbf{M}$ . Let $n$ be the integer such that $\mathbf{A}=\mathbf{M}_{n}$ . By Lemma 6.1, $\theta([\mathbf{A},\mathbf{M}])=[r_{k_{n}}(T_{\mathbf{M}}),T_{\mathbf{M}}]$ . Let $A$ denote $r_{k_{n}}(T_{\mathbf{M}})$ .

Let $\mathcal{Y}$ be the $\theta$ -image of $\mathcal{X}$ , noting that $\mathcal{Y}$ is Borel in $\mathcal{D}(\mathbb{D})$ with the metric topology by Lemma 6.2. Apply Theorem 5.17 to obtain an $N\in[A,T_{\mathbf{M}}]$ such that either $[A,N]\subseteq\mathcal{Y}$ or else $[A,N]\cap\mathcal{Y}=\emptyset$ . Let $\mathbf{N}=\mathbf{D}\restriction N$ . Then $T_{\mathbf{N}}=N$ , $A=r_{k_{n}}(T_{\mathbf{N}})$ , and $\theta^{-1}([A,N])=\theta^{-1}([r_{k_{n}}(T_{\mathbf{N}}),T_{\mathbf{N}}])=[\mathbf{A},\mathbf{N}]$ , by Lemma 6.1. Thus, either $[\mathbf{A},\mathbf{N}]\subseteq\mathcal{X}$ or else $[\mathbf{A},\mathbf{N}]\cap\mathcal{X}=\emptyset$ .

Minor modifications of the proofs yield the same result for structures with LSDAP⁺. ∎

6.2. Topological Ramsey spaces of homogeneous structures

Theorem 6.4.

Let $\mathbf{K}$ be any one of the following structures with universe $\mathbb{N}$ : The rationals, $\mathbb{Q}_{n}$ , $\mathbb{Q}_{\mathbb{Q}}$ , and or any Fraïssé structure satisfying SDAP⁺ or LSDAP⁺ for which the coding tree of $1$ -types $\mathbb{U}(\mathbf{K})$ has the property that on any given level of $\mathbb{U}(\mathbf{K})$ , only the coding node splits. Then the spaces $\mathcal{D}(\mathbb{D})$ , where $\mathbb{D}$ is a diagonal coding antichain for $\mathbf{K}$ , are actually topological Ramsey spaces.

Proof.

For structures as in the theorem statement, it is straightforward to check that Todorcevic’s Axiom A.3(2) holds. (This is the axiom which fails for the Rado graph and similar structures if one works with good diagonal antichains.) It is simple to check that Axioms A.1, A.2, and A.3(1) hold, and Axiom A.4 is a special case of Theorem 4.5 (these in fact hold for all structures considered in this paper). Then by Todorcevic’s Abstract Ellentuck Theorem in [16], the spaces $\mathcal{D}(\mathbb{D})$ satisfy analogues of Ellentuck’s Theorem. ∎

6.3. Exact big Ramsey degrees from infinite-dimensional Ramsey theory

Let $\mathbb{D}$ be a good diagonal coding antichain for $\mathbf{K}$ , and let $M\in\mathcal{D}(\mathbb{D})$ . Given a finite antichain of coding nodes $A\subseteq M$ , let $\langle c^{A}_{j}:j<n\rangle$ enumerate the coding nodes in $A$ and let $\mathbf{A}$ denote the structure $\mathbf{K}\restriction A$ . Recall that we identify $A$ with the tree which it induces, and that $\mathbf{A}_{j}$ denotes $\mathbf{A}\restriction\{c^{A}_{i}:i<j\}$ . Let $k$ be least such that $A\subseteq r_{k}(M)$ . An envelope $E(A)$ of $A$ in $M$ is a minimal set of nodes in $r_{k+1}(M)$ containing $A$ such that for each $j<n$ , the splitting predecessor of $c^{A}_{j}$ in $M$ is in $E(A)$ , and each $1$ -type over $\mathbf{A}$ is represented by exactly one maximal node in $E(A)$ .

Envelopes can be made canonically as follows: First, add all the splitting predecessors of coding nodes in $A$ and extend them $\prec$ -leftmost in $M$ to length $\ell^{A}_{n-1}+1$ ; let $A^{\prime}$ denote this extension of $A$ . Then proceed by induction on $j<n$ : For each $1$ -type $\tau$ over $\mathbf{A}_{1}$ not already represented by a node in $A^{\prime}$ , add one node $t$ in $M$ of length $\ell^{A}_{0}+1$ such that $t/\mathbf{A}_{0}\sim\tau$ ; let $E_{0}$ denote the set of these nodes of length $\ell^{A}_{0}+1$ . Whenever there is a choice of more than one node $t$ , add the $\prec$ -leftmost such node. Given $E_{j-1}$ for $1\leq j<n$ , for each $1$ -type $\tau$ over $\mathbf{A}_{j+1}$ which is not represented by any node in $A^{\prime}\restriction(\ell^{A}_{j}+1)$ , take the $\prec$ -leftmost node $s$ in $E_{j-1}\cup A^{\prime}\restriction(\ell^{A}_{j-1}+1)$ such that $s/\mathbf{A}_{j}\sim\tau/\mathbf{A}_{j}$ , and extend $s$ $\prec$ -leftmost to a node $t$ in $M$ of length $\ell^{A}_{j}+1$ such that $t/\mathbf{A}_{j+1}\sim\tau$ . Let $E_{j}$ denote the set of these nodes of length $\ell^{A}_{j}+1$ . Then, let $E(A)=A^{\prime}\cup\bigcup_{j<n}E_{j}$ .

Notice that for each $M\in\mathcal{D}(\mathbb{D})$ , every finite antichain $A$ of coding nodes in $M$ has such an envelope in $M$ . Moreover, for any $A,B\subseteq M$ such that $A\sim B$ , the canonical construction of envelopes produces envelopes $E(A)$ and $E(B)$ such that $E(A)\sim E(B)$ .

Now, given a good diagonal coding antichain $\mathbb{D}$ and a finite antichain $A\subseteq\mathbb{D}$ with $n$ coding nodes, let $E(A)$ be the canonical envelope of $A$ in $\mathbb{D}$ . Define $\mathbb{E}$ to be a good diagonal coding antichain contained in $\mathbb{D}$ such that $\mathbb{E}\restriction(\ell^{A}_{n-1}+1)=E(A)$ , and above $E(A)$ , each $1$ -type over an initial structure of $\mathbb{E}$ is represented by exactly one node in $\mathbb{E}$ .

The following theorem of Coulson–Dobrinen–Patel in [3] is recovered as a Nash-Williams style corollary from the Main Theorem in this paper.

Corollary 6.5.

Let $\mathbf{K}$ be an enumerated Fraïssé structure satisfying SDAP⁺ (or LSDAP⁺) with finitely many relations of arity at most two, and let $\mathbb{D}$ be a good diagonal coding antichain representing a copy of $\mathbf{K}$ . Let $A\subseteq\mathbb{D}$ be a finite diagonal antichain, and let $f$ color all similarity copies of $A$ in $\mathbb{D}$ into finitely many colors. Then there is a good diagonal coding antichain $\mathbb{E}\subseteq\mathbb{D}$ representing $\mathbf{K}$ in which all copes of $A$ have the same color.

Proof.

Let $\mathbb{E}$ be an end-extension of the envelope $E(A)$ in $\mathbb{D}$ to a good diagonal coding antichain, and let $f$ color all similarity copies of $A$ in $\mathbb{E}$ into finitely many colors. Let $k$ be the least integer such that $r_{k}(\mathbb{E})$ contains $A$ . Notice that for each $M\in\mathcal{D}(\mathbb{E})$ , $r_{k}(M)\sim E(A)$ , so the coding nodes in any $C\in\mathcal{AD}_{k}(\mathbb{E})$ induce a tree similar to $A$ ; denote this tree by $C_{A}$ . Moreover, for each similarity copy $B$ of $A$ in $\mathbf{E}$ , the canonical envelope $E(B)$ in $\mathbb{E}$ is in $\mathcal{AD}_{k}(\mathbb{E})$ . Thus, $f$ induces a coloring $g$ on $\mathcal{AD}_{k}(\mathbb{E})$ by $g(C)=f(C_{A})$ . This in turn induces an open, hence Borel, coloring $h$ on $\mathcal{D}(\mathbb{E})$ via $h(M)=g(r_{k}(M))$ . By Theorem 6.3, there is an $N\in\mathcal{D}(\mathbb{E})$ on which $h$ is constant. Thus, $f$ is constant on the similarity copies of $A$ in $N$ . ∎

Remark 6.6.

As pointed out in the introduction, the fact that the number of similarity types of diagonal antichains yields the exact big Ramsey degrees is a theorem of Coulson–Dobrinen-Patel in [3].

References

[1] Peter Cameron, Oligomorphic Permutation Groups, Cambridge University Press, 1990.
[2] Rebecca Coulson, Natasha Dobrinen, and Rehana Patel, Fraïssé classes with SDAP⁺, Part I: Indivisibility, (2021), 56 pp, Submitted. arXiv:2207.06393.
[3] by same author, Fraïssé structures with SDAP⁺, Part II: simply characterized big Ramsey structures, (2021), 59 pp, Submitted. arXiv:2207.06505.
[4] Natasha Dobrinen, Borel sets of Rado graphs and Ramsey’s theorem, European Journal of Combinatorics, Proceedings of the 2016 Prague DocCourse on Ramsey Theory, 29 pp, To appear. arXiv:1904.00266v1.
[5] by same author, Ramsey theory of the universal homogeneous k-clique-free graph, Journal of Mathematical Logic, 75 pp, To appear. arXiv:1901.06660.
[6] by same author, The Ramsey theory of the universal homogeneous triangle-free graph, Journal of Mathematical Logic 20 (2020), no. 2, 2050012, 75 pp.
[7] Erik Ellentuck, A new proof that analytic sets are Ramsey, Journal of Symbolic Logic 39 (1974), no. 1, 163–165.
[8] Fred Galvin and Karel Prikry, Borel sets and Ramsey’s Theorem, Journal of Symbolic Logic 38 (1973), no. 2, 193–198.
[9] Alexander Kechris, Vladimir Pestov, and Stevo Todorcevic, Fraïssé limits, Ramsey theory, and topological dynamics of automorphism groups, Geometric and Functional Analysis 15 (2005), no. 1, 106–189.
[10] Alex Kruckman, Disjoint $n$ -amalgamation and pseudofinite countably categorical theories, Notre Dame Journal of Formal Logic 60 (2019), no. 1, 139–160.
[11] Claude Laflamme, Norbert Sauer, and Vojkan Vuksanovic, Canonical partitions of universal structures, Combinatorica 26 (2006), no. 2, 183–205.
[12] C. St. J. A. Nash-Williams, On well-quasi-ordering transfinite sequences, Proceedings of the Cambridge Philosophical Society 61 (1965), 33–39.
[13] Frank P. Ramsey, On a problem of formal logic, Proceedings of the London Mathematical Society 30 (1929), 264–296.
[14] Norbert Sauer, Coloring subgraphs of the Rado graph, Combinatorica 26 (2006), no. 2, 231–253.
[15] Jack Silver, Some applications of model theory in set theory, Annals of Mathematical Logic 3 (1971), no. 1, 45–110.
[16] Stevo Todorcevic, Introduction to Ramsey Spaces, Princeton University Press, 2010.
[17] Andy Zucker, A Note on Big Ramsey degrees, (2020), 21pp, Submitted. arXiv:2004.13162.

Infinite-dimensional Ramsey theory for homogeneous structures with SDAP+

Abstract.

2020 Mathematics Subject Classification:

1. Introduction

Theorem 1.1 (Ramsey [13]).

Theorem 6.3.

Theorem 6.4.

2. Background

2.1. Fraïssé theory and substructure amalgamation properties

Definition 2.1 ([2]).

Definition 2.2 ([2]).

2.2. Coding trees of 11-types

Definition 2.3 (The Coding Tree of 11-Types, [2]).

Definition 2.4 (The Unary-Colored Coding Tree of 11-Types, [2]).

Remark 2.5.

2.3. Passing types and similarity

Definition 2.6 (Passing Type, [2]).

Definition 2.7 (Similarity of Passing Types, [2]).

Definition 2.8.

Fact 2.9 ([2]).

Definition 2.10 (Similarity Map, [2]).

2.4. The properties SDAP+ and LSDAP+

Definition 2.11 (Subtree).

Definition 2.12 (Diagonal tree).

Notation 2.13.

Definition 2.14 (Diagonal Coding Subtree).

Definition 2.15 (Diagonal Coding Tree Property, [2]).

Definition 2.16 (++-Similarity, [2]).

Definition 2.17 (Extension Property, [2]).

Definition 2.18 (SDAP+, [2]).

Remark 2.19.

Convention 2.20.

Convention 2.21.

Definition 2.22 (Diagonal Coding Antichain, [2]).

Lemma 2.23 ([2]).

Theorem 2.24 (Coulson, Dobrinen, Patel, [3]).

3. Baire spaces of diagonal coding antichains

Definition 3.1 (Spaces of Diagonal Coding Antichains).

4. Forcing the Extended Pigeonhole Principle

Definition 4.1 (Good Diagonal Coding Antichains).

Definition 4.2.

Assumption 4.3.

Theorem 4.4 (Erdős-Rado).

Theorem 4.5 (Extended Pigeonhole Principle).

Proof.

Lemma 4.6.

Proof.

Lemma 4.7.

Proof.

Lemma 4.8 (Homogeneity of {pα→:α→∈K→}\{p_{\vec{\alpha}}:\vec{\alpha}\in\vec{K}\,\}).

Proof.

Remark 4.9.

5. Borel sets of 𝒟​(𝔻)\mathcal{D}(\mathbb{D}) are completely Ramsey

Convention 5.1.

Definition 5.2.

Definition 5.3.

Assumption 5.4.

Theorem 5.5.

Proof.

Fact 5.6.

Proof.

Lemma 5.7.

Proof.

Fact 5.8.

Proof.

Fact 5.9.

Proof.

Lemma 5.10.

Proof.

Definition 5.11.

Remark 5.12.

Lemma 5.13.

Proof.

Lemma 5.14.

Proof.

Lemma 5.15.

Proof.

Lemma 5.16.

Proof.

Theorem 5.17.

Infinite-dimensional Ramsey theory for homogeneous structures with SDAP⁺

2.2. Coding trees of $1$ -types

Definition 2.3 (The Coding Tree of $1$ -Types, [2]).

Definition 2.4 (The Unary-Colored Coding Tree of $1$ -Types, [2]).

2.4. The properties SDAP⁺ and LSDAP⁺

Definition 2.16 ( $+$ -Similarity, [2]).

Definition 2.18 (SDAP⁺, [2]).

Lemma 4.8 (Homogeneity of $\{p_{\vec{\alpha}}:\vec{\alpha}\in\vec{K}\,\}$ ).

5. Borel sets of $\mathcal{D}(\mathbb{D})$ are completely Ramsey