The Polarised Partition Relation for Order Types

Lukas Daniel Klausner and Thilo Weinert

Abstract. We analyse partitions of products with two ordered factors in two classes where both factors are countable or well-ordered and at least one of them is countable. This relates the partition properties of these products to cardinal characteristics of the continuum. We build on work by Erdős, Garti, Jones, Orr, Rado, Shelah and Szemerédi. In particular, we show that a theorem of Jones extends from the natural numbers to the rational ones but consistently extends only to three further equimorphism classes of countable orderings. This is made possible by applying a thirteenyear old theorem of Orr about embedding a given order into a sum of finite orders indexed over the given order.

1. Introduction

The partition calculus was introduced over six decades ago by Erdős and Rado in their seminal paper [ER56]. They introduced the ordinary partition relation which concern partitions of finite subsets of a set of a given size and the polarised partition relation which concerns partitions of finite subsets of products of sets of a given size. The notion of “size” here was mostly taken to refer to the cardinality of a set, but can easily be interpreted to refer to other notions of size, for example the order type of an ordered set. Assuming the axiom of choice, every set can be wellordered and there naturally is the smallest ordinal which can be the order type of such a well-order. In this context, it is convenient to refer to this ordinal as the cardinality of the set in question and the analysis of partition relations for order types thereby naturally includes the one of partition relations for cardinality. Partition relations for order types have been investigated in many papers. Chapter 7 of the book [Wil77] was devoted to them, and recently there has been renewed interest, cf. [Sch10, Sch12, Wei14, Hil16, CH17, Mer, LHW, IRW]. In these papers, however, the focus has been on the ordinary partition relation. To the authors’ knowledge, relations for partitions of products of order types other than initial ordinals have only been studied in [EHM70, EHM71]. In this paper we aim to study polarised partition relations for order types. We limit the study to partitions of products with two factors such that both are countable or well-ordered and at least one of them is countable. We prove a partition relation in the case where both factors are indecomposable ordinals smaller than ω^{ω}, and we show that analogues of a theorem of Jones hold

2010 Mathematics Subject Classification. Primary 03E02; Secondary 03E17, 05D10, 06A05.

Key words and phrases. partition relations, polarised partitions, total order, Ramsey theory.

The first author was supported by the Austrian Science Fund (FWF) project P29575 “Forcing Methods: Creatures, Products and Iterations”.

The second author was supported by the Austrian Science Fund (FWF) projects I3081 “Filters, Ultrafilters and Connections with Forcing” and Y1012 “Infinitary Combinatorics and Definability”.

We are grateful to Raphaël Carroy and Martin Goldstern for inspiring discussions.

2 LUKAS DANIEL KLAUSNER AND THILO WEINERT

when the order type of the natural numbers is replaced by its reverse or the order type of the rational numbers, but consistently fails for all other countable order types. We achieve this by proving partition relations involving cardinal characteristics of the continuum. These characteristics have been extensively studied over the past decades and many independence results regarding them have been attained. Via our results, some of these independence results directly lead to the independence of certain partition relations over zfc. Connections between cardinal characteristics and partition relations have been explored before in [GS12, GS14, RT18, LHW, CGW]. It is worth noting that one of the difficulties of working with non-well-ordered types was resolved quite elegantly by employing a theorem of Orr. We conclude the paper by asking a few questions, some of which we expect to be decided within the framework of zfc.

2. Cardinal Characteristics

We briefly recall the definitions of some cardinal characteristics relevant to our discussion. For further background, cf. [vD84, BJ95, Bla10, Hal17]. For functions g, h: ω ⟶ ω, we say that g eventually dominates h if the set of all natural numbers n such that g(n) ⩽ h(n) is finite. For sets x and y of natural numbers we say that x splits y if both y ∩ x and y \ x are infinite. We say that x almost contains y if y \ x is finite.

Definition 2.1 ([vD84]). An unbounded family is a family F of functions g: ω ⟶ ω such that no single function h: ω ⟶ ω eventually dominates all members of F. The unbounding number (sometimes called the bounding number) 𝔟 is the smallest cardinality of an unbounded family.

Definition 2.2 ([vD84]). A splitting family is a family F of sets of natural numbers such that for every infinite set x of natural numbers, there is a member of F splitting x. The splitting number 𝔰 is the smallest cardinality of a splitting family.

Definition 2.3. A countably splitting family is a family F of sets of natural numbers such that for every countable collection X of infinite sets of natural numbers, there is a member of F splitting every element of X. The countably splitting number 𝔰_{ℵ0} is the smallest cardinality of a countably splitting family.

Definition 2.4 ([vD84]). A tower is a sequence ⟨x_{ξ} | ξ < α⟩ of infinite sets of natural numbers such that for γ < β, the set x_{γ} almost contains x_{β}. A tower is extendible if there is an infinite set almost contained in every member of it. The tower number 𝔱 is the smallest ordinal α such that not all towers of length α are extendible.

Also recall that cov(M) denotes the minimal number of meagre sets of reals necessary to cover the reals.

Observation 2.5. 𝔰 ⩽ 𝔰_{ℵ0}.

Theorem 2.6. 𝔰_{ℵ0} ⩽ max(𝔟, 𝔰).

Theorem 2.7. min(cov(M), 𝔰_{ℵ0}) ⩽ 𝔰.

Theorem 2.6 is due to Kamburelis and Węglorz, cf. [KW96, Proposition 2.1]. Theorem 2.7 is due to Kamburelis, cf. [KW96, Proposition 2.3]. It is still an unanswered question whether 𝔰 < 𝔰_{ℵ0} is consistent. The notion of a countably splitting family was introduced by Malyhin in [Mal89];

THE POLARISED PARTITION RELATION FOR ORDER TYPES 3

also cf. [Ste93, Question 5.3]. We also note that the theorems we quote which mention the tower number were originally proved for the pseudointersection number 𝔭. By the recent seminal result by Malliaris and Shelah that 𝔭 = 𝔱, the theorems follow in the form stated here. For the proof that the pseudointersection number equals the tower number, cf. [MS13]. As the unbounding number and the splitting number seem most relevant to the results in this paper, we would like to point out that their behaviour on regular cardinals was shown to be uncorrelated by Fischer et al., cf. [FS08, BF11, FM17].

𝔠

max(𝔟, 𝔰)

𝔰_{ℵ0}

𝔟

𝔰

cov(M)

min(cov(M), 𝔰_{ℵ0})

𝔱

ℵ_{1}

Figure 1. The inequalities between the aforementioned cardinal characteristics known to be zfc-provable.

3. Order Types

By an order type we understand an equivalence class of ordered sets equivalent under orderpreserving bijections. For an order type φ, we denote its reverse by φ^{∗}. We denote the order type of the natural numbers by ω and the order type of the rational numbers by η. If φ and ψ are order types, φ + ψ denotes the order type of the set F ∪ P under the ordering given by (x ∈ F ∧ y ∈ P) or (x <_{F} y) or (x <_{P} y), where F and P are disjoint sets of order types φ and ψ, respectively. Furthermore, φψ denotes the order type of P × F under the (lexicographic) ordering ⟨p_{0}, f_{0}⟩ < ⟨p_{1}, f_{1}⟩ given by p_{0} <_{P} p_{1} or (p_{0} = p_{1} ∧ f_{0} <_{F} f_{1}). If φ and ψ are order types, we write φ ⩽ ψ to indicate that an ordered set of type φ may be embedded order-preservingly into an ordered set of type ψ. Contrary to the class of ordinals, which is well-ordered under embeddability, even the class of linear orders is only quasi-ordered by the embeddability relation. Embeddability is not a linear order between the linear orders, as shown by ω and ω^{∗}. It also fails to be antisymmetric, as witnessed by η and η + 1. An ordering which fails to embed η is called scattered. Orderings which are presentable as countable unions of

4 LUKAS DANIEL KLAUSNER AND THILO WEINERT

scattered orderings are called σ-scattered. By a seminal result of Laver, cf. [Lav71], the class of σscattered orderings is well-quasi-ordered by the embeddability relation. Recall that an ordering is a well-quasi-ordering if both every strictly descending sequence and every set of pairwise incomparable elements is finite, cf. [Ros82, chapter 10] or [Fra00, chapter 4]. We say that two orders are equimorphic (sometimes also called biembeddable) if they may be embedded order-preservingly into each other. While equimorphic ordinals are identical, there are pairs of non-isomorphic yet equimorphic order types. We call an order type φ additively decomposable if there are types ψ and τ such that φ = ψ + τ but neither φ ⩽ ψ nor φ ⩽ τ. We call it unionwise decomposable if there is an ordered set ⟨X, <⟩ of type φ and a Y ⊆ X such that neither φ ⩽ otp(⟨Y, <⟩) nor φ ⩽ otp(⟨X \ Y, <⟩). We call it multiplicatively decomposable if there are types ψ and τ such that φ = ψτ but neither φ ⩽ ψ nor φ ⩽ τ. We call it typewise decomposable if there is an ordered set ⟨X, <_{X}⟩ and for every x ∈ X disjoint ordered sets ⟨Y_{x}, <_{x}⟩ such that the set ⟨ ⋃_{x∈X} Y_{x}, <⟩ has type φ if a < b is given by ∃ x (∃ y: a ∈ x ∧ b ∈ y ∧ x <_{X} y) ∨ (a ∈ x ∧ b ∈ x ∧ a <_{x} b) and furthermore neither φ ⩽ otp(⟨X, <_{X}⟩) nor φ ⩽ otp(⟨Y_{x}, <_{x}⟩) for any x ∈ X. An order type is called (additively, unionwise, multiplicatively, typewise) indecomposable if it fails to be (additively, unionwise, multiplicatively, typewise) decomposable. (Unionwise indecomposability is called strong indecomposability in [EM72].) For ordinals, additive decomposability is equivalent to unionwise decomposability. An ordinal α is additively indecomposable if and only if there is an ordinal β such that α = ω^{β}. We call it multiplicatively surpassable if there are types ψ and τ such that φ ⩽ ψτ but neither φ ⩽ ψ nor φ ⩽ τ. It is called multiplicatively unsurpassable if it fails to be multiplicatively surpassable. We call it multiplicatively transcendable if there are types ψ and τ such that φ ⩽ ψτ and ψ ⩽ φ and τ ⩽ φ but neither φ ⩽ ψ nor φ ⩽ τ. It is called multiplicatively untranscendable if it fails to be multiplicatively transcendable. Clearly, additive decomposability implies unionwise decomposability and multiplicative decomposability implies typewise decomposability. Let us recall a famous Theorem of Hausdorff, cf. [Hau08, Satz XII].

Theorem 3.1. The class of scattered order types is the smallest non-empty class containing all reversals and well-ordered sums.

Corollary 3.2. Up to equimorphism, the only countable typewise indecomposable order types are 0, 1, 2, ω, ω^{∗}, and η.

Observation 3.3.

• Unionwise decomposability fails to imply additive decomposability as shown by the order type ω (ω^{∗} + ω).

• Typewise decomposability fails to imply multiplicative decomposability as shown by the order type ω^{ω}.

• Multiplicative transcendability fails to imply multiplicative decomposability as shown by the order type ω + ω^{∗}.

4. Polarised Partition Relations

We will analyse the polarised partition relation for order types:

\binom{α}{β} ⟶ (\begin{matrix}γ & ε \\ δ & ζ \end{matrix}).

This relation states that for every colouring c: A × B ⟶ 2 of the product of a set A of size α and a set B of size β, either there is a C ⊆ A of size γ and a D ⊆ B of size δ such that c[C ×D] ⊆ {0} or there is an E ⊆ A of size ε and a Z ⊆ D of size ζ such that c[E × Z] = {1}. The following relation states that for every ordinal κ and every colouring c: A × B ⟶ κ of a set A of size α and a set B of size β, there is a ϑ < κ, a C ⊆ A of size γ and a D ⊆ B of size δ such that c[C × D] = {ϑ}:

\binom{α}{β} ⟶ \binom{γ}{δ}_{κ}.

The term “size” is intentionally vague in these statements and will be taken to mean cardinality or order type depending on the context. Note that

\binom{α}{β} ⟶ (\begin{matrix}γ & γ \\ δ & δ \end{matrix})

is equivalent to

\binom{α}{β} ⟶ \binom{γ}{δ}_{2}.

It is common to call the parameters to the left of the arrow sources and the ones to the right of the arrow targets of the relation. The failure of the relations above is expressed by crossed arrows, i. e.

\binom{α}{β} −̸→ (\begin{matrix}γ & ε \\ δ & ζ \end{matrix})

and

\binom{α}{β} −̸→ \binom{γ}{δ}_{ε},

respectively. We will also use the ordinary partition relation: α ⟶ (β_{0}, …, β_{k})^{n} states that for every colouring c: [A]^{n} ⟶ n + 1 of the unordered n-tuples with n + 1 colours, there is an i ⩽ n and a C ⊆ A of size β_{i} such that c[[C]^{n}] ⊆ \{i\}. Moreover, α ⟶ (β)_{m}^{n} stands for α ⟶ (\underbrace{β, …, β}_{m times})^{n}.

5. Both Sources Countable

The following fact limits the realm of relations holding for countable sources; it is easily verified by enumerating both sources in order type ω and colouring a pair of one element each of both sources by comparing their respective indices in these enumerations.

Fact 5.1.

\binom{η}{η} −̸→ (\begin{matrix}1 & ℵ_{0} \\ ℵ_{0} & 1 \end{matrix}).

The following fact can be verified by use of the pigeonhole principle and the notion of unionwise indecomposablity.

Fact 5.2. For all natural numbers m, n and all unionwise indecomposable types φ,

\binom{φ}{mn + 1} ⟶ \binom{φ}{n + 1}_{m}.

Considering these facts, it is natural to ask for which countable linear order types φ, ψ and natural numbers n the relation

\binom{φ}{ψ} ⟶ (\begin{matrix}φ & n \\ ψ & n \end{matrix})

holds. We can partially answer this using Ramsey’s theorem, a technique which was used in [HS69] to analyse ordinary partition relations involving finite powers of ω.

Lemma 5.3. If k, m and n are natural numbers, then

\binom{ω^{k}}{ω^{m}} ⟶ (\begin{matrix}ω^{k} & n \\ ω^{m} & n \end{matrix}).

Proof. Let k, m and n be natural numbers and E ⊆ ω^{k} × ω^{m}. Let

⟨⟨n_{i,j} | j < k⟩ | i < \binom{k + m}{k}⟩

be an enumeration of all descending enumerations of [k + m]^{k}, and for all i < \binom{k+m}{k}, let ⟨n_{i,j} | j ∈ k+m\k⟩ be the descending enumeration of k+m\{n_{i,j} | j < k}. Now let c: ω^{k}×ω^{m} ⟶ 2. We may define a colouring c′: [ω]^{k+m} ⟶ 2^{\binom{k+m}{k}} by

\begin{matrix}\{ℓ_{i} | i < k + m\}_{<} ⟼ ∑_{i<\binom{k+m}{k}} 2^{i} c( & ω^{k−1}ℓ_{ni,k−1} + ⋯ + ℓ_{ni,0}, \\ ω^{m−1}ℓ_{ni,k+m−1} + ⋯ + ℓ_{ni,k+m}). \end{matrix} (∗_{1})

Now by Ramsey’s theorem, there is an infinite set H of natural numbers homogeneous for c′. We distinguish two cases. First, assume that H is homogeneous for c′ in colour 0. Consider a partition {H_{0}, H_{1}} of H into two infinite sets. Furthermore consider the sets

X := {ω^{k−1}n′_{k−1} + ⋯ + n′_{0} | ⟨n′_{i} | i < k⟩ is descending and {n′_{i} | i < k} ⊆ H_{0}}

and

Y := {ω^{m−1}ñ_{m−1} + ⋯ + ñ_{0} | ⟨ñ_{i} | i < m⟩ is descending and {ñ_{i} | i < m} ⊆ H_{1}}.

Note that X has order type ω^{k} while Y has order type ω^{m}. We will prove that X × Y is homogeneous for c in colour 0. To this end, let ω^{k−1}n′_{k−1}+⋯+n′_{0} = x ∈ X and ω^{m−1}ñ_{m−1}+⋯+ñ_{0} = y ∈ Y. Consider the ascending enumeration ⟨ℓ_{i} | i < k + m⟩ of x ∪ y. There is an i < k + m such

THE POLARISED PARTITION RELATION FOR ORDER TYPES 7

that n′_{j} = ℓ_{ni,j} for j < k and ñ_{j} = ℓ_{ni,k+j} for j < m. As H is homogeneous for c in colour 0, we have c′(x ∪ y) = 0 and as c′ assigns a set the value 0 if and only if all summands in Eq. (∗_{1}) have value 0, we also have c(x, y) = 0. This concludes the argument for X × Y being homogeneous for c in colour 0. Now assume that H is homogeneous for c′ in a positive colour. This means that there is an i < \binom{k+m}{k} such that c(ω^{k−1}ℓ_{ni,k−1} + ⋯ + ℓ_{ni,0}, ω^{m−1}ℓ_{ni,k+m−1} + ⋯ + ℓ_{ni,k+m}) = 1 for all \{ℓ_{j} | j < k + m}_{<} ∈ [ω]^{k+m}. Now we are going to inductively construct two disjoint sets X, Y ⊆ H of cardinality n such that c(x, y) = 1 for all x ∈ X and y ∈ Y. Let ⟨h_{j} | j < (k + m) · n⟩ be an ascending enumeration of elements of H. We define x_{j} := ω^{k−1}h_{ni,k−1·n+j} +⋯+h_{ni,0·n+j} and y_{j} := ω^{m−1}h_{ni,k+m·n+j} + ⋯ + h_{ni,k·n+j} for j < n. We furthermore define X := {x_{j} | j < n} and Y := {y_{j} | j < n}. It is easy to see that c(x, y) = 1 for all x ∈ X and y ∈ Y. □

Lemma 5.4. For all order types ρ, τ, φ and ψ, ρ ⟶ (2τ, φ + ψ, ψ + φ)^{2} implies

\binom{ρ}{ρ} ⟶ (\begin{matrix}τ & φ \\ τ & ψ \end{matrix}).

Proof. Let ρ, τ, φ and ψ be order types as above and assume that ρ ⟶ (2τ, φ + ψ, ψ + φ)^{2}. Furthermore, let E ⊆ ρ × ρ. We define a colouring

c: [ρ]^{2} ⟶ 3: {ν, ξ}_{<} ⟼ [⟨ν, ξ⟩ ∈ E] + 2[⟨ν, ξ⟩ ∉ E ∋ ⟨ξ, ν⟩]

As ρ ⟶ (2τ, φ + ψ, ψ + φ)^{2}, we have to distinguish three cases. For the first case, assume that there is an X ∈ [ρ]^{2τ} homogeneous for c in colour 0. Then there is A ∈ [X]^{τ} such that X \ A ∈ [X]^{τ} and clearly A × (X \ A) ⊆ ρ × ρ \ E. For the second case, assume that there is a Y ∈ [ρ]^{φ+ψ} homogeneous for c in colour 1. Let B ∈ [Y]^{φ} be such that B < Y \ B and Y \ B ∈ [Y]^{ψ}. Then B × (Y \ B) ⊆ E. For the final case, assume that there is a Z ∈ [ρ]^{ψ+φ} homogeneous for c in colour 2. Let C ∈ [Z]^{ψ} be such that C < Z \ C and Z \ C ∈ [Z]^{φ}. Then (Z \ C) × C ⊆ E. □

Theorem 5.5 ([ER56, Theorem 6]). η ⟶ (η, ℵ_{0})^{2}.

Theorem 5.6 ([Lar73]). For all natural numbers n, ω^{ω} ⟶ (ω^{ω}, n)^{2}.

Proposition 5.7. For all natural numbers k,

\binom{η}{η} ⟶ (\begin{matrix}η & k \\ η & k \end{matrix}).

Proof. Let k be any natural number. By Theorem 5.5, we have that η ⟶ (η, ℵ_{0})^{2}, so in particular we have η ⟶ (η, \binom{4k−2}{2k−1})^{2}. As \binom{4k−2}{2k−1} ⟶ (2k)_{2}^{2}, cf. [ES35], this implies η ⟶ (η, 2k, 2k)^{2} and (as 2η may be embedded into η) also η ⟶ (2η, 2k, 2k)^{2}. Then by Lemma 5.4, the statement of the proposition follows. □

Proposition 5.8. For all natural numbers k,

\binom{ω^{ω}}{ω^{ω}} ⟶ (\begin{matrix}ω^{ω} & k \\ ω^{ω} & k \end{matrix}).

Proof. Let k be any natural number. By Theorem 5.6, we have that ω^{ω} ⟶ (ω^{ω}, \binom{4k−2}{2k−1})^{2}. Via \binom{4k−2}{2k−1} ⟶ (2k)_{2}^{2}, cf. [ES35], this implies ω^{ω} ⟶ (ω^{ω}, 2k, 2k)^{2}. Note that 2ω^{ω} = ω^{ω}, so Lemma 5.4 implies the statement of the proposition. □

At this point we would like to recall the notion of pinning, cf. [GL75].

Definition 5.9. An order type φ can be pinned to an order type ψ (written as φ → ψ) if for every ordered set F of type φ and P of type ψ there is a function (a so-called pinning map) f: F ⟶ P such that every f[X] ∈ [P]^{ψ} for every X ∈ [F]^{φ}.

Clearly, every order type can be pinned to the initial ordinal of its cardinality. If ξ → ρ, then replacing all occurences of ξ by ρ in a valid partition relation yields a partition relation which itself again is valid. In particular:

\binom{σ}{ξ} ⟶ (\begin{matrix}τ & φ \\ ξ & ψ \end{matrix}) implies \binom{σ}{ρ} ⟶ (\begin{matrix}τ & φ \\ ρ & ψ \end{matrix}) (∗_{2})

and

\binom{σ}{ξ} ⟶ (\begin{matrix}τ & φ \\ ξ & ξ \end{matrix}) implies \binom{σ}{ρ} ⟶ (\begin{matrix}τ & φ \\ ρ & ρ \end{matrix}) (∗_{3})

for all order types ξ, ρ, σ, τ, φ, ψ. Therefore, Eq. (∗_{2})implies that Proposition 5.7and Proposition 5.8 have the following corollary.

Corollary 5.10. For all natural numbers k,

\binom{η}{ω} ⟶ (\begin{matrix}η & k \\ ω & k \end{matrix}) and \binom{ω^{ω}}{ω} ⟶ (\begin{matrix}ω^{ω} & k \\ ω & k \end{matrix}).

Lemma 5.11. For all natural numbers k and m and all order types φ and ψ and collections of order types ⟨σ_{i} | i < k⟩ and ⟨τ_{j} | j < m⟩, if

\binom{σ_{i}}{τ_{j}} ⟶ (\begin{matrix}σ_{i} & φ \\ τ_{j} & ψ \end{matrix})

for all i < k and all j < m, then

(\begin{matrix}∑_{i<k} σ_{i} \\ ∑_{j<m} τ_{j} \end{matrix}) ⟶ (\begin{matrix}∑_{i<k} σ_{i} & φ \\ ∑_{j<m} τ_{j} & ψ \end{matrix}).

Proof. Assume towards a contradiction that

\binom{σ_{i}}{τ_{j}} ⟶ (\begin{matrix}σ_{i} & φ \\ τ_{j} & ψ \end{matrix})

for all i < k and all j < m, but

(\begin{matrix}∑_{i<k} σ_{i} \\ ∑_{j<m} τ_{j} \end{matrix}) −̸→ (\begin{matrix}∑_{i<k} σ_{i} & φ \\ ∑_{j<m} τ_{j} & ψ \end{matrix}) .

Let ⟨⟨i_{ℓ}, j_{ℓ}⟩ | ℓ < km⟩ be an enumeration of k × m. Moreover, for i < k, let X_{i}^{(0)} be a set ordered by <_{i} of type σ_{i} and for j < m, let Y_{j}^{(0)} be a set ordered by <_{k+j} of type ψ_{j}. Then X := ⋃_{i<k} X_{i}^{(0)} ordered by

⋃_{i<k}(<_{i} ∪ ⋃_{j<i}(X_{j}^{(0)} × X_{i}^{(0)}))

has type ∑_{i<k} σ_{i} and Y := ⋃_{i<m} Y_{i}^{(0)} ordered by

⋃_{i<m}(<_{k+i} ∪ ⋃_{j<i}(Y_{j}^{(0)} × Y_{i}^{(0)}))

has type ∑_{j<m} τ_{j}. As

(\begin{matrix}∑_{i<k} σ_{i} \\ ∑_{j<m} τ_{j} \end{matrix}) −̸→ (\begin{matrix}∑_{i<k} σ_{i} & φ \\ ∑_{j<m} τ_{j} & ψ \end{matrix}), (∗_{4})

we know that there is an E ⊆ X × Y witnessing this; in particular this E is such that for no A ∈ [X]^{φ} there is a B ∈ [Y]^{ψ} such that A × B ⊆ E. As

\binom{σ_{i}}{τ_{j}} ⟶ (\begin{matrix}σ_{i} & φ \\ τ_{j} & ψ \end{matrix})

for all i < k and all j < m, we know that for all i < k, all j < m, all A ∈ [X]^{σi} and all B ∈ [Y]^{τj}, there are C ∈ [A]^{σi} and D ∈ [B]^{τj} such that

C × D ⊆ X × Y \ E. (∗_{5})

Now suppose that we are in step ℓ of the induction and have by now defined X_{i}^{(ℓ)} ∈ [X_{i}^{(0)}]^{σi} for i < k and Y_{j}^{(ℓ)} ∈ [Y_{j}^{(0)}]^{τj} for j < m. Now Eq. (∗_{5}) implies that there are X_{iℓ}^{(ℓ+1)} ∈ [X_{iℓ}^{(ℓ)}] and

Y_{jℓ}^{(ℓ+1)} ∈ [Y_{jℓ}^{(ℓ)}] such that X_{iℓ}^{(ℓ+1)} × Y_{jℓ}^{(ℓ+1)} ⊆ X × Y \ E. Let X_{i}^{(ℓ+1)} := X_{i}^{(ℓ)} for all i ∈ k \ {i_{ℓ}}

and Y_{j}^{(ℓ+1)} := Y_{j}^{(ℓ)} for all j ∈ m \ {j_{ℓ}}. After the induction, we have that ⋃_{i<k} X_{i}^{(km)} ⊆ X has order type ∑_{i<k} σ_{i} and ⋃_{j<m} Y_{j}^{(km)} has order type ∑_{j<m} τ_{j}. Moreover, (⋃_{i<k} X_{i}^{(km)} ⊆ X) × (⋃_{j<m} Y_{j}^{(km)}) ⊆ X × Y \ E. This contradicts E being a witness to Eq. (∗_{4}). □

Proposition 5.12. For all ordinals α, β < ω^{ω} and all natural numbers n,

\binom{ωα}{ωβ} ⟶ (\begin{matrix}ωα & n \\ ωβ & n \end{matrix}) .

Proof. Note that if ν < ω^{ω}, then ων is a finite sum of infinite indecomposable ordinals smaller than ω^{ω}. So as {α, β} ⊆ ω^{ω}, both ωα and ωβ are finite sums of infinite indecomposable ordinals smaller than ω^{ω}. Using Lemma 5.3 together with Lemma 5.11 proves the proposition. □

6. One Source Countable

Having gained some understanding of the case with two countable sources, we now consider the case of one countable and one well-ordered source. The guiding question is the following:

Question A. For which countable linear order types φ and which ordinals α, β do we have

\binom{ω_{1}}{φ} ⟶ (\begin{matrix}α & β \\ φ & φ \end{matrix})?

Let us note that we cannot hope for a relation in the case that φ is decomposable.

Observation 6.1. If φ is a unionwise decomposable order type and ψ is any order type, then

\binom{ψ}{φ} −̸→ (\begin{matrix}1 & 1 \\ φ & φ \end{matrix}).

The following is a corollary of a claim proved by Garti and Shelah in [GS14, Claim 1.2]:

Corollary 6.2. If κ < 𝔰 is an infinite cardinal, then

\binom{κ}{ω} ⟶ \binom{κ}{ω}_{2} if and only ifω < cf(κ).

We would like to point out an observation made by Brendle and Raghavan:

Definition 6.3 ([BR14, Definition 31]). Let κ be a regular cardinal, and let Ā = ⟨a_{α,n} | α < κ ∧ n < ω⟩. Ā is tail-splitting if for every b ∈ [ω]^{ω}, there is α < κ such that a_{β} splits b for all β ⩾ α. Ā is club-splitting if for every b ∈ [ω]^{ω}, C_{b} = {α < κ | a_{α} splits b} contains a club.

Observation 6.4 ([BR14, Observation 44]). The following are equivalent (for infinite ordinals λ):

• \binom{λ}{ω} ⟶ \binom{λ}{ω}_{2}

• cf(λ) ≠ ω and there does not exist a tail-splitting sequence of length λ.

As every tail-splitting sequence of a length with uncountable cofinality is club-splitting and every club-splitting sequence of a length with uncountable cofinality is countably splitting, we get the following corollary:

Corollary 6.5. If κ < 𝔰_{ℵ0} is an infinite cardinal of uncountable cofinality, then

\binom{κ}{ω} ⟶ \binom{κ}{ω}_{2}.

In [Jon08], Jones proved the following theorem, thus generalising an unpublished result of Szemerédi who proved it for the special case where κ = 𝔠, α is a cardinal and Martin’s Axiom holds. (Szemerédi’s result in turn generalised a result of Erdős and Rado from [ER56, penultimate page] who proved it for κ = ω_{1} and α = ω.)

Theorem 6.6. For any regular uncountable κ ⩽ 𝔠 and any ordinal α < min{𝔱, κ},

\binom{κ}{ω} ⟶ (\begin{matrix}κ & α \\ ω & ω \end{matrix}).

We can improve Jones’ theorem by weakening its hypothesis and replacing the order type of the natural numbers ω by the order type of the rational numbers η; using pinning, this can be viewed as a strengthening of Jones’ result.

Theorem 6.7. For all cardinals κ ⩽ 𝔠 of uncountable cofinality and any ordinal α < min{𝔱, cf(κ)},

\binom{κ}{η} ⟶ (\begin{matrix}κ & α \\ η & η \end{matrix}).

By pinning (cf. Definition 5.9), more precisely because of Eq. (∗_{3}), we can immediately attain the following corollary.

Corollary 6.8. For all cardinals κ ⩽ 𝔠 of uncountable cofinality, any ordinal α < min{𝔱, cf(κ)} and both φ ∈ {ω, ω^{∗}},

\binom{κ}{φ} ⟶ (\begin{matrix}κ & α \\ φ & φ \end{matrix}).

First, note that by work of Bell, cf. [Bel81], its generalisation to all uncountable cardinals below the continuum, cf. [Bla10], and the recent breakthrough of Malliaris and Shelah, cf. [MS13], we have the following theorem.

Theorem 6.9. For every cardinal κ, the following are equivalent:

• κ < 𝔱.

• Every family F of cardinality κ of infinite sets of natural numbers for which the intersection of finitely many members of F is always infinite has an infinite pseudointersection. (Equivalently, κ < 𝔭.)

• Martin’s Axiom holds for every family of cardinality κ of dense subsets of a σ-centred partially ordered set. (Equivalently: For every σ-centred partially ordered set P and every family C of cardinality κ of dense subsets of P, there is a filter on P meeting every member of C.)

Similar to Jones’ proof, we require two lemmata. First, however, we make the following definition.

Definition 6.10. A family {A_{ξ} | ξ ∈ X} ⊆ P(ℚ) is an ω-complete filter basis dense in ℚ (or ω-complete ℚ-basis for short) if for any x ∈ [X]^{<ω}, ⋂_{ξ∈x} A_{ξ} is dense in ℚ.

Lemma 6.11. Suppose κ is a cardinal of uncountable cofinality. For A ⊆ ℚ, let \overline{A} := ℚ\A. Then for any {A_{ξ} | ξ < κ} ⊆ P(ℚ) either

(a) there is X ∈ [κ]^{κ} such that {A_{ξ} | ξ ∈ X} is an ω-complete ℚ-basis, or

(b) there is Y ∈ [κ]^{κ} such that ⋂_{ξ∈Y} \overline{A_{ξ}} contains a copy of ℚ.

Proof. For x ∈ [κ]^{<ω}, let A(x) := ⋂_{ξ∈x} A_{ξ}. Suppose that (a) is false; we will show that (b) must hold. Fix X ⊆ κ maximal such that {A_{ξ} | ξ ∈ X} is an ω-complete ℚ-basis. Clearly, |X| < κ. For any δ ∉ X, there must be a set of witnesses x_{δ} ∈ [X]^{<ω} and r_{δ}, s_{δ} ∈ ℚ showing the maximality of X, i. e. witnessing that A_{δ} ∩ A(x_{δ}) avoids the interval (r_{δ}, s_{δ}) and hence is not dense in ℚ. Since cf(κ) > ℵ_{0} = |ℚ|, by applying the pigeonhole principle, we can find some Y of size κ and some x^{∗} ∈ [X]^{<ω} and r^{∗}, s^{∗} ∈ ℚ such that for any δ ∈ Y, we have x_{δ} = x^{∗} and (r_{δ}, s_{δ}) = (r^{∗}, s^{∗}). Hence ⋃_{δ∈Y} A_{δ} avoids A(x^{∗}) ∩ (r^{∗}, s^{∗}), which implies that ⋂_{δ∈Y} \overline{A_{δ}} contains A(x^{∗}) ∩ (r^{∗}, s^{∗}) – which, by the definition of X, contains a copy of ℚ. □

While the proof of the previous lemma is a significant simplification of Jones’ proof, the following lemma’s proof is more or less the same as Jones’.

12 LUKAS DANIEL KLAUSNER AND THILO WEINERT

Lemma 6.12. Suppose κ is a cardinal of uncountable cofinality. Then for any ω-complete ℚ-basis {A_{ξ} | ξ < κ} ⊆ P(ℚ) and any ordinal α < min{𝔱, cf(κ)}, there is an X ∈ [κ]^{α} such that ⋂_{ξ∈X} A_{ξ} contains a copy of ℚ.

Proof. Let μ := |ω + α|. Construct a sequence {M_{γ} | γ ⩽ α} of elementary submodels of W := H_{κ+} such that |M_{γ}| = μ, {A_{ξ} | ξ < κ} ∈ M_{γ}, μ ∪ {μ} ⊆ M_{γ}, and M_{β} ∈ M_{γ} whenever β < γ ⩽ α. Let ϑ := sup(κ ∩ M_{α}) and note that ϑ < κ because |M_{α}| = μ = |ω + α| < cf(κ). Choose δ ∈ κ \ ϑ arbitrarily. For x ∈ [κ]^{<ω}, let A(x) := ⋂_{ξ∈x} A_{ξ}. For a ∈ [ℚ]^{<ω}, let X(a) := {ξ < κ | a ⊆ A_{ξ}}. Let ℙ be the collection of all p := ⟨a_{p}, x_{p}⟩ with a_{p} ∈ [A_{δ}]^{<ω}, x_{p} ∈ [κ ∩ M_{α}]^{<ω} and x_{p} ⊆ X(a_{p}) (or equivalently, a_{p} ⊆ A(x_{p})). Write q ⩽ p (“q is stronger than p”) if a_{p} ⊆ a_{q} and x_{p} ⊆ x_{q} (i. e. stronger conditions consist of larger sets), and note that ℙ is σ-centred. For r, s ∈ ℚ, let D_{r,s} := {p ∈ ℙ | a_{p} ⊈ ℚ \ (r, s)}. Each such D_{r,s} is dense in ℙ, since given any p ∈ ℙ, A(x_{p}) is dense in ℚ, and hence we can pick some t ∈ A(x_{p}) ∩ (r, s) and define q := ⟨a_{p} ∪ {t}, x_{p}⟩, which is stronger than p and an element of D_{r,s}. For ξ < α, let E_{ξ} := {p ∈ ℙ | x_{p} ∩ M_{ξ+1} ⊈ M_{ξ}}. Each such E_{ξ} is dense in ℙ, since for any p = ⟨a_{p}, x_{p}⟩ ∈ ℙ, the following consideration holds: In W, the formula

∀ ν < κ^{W} = |{A_{ξ} | ξ < κ}| ∃γ > ν: a_{p} ⊆ A_{γ}

is true (namely, one can pick γ := δ); by elementarity, the formula must also hold in M_{ξ+1} for any ν < κ ∩ M_{ξ+1} – specifically for ν := κ ∩ M_{ξ}, and so we can find some γ > ν in M_{ξ+1} such that a_{p} ⊆ A_{γ}. Letting q := ⟨a_{p}, x_{p} ∪ {γ}⟩, we have found a condition q which is stronger than p and an element of E_{ξ}. Since |ω + α| < 𝔱, there is a ℙ-generic filter G meeting all D_{r,s} and E_{ξ} simultaneously. Letting A := ⋃_{p∈G} a_{p} and X := ⋃_{p∈G} x_{p}, A ⊆ ⋂_{ξ∈X} A_{ξ} is dense in ℚ (and hence ⋂_{ξ∈X} A_{ξ} contains a copy of ℚ) and otp(X) ⩾ α. □

Proof of Theorem 6.7. Let η × κ =: K_{0} ∪ K_{1}. For each ξ < κ and i ∈ {0, 1}, let K_{i}^{ξ} := {r ∈ ℚ | ⟨r, ξ⟩ ∈ K_{i}}. By Lemma 6.11, there is either (a) an X ∈ [κ]^{κ} such that {K_{1}^{ξ} | ξ ∈ X} is an ω-complete ℚ-basis or (b) a Y ∈ [κ]^{κ} such that ⋂_{ξ∈Y} K_{0}^{ξ} contains a copy Q_{0} of ℚ. In case (b), simply let A_{0} := Y ∈ [κ]^{κ} and B_{0} := Q_{0} ∈ [ℚ]^{η}; then B_{0}×A_{0} ⊆ K_{0}. In case (a), by Lemma 6.12 there is an X′ ∈ [X]^{α} such that ⋂_{ξ∈A1} K_{1}^{ξ} contains a copy Q_{1} of ℚ. Let A_{1} := X′ ∈ [κ]^{α} and B_{1} := Q_{1} ∈ [ℚ]^{η}; then B_{1} × A_{1} ⊆ K_{1}. □

Now we are going to show that consistently, other order types can take the place of ω and η in the preceding results.

Proposition 6.13. If κ < 𝔟 is a cardinal of uncountable cofinality while n is a natural number and α ⩽ κ, then

\binom{κ}{ω^{n}} ⟶ (\begin{matrix}κ & α \\ ω^{n} & ω^{n} \end{matrix}) if and only if \binom{κ}{ω} ⟶ (\begin{matrix}κ & α \\ ω & ω \end{matrix}).

Proof. We will prove the theorem by induction. It obviously holds in case n < 2. So assume that κ < 𝔟 is a cardinal of uncountable cofinality, that n is a natural number, that α ⩽ κ and that the equivalence has been proved up to n. As for any positive ordinal n, the ordinal ω^{n} may be pinned

THE POLARISED PARTITION RELATION FOR ORDER TYPES 13

(cf. Definition 5.9) to ω, the first statement implies the second. In order to show the converse, assume that the second statement holds. Towards a contradiction, let c: κ × ω^{n+1} ⟶ 2 be such that 1 ∈ c[A × B] for every A ∈ [κ]^{κ} and B ∈ [ω^{n+1}]^{ωn+1} while 0 ∈ c[A × B] for every A ∈ [κ]^{α} and B ∈ [ω^{n+1}]^{ωn+1}. Let b: ω ⟶ ω^{n} be a bijection. For every countable ordinal ξ, we are going to define an infinite set X_{ξ} of natural numbers and a sequence ⟨i_{ξ,ν} | ν < ω^{n}⟩ such that for all ordinals ν < ω^{n}, the set {n ∈ X_{ξ} | c(ξ, ων + n) ≠ i_{ξ,ν}} is finite. Let X′_{ξ,0} ∈ [ω]^{ω} and i_{ξ,b(0)} be such that c(ξ, ωb(0) + ℓ) = i_{ξ,b(0)} for all ξ < κ and all ℓ ∈ X′_{ξ,0}. Suppose that there is a natural number k such that we have defined X′_{ξ,ν} and i_{ξ,ν} for all ν < ω^{n} such that b^{−1}(ν) ⩽ k. We may choose X′_{ξ,b(k+1)} ∈ [X′_{ξ,b(k)}]^{ω} and i_{ξ,b(k+1)} such that c(ξ, ωb(k + 1) + ℓ) = i_{ξ,b(k+1)} for all ξ < κ and all ℓ ∈ X′_{ξ,0}. For every ξ < κ, let X_{ξ} be a pseudointersection of the X′_{ξ,ν} for ν < ω^{n}. Now we define a family {f_{ξ} | ξ < κ} of functions

f_{ξ}: ω ⟶ ω: k ⟼ max {n ∈ X_{ξ} | c(ξ, ωb(k) + n) ≠ i_{ξ,k}}.

Now, as 𝔟 > κ, there is a g: ω ⟶ ω which eventually properly dominates every member of {f_{ξ} | ξ < κ}. For ξ < κ, let n_{ξ} be a natural number such that g dominates f_{ξ} from n_{ξ} on. As κ has uncountable cofinality, there is a natural number n and an A ∈ [κ]^{κ} such that n_{ξ} = n for all ξ ∈ A. We define a colouring

ψ: κ × ω ⟶ 2: ⟨ξ, k⟩ ⟼ i_{ξ,k},

and as we assumed

\binom{κ}{ω} ⟶ (\begin{matrix}κ & α \\ ω & ω \end{matrix}),

we may consider two cases. First, assume that there is A′ ∈ [A]^{κ} and Z ∈ [ω]^{ω} such that ψ[A′ × Z] = {0}. We consider the set B := {ωb(k) + m | k ∈ Z \ n ∧ m ∈ ω \ g(k)}. Clearly, B has order type ω^{n+1}. There has to be a ξ ∈ A′ and an ν ∈ B such that c(ξ, ν) = 1. There is a k ∈ Z \ n and an m ∈ ω \ g(k) such that ν = ωb(k) + m. As c(ξ, ωb(k) + m) = 1 ≠ 0 = i_{ξ,k} = ψ(ξ, k), we have m ⩽ f_{ξ}(k). But g properly dominates f_{ξ} from n on, so m ⩽ f_{ξ}(k) < g(k) ⩽ m, a contradiction. The second case works completely analogously. We assume that there is an A′ ∈ [A]^{α} and a Z ∈ [ω]^{ω} such that ψ[A′ × Z] = {1}. We consider the set B := {ωb(k) + m | k ∈ Z \ n ∧ m ∈ ω \ g(k)}. Clearly, B has order type ω^{n+1}. There has to be a ξ ∈ A′ and a ν ∈ B such that c(ξ, ν) = 0. There is a k ∈ Z \ n and an m ∈ ω \ g(k) such that ν = ωb(k) + m. As c(ξ, ωb(k) + m) = 0 ≠ 1 = i_{ξ,k} = ψ(ξ, k), we have m ⩽ f_{ξ}(k). But g properly dominates f_{ξ} from n on, so m ⩽ f_{ξ}(k) < g(k) ⩽ m, a contradiction. □

By Theorem 6.6 we get the following.

Corollary 6.14. If κ is a regular uncountable cardinal smaller than 𝔟 while β ∈ ω^{ω}\ω is additively indecomposable and α < min(𝔱, κ), then

\binom{κ}{β} ⟶ (\begin{matrix}κ & α \\ β & β \end{matrix}).

Corollary 6.5 immediately yields another corollary:

Corollary 6.15. If κ < min(𝔟, 𝔰_{ℵ0}) is an infinite cardinal and β ∈ ω^{ω} \ ω is additively indecomposable, then

\binom{κ}{β} ⟶ \binom{κ}{β}_{2} if and only ifω < cf(κ).

In order to prove the last theorem we reference a result of Orr.

Proposition 6.16 ([Orr95, Proposition 2]). Let A be a countable linearly ordered set and for every a ∈ A let L_{a} be a finite linearly ordered set. Then there is an increasing map

σ: A ⟶ L = ∑_{a∈A} L_{a}

which maps onto all but finitely many points of L, and, in any event, onto at least one point in every L_{a}.

Our final theorem shows that the assumption of κ < 𝔟 in Proposition 6.13 was indeed necessary.

Theorem 6.17. If α is an ordinal of cofinality 𝔟 and φ is a countable typewise decomposable order type, then

\binom{α}{φ} −̸→ (\begin{matrix}α & 1 \\ φ & φ \end{matrix}).

Proof. Let α be an ordinal of cofinality 𝔟 and let this be witnessed by an ascending sequence ⟨μ_{ξ} | ξ < 𝔟⟩ of ordinals cofinal in α. Let ⟨f_{ξ} | ξ < 𝔟⟩ be an unbounded sequence of functions. We may assume without loss of generality that it is increasing modulo finite and every element of it is itself increasing. Let φ be a countable typewise decomposable order type. Considering Observation 6.1, we may assume without loss of generality that φ is unionwise indecomposable. As φ is typewise decomposable, we have 3 ⩽ φ, so as φ is unionwise indecomposable, we have that φ is infinite. Now for every ξ < α, let ν_{ξ} be the smallest ν < 𝔟 such that μ_{ν} ⩾ ξ. Furthermore let ⟨T, <_{T} ⟩ be an ordered set and for every t ∈ T let ⟨P_{t}, <_{t}⟩ be an ordered set such that ∑_{t∈T} P_{t} has order type φ and so witnesses the typewise decomposability of φ, i. e. neither φ ⩽ otp(T) nor φ ⩽ P_{t} for any t ∈ T. Moreover, let b: ω ⟶ T and, for every natural number n, let e_{n}: ω ⟶ P_{b(n)} be enumerations. We define

E := {⟨β, ⟨p, t⟩⟩ | β < α ∧ t ∈ T ∧ p ∈ P_{t} ∧ f_{νβ}(b^{−1}(t)) > e_{b−1(t)}^{−1}(p)}. (∗_{6})

For the first half of the proof, let X ∈ [α]^{α} and Y ∈ [∑_{t∈T} P_{t}]^{φ}. We assume towards a contradiction that X × Y ⊆ α × ∑_{t∈T} P_{t} \ E and define

a: ω ⟶ ω: n ⟼ min {k ∈ ω \ n | |Y ∩ P_{b(k)}| = ℵ_{0}}. (∗_{7})

We first have to make sure that a is well-defined.

Claim 1. Eq. (∗_{7}) defines a function.

Proof of Claim. Assume towards a contradiction that for all but finitely many t ∈ T the set Y ∩ P_{t} is finite. Let T′ := {t ∈ T | Y ∩ P_{t} is finite}. Then, by Proposition 6.16, there is a finite F ⊆ ∑_{t∈T ′}(Y ∩ P_{t}) such that there is an increasing surjection σ: T′ ⟶ ∑_{t∈T ′}(Y ∩ P_{t}) \ F. Using the Axiom of Choice, we may invert σ to find that ∑_{t∈T ′}(Y ∩P_{t})\F ⩽ T′. As φ ⩽̸ otp(T′), we have φ ⩽̸ ∑_{t∈T ′}(Y ∩ P_{t}) \ F. As φ is unionwise indecomposable and infinite and F is finite,

THE POLARISED PARTITION RELATION FOR ORDER TYPES 15

it follows that φ ⩽̸ ∑_{t∈T ′}(Y ∩ P_{t}). Again, as φ is unionwise indecomposable (and otp(Y) = φ), we have φ ⩽ ∑_{t∈T \T ′}(Y ∩ P_{t}). Let {t_{k} | k < n} be the ascending enumeration of T \ T′. Let m < n be minimal such that φ ⩽ ∑_{k⩽m}(Y ∩ P_{tk}). As φ ⩽̸ P_{tm}, we have φ ⩽̸ Y ∩ P_{tm}, and as φ is unionwise indecomposable, it follows that φ ⩽ ∑_{k<m} P_{tk}, contradicting the minimality of m and thus concluding the proof of the claim. □ We now define

g: ω ⟶ ω: n ⟼ min {k < ω | Y ∩ P_{b(n)} = ∅ ∨ e_{n}(k) ∈ Y)} and
h: ω ⟶ ω: n ⟼ max{a(n), g(a(n))}. (∗_{8})

As ⟨f_{ξ} | ξ < 𝔟⟩ is unbounded and increasing modulo finite and X has order type α, we can find a β ∈ X such that f_{νβ} is not eventually bounded by h. Let k be a natural number such that f_{νβ}(k) > h(k). By Eq. (∗_{7}), the set Y ∩ P_{a(k)} is infinite. By Eq. (∗_{8}), e_{a(k)}(g(a(k))) ∈ Y. By Eq. (∗_{6}) and since X × Y ⊆ α × ∑_{t∈T} P_{t} \ E, we have f_{νβ}(a(k)) ⩽ g(a(k)). Ultimately, we thus get

g(a(k)) ⩽ h(k) < f_{νβ}(k) ⩽ f_{νβ}(a(k)) ⩽ g(a(k)),

a contradiction. For the second half of the proof, let γ < α and Y ∈ [∑_{t∈T} P_{t}]^{φ} and assume towards a contradiction that {γ} × Y ⊆ E. We distinguish two cases. For the first case, we assume that there is a t ∈ T such that Q := {p ∈ P_{t} | ⟨t, p⟩ ∈ Y } is infinite. Let q ∈ Q be such that e_{b−1(t)}^{−1}(q) ∈ ω \ f_{γ}(b^{−1}(t)). Then by Eq. (∗_{6}) we have ⟨γ, ⟨t, p⟩⟩ ∉ E, a contradiction. For the second case, we assume that for all t ∈ T the set {p ∈ P_{t} | ⟨t, p⟩ ∈ Y } is finite. Then by Proposition 6.16 there is a finite F ⊆ Y and an increasing map σ: T ⟶ Y \ F which is onto. Using the Axiom of Choice we may invert σ to see that Y \F may be embedded order-preservingly into T. As φ ⩽̸ otp(T), we have φ ⩽̸ otp(Y \ F). As φ is unionwise indecomposable and infinite and F is finite, it follows that φ ⩽̸ otp(Y) = φ, a contradiction. □

The fact that 𝔟 has uncountable cofinality together with Corollary 3.2, Theorem 6.7and Corollary 6.8 yields the following corollary summarising the central results of this paper:

Corollary 6.18. Let φ be a countable order type. If φ is equimorphic to an order type in {0, 1, ω^{∗}, ω, η}, then

\binom{𝔟}{φ} ⟶ (\begin{matrix}𝔟 & α \\ φ & φ \end{matrix})

for all α < 𝔱; otherwise

\binom{𝔟}{φ} −̸→ (\begin{matrix}𝔟 & 1 \\ φ & φ \end{matrix}).

7. Questions

We are interested in relations which can be proved using only zfc. Therefore the following questions seem natural:

Question B. Does the relation

\binom{φ}{ψ} ⟶ (\begin{matrix}φ & n \\ ψ & n \end{matrix})

hold for all countable unionwise indecomposable order types φ and ψ and all natural numbers n? For example, what about φ = ω^{ω+1} while ψ = ω and n = 2?

Question C. Does the relation

\binom{ω_{1}}{φ} ⟶ (\begin{matrix}α & α \\ φ & φ \end{matrix})

necessarily hold for all countable ordinals α and all countable unionwise indecomposable order types φ?

In light of Proposition 6.13, the following question suggests itself:

Question D. Is it consistent that

\binom{ω_{1}}{φ} ⟶ (\begin{matrix}ω_{1} & α \\ φ & φ \end{matrix})

for all countable ordinals α and all countable unionwise indecomposable order types φ?

Furthermore, in light of Corollary 6.2 and Theorem 6.7, the following question arises:

Question E. Does the relation

\binom{κ}{ω} ⟶ (\begin{matrix}κ & α \\ ω & ω \end{matrix})

hold for all uncountable cardinals κ ⩽ 𝔠 and all α < min(𝔰_{ℵ0}, cf(κ))?

Finally, the following question seems deceptively simple:

Question F. Is 2 the only linear order type which is unionwise decomposable yet multiplicatively untranscendable?

References

[Bel81] Murray G. Bell, On the Combinatorial Principle P (𝔠), Fund. Math. 114 (1981), no. 2, 149–157, doi: 10.4064/FM-114-2-149-157, also available at https://eudml.org/doc/211293 .

[BF11] Jörg Brendle and Vera Fischer, Mad Families, Splitting Families and Large Continuum, J. Symb. Logic 76 (2011), no. 1, 198–208, doi: 10.2178/JSL/1294170995, also available at

http://www.logic.univie.ac.at/~vfischer/absplit.pdf  .

[BJ95] Tomek Bartoszyński and Haim Judah, Set Theory: On the Structure of the Real Line, A K Peters, Wellesley, MA, 1995, doi: 10.1112/S0024609396222374.

[Bla10] Andreas Blass, Combinatorial Cardinal Characteristics of the Continuum, Handbook of Set Theory (Matthew Foreman and Akihiro Kanamori, eds.), Springer, Dordrecht, 2010, pp. 395–489, doi: 10.1007/978-1-4020-5764-9_7.

[BR14] Jörg Brendle and Dilip Raghavan, Bounding, Splitting, and Almost Disjointness, Ann. Pure Appl. Logic 165 (2014), no. 2, 631–651, doi: 10.1016/J.APAL.2013.09.002, arXiv: 1211.5170 [math.LO].

[CGW] William Chen, Shimon Garti, and Thilo Volker Weinert, Cardinal Characteristics of the Continuum and Partitions, arXiv: 1801.00238 [math.LO].

[CH17] Andrés Eduardo Caicedo and Jacob Hilton, Topological Ramsey Numbers and Countable Ordinals, Foundations of Mathematics, Contemp. Math., vol. 690, Amer. Math. Soc., Providence, RI, 2017, pp. 87–120, doi: 10.1090/CONM/690/13864, arXiv: 1510.00078 [math.LO].

[EHM70] Paul Erdős, András Hajnal, and Eric Charles Milner, Set Mappings and Polarized Partition Relations, Combinatorial Theory and Its Applications, I (Proc. Colloq., Balatonfüred, 1969) (Paul Erdős, Alfréd Rényi, and Vera Turán Sós, eds.), North-Holland, Amsterdam, 1970, pp. 327–363, available at

https://pdfs.semanticscholar.org/62df/2699160f4cc06e5968e66339e14a6d3911fa.pdf  .

[EHM71] Paul Erdős, András Hajnal, and Eric Charles Milner, Polarized Partition Relations for Ordinal Numbers, Studies in Pure Mathematics (Leonid Mirsky, ed.), Academic Press, London, 1971, pp. 63–87, available at

https://users.renyi.hu/~p_erdos/1971-17.pdf  .

[EM72] Paul Erdős and Eric Charles Milner, A Theorem in the Partition Calculus, Canad. Math. Bull. 15 (1972),

no. 4, 501–505, available at http://www.renyi.hu/~p_erdos/1972-03.pdf  .

[ER56] Paul  Erdős  and  Richard  Rado,  A  Partition  Calculus  in  Set  The-
ory,  Bull.  Amer.  Math.  Soc.  62  (1956),  427–489,  available  at

http://www.ams.org/journals/bull/1956-62-05/S0002-9904-1956-10036-0/S0002-9904-1956-10036-0.pdf  .

[ES35] Paul Erdős and George Szekeres, A Combinatorial Problem in Geometry, Compos. Math. 2 (1935), 463–470,

available at http://www.numdam.org/item/CM_1935__2__463_0/  .

[FM17] Vera Fischer and Diego Alejandro Mejia, Splitting, Bounding, and Almost Disjointness Can Be Quite Different, Canad. J. Math. 69 (2017), no. 3, 502–531, doi: 10.4153/CJM-2016-021-8, arXiv: 1508.01068 [math.LO].

[Fra00] Roland Fraïssé, Theory of Relations, Studies in Logic and the Foundations of Mathematics, vol. 145, North-Holland, Amsterdam, 2000.

[FS08] Vera Fischer and Juris Steprāns, The Consistency of 𝔟 = κ and 𝔰 = κ^{+}, Fund. Math. 201 (2008), no. 3, 283–293, doi: 10.4064/FM201-3-5.

[GL75] Frederick William Galvin and Jean Ann Larson, Pinning Countable Ordinals, Fund. Math. 82 (1975), 357– 361, doi: 10.4064/FM-82-4-357-361.

[GS12] Shimon Garti and Saharon Shelah, Combinatorial Aspects of the Splitting Number, Ann. Comb. 16 (2012), no. 4, 709–717, doi: 10.1007/S00026-012-0154-5, arXiv: 1007.2266 [math.LO].

[GS14] , Partition Calculus and Cardinal Invariants, J. Math. Soc. Japan 66 (2014), no. 2, 425–434, doi: 10.2969/JMSJ/06620425, arXiv: 1112.5772 [math.LO].

[Hal17] Lorenz J. Halbeisen, Combinatorial Set Theory: With a Gentle Introduction to Forcing, Springer Monographs in Mathematics, Springer, London,^{2}2017, doi: 10.1007/978-3-319-60231-8.

[Hau08] Felix Hausdorff, Grundzüge einer Theorie der geordneten Mengen, Math. Ann. 65 (1908), no. 4, 435–505, doi: 10.1007/BF01451165.

[Hil16] Jacob Hilton, The Topological Pigeonhole Principle for Ordinals, J. Symb. Log. 81 (2016), no. 2, 662–686, doi: 10.1017/JSL.2015.45, arXiv: 1410.2520 [math.LO].

[HS69] Labib Haddad and Gabriel Sabbagh, Calcul de certains nombres de Ramsey généralisés, C. R. Acad. Sci. Paris Sér. A-B 268 (1969), A1233–A1234.

[IRW] Ferdinand Ihringer, Deepak Rajendraprasad, and Thilo Volker Weinert, New Bounds on the Ramsey Numbers r(I_{m}, L_{n}), arXiv: 1707.09556 [math.CO].

[Jon08] Albin Lee Jones, On a Result of Szemerédi, J. Symb. Logic 73 (2008), no. 3, 953–956, doi: 10.2178/JSL/1230396758.

[KW96] Anastasis Kamburelis and Bogdan Zbigniew Węglorz, Splittings, Arch. Math. Logic 35 (1996), no. 4, 263– 277, doi: 10.1007/S001530050044.

[Lar73] Jean Ann Larson, A Short Proof of a Partition Theorem for the Ordinal ω^{ω}, Ann. Math. Logic 6 (1973), 129–145, doi: 10.1016/0003-4843(73)90006-5.

[Lav71] Richard Laver, On Fraïssé’s Order Type Conjecture, Ann. of Math. (2) 93 (1971), 89–111, available at

https://www.jstor.org/stable/pdf/1970754.pdf  .

[LHW] Chris Lambie-Hanson and Thilo Volker Weinert, Partitioning Subsets of Generalised Scattered Orders, arXiv: 1701.05791 [math.LO].

[Mal89] Vyacheslav  Ivanovich  Malyhin,  Topological  Properties  of  Cohen  Generic
Extensions,  Trans. Mosc. Math. Soc. 52 (1989),  3–33,  available at

       http://www.mathnet.ru/links/cc672532bfb79cbe49268c92dbe18bbe/mmo483.pdf  .

[Mer] Omer Mermelstein, Calculating the Closed Ordinal Ramsey Number R^{cl}(ω · 2, 3)^{2}, arXiv: 1702.03878 [math.LO].

[MS13] Maryanthe Malliaris and Saharon Shelah, General Topology Meets Model Theory, on 𝔭 and 𝔱, Proc. Natl. Acad. Sci. USA 110 (2013), no. 33, 13300–13305, doi: 10.1073/PNAS.1306114110.

[Orr95] John Lindsay Orr, Shuffling of Linear Orders, Canad. Math. Bull. 38 (1995), no. 2, 223–229, doi: 10.4153/CMB-1995-032-1.

[Ros82] Joseph Goeffrey Rosenstein, Linear Orderings, Pure and Applied Mathematics, vol. 98, Academic Press, New York, 1982.

[RT18] Dilip Raghavan and Stevo Todorcevic, Suslin Trees, the Bounding Number, and Partition Relations, Israel J. Math. 225 (2018), no. 2, 771–796, doi: 10.1007/S11856-018-1677-1, arXiv: 1602.07901 [math.LO].

[Sch10] Rene Schipperus, Countable Partition Ordinals, Ann. Pure Appl. Logic 161 (2010), no. 10, 1195–1215, doi: 10.1016/J.APAL.2009.12.007.

[Sch12] , The Topological Baumgartner-Hajnal Theorem, Trans. Amer. Math. Soc. 364 (2012), no. 8, 3903– 3914, doi: 10.1090/S0002-9947-2012-04990-7.

[Ste93] Juris Steprāns, Combinatorial Consequences of Adding Cohen Reals, Set Theory of the Reals (Haim Judah, ed.), Israel Mathematics Conference Proceedings, vol. 6, Gelbart Research Institute for Mathematical Sciences, Bar-Ilan University, Ramat-Gan, 1993, pp. 583–617.

[vD84] Eric Karel van Douwen, The Integers and Topology, Handbook of Set-Theoretic Topology (Kenneth Kunen and Jerry E. Vaughan, eds.), North-Holland, Amsterdam, 1984, pp. 111–167, doi: 10.1016/B978-0-444-86580-9.50006-9.

[Wei14] Thilo  Volker  Weinert,  Idiosynchromatic  Poetry,  Combinatorica  34  (2014),
no.  6,  707–742,  doi: 10.1007/S00493-011-2980-1,  also  available  at

       https://www.math.bgu.ac.il/~weinert/Poetry_colour0.pdf  .

[Wil77] Neil Hale Williams, Combinatorial Set Theory, Studies in Logic and the Foundations of Mathematics, vol. 91, North-Holland, Amsterdam, 1977.

Institute of Discrete Mathematics and Geometry, TU Wien, Wiedner Hauptstraße 8–10/104, 1040 Wien, Austria

E-mail address: klausner.lukas@gmail.com

Kurt Gödel Research Center for Mathematical Logic, University of Vienna, Währinger Straße 25, 1090 Wien, Austria

E-mail address: thilo.weinert@univie.ac.at