PARTITIONING SUBSETS OF GENERALISED SCATTERED ORDERS

CHRIS LAMBIE-HANSON AND THILO WEINERT

Abstract. In 1956, 48 years after Hausdorff provided a comprehensive account on ordered sets and defined the notion of a scattered order, Erdős and Rado founded the partition calculus in a seminal paper. The present paper gives an account of investigations into generalisations of scattered linear orders and their partition relations for both singletons and pairs. We provide analogues of the Milner-Rado paradox for these orders instead of ordinals. For infinite, regular κ, we investigate the extent to which the classes of κ-scattered, weakly κ-scattered, and κ-saturated linear orders of size κ are closed under the partition relation τ ⟶ (φ, n)^{2} for all n < ω. We prove that for a regular cardinal κ such that |•(κ) = 𝔟_{κ} = κ^{+}, the partition relation κ^{+}κ ⟶ (κ^{+}κ, 3)^{2} fails. Finally we generalise a result of Komjáth and Shelah about partitions of scattered linear orders to a similar result about partitions of κ-scattered linear orders for uncountable κ. Together, this continues older research by Erdős, Galvin, Hajnal, Larson and Takahashi and more recent investigations by Abraham, Bonnet, Cummings, Džamonja, Komjáth, Shelah and Thompson.

2010 Mathematics Subject Classification. Primary 03E02, Secondary 03E17, 05C63, 05D10, and 06A05. Key words and phrases. graph, linear order, partition relation, Ramsey theory, scattered order, stick, unbounding number. A portion of this research was undertaken while the first author was a Lady Davis Postdoctoral Fellow and the second author was

a postdoctoral fellow at the Ben-Gurion-University of the Negev. The first author would like to thank the Lady Davis Fellowship Trust and the Hebrew University of Jerusalem. The second author would like to thank the Ben-Gurion University of the Negev and the Israel Science Foundation which supported this research(grant #1365/14). Both authors wish to thank William Chen, Fred Galvin, Menachem Kojman and Ashutosh Kumar for discussing proofs, results, or problems of this paper. They also wish to thank the logic and topology seminar of Ben-Gurion University organised by Nadav Meir and Omer Mermelstein for hosting a pair of lectures which triggered this cooperation. Finally they would like to thank Heike Mildenberger who shared her L^{A}TEX-Code for |• with them.

1. Introduction

In this paper, we study partition relations in the context of scattered linear orders and their generalisations. Recall that a linear order is scattered if it does not embed a copy of the rationals and is σ-scattered if it is a countable union of scattered linear orders. The classes of scattered and σ-scattered linear orders are, in a sense, the simplest classes of linear orders past the class of well-orders, and, as such, they have played a central role in the study of general linear orders.

One of the central questions motivating the investigations of this paper concerns the extent to which the classes of scattered and σ-scattered linear orders behave similarly to the class of well-orders. Two seminal results contributing to the understanding of this issue are the following:

• In [908Ha], Hausdorff characterizes the class of scattered linear orders as the smallest class containing all well-orders and anti-well-orders and closed under well-ordered and anti-well-ordered lexicographic sums.

• In [971La], Laver proves Fraïssé’s Conjecture by showing that the class of σ-scattered linear orders is

well-quasi-ordered by embeddability. We will be interested not just in scattered linear orders but also in generalisations of scattered linear orders

introduced by Džamonja and Thompson in [006DT]. We first recall some relevant definitions. For unfamiliar notation, see the Notation subsection at the end of the Introduction.

Definition 1.1. Suppose κ is an infinite cardinal, φ is a linear order type, and P is a linear order of type φ. (1) φ is κ-dense if |P | > 1 and, for all a, b ∈ P, if a <_{P} b, then |]a, b[_{P} | ⩾ κ.

(2) φ is κ-saturated if P ≠ ∅ and, for all A, B ⊆ P such that |A|, |B| < κ and A <_{P} B, there is c ∈ P such that A <_{P} c <_{P} B.

In [908Ha, 914Ha] Hausdorff shows that, if κ is an infinite cardinal, the following hold:

• If P is a κ-saturated linear order, then every linear order of cardinality κ embeds into P.

• There is a κ^{+}-saturated linear order L of cardinality 2^{κ} such that: – L is embeddable into every κ^{+}-saturated linear order;

– no suborder of L of cardinality κ^{++} is well-ordered or anti-well-ordered.

• If κ is singular, then every κ-saturated order is also κ^{+}-saturated. In [949Si], Sierpiński defines, for every infinite cardinal κ, a linear order of size κ^{<κ}, which he calls ℚ_{κ}. In

addition, he shows that, for every κ, ℚ_{κ+} is κ^{+}-saturated. In [956Gi], Gillman shows:

(1) for every infinite cardinal κ, ℚ_{κ} is embeddable into every κ-saturated linear order;

(2) for every limit cardinal κ, both that every κ-sized linear order embeds into ℚ_{κ} and that it is κ-saturated if and only if κ is inaccessible.

In [006DT] Džamonja and Thompson, building on previous work of Abraham and Bonnet, introduce the following definition.

Definition 1.2 (Džamonja-Thompson, [006DT]). Suppose κ is an infinite, regular cardinal, and φ is a linear order type.

(1) φ is κ-scattered if there is no κ-dense order type τ such that τ ⩽ φ.

(2) φ is weakly κ-scattered if there is no κ-saturated τ such that τ ⩽ φ.

Note that, for κ = ℵ_{0}, the classes of κ-scattered and weakly κ-scattered linear orders coincide and are equal to the class of scattered linear orders. For uncountable κ, the classes are provably different, i.e., there is a weakly κ-scattered linear order that is not κ-scattered.

In [012A^{&}], Abraham et al. prove a generalisation of Hausdorff’s structure theorem for the class of κ-scattered linear orders.

Definition 1.3. Suppose κ is an infinite cardinal. Then BL_{κ} denotes the class of all linear order types φ such that either |φ| < κ, φ is a well-ordering, or φ is an anti-well-ordering.

Theorem 1.4 ([012A^{&}, Theorem 3.10]). Let κ be an infinite cardinal. The class of κ-scattered linear order types is the smallest class of linear order types containing BL_{κ} and closed under lexicographic sums with index set in BL_{κ}.

The results in this paper concern the behavior of generalised scattered orders with respect to partition relations. The following folklore result provides some motivation for our investigations. The proof uses a pair-colouring first deployed by Sierpiński, cf. [933Si].

Theorem 1.5 (Folklore). If τ is a linear order type, then τ−̸→(ω, ω^{∗})^{2}.

Theorem 1.5 implies that, in any consistent positive partition relation of the form τ ⟶ (φ_{0}, φ_{1})^{2}, where all variables indicate linear order types, if φ_{0} and φ_{1} are infinite, then either both must be well-orders or both must be anti-well-orders. Since we want to work with classes of linear orders larger than the class of well-orders, this indicates that we should look at partition relations of the form τ ⟶ (φ, n)^{2}, where n is a natural number. Note that, if κ is an infinite cardinal and α < κ^{+}, then there is β < κ^{+} such that, for all n < ω, we have β ⟶ (α, n)^{2}, cf. [972EM]. Our goal of comparing the classes of generalised scattered orders with the class of well-orders thus leads us naturally to the following general question.

Question 1.6. Suppose κ is an infinite cardinal and φ is a κ-scattered (resp. weakly κ-scattered) linear order type of size κ. Must there be a κ-scattered (resp. weakly κ-scattered) τ of size κ such that, for all n < ω, τ ⟶ (φ, n)^{2}?

In most of the existing literature concerning partition relations and linear orders, the linear orders under consideration are in fact well-orders. Let us mention the exceptions we are aware of: Erdős and Rado prove in [956ER, Theorem 6] that η ⟶ (η, ℵ_{0})^{2}. Erdős and Hajnal prove in [963EH, Corollary 1] that for any countable scattered linear order type τ we have that τ ⟶ (φ, ℵ_{0})^{2} implies φ ∈ {n, n + ω^{∗}, ω + n : n < ω}. Larson proves in [974La, Theorem 4.1] that (ωω^{∗})^{ω} ⟶ ((ωω^{∗})^{ω}, n)^{2} for all natural numbers n; she also shows in [974La, Theorem 4.3] that (ωω^{∗})^{kn} ⟶ ((ωω^{∗})^{k}, n)^{2} for all natural numbers k and n.

Remark 1.7. Recall that (αα^{∗})^{ω} can be defined as the order type of the set S_{α} := α^{<ω} of finite sequences of elements of α, ordered by ≺_{α}. In order to define ≺_{α} let, for s, t ∈ S_{α}, δ(s, t) := min {n < ω : n ∈ dom(s)△dom(t) ∨ s(n) ≠ t(n)}.

For s, t ∈ S_{α} let s ≺_{α} t ⇔ \begin{cases}δ(s, t) is even and (t ⊏ s or t(δ(s, t)) < s(δ(s, t))) or \\ δ(s, t) is odd and (s ⊏ t or s(δ(s, t)) < t(δ(s, t))). \end{cases}

Regarding this order type, cf. Corollaries 5.7 and 5.12 where it appears as a factor of some order types in negative partition relations. Also cf. Questions 7.3 and 7.4.

The paper is structured as follows. In Section 2, we prove some basic results concerning generalised scattered orders that will be used throughout the paper. Furthermore, we show that, if τ is a κ-saturated linear order type and φ is a linear order type of size κ, then τ ⟶ (φ, n)^{2} for all n < ω. In Section 3, we show that, if κ^{<κ} = κ and φ is a weakly κ-scattered linear order type of size κ, then there is a weakly κ-scattered linear order type τ of size κ such that τ ⟶ (φ, n)^{2} for all n < ω. ^{1}

In Section 4, we prove that, for a regular cardinal κ, the negative partition relation κ^{+}κ−̸→(κ^{+}κ, 3)^{2} follows from 𝔟_{κ} = |•(κ) = κ^{+}. This complements a result of Larson indicating that the same negative relation follows from 𝔡 = ℵ_{1}. In Section 5, we use this negative partition relation to show that, if 𝔟 = |• = ℵ_{1} or 𝔡 = ℵ_{1}, then there is an ℵ_{1}-scattered linear order type φ of size ℵ_{1} such that, for every ℵ_{1}-scattered linear order type τ of size ℵ_{1}, τ−̸→(φ, 3)^{2}. We show, moreover, that if κ > ω is a regular cardinal, it is consistent that κ^{<κ} = κ and that there is a κ-scattered order type φ of size κ such that, for all κ-scattered order types τ of size κ, τ−̸→(φ, 3)^{2}. Finally, in Section 6, we generalise a result of Komjath and Shelah from [003KS]. We prove that, if κ^{<κ} = κ, φ is a κ-scattered linear order type, and ν is a cardinal, then there is a κ-scattered linear order type τ such that τ ⟶ [φ]_{ν,κ}^{1}.

1For κ = ℵ_{0} this result is probably due to Galvin but has never been published, cf. [014Ga, 015Sh]. Its noticable absence from [982Ro] led the second author to its rediscovery. Subsequently the first author generalised it to its current form.

1.1. Notation. We use Greek minuscules ρ, τ, φ and ψ to refer to order types of linear orders. In particular, ω refers to the order type of the natural numbers and η to that of the rational numbers. The Greek letters κ, μ and ν refer to cardinals. All other Greek letters used refer to ordinals. The only exception is σ which appears in the notion of σ-scatteredness. We will use Roman capitals to refer to actual ordered sets, ⟨P, <_{P} ⟩, for instance. If A, B ⊆ P (with one or both possibly empty), then A <_{P} B means that, for all a ∈ A and b ∈ B, a <_{P} b. If A ⊆ P and b ∈ P, then A <_{P} b and b <_{P} A have the obvious meanings. If P is a linear order of order type φ, we will denote this by otp(P) = φ. We will sometimes abuse notation and write |φ| to denote |P |, where P is an order of type φ. If φ and τ are linear order types, we will write φ ⩽ τ to mean that there are linear orders P and Q of type φ and τ, respectively, such that P is a suborder of Q.

If a, b ∈ P and a <_{P} b, then ]a, b[_{P} denotes the open interval {c ∈ φ : a <_{P} c <_{P} b} and [a, b]_{P} denotes the closed interval {c ∈ P : a ⩽_{φ} c ⩽_{φ} b}. [a, b[_{P} and ]a, b]_{P} are given the obvious meanings. If s is a sequence, then ℓ(s) denotes its length. If φ is an order type, then φ^{∗} denotes the reverse of φ. If φ is a linear order type and, for all a ∈ φ, τ_{a} is a linear order type, then the lexicographic sum ∑_{a∈φ} τ_{a} is the type of the linear order consisting of pairs in X := {⟨a, b⟩ : a ∈ P ∧ b ∈ T_{a}} where ⟨P, <_{P} ⟩ is an order of type φ and, for every a ∈ P, the pair ⟨T_{a}, <_{Ta}⟩ is an order of type τ_{a}. If ⟨a_{0}, b_{0}⟩, ⟨a_{1}, b_{1}⟩ ∈ X are of this kind, then ⟨a_{0}, b_{0}⟩ <_{X} ⟨a_{1}, b_{1}⟩ iff a_{0} <_{P} a_{1} or (a_{0} = a_{1} and b_{0} <_{Ta0} b_{1}). If there is a linear order type τ such that τ_{a} = τ for all a ∈ φ, then we may denote the lexicographic sum ∑_{a∈φ} τ as τφ.

If β is an ordinal and f ≠ g are functions with dom(f) = dom(g) = β, then Δ(f, g) is the least α < β such that f(α) ≠ g(α). For every sequence of sets ⟨X_{α} : α < β⟩ we denote the family of all functions having domain β which, for all α < β, satisfy f(α) ∈ X_{α}, by×_{α<β} X_{α}. If β is an ordinal and, for all α < β, φ_{α} is an order type, then ∏_{α<β} φ_{α} is given by the lexicographic ordering on×_{α<β} P_{α} where P_{α} has type φ_{α} for every α < β. More precisely, if f, g ∈×_{α<β} P_{α}, then f <_{lex} g iff f(Δ(f, g)) <_{PΔ(f,g)} g(Δ(f, g)). If there is φ

such that φ_{α} = φ for all α < β, we will often write ^{β}φ instead of ∏_{α<β} φ_{α}. Finally, for every cardinal κ, let ℚ_{κ} denote the lexicographic ordering of the set of sequences s of zeros and ones of length κ for which there is a largest α < κ such that s(α) = 1. Cf. [913Sc, 005Ha] for discussions of order types and their arithmetic.

For an ordered set X and an order type τ the expression [X]^{τ} denotes the set of all subsets of X having order type τ. If Y is any set and κ is a cardinal then [X]^{κ} denotes the collection of all subsets of X having cardinality κ.

If φ and τ are linear order types and ν, μ are cardinals, then τ ⟶ (φ)_{μ}^{ν} holds if, whenever P has order type τ and f : [P]^{ν} → μ, there is a suborder Q of P such that Q has order type φ and f ↾ [Q]^{ν} is constant. If n is a natural number, then τ ⟶ (φ_{0}, …, φ_{n})^{ν} holds if, whenever P has order type τ and f : [P]^{ν} → n + 1, there is a suborder Q of P and some i ⩽ n such that Q has order type φ_{i} and f ↾ [Q]^{ν} is constant with value i. If n is a natural number and, for all i ⩽ n, k_{i} is a natural number, then

τ ⟶ (φ_{0,0} ∨ ⋯ ∨ φ_{0,k0}, …, φ_{n,0} ∨ ⋯ ∨ φ_{n,kn})^{ν}

holds if, whenever P has order type τ and f : [P]^{ν} → n + 1 there is an i ⩽ n, an m ⩽ k_{i} and a suborder Q of P such that Q has order type φ_{i,m} and f ↾ [Q]^{ν} is constant with value i. In all cases of interest to us, ν will be finite.

We will also be discussing square-bracket partition relations, which we recall here. Suppose φ and ψ are linear orders, 1 ⩽ n < ω, and μ ⩽ ν are cardinals. Then ψ ⟶ [φ]_{ν,<μ}^{n} is the assertion that, whenever P has order type ψ and f : [P]^{n} → ν, there is A ∈ [ν]^{<μ} and a suborder Q of P such that Q has order type φ and f[[Q]^{n}] ⊆ A. If κ is a cardinal, ψ ⟶ [φ]_{ν,<κ+}^{n} is typically written as ψ ⟶ [φ]_{ν,κ}^{n}.

This style of notation for partition problems was first introduced in [956ER]; both the square-bracket partition relation and the partition relation with alternatives were introduced in [965E]. The latter is was not that widely considered up to now as it is superfluous whenever all the entries are ordinals, which is still the most widespread version. To our knowledge, after [965E, 971E, 016L] this is only the fourth paper in which this relation is considered.

2. Preliminaries

To state our results in their full generality, we will be interested in the following notion, which is slightly finer than that given by Definition 1.2.

Definition 2.1. Suppose κ is an infinite, regular cardinal, μ is an infinite cardinal, φ is a linear order type, and P is an order of type φ. φ is ⟨κ, μ⟩-scattered (resp. weakly ⟨κ, μ⟩-scattered) if there is ν < μ and a sequence of suborders ⟨P_{ζ} | ζ < ν⟩ of P such that otp(P_{ζ}) is κ-scattered (resp. weakly κ-scattered) for all ζ < ν and ⋃_{ζ<ν} P_{ζ} = P.

We start by investigating the relationships between these different classes of linear order types. Suppose κ is an infinite cardinal. The characterisation of the class of κ-scattered linear order types given by Theorem 1.4 allows one to prove results about κ-scattered linear order types by induction on the “complexity” of the type. More precisely, let L be the class of κ-scattered linear order types. Define L_{α} inductively for ordinals α as follows. L_{0} = BL_{κ}. If β is a limit ordinal, then L_{β} = ⋃_{α<β} L_{α}. If L_{α} has been defined, then L_{α+1} is the class of all lexicographic sums ∑_{a∈τ} φ_{a}, where τ ∈ BL_{κ} and, for all a ∈ τ, φ_{a} ∈ L_{α}. Then ⋃_{α∈On} L_{α} = L.

We use this method here to relate the classes of κ-scattered and ⟨ℵ_{0}, κ⟩-scattered linear order types when κ is a successor cardinal.

Proposition 2.2. Suppose κ = ν^{+} and φ is a κ-scattered linear order type. Then φ is ⟨ℵ_{0}, κ⟩-scattered.

Proof. Let P be an order of type φ. We proceed by induction on the complexity of φ. First suppose φ ∈ BL_{κ}. If |φ| < κ, then P is the union of fewer than κ singletons, so φ is certainly ⟨ℵ_{0}, κ⟩-scattered. If, on the other hand, φ is a well-order or anti-well-order, then φ is itself scattered and hence ⟨ℵ_{0}, κ⟩-scattered.

Next, suppose τ ∈ BL_{κ}, φ = ∑_{a∈τ} φ_{a}, and each φ_{a} is ⟨ℵ_{0}, κ⟩-scattered. Let T be an order of type τ. For each a ∈ T, let P_{a} be an order of type φ_{a} and let {P_{a,ζ} : ζ < ν} be a family of suborders of P_{a} witnessing that φ_{a} is ⟨ℵ_{0}, κ⟩-scattered. We may assume that P consists of the set {⟨a, b⟩ : a ∈ T ∧ b ∈ P_{a}} ordered lexicographically.

Suppose first that |T | < κ. For a ∈ T and ζ < ν, let P′_{a,ζ} = {a} × P_{a,ζ}. Then P′_{a,ζ} is scattered as a suborder of P, so P = ⋃_{a∈T,ζ<ν} P′_{a,ζ} is the union of fewer than κ scattered linear orders, so φ is ⟨ℵ_{0}, κ⟩-scattered.

Finally, suppose that T is a well-order or anti-well-order. Then, for each ζ < ν, Q_{ζ} := ⋃_{a∈T} P′_{a,ζ} is scattered as a suborder of P, so P = ⋃_{ζ<ν} Q_{ζ} and φ is ⟨ℵ_{0}, κ⟩-scattered. □

For strongly inaccessible κ, the preceding proposition fails. To show this, we need some useful facts about saturated linear orders. Let μ be an infinite, regular cardinal. An easy argument shows that there is a μsaturated linear order of size μ^{<μ}. In fact, if τ_{0} is any linear order of size μ^{<μ}, there is a μ-saturated linear order τ of size μ^{<μ} such that τ_{0} ⩽ τ. If μ^{<μ} = μ, there is thus a μ-saturated linear order of size μ. Any two such linear orders are isomorphic. Similarly, if τ is μ-saturated and φ is a linear order of size μ, then φ ⩽ τ. In fact, the following holds.

Lemma 2.3. Suppose τ is a μ-saturated order type and φ is an order type of size μ. Then there are μ-saturated order types {τ_{a} : a ∈ φ} such that ∑_{a∈φ} τ_{a} ⩽ τ.

Proof. Let P be an order of type φ and let {a_{α} : α < μ} be an enumeration of its elements. Furthermore, let T be an order of type τ. By recursion on α < μ, define ⟨b_{α}^{0}, b_{α}^{1} | α < μ⟩ such that:

• for all α < μ, b_{α}^{0}, b_{α}^{1} ∈ T and b_{α}^{0} <_{T} b_{α}^{1};

• for α, β < μ, if a_{α} <_{P} a_{β}, then b_{α}^{1} <_{T} b_{β}^{0} and, if a_{β} <_{P} a_{α}, then b_{β}^{1} <_{T} b_{α}^{0}.

The construction is straightforward using the fact that τ is μ-saturated. Also, since τ is μ-saturated, for each α < μ, the interval ]b_{α}^{0}, b_{α}^{1}[_{T} is itself a μ-saturated order. For all α < μ, let T_{aα} = ]b_{α}^{0}, b_{α}^{1}[_{T}, and let τ_{aα} = otp(T_{aα}). Then ⋃_{a∈P} T_{a} is a suborder of T of type ∑_{a∈φ} τ_{a}. □

Proposition 2.4. Suppose T is a μ-saturated linear order, ν < μ, and {T_{α} : α < ν} is a collection of weakly μ-scattered suborders of T. Then ⋃_{α<ν} T_{α} ≠ T.

Proof. We define sequences ⟨A_{α} | α < ν⟩ and ⟨B_{α} | α < ν⟩ such that the following hold:

(1) For all α < ν, A_{α}, B_{α} ⊆ T_{α} and |A_{α}|, |B_{α}| < μ (one or both of A_{α} and B_{α} may be empty).

(2) For all α < β < ν, A_{α} <_{T} A_{β} and B_{β} <_{T} B_{α}.

(3) For all α, α′ < ν, A_{α} < B_{α′}.

(4) For all α < ν, ]A_{α}, B_{α}[_{Tα} = ∅. The construction is by recursion, as follows. Suppose β < ν and ⟨A_{α} | α < β⟩ and ⟨B_{α} | α < β⟩ have been defined. Let C_{β} = ⋃_{α<β} A_{α} and D_{β} = ⋃_{α<β} B_{α}. Note that C_{β} <_{T} D_{β}. By assumption, T_{β} is weakly μ-scattered. In particular, T_{β} ∩]C_{β}, D_{β}[_{T} is not μ-saturated. There are thus A_{β}, B_{β} ⊆ T_{β} ∩]C_{β}, D_{β}[_{T} such that |A_{β}|, |B_{β}| < μ, A_{β} <_{T} B_{β}, and ]A_{β}, B_{β}[_{Tβ} = ∅. A_{β} and B_{β} are then as desired.

At the end of the construction, let A = ⋃_{α<ν} A_{α} and B = ⋃_{α<ν} B_{α}. Then |A|, |B| < μ and A <_{T} B. Thus, since T is μ-saturated, there is d ∈ T such that A <_{T} {d} <_{T} B. Suppose that, for some α < ν, d ∈ T_{α}. Then d ∈ ]A_{α}, B_{α}[_{Tα}, which contradicts requirement (4) in the construction. Thus, ⋃_{α<ν} T_{α} ≠ T. □

This has two corollaries, the first of which is immediate.

Corollary 2.5. Suppose T is a μ-saturated linear order, ν < μ, and c : T → ν. Then there is a μ-saturated suborder T′ ⊆ T such that c ↾ T′ is constant.

Corollary 2.6. Suppose κ is a strongly inaccessible cardinal. Then there is a κ-scattered linear order that is not ⟨ℵ_{0}, κ⟩-scattered.

Proof. Let ⟨μ_{ζ} | ζ < κ⟩ be an increasing sequence of regular cardinals, cofinal in κ. For each ζ < κ, let φ_{ζ} be a μ_{ζ}-saturated linear order type of size μ_{ζ}^{<μζ}. Since κ is strongly inaccessible, |φ_{ζ}| < κ so, in particular, φ_{ζ} is κ-scattered. Let φ = ∑_{ζ<κ} φ_{ζ}. Then φ is κ-scattered. We claim φ is not ⟨ℵ_{0}, κ⟩-scattered. Otherwise, there would be ν < κ, an order T of type φ, and a family {T_{ξ} : ξ < ν} of suborders of T such that each T_{ξ} is scattered and T = ⋃_{ξ<ν} T_{ξ}. Fix ζ < κ such that ν < μ_{ζ}, and let P ⊆ T be a μ_{ζ}-saturated linear order of

size μ_{ζ}^{<μζ}. Since P is μ_{ζ}-saturated, by Lemma 2.4, P ≠ ⋃_{ξ<ν}(T_{ξ} ∩ P). This is a contradiction, so φ is not ⟨ℵ_{0}, κ⟩-scattered. □

On the other hand, it is straightforward to construct even a σ-scattered (i.e. ⟨ℵ_{0}, ℵ_{1}⟩-scattered) linear order of arbitrarily high density, so, for every regular, uncountable cardinal κ, there is an ⟨ℵ_{0}, κ⟩-scattered linear order that is not κ-scattered. Later results will imply that, for every regular, uncountable κ, there is a weakly κ-scattered linear order that is not ⟨ℵ_{0}, κ⟩-scattered. Therefore, we will obtain the following corollary.

Corollary 2.7. Suppose κ is a successor cardinal. Let S_{κ}, S_{ℵ0,κ}, and WS_{κ} be the classes of κ-scattered, ⟨ℵ_{0}, κ⟩-scattered, and weakly κ-scattered linear order types, respectively. Then S_{κ} ⊆ S_{ℵ0,κ} ⊆ WS_{κ}, and neither of the inclusions is reversible.

We turn now to partition relations. Due to the restrictions identified by Theorem 1.5, we will largely be interested in partition relations of the form τ ⟶ (φ, n)^{2}, where n < ω. The following Lemma will be very useful.

Lemma 2.8. Suppose φ, τ, and ρ are linear order types, n < ω, τ ⟶ (φ, n)^{2}, and, for all cardinals ν < |φ|, ρ ⟶ (τ)_{ν}^{1}. Then ρφ ⟶ (φ, n + 1)^{2}.

Proof. Let ψ = ρφ, let ⟨R, <_{R}⟩ be an ordered set of type ρ and ⟨P, <_{P} ⟩ an ordered set of type φ. Let f : [P × R]^{2} → 2. We will show that there is either a subset of P × R having order type φ under the lexicographic order that is 0-homogeneous for f or a subset of size n+1 that is 1-homogeneous for f. Enumerate the elements of P as ⟨a_{ζ} : ζ < |P |⟩. We will attempt to construct a sequence ⟨b_{ζ} : ζ < |φ|⟩ from R such that H := {⟨a_{ζ}, b_{ζ}⟩ : ζ < |P |} is 0-homogeneous for f. Since the order type of H under the lexicographic ordering is φ, a successful construction will establish the Lemma for this particular coloring..

We proceed by recursion on ζ < |P |. To start, let b_{0} be an arbitrary element of R. Suppose ζ < |P | and b_{ξ} has been defined for ξ < ζ so that {⟨a_{ξ}, b_{ξ}⟩ : ξ < ζ} is 0-homogeneous for f. If there is b ∈ R such that, for all ξ < ζ, f({⟨a_{ξ}, b_{ξ}⟩, ⟨a_{ζ}, b⟩}) = 0, then let b_{ζ} be such a b. Suppose there is no such b. Define a function g : R → ζ by letting, for all b ∈ R, g(b) be least such that f({⟨a_{g(b)}, b_{g(b)}⟩, ⟨a_{ζ}, b⟩}) = 1. Since ρ ⟶ (τ)_{|ζ|}^{1}, there is ξ < ζ and B ⊆ R of order type τ such that B is ξ-homogeneous for g. Consider f ↾ [{a_{ζ}} × B]^{2}. Since τ ⟶ (φ, n)^{2}, we either have a subset B_{0} ⊆ B of order type φ such that {a_{ζ}} × B_{0} is 0-homogeneous for f or a subset B_{1} ⊆ B of size n such that {a_{ζ}} × B_{1} is 1-homogeneous for f. In the former case, we have found a 0-homogeneous subset of P ×R of order type φ and are thus finished. In the latter case, {⟨a_{ξ}, b_{ξ}⟩}∪({a_{ζ}}×B_{1}) is a 1-homogeneous subset of P × R of size n + 1, and we are again done.

Therefore, if our attempted construction of H fails, it is necessarily because we have found either a 0homogeneous set of order type φ or a 1-homogeneous of size n + 1. In any outcome, we have verified the Lemma. □

We now easily have the following.

Theorem 2.9. Suppose κ is an infinite, regular cardinal and φ is a linear order type of size κ. Then, for all n < ω and all κ-saturated linear order types τ, τ ⟶ (φ, n)^{2}.

Proof. We proceed by induction on n simultaneously for all κ-saturated linear order types τ. If n ∈ {0, 1, 2}, then trivially φ ⟶ (φ, n)^{2}, so certainly τ ⟶ (φ, n)^{2} for all κ-saturated τ. Thus, suppose 2 ⩽ n < ω and we have proven the theorem for n. Fix a κ-saturated type τ. By Lemma 2.3, we can find κ-saturated order types {τ_{a} : a ∈ φ} such that ∑_{a∈φ} τ_{a} ⩽ τ. By Corollary 2.5, the assumption that ψ ⟶ (φ, n)^{2} for all κ-saturated ψ, and the argument from Lemma 2.8, we have ∑_{a∈φ} τ_{a} ⟶ (φ, n + 1)^{2}, so also τ ⟶ (φ, n + 1)^{2}. □

3. Weakly scattered linear orders

In this section, we establish positive partition relations for the class of weakly κ-scattered linear orders under the assumption κ^{<κ} = κ. Our aim is to prove the following theorem.

Theorem 3.1. Suppose κ^{<κ} = κ and φ is a weakly κ-scattered linear order type of size at most κ. Then there is a weakly κ-scattered linear order type τ of size at most κ such that, for all n < ω, τ ⟶ (φ, n)^{2}.

Fix for the rest of the section a cardinal κ such that κ^{<κ} = κ. The following lemma will be useful.

Lemma 3.2. Suppose φ is a linear order type and ν is a cardinal. Then ^{ν}φ ⟶ (φ)_{ν}^{1}.

Proof. Let P be an ordered set of type φ, let F : ^{ν}P → ν, and suppose for sake of contradiction that there is no homogeneous set of order type φ in the lexicographic order. By recursion on α ⩽ ν, we will construct f_{α} ∈ ^{α}P such that, for all α < β ⩽ ν:

(1) f_{β} ↾ α = f_{α};

(2) for all g ∈ ^{ν}P such that g ↾ (α + 1) = f_{α+1}, F (g) ≠ α. Suppose β ⩽ ν and we have constructed f_{α} for all α < β. If β is a limit ordinal, then easily f_{β} = ⋃_{α<β} f_{α} satisfies our requirements. Thus, suppose β = α + 1. Suppose that, for all a ∈ P, there is g ∈ ^{ν}P such that g ↾ α = f_{α}, g(α) = a, and F (g) = α. Choose such a g_{a} for each a ∈ P. Then {g_{a} : a ∈ P } is an α-monochromatic set for F of order type φ, contradicting our assumptions. Thus, there is an a ∈ P such that, for all g ∈ ^{ν}P such that g ↾ α = f_{α} and g(α) = a, we have F (g) ≠ α. Choose such an a, and define f_{β} by f_{β} ↾ α = f_{α} and f_{β}(α) = a.

At the end of the recursion, we have constructed f_{ν} ∈ ^{ν}P. Let α = F (f_{ν}). Then f_{ν} contradicts requirement (2) from the construction applied to α and ν. Thus, ^{ν}φ ⟶ (φ)_{ν}^{1}. □

Lemma 3.3. Suppose P_{0} and P_{1} are weakly κ-scattered linearly ordered sets. Then ⟨P_{0} × P_{1}, <_{lex}⟩ is weakly κ-scattered.

Proof. Suppose for sake of contradiction that C ⊆ P_{0} × P_{1} is κ-saturated. Let

T_{0} = {a ∈ P_{0} : there is b ∈ P_{1} such that ⟨a, b⟩ ∈ C}.

For a ∈ T_{0}, let T_{1,a} = {b ∈ P_{1} : ⟨a, b⟩ ∈ C}. The proof now splits into two cases.

Case 1: for all a ∈ T_{0}, |T_{1,a}| = 1. In this case, we must have |T_{0}| > 1. Thus, choose a_{0} <_{P0} a_{1}, both in T_{0}. Since P_{0} is weakly κ-scattered, T_{0} ∩]a_{0}, a_{1}[_{P0} is not κ-saturated. Thus, there are A_{0}, A_{1} ⊆ T_{0} ∩]a_{0}, a_{1}[_{P0} such that |A_{0}|, |A_{1}| < κ, A_{0} <_{P0} A_{1}, and there is no c ∈ T_{0} such that A_{0} <_{P0} c <_{P0}< A_{1}. For each a ∈ {a_{0}, a_{1}}∪A_{0}∪A_{1}, let b_{a} be the unique b ∈ P_{1} such that ⟨a, b⟩ ∈ C. For i < 2, let B_{i} = {⟨a, b_{a}⟩ : a ∈ {a_{i}} ∪ A_{i}}. Then B_{i} ⊆ C, |B_{i}| < κ, B_{0} <_{lex} B_{1}, and there is no c ∈ C such that B_{0} <_{lex} c <_{lex} B_{1}, contradicting the assumption that C is κ-saturated.

Case 2: there is a ∈ T_{0} such that |T_{1,a}| > 1. Choose such an a ∈ T_{0}, and fix b_{0} <_{P1} b_{1}, both in T_{1,a}. Since P_{1} is weakly κ-scattered, T_{1,a} ∩]b_{0}, b_{1}[_{P1} is not κ-saturated. Thus, there are B_{0}, B_{1} ⊆ T_{1,a} ∩]b_{0}, b_{1}[_{P1} such that |B_{0}|, |B_{1}| < κ and B_{0} <_{P1} B_{1}, and there is no c ∈ T_{1,a} such that B_{0} <_{P1} c <_{P1} B_{1}. For i < 2, let A_{i} = {⟨a, b⟩ : b ∈ {b_{i}} ∪ B_{i}}. As in Case 1, A_{0} and A_{1} contradict the assumption that C is κ-saturated. □

Lemma 3.4. Suppose that β < κ and, for all α < β, φ_{α} is weakly κ-scattered. Then ∏_{α<β} φ_{α} is weakly κ-scattered.

Proof. The proof is by induction on β. For β ∈ {0, 1}, the Lemma is trivial. For the successor step of the induction, simply apply the induction hypothesis and Lemma 3.3. Thus, assume γ < κ is a limit ordinal, φ_{α} is a weakly κ-scattered linear order type for all α < γ and, for all β < γ, ∏_{α<β} φ_{α} is weakly κ-scattered. For all α < γ, let ⟨P_{α}, <_{α}⟩ be an ordered set of type φ_{α}. For notational simplicity, for β ⩽ γ, let T_{β} =×_{α<β} P_{α}. Suppose for sake of contradiction that R ⊆ T_{γ} is κ-saturated. For f ∈ R, let

D^{+}(f) :={α < γ : ∃g ∈ R(Δ(f, g) = α ∧ f <_{R} g)};
D^{−}(f) :={α < γ : ∃g ∈ R(Δ(f, g) = α ∧ g <_{R} f)}.

There are now three cases to consider.

Case 1: there is f ∈ R such that D^{+}(f) is unbounded in γ. For α ∈ D^{+}(f), fix a g_{α} ∈ R such that Δ(f, g_{α}) = α and f <_{R} g. Let A = {f} and B = {g_{α} : α ∈ D^{+}(f)}. Then A, B ⊆ R, |A|, |B| < κ, A <_{R} B, and there is no h ∈ R such that A <_{R} h <_{R} B, contradicting the assumption that R is κ-saturated.

Case 2: there is f ∈ R such that D^{−}(f) is unbounded in γ. This is symmetric to Case 1.

Case 3: for all f ∈ R, there is β < γ such that D^{+}(f) ∪ D^{−}(f) ⊆ β. For all f ∈ R, choose β_{f} such that D^{+}(f) ∪ D^{−}(f) ⊆ β_{f}. By Corollary 2.5, there is β < γ and a κ-saturated S ⊆ R such that, for all f ∈ S, β_{f} = β. Then, for all f, g ∈ S, Δ(f, g) < β. In particular, f ↾ β ≠ g ↾ β. Let S_{β} = {f ↾ β : f ∈ S}. Then S_{β} is a κ-saturated suborder of T_{β}, contradicting the inductive hypothesis that T_{β} is weakly κ-scattered. □

We are now ready to prove the main result of this section.

Proof of Theorem 3.1. For n < ω, we will find a weakly κ-scattered order of size κ, τ_{n}, such that τ_{n} ⟶ (φ, n)^{2}. Then τ = ∑_{n<ω} τ_{n} will be as desired.

We proceed by induction on n < ω. For n ∈ {0, 1, 2}, we may simply set τ_{n} = φ. Suppose 2 ⩽ n < ω and τ_{n} has been found. Suppose first that κ is a successor cardinal, say κ = ν^{+}. In this case, let τ_{n+1} = ^{ν}τ_{n}. If, on the other hand, κ is a limit ordinal, let τ_{n+1} = ∑_{ν<κ}^{ν}τ_{n}, where the sum is over all cardinals ν < κ. In either case, by Lemma 3.4, τ_{n+1} is weakly κ-saturated. Also, by Lemma 3.2, for all ν < κ, τ_{n+1} ⟶ (τ_{n})_{ν}^{1}. Therefore, by Lemma 2.8, τ_{n+1} ⟶ (φ, n + 1)^{2}. □

Remark 3.5. Note that, for the case κ = ν^{+}, for 2 ⩽ n < ω, the value for τ_{n} obtained in the above proof is νn−2φ. In particular, we can take τ to be ^{νω}φ.

16 CHRIS LAMBIE-HANSON AND THILO WEINERT

4. A negative partition relation from a small unbounding number and the stick-principle

We define:

|•(κ) := min {|X| : X ⊆ [κ^{+}]^{κ} ∧ ∀y ∈ [κ^{+}]^{κ+}∃x ∈ X (x ⊆ y)}. (1)

Remark 4.1. |•(κ) is called |•(κ, κ^{+}) by Brendle in [006BiP], generalising |•, which was introduced by Fuchino, Shelah and Soukup in [997F] and corresponds to our notion of |•(ℵ_{0}). Fuchino, Shelah and Soukup had in turn generalised the stick principle |• which can in hindsight be read as a shorthand for |• = ℵ_{1}. The stick principle was introduced by Broverman, Ginsburg, Kunen & Tall in [978B, page 1311]. |•(κ) as defined here should not be confused with |•_{λ} as defined in [997F] or |•_{δ} as defined in [XXXCh].

For an infinite cardinal κ, we let 𝔟_{κ} and 𝔡_{κ} denote, respectively, the unbounding number and the dominating number at κ as they are defined by Cummings and Shelah in [995CS]. Here, 𝔟 and 𝔡 are shorthands for 𝔟_{ℵ0} and 𝔡_{ℵ0}, respectively.

In [971EH, Corollary 1, implicitly], ω_{1}ω−̸→(ω_{1}ω, 3)^{2} is shown to follow from the Continuum Hypothesis. In [987Ta], Takahashi shows that the same consequence follows already from 𝔡 = |• = ℵ_{1}. In [998La], the hypothesis 𝔡 = |• = ℵ_{1} is weakened further and the result is generalised by Jean Larson, who shows that, for a regular cardinal κ, the hypothesis 𝔡_{κ} = κ^{+} implies κ^{+}κ−̸→(κ^{+}κ, 3)^{2} . We provide here an improvement in a different direction.

Theorem 4.2. Suppose that κ is regular and λ = κ^{+} = 𝔟_{κ} = |•(κ). Then λκ−̸→(λκ, 3)^{2}.

Proof. Assume towards a contradiction that the statement of the Theorem were wrong, i.e. that 𝔟_{κ} = |•(κ) = λ and λκ ⟶ (λκ, 3)^{2}. Let |•(κ) = λ be witnessed by a family D = {d(ρ) : ρ ∈ λ \ κ} ⊆ [λ]^{κ}, and let 𝔟_{κ} = λ be witnessed by a family U = {u_{ρ} : ρ < λ} of increasing sequences of ordinals below κ having the property that for all {ξ, ρ}_{<} ∈ [λ]^{2} the set {ι < κ : u_{ξ}(ι) ⩾ u_{ρ}(ι)} has cardinality less than κ. We may also assume for notational convenience that d(ρ) ⊆ ρ for all ρ ∈ λ \ κ. Finally, let ⟨g_{γ} : κ ⩽ γ < λ⟩ be a sequence of bijections g_{γ} : κ ⟷ γ. We are now going to define a graph E ⊆ [λκ]^{2} by transfinite induction on the set of ordinals less than λ. We are going to have E = ⋃_{ρ<λ} E_{ρ}. In step ρ we will define E_{ρ} := E ∩ [{λν + ξ : ξ < ρ ∧ ν < κ}]^{2}. The following is going to hold in every step ρ of the induction:

∀ξ < ρ∀ι, ν < κ(|{ϑ < ξ | {λι + ϑ, λν + ξ} ∈ E}| < κ∧ (2)

∀ϑ < ξ({λι + ξ, λν + ϑ} ∈ E ⇒ ι < ν))

Let E_{0} be the empty set. For positive limit ordinals ρ < λ, define E_{ρ} := ⋃_{ξ<ρ} E_{ξ}, and for all ordinals ρ < λ let E_{ρ+1} := E_{ρ} ∪ D_{ρ}, where D_{ρ} is constructed as follows.

We inductively define a sequence ⟨C_{κρ+ι} : ι < κ⟩ of sets C_{κρ+ι} ∈ [ρ]^{<κ} as follows: Let ζ be a ordinal less than κ and suppose that C_{ξ} has been defined for all ξ < κρ + ζ. We now define C_{κρ+ζ} by letting

C_{κρ+ζ} := { min (d(g_{gρ(ι)}(μ)) \ ⋃ ; ϑ∈⋃ν<ζ Cκρ+ν C_{κϑ+ζ}) | ι < ζ ∧ μ < u_{ρ}(ζ)} (3)

Finally we set D_{ρ} := {{λι + ρ, λν + ξ} | {ι, ν} ⊆ κ ∧ ι < ν ∧ ξ ∈ C_{κρ+ν}}. This completes the construction of E.

Now suppose that T = {λι + ρ, λν + ξ, λμ + ϑ} ∈ [λκ]^{3}. If [T]^{2} ⊆ E then w.l.o.g. ι < ν < μ and ϑ < ξ < ρ. Then ξ ∈ C_{κρ+ν} while ϑ ∈ C_{κξ+μ} ∩ C_{κρ+μ}, contradicting ν < μ in conjunction with (3). So by λκ ⟶ (λκ, 3)^{2} there must be an X ∈ [λκ]^{λκ} such that [X]^{2} ⊆ [λκ]^{2} \ E. Let A := {ι < κ | |{ξ < λ : λι + ξ ∈ X}| = λ} and ν := min(A). Furthermore, for all ι ∈ A, let γ_{ι} ∈ λ \ κ be such that λι + ϑ ∈ X for all ϑ ∈ d(γ_{ι}). Set ξ := sup_{ι<κ} γ_{ι} and define a sequence of natural numbers ⟨σ_{ι} : ι < κ⟩ by setting σ_{ι} := min(A \ ι). We are going

18 CHRIS LAMBIE-HANSON AND THILO WEINERT

to define a function f from κ into itself:

(4)  f : κ ⟶ κ,
ι ⟼ max (σ_{ι}, g_{ξ}^{−1}(γ_{σι})).

Now let ρ ∈ λ \ ξ be such that λν + ρ ∈ X and u_{ρ} is unbounded over f. Set ι := g_{ρ}^{−1}(ξ) and let τ ∈ κ\(1+max(ι, ν)) be such that u_{ρ}(τ) > f(τ). Let ζ = σ_{τ}. By definition of f, we have ζ < u_{ρ}(τ). Now consider (3) with μ := g_{ξ}^{−1}(γ_{ζ}). We have ι < τ ⩽ ζ = σ_{τ} ∈ A, and hence

μ = g_{ξ}^{−1}(γ_{ζ}) ⩽ max (ζ, g_{ξ}^{−1}(γ_{ζ})) = max (σ_{τ} , g_{ξ}^{−1}(γ_{στ})) = f(τ) < u_{ρ}(τ) < u_{ρ}(ζ). (5)

Finally we have g_{ρ}(ι) = ξ and A ∋ ν < τ ⩽ ζ ∈ A. Then there is a ϑ ∈ d(g_{gρ(ι)}(μ)) = d(γ_{ζ}) with ϑ ∈ C_{κρ+ζ} so we get that {λν + ρ, λζ + ϑ} ∈ D_{ρ} ⊆ E_{ρ+1} ⊆ E, contradicting the assumption that [X]^{2} ⊆ [λκ]^{2} \ E. □

Observe that if n is a natural number, ι and ξ are ordinals, μ is a cardinal, α ∈ μ^{+} \ μ and E is an (n + 1)- hypergraph on ιμ which witnesses ιμ−̸→(ιμ, ξ)^{n}, then for any bijection f : α ↔ μ witnessing α < μ^{+} the n-hypergraph

{{ιγ_{0} + δ_{0}, …, ιγ_{n} + δ_{n}} | {ιγ_{k} + f(δ_{k}) : k ⩽ n} ∈ E}

witnesses ια−̸→(ια, ξ)^{n}. We therefore obtain the following corollary.

Corollary 4.3. If κ is regular and λ = κ^{+} = 𝔟_{κ} = |•(κ), then α−̸→(λκ, 3)^{2} for all α < λ^{2}.

In an upcoming paper of William Chen, Shimon Garti and the second author the same hypothesis is shown to imply λ^{2}−̸→(λκ, 4)^{2} as well.

Recall that ♣, introduced in [976Os], implies |• = ℵ_{1}. To see that this is the case, consider a sequence witessing the truth of ♣. Its range then witnesses the truth of |•. In [997F], Fuchino, Shelah and Soukup show that ♣ is consistent with cov(M) = 2^{ℵ0} = ℵ_{2}. Brendle [017Br] points out that in their model the unbounding number is small as well. As cov(M) ⩽ 𝔡, we have

ZFC +“ℵ_{1} = |• = 𝔟 < 𝔡 = ℵ_{2}” is consistent,

which shows that our result does in fact provide information not given by Larson’s result.

Brendle proves in [006Br] that ♣ is consistent with cov(N) = ℵ_{2}. In the same paper in a footnote on page 45 he also gives a sketch of how to extract a proof of the consistency of ♣ with add(M) = ℵ_{2} from [999DS]. Before all this, Truss, in [983Tr], shows limitations to these pursuits by proving—in effect—that if |• = ℵ_{1}, then min ( cov(M), cov(N)) = ℵ_{1}.

5. Scattered linear orders

In this section, we deal with κ-scattered linear orders for infinite, regular cardinals κ. We first prove a generalisation of the Milner-Rado paradox [965MR] to the class of κ-scattered linear orders of size κ. We call to your attention the classical statement of the paradox.

Paradox 5.1 ([965MR, Theorem 5]). Suppose κ is an infinite cardinal and α < κ^{+}. Then α can be written as ⋃_{n<ω} X_{n} where, for all n < ω, otp(X_{n}) < κ^{n+1}.

A related statement can be found in a paper by Komjáth and Shelah:

Lemma 5.2 ([003KS, Lemma 1]). Suppose φ is a scattered order type and S is a linear order of type φ. Then there is f : S → ω such that, for all n < ω, f^{−1}(n) has no subset of order type (ω^{∗}+ω)^{n}. Therefore, φ−̸→(ψ)_{ℵ0}^{1} where ψ = ∑_{n<ω}(ω^{∗} + ω)^{n}.

Fix infinite cardinals κ and μ such that cof(μ) ⩾ κ. Let B_{κ,μ} be the class of linear order types φ such that either |φ| < κ or φ is a well-order or anti-well-order of size ⩽ μ. The following structure theorem for κ-scattered linear orders of size at most μ follows from Theorem 1.4.

Theorem 5.3 ([012A^{&}, Corollary 3.11]). The class of κ-scattered linear orders of size at most μ is the smallest class of orders containing B_{κ,μ} which is closed under lexicographic sums with index set in B_{κ,μ}.

The following Lemma has a straightforward proof and can be found, for example, in [014LH, Lemma 5].

Lemma 5.4. Suppose κ is an infinite cardinal, ν < cof(κ), and m < ω. Suppose that, for each ζ < ν, X_{ζ} is a set of ordinals such that otp(X_{ζ}) < κ^{m}. Let X = ⋃_{ζ<ν} X_{ζ}. Then otp(X) < κ^{m}.

A close relative is the following Lemma.

Lemma 5.5. Suppose α is an indecomposable ordinal, ν < cof(α), and m < ω. Suppose that X is an ordered set, X = ⋃_{ζ<ν} X_{ζ}, and, for each ζ < ν, otp(X_{ζ}) ⩾̸ (αα^{∗})^{m}. Then otp(X) ⩾̸ (αα^{∗})^{m}.

Proof. Suppose towards a contradiction that the Lemma were false, and let m be the largest natural number for which it holds. So otp(X) ⩾ (αα^{∗})^{1+m}. Let Y be a set of order type αα^{∗} and let f : ^{1+m}Y ⟶ X be an embedding preserving the lexicographic ordering on ^{1+m}Y. For y ∈ Y, define

Z_{y} := {x ∈ X : ∃y⃗ ∈ ^{m}Y (f(y, y⃗) ⩽ x) ∧ ∃y⃗ ∈ ^{m}Y (x ⩽ f(y, y⃗))}, (6)

and let Z_{y,ζ} := Z_{y} ∩ X_{ζ}.

Note that for any y, z ∈ Y with y < z and any x_{0} ∈ Z_{y} and x_{1} ∈ Z_{z} we have x_{0} < x_{1}. Clearly, for every y ∈ Y we have Z_{y} = ⋃_{ζ<ν} Z_{y,ζ}, and f ↾ ({y} ×^{m}Y) yields an order-preserving embedding of ^{m}Y into Z_{y}. Now we may use the inductive hypothesis and conclude that for every y ∈ Y there is a ζ_{y} < ν and an order-preserving embedding f_{y} : ^{m}Y ⟶ Z_{y,ζy}. Considering both the indecomposability and the cofinality of α twice, we conclude that there is an A ∈ [Y]^{αα∗} and a ζ < ν such that ζ_{a} = ζ for all a ∈ A. Then the function

(7)  g : A ×^{m}Y ⟶ X
⟨a, y⃗⟩ ⟼ f_{a}(y⃗)

is an order-preserving embedding of a set of order type (αα^{∗})^{1+m} into X_{ζ}, a contradiction. □

An easy variation yields the fact that Lemma 5.5 remains true if all instances of αα^{∗} are replaced by α^{∗}α. We are now ready to state and prove our generalisation of Theorem 5.1.

Theorem 5.6. Let κ, μ be infinite regular cardinals such that κ ⩽ μ, and suppose φ is a ⟨κ, max(ℵ_{1}, κ)⟩- scattered linear order type of size at most μ. Then every order P of type φ can be written as a union P = ⋃_{n<ω} P_{n} such that there is no n < ω for which P_{n} has a suborder of type μ^{n}, (μ^{n})^{∗}, (κκ^{∗})^{n}, or (κ^{∗}κ)^{n}.

Proof. We first prove the theorem assuming φ is a κ-scattered linear order type of size at most μ. We proceed by induction on the complexity of φ. If φ ∈ B_{κ,μ}, then the statement of the theorem is either trivial (if |φ| < κ) or is trivially implied by the Milner-Rado paradox (if φ is a well-order or anti-well-order). It thus suffices to prove that, if φ = ∑_{a∈τ} ρ_{a}, where τ and ρ_{a} satisfy the statement of the theorem for all a ∈ τ, then φ satisfies the statement of the theorem. Fix such a φ.

Let T be an order of type τ, and, for a ∈ T, let R_{a} be an order of type ρ_{a}. Let P = {⟨a, b⟩ : a ∈ T ∧ b ∈ R_{a}} be equipped with the lexicographic order, and note that otp(P) = φ. Fix f : T → ω such that, for all n < ω, f^{−1}(n) does not contain a suborder of type μ^{n}, (μ^{n})^{∗}, (κκ^{∗})^{n}, or (κ^{∗}κ)^{n}. Similarly, for all a ∈ T, fix f_{a} : R_{a} → ω such that, for all n < ω, f_{a}^{−1}(n) does not contain a suborder of type μ^{n}, (μ^{n})^{∗}, (κκ^{∗})^{n}, or (κ^{∗}κ)^{n}. Fix an injective function π : ω × ω → ω such that, for all m, n < ω, π(m, n) ⩾ m + n + 1. Define g : P → ω by letting, for a ∈ T and b ∈ R_{a}, g(a, b) = π(f(a), f_{a}(b)). We claim that, for all i < ω, g^{−1}(i) does not contain a suborder of type μ^{i}, (μ^{i})^{∗}, (κκ^{∗})^{i}, or (κ^{∗}κ)^{i}.

Suppose for sake of contradiction that there is an i < ω such that g^{−1}(i) contains a suborder of type μ^{i}. There must be m, n < ω such that π(m, n) = i, as g^{−1}(i) is empty for all other values of i. Let P′ ⊆ g^{−1}(i) have type μ^{i}, and let T′ = {a ∈ T : ∃b ∈ R_{a}(⟨a, b⟩ ∈ P′)}. T′ is then a well-ordered subset of f^{−1}(m), so otp(T′) < μ^{m}. For each a ∈ T′, let R′_{a} = {b ∈ R_{a} : ⟨a, b⟩ ∈ P′}. R′_{a} is a well-ordered subset of f_{a}^{−1}(n), so otp(R′_{a}) < μ^{n}. Moreover, P′ = ∑_{a∈T ′} R′_{a}, so otp(P′) < (μ^{n}) · (μ^{m}) = μ^{m+n} < μ^{i}. Contradiction.

The argument for (μ^{i})^{∗} is similar.

Now suppose that there is an i < ω such that g^{−1}(i) contains a suborder of type (κκ^{∗})^{i}. Again there are natural numbers m and n such that π(m, n) = i. Let P′ ⊆ g^{−1}(i) have type (κκ^{∗})^{i}. As before, we may define T′ := {a ∈ T : ∃b ∈ R_{a}(⟨a, b⟩ ∈ P′}) and, for each a ∈ T′, R′_{a} := {b ∈ R_{a} : ⟨a, b⟩ ∈ P′}. We then have T′ ⩾̸ (κκ^{∗})^{m} and otp(R′_{a}) ⩾̸ (κκ^{∗})^{n}. Now let Q be a linear order of type (κκ^{∗})^{i−n} and, for all q ∈ Q, let P_{q} ⊆ P′ be a suborder of type (κκ^{∗})^{n} such that, for all p < q in Q, P_{p} < P_{q}. Consider the function f : Q ⟶ POW(T′) given by q ⟼ {a ∈ T′ : ∃b ∈ R_{a}(⟨a, b⟩ ∈ P_{q})}. Clearly, for every q ∈ Q, the set f(Q) is an interval in T′. Moreover for any p, q, r ∈ Q with p < q < r we have f(p) ∩ f(r) = ∅, as f(p) ∩ f(r) ⊆ f(q) and (κκ^{∗})^{n} ⩽̸ otp(R′_{a}) for every a ∈ f(p)∩f(q)∩f(r). Consider a partition {Q_{0}, Q_{1}} of Q having the property that for both i < 2 and p, q ∈ Q_{i} with p < q there is always an r ∈ ]p, q[_{<Q} ∩ Q_{1−i}. Let c be a choice function for f[Q_{0}]. Then otp(Q_{0}) = (κκ^{∗})^{i−n} ⩾ (κκ^{∗})^{m} and c ∘ f is an embedding of Q_{0} into T′. Contradiction.

The argument for (κ^{∗}κ)^{i} is similar.

This finishes the proof for the special case of κ-scattered linear orders of cardinality at most μ. Now we continue the proof to prove the general case stated above.

Fix a ⟨κ, max(ℵ_{1}, κ)⟩-scattered linear order type φ of size at most μ. Let P be an order of type φ, let ν < max(ℵ_{1}, κ) be a cardinal, and, for each ζ < ν, let P_{ζ} be a κ-scattered suborder of P such that P = ⋃_{ζ<ν} P_{ζ}. Without loss of generality, we may assume that the P_{ζ}’s are pairwise disjoint. For each ζ < ν, let f_{ζ} : P_{ζ} → ω be such that, for all n < ω, f_{ζ}^{−1}(n) does not contain a suborder of type μ^{n}, (μ^{n})^{∗}, (κκ^{∗})^{n}, or (κ^{∗}κ)^{n}.

Now we distinguish two non-exclusive cases which cover the issue at hand:

First, assume that κ is uncountable. For each n < ω, let f^{−1}(n) := ⋃_{ζ<ν} f_{ζ}^{−1}(n). Then ν < κ so, by Lemmas 5.4 and 5.5, for all n < ω, f^{−1}(n) does not contain a suborder of type μ^{n}, (μ^{n})^{∗}, (κκ^{∗})^{n}, or (κ^{∗}κ)^{n}.

Now assume that κ < ℵ_{2}. Then ν ⩽ ℵ_{0}. Let ι : ω × ν ⟶ ω be an injection such that for all m < ω and n < ν one has ι(m, n) ⩾ m. For each a ∈ P, let ζ_{a} be the unique ζ < ν such that a ∈ P_{ζ}, and let f(a) := ι(f_{ζa}(a), ζ_{a}). Clearly, for all n < ω, f^{−1}(n) does not contain a suborder of type μ^{n}, (μ^{n})^{∗}, (κκ^{∗})^{n}, or (κ^{∗}κ)^{n}. □

For κ = ℵ_{0} and μ = ℵ_{1} this yields the following corollary.

Corollary 5.7. Suppose φ is a σ-scattered linear order type of size at most ℵ_{1}. Then every order P of type φ can be written as a union P = ⋃_{n<ω} P_{n} such that there is no n < ω for which P_{n} has a suborder of type ω_{1}^{n}, (ω_{1}^{n})^{∗}, (ωω^{∗})^{n}, or (ω^{∗}ω)^{n}.

We can now complete the proof of Corollary 2.7.

Proposition 5.8. Suppose κ is a regular, uncountable cardinal. Then there is a linear order of size κ that is weakly κ-scattered but not ⟨κ, κ⟩-scattered.

Proof. Suppose first that κ^{ℵ0} = κ. Let δ = κ^{ω} (ordinal exponentiation), and let φ = ^{ω}δ. Since κ^{ℵ0} = κ, |φ| = κ. By Lemma 3.4, φ is weakly κ-scattered. By Lemma 3.2, φ ⟶ (κ^{ω})_{ℵ0}^{1}. Therefore, by Theorem 5.6, φ is not ⟨κ, κ⟩-scattered.

Next, suppose that κ^{ℵ0} > κ. Then there is a regular μ < κ such that μ^{ℵ0} > κ. Let P be a suborder of ^{ω}μ of size κ. By Lemma 3.4, P is weakly κ-scattered. Also, ^{ω}μ has a dense suborder of size μ, namely the set of f ∈ ^{ω}μ such that f(n) = 0 for all but finitely many n < ω. Thus, P does not contain a suborder of type κ or κ^{∗}. Suppose for sake of contradiction that P = ⋃_{ζ<ν} P_{ζ}, where ν < κ and P_{ζ} is κ-scattered for all ζ < ν. Since |P | = κ, there is ζ < ν such that |P_{ζ}| = κ. But Theorem 5.3 implies that every κ-scattered linear order of size κ contains either a suborder of type κ or a suborder of type κ^{∗}, which is a contradiction. □

We next use Theorem 5.6 to give a negative partition relation for ⟨ℵ_{1}, ℵ_{1}⟩-scattered linear order types of size at most ℵ_{1}, assuming ω_{1}ω−̸→(ω_{1}ω, 3)^{2}.

Theorem 5.9. Assume that ω_{1}ω−̸→(ω_{1}ω, 3)^{2}, and let τ be an ⟨ℵ_{1}, ℵ_{1}⟩-scattered linear order type of size at most ℵ_{1}. Then τ−̸→(ω_{1}^{ω} ∨ (ω_{1}^{ω})^{∗}, 3)^{2}.

Proof. Let T be a linear order of type τ, and use Theorem 5.6 to write T as a union T = ⋃_{n<ω} T_{n} such that, for all n < ω, ω_{1}^{ω}, (ω_{1}^{ω})^{∗} ⩽̸ otp(T_{n}). Then use ω_{1}ω−̸→(ω_{1}ω, 3)^{2} to find E ⊆ [T]^{2} such that [X]^{2} ⊈ E for all X ∈ [T]^{3} and [Y]^{2} ⊈ [T]^{2} \ E for all Y ⊆ τ such that |{n < ω : |Y ∩ T_{n}| = ℵ_{1}}| = ℵ_{0}. It is easily verified that the function f : [T]^{2} → 2 defined by f(a, b) = 0 iff {a, b} ∉ E witnesses the negative partition relation. □

Since ω_{1}^{ω} and (ω_{1}^{ω})^{∗} are themselves scattered, and therefore ℵ_{1}-scattered, order types of size ℵ_{1}, Theorem 5.9, when compared with Theorem 3.1, provides an instance in which the classes of ℵ_{1}-scattered or ⟨ℵ_{1}, ℵ_{1}⟩-scattered linear orders behave quite differently from the class of weakly ℵ_{1}-scattered linear orders. By examining the proof of Theorem 5.9, it is evident that ℵ_{1} can be replaced by an arbitrary regular, uncountable κ provided that κω−̸→(κω, 3)^{2}. This hypothesis does not always hold. In [987SS], Shelah and Stanley prove that, if κ > ω is regular and, for all μ < κ, μ^{ℵ0} < κ, then κω ⟶ (κω, n)^{2} for all n < ω. However, in the same paper, they show that, if κ > ℵ_{1} is regular, then there is a ccc forcing extension in which κω−̸→(κω, 3)^{2}. We thus easily obtain the following corollary.

Corollary 5.10. Suppose that κ > ℵ_{1} is regular. Then there is a ccc forcing extension in which there is a κ-scattered linear order type φ of size κ such that, for all ⟨κ, κ⟩-scattered linear order types τ of size κ, τ−̸→(φ, 3)^{2}.

We are also able to prove a slightly recondite theorem which, assuming ω_{1}ω−̸→(ω_{1}ω, 3)^{2}, provides a stark contrast to Theorem 2.9 for κ = ℵ_{0}. It is strongly inspired by [971EH, §2, Corollary 2] and features six different order types φ of size ℵ_{1} such that either φ or φ^{∗} has one of the following three characteristics of smallness:

(1) It is well-ordered.

(2) It is both scattered and the product of ω_{1} with a countable order-type.

(3) Every proper initial segment is countable.

In (2), note that the multiplication of order types fails to be commutative in general. Also note that the sole order types satisfying any two of the above conditions are ordinals smaller than ω_{1}^{2}.

Theorem 5.11. Assume ω_{1}ω−̸→(ω_{1}ω, 3)^{2}, let τ be a σ-scattered linear order type of size at most ℵ_{1}, and let ρ be an order type such that (ωω^{∗})^{n} ⩽ ρ for all natural numbers n. Then

τ−̸→(ω_{1}^{ω} ∨ (ω_{1}^{ω})^{∗} ∨ ω_{1}ρ ∨ ω_{1}^{∗}ρ ∨ ρω_{1} ∨ ρω_{1}^{∗}, 3)^{2}.

Proof. The first part of the proof follows the line of the proof of Theorem 5.9.

Let T be an order of type τ, and use Corollary 5.7 to write T as a union T = ⋃_{n<ω} T_{n} such that, for all n < ω, T_{n} does not contain a suborder of type ω_{1}^{ω}, (ω_{1}^{ω})^{∗}, or (ωω^{∗})^{n}. Use ω_{1}ω−̸→(ω_{1}ω, 3)^{2} to find E ⊆ [T]^{2} such that [X]^{2} ⊈ E for all X ∈ [T]^{3} and [Y]^{2} ⊈ [T]^{2}\E for all Y ⊆ T such that |{n < ω : |Y ∩ T_{n}| = ℵ_{1}}| = ℵ_{0}. Define c : [T]^{2} → 2 by c(a, b) = 0 iff {a, b} ∉ E. We show that c witnesses the negative partition relation, i.e. that, for every suborder Y of T whose order type appears in the first coordinate of the partition relation, [Y]^{2} ∩ E ≠ ∅. For Y ∈ [T]^{ωω 1} ∪ [T]^{(ωω 1)∗}, this follows as in the proof of Theorem 5.9.

Now let ρ be an order-type such that (ωω^{∗})^{n} ⩽ ρ for all natural numbers n and let R be an order of type ρ. First assume that Y ∈ [T]^{ω1ρ}. Let f : ⟨R × ω_{1}, <_{lex}⟩ ⟷ Y be order-preserving. By the pigeonhole principle we may assume w.l.o.g. that for all r ∈ R there is an n < ω such that f[{r} × ω_{1}] ⊆ T_{n}. Since, for all n < ω, (ωω^{∗})^{n} ⩽ ρ and (ωω^{∗})^{n} ⩽̸ otp(⋃_{k<n} T_{k}), it follows that for all natural numbers n there is an r ∈ R and a k ∈ ]n, ω[_{<} such that f[{r} × ω_{1}] ⊆ T_{k}. This easily implies that [Y]^{2} ∩ E ≠ ∅.

Next, assume that Y ∈ [T]^{ρω1}. Let f : ⟨ω_{1} × R, <_{lex}⟩ ⟷ Y be order-preserving. We distinguish two cases: First assume that there are α < ω_{1} and n < ω such that (ωω^{∗})^{n} ⩽ otp{r ∈ R : f(α, r) ∈ ⋃_{k<n} T_{k}}. But

then (ωω^{∗})^{n} ⩽ otp(⋃_{k<n} T_{k}) and so by Lemma 5.5 there is a k < n with (ωω^{∗})^{n} ⩽ otp(T_{k}), a contradiction. Next, assume that for all α < ω_{1} and n < ω we have

(ωω^{∗})^{n} ⩽̸ otp{r ∈ R : f(α, r) ∈ ⋃_{k<n} T_{k}}.

This means that, in particular, f[{α} × R] ⊈ ⋃_{k<n} T_{k}. Using the pigeonhole principle, let X_{0} ∈ [ω_{1}]^{ω1}, r_{0} ∈ R, and n_{0} < ω be such that f(α, r_{0}) ∈ T_{n0} for all α ∈ X_{0}. Now, inductively, for every k < ω, choose X_{k+1} ∈ [X_{k}]^{ω1}, r_{k+1} ∈ R, and n_{k+1} ∈ ]n_{k}, ω[_{<} such that f(α, r_{k+1}) ∈ T_{nk+1} for all α ∈ X_{k+1}.

At the end of the inductive construction let Z := {f(α, r_{i}) : i < ω ∧ α ∈ X_{i}}. Then Z ⊆ Y and, clearly, |{n < ω : |Z ∩ T_{n}| = ℵ_{1}}| = ℵ_{0}, so E ∩ [Y]^{2} ≠ ∅.

The arguments for sets of order-type ρω_{1}^{∗} and ω_{1}^{∗}ρ are analogous, so this finishes the proof of the Theorem. □

Corollary 4.3 yields the following (cf. Remark 1.7):

Corollary 5.12. Assume ω_{1}ω−̸→(ω_{1}ω, 3)^{2}, and let τ be a σ-scattered linear order type of size at most ℵ_{1}. Then

τ−̸→(ω_{1}^{ω} ∨ (ω_{1}^{ω})^{∗} ∨ ω_{1}(ωω^{∗})^{ω} ∨ ω_{1}^{∗}(ωω^{∗})^{ω} ∨ (ωω^{∗})^{ω}ω_{1} ∨ (ωω^{∗})^{ω}ω_{1}^{∗}, 3)^{2}. (8)

6. Generalizing a result of Komjáth and Shelah

In this section, we generalise the following result of Komjáth and Shelah from [003KS] about partitioning scattered linear orders.

Theorem 6.1. If φ is a scattered linear order and ν is a cardinal, then there is a scattered linear order ψ such that ψ ⟶ [φ]_{ν,ℵ0}^{1}.

We will prove the following generalisation.

Theorem 6.2. Suppose κ is a cardinal such that κ^{<κ} = κ, φ is a κ-scattered linear order type, and ν is a cardinal. Then there is a κ-scattered linear order type ψ such that ψ ⟶ [φ]_{ν,κ}^{1}.

The proof of Theorem 6.2 is a modification of Komjáth and Shelah’s proof from [003KS]. We will state without proof the main technical lemma from [003KS] but will provide the rest of the details for completeness.

Suppose β is an ordinal, ⟨P_{α} | α < β⟩ is a sequence of linear orders and, for all α < β, we have specified a designated element 0_{α} ∈ P_{α}. Then ⨁′_{α<β} P_{α} is a linear order whose underlying set is the set of functions f such that:

• dom(f) = β;

• for all α < β, f(α) ∈ P_{α};

• for all but finitely many α < β, f(α) = 0_{α}. If f ∈ ⨁′_{α<β} P_{α}, then supp(f) is the set of α < β such that f(α) ≠ 0_{α}. ⨁′_{α<β} P_{α} is ordered antilexicographically. Namely, if f, g ∈ ⨁′_{α<β} P_{α}, let Δ′(f, g) denote the largest α < β such that f(α) ≠ g(α), and let f <_{⨁{′ \atop α<β} Pα} g iff f(α) <_{Pα} g(α). As usual, if there is P such that P_{α} = P for all α < β, we write

⨁′_{α<β} P in place of ⨁′_{α<β} P_{α}.

Lemma 6.3. Let β be an ordinal and, for α < β, let P_{α} be a linear order. Let Q = ⨁′_{α<β} P_{α}. Suppose f, g, h ∈ Q are such that f <_{Q} g <_{Q} h. Then max(Δ′(f, g), Δ′(g, h)) ⩽ Δ′(f, h).

Proof. Let α = Δ′(f, h). Suppose for sake of contradiction that γ = Δ′(f, g) > α. Then f(γ) <_{Pγ} g(γ), and, since f(γ) = h(γ), we also have h(γ) <_{Pγ} g(γ). Since g <_{Q} h, we must have ξ = Δ′(g, h) > γ. Then g(ξ) <_{Pξ} h(ξ) = f(ξ), contradicting the fact that ξ > γ and Δ′(f, g) = γ. Thus, Δ′(f, g) ⩽ α. Δ′(g, h) ⩽ α follows similarly. □

Lemma 6.4. Suppose β is an ordinal, κ is a regular cardinal, and, for all α < β, P_{α} is a κ-scattered linear order. Let Q = ⨁′_{α<β} P_{α}. Then Q is κ-scattered.

Proof. Suppose for sake of contradiction that R is a κ-dense suborder of Q. Let α < β be least such that, for some f, g ∈ R, Δ′(f, g) = α, and fix such f, g ∈ R. As R is κ-dense, ]f, g[_{R} itself must be κ-dense as a suborder of R. By the minimality of α and Lemma 6.3, for all h_{0} <_{R} h_{1} in ]f, g[_{R}, we must have Δ′(h_{0}, h_{1}) = α and hence h_{0}(α) <_{Pα} h_{1}(α). But this implies that {h(α) | h ∈ R} is a κ-dense suborder of P_{α}, contradicting the assumption that P_{α} is κ-scattered. □

We now need some definitions and a lemma from [003KS].

Definition 6.5. Suppose α is an ordinal. FS(α) is the set of all finite decreasing sequences from α, i.e. sequences of the form s⃗ = ⟨s_{0}, s_{1}, …, s_{n−1}⟩ such that α > s_{0} > s_{1} > … > s_{n−1}. For such an s⃗ of length n, min(s⃗) will denote s_{n−1}. An α-tree is a function x : FS(α) → On such that, for all s⃗ ∈ FS(α) and all γ_{0} < γ_{1} < min(s⃗), we have x(s⃗ ^{⌢}⟨γ_{0}⟩) < x(s⃗ ^{⌢}⟨γ_{1}⟩) < x(s⃗).

Lemma 6.6. Suppose α is an ordinal and ν is a cardinal. Let μ = (|α|^{νℵ0})^{+}, and suppose that F : FS(μ^{+}) → ν. Then there is an α-tree x : FS(α) → μ^{+} and a function c : ω → ν such that, for every n < ω and every ⟨s_{0}, s_{1}, …, s_{n}⟩ in FS(α) of length n + 1, we have F (x(⟨s_{0}⟩), x(⟨s_{0}, s_{1}⟩), …, x(⟨s_{0}, s_{1}, …, s_{n}⟩)) = c(n).

A proof of Lemma 6.6 can be found in [003KS].

Fix now a cardinal κ such that κ^{<κ} = κ. We next identify a class of κ-scattered linear orders such that every κ-scattered linear order embeds into a member of the class. First, let T be a set of linear orders such that, for every linear order type τ of size < κ, there is a unique T ∈ T such that otp(T) = τ. Now, let ⟨⟨T_{α}, 0_{α}⟩ | α < κ⟩ enumerate all pairs ⟨T, a⟩ such that T ∈ T and a ∈ T. For the rest of the section, let S denote ⨁′_{α<κ} T_{α}. If δ is an ordinal, let P_{δ} = ⨁′_{γ<δ} S. We will sometimes think of elements of P_{δ} as functions f such that dom(f) = δ × κ, f(γ, α) ∈ T_{α} for all ⟨γ, α⟩ ∈ δ × κ, and, for all but finitely many ⟨γ, α⟩ ∈ δ × κ, f(γ, α) = 0_{α}. If f, g are two such functions, then Δ′(f, g) is the lexicographically largest ⟨γ, α⟩ ∈ δ×κ such that f(γ, α) ≠ g(γ, α), and f <_{Pδ} g iff f(γ, α) <_{Tα} g(γ, α). By Lemma 6.4, for every ordinal δ, P_{δ} is κ-scattered. Let ψ_{δ} = otp(P_{δ}).

Lemma 6.7. For every κ-scattered linear order φ, there is δ such that φ ⩽ ψ_{δ}.

Proof. We proceed by induction. If |φ| < κ, then there is α < κ such that otp(T_{α}) = φ. But then φ ⩽ otp(S) = ψ_{1}. Suppose β is an ordinal, φ = ∑_{ξ<β} φ_{ξ} and, for each ξ < β, there is δ_{ξ} such that φ_{ξ} ⩽ otp(P_{δξ}). For ξ < β, let Q_{ξ} be an order of type φ_{ξ}, and let Q = ∑_{ξ<β} Q_{ξ}, so otp(Q) = φ.. Let δ′ = sup {δ_{ξ} : ξ < β}, and, for all ξ < β, fix an order embedding F_{ξ} : Q_{ξ} → P_{δ′}. Let α′ < κ be such that T_{α′} is a 2-element linear order and 0_{α′} is the smaller of the elements (call the other 1_{α′}). Let δ = δ′ + β. Define F : Q → P_{δ} as follows. If ξ < β and a ∈ Q_{ξ}, let F (ξ, a) ∈ P_{δ} be defined as follows.

F (ξ, a)(γ, α) = \begin{cases}F_{ξ}(a)(γ, α) & if ⟨γ, α⟩ ∈ δ′ × κ \\ 1_{α′} & if ⟨γ, α⟩ = ⟨δ′ + ξ, α′⟩ \\ 0_{α} & otherwise \end{cases}

It is easy to check that F is an order embedding. The cases in which φ is a lexicographic sum whose index set is anti-well-ordered or of size < κ are similar. □

Theorem 6.2 will therefore follow from the following lemma.

Lemma 6.8. For every ordinal δ and every cardinal ν, there is μ such that ψ_{μ} ⟶ [ψ_{δ}]_{ν,κ}^{1}.

Proof. Fix an ordinal δ and a cardinal ν. Let μ = (|δ|^{νκ})^{++}. Let H : P_{μ} → ν. We define a colouring F of FS(μ) as follows. Suppose s⃗ = ⟨s_{0}, …, s_{n−1}⟩ ∈ FS(μ). Then F (s⃗) is the function defined on ∏_{i<n} S defined as follows. If a⃗ = ⟨a_{0}, …, a_{n−1}⟩ ∈ ∏_{i<n} S, then F (s⃗)(a⃗) = H(f), where f ∈ P_{μ} is such that supp(f) ⊆ {s_{0}, …, s_{n−1}} and, for all i < n, f(s_{i}) = a_{i}. Since |S| = κ, F is a colouring with ν^{κ} colours. Therefore, by Lemma 6.6, there is a δ-tree x : FS(δ) → μ and a function c with domain ω such that, for every n < ω and every ⟨s_{0}, …, s_{n−1}⟩ ∈ FS(δ), F (x(⟨s_{0}⟩), …, x(⟨s_{0}, …, s_{n−1}⟩)) = c(n).

Fix such an x and c. Define a function h : P_{δ} → P_{μ} as follows. Suppose f ∈ P_{δ} and supp(f) = ⟨s_{0}, …, s_{n−1}⟩, listed in decreasing order. For each i < n, let t_{i} = x(⟨s_{0}, …, s_{i}⟩). Let h(f) ∈ P_{μ} be such that supp(h(f)) = {t_{i} : i < n} and such that, for all i < n, h(f)(t_{i}) = f(s_{i}).

Claim 6.9. h is order-preserving.

Proof. Suppose f, f′ ∈ P_{δ} with f <_{Pδ} f′. Let supp(f) = ⟨s_{0}, …, s_{m−1}⟩ and supp(f′) = ⟨s′_{0}, …, s′_{n−1}⟩, both listed in decreasing order. Let i be least such that either s_{i} ≠ s′_{i} or f(s_{i}) ≠ f(s′_{i}).

Suppose first that s_{i} ≠ s′_{i}. Without loss of generality, assume s_{i} < s′_{i} (the argument in the other case is symmetric). In particular, since f <_{Pδ} f′, we have 0 <_{S} f′(s′_{i}). Then x(⟨s_{0}, …, s_{i}⟩) < x(⟨s_{0}, …, s′_{i}⟩), so, by our definition of h, Δ′(h(f), h(f′)) = x(⟨s_{0}, …, s′_{i}⟩) =: t and h(f)(t) = 0 <_{S} f′(s′_{i}) = h(f′)(t), so h(f) <_{Pμ} h(f′).

If s_{i} = s′_{i} and f(s_{i}) <_{S} f(s′_{i}), let x(⟨s_{0}, …, s_{i}⟩) = t. Again, Δ′(h(f), h(f′)) = t and h(f)(t) = f(s_{i}) <_{S} f′(s_{i}) = h(f′)(t), so h(f) <_{Pμ} h(f′). □

Now let P′ = h[P_{δ}]. Then P′ ⊆ P_{μ} and otp(P′) = ψ_{δ}. We claim that |H[P′]| ⩽ κ.

Recall that, for n < ω, c(n) is a function from ∏_{i<n} S to ν. Let A_{n} = c[ ∏_{i<n} S], and let A = ⋃_{n<ω} A_{n}. Since |S| = κ, we have |A| = κ. We claim that H[P′] ⊆ A. To see this, let g ∈ P′. By definition, there is f ∈ P_{δ} such that g = h(f). Let s⃗ = ⟨s_{0}, …, s_{n−1}⟩ = supp(f) and, for i < n, t_{i} = x(⟨s_{0}, …, s_{i}⟩), so supp(g) = ⟨t_{0}, …, t_{n−1}⟩. Let a⃗ = ⟨a_{0}, …, a_{n−1}⟩ be such that, for i < n, f(s_{i}) = a_{i} = g(t_{i}). Retracing the definitions, we have:

H(f) = F (t⃗)(a⃗) = F (x(⟨s_{0}⟩), …, x(⟨s_{0}, …, s_{n−1}⟩))(a⃗) = c(n)(a⃗) ∈ A_{n} ⊆ A.

Thus, |H[P′]| ⩽ κ, completing the proof the theorem. □

7. Questions

At the end of this paper we are left with many open questions, some of which we would like to state explicitly. Recall that Todorcevic showed in [989To, Chapter 2] that 𝔟 = ℵ_{1} implies ω_{1}−̸→(ω_{1}, ω + 2)^{2}. Together with

Theorem 4.2 this suggests the following Question:

Question 7.1. Does 𝔟 = ℵ_{1} imply ω_{1}ω−̸→(ω_{1}ω, 3)^{2}?

Both the statements ∀n < ω (ω_{1}ω ⟶ (ω_{1}ω, n)^{2}) and

∀n < ω (ω_{1}ω^{2} ⟶ (ω_{1}ω^{2}, n)^{2}) were shown to follow from MA_{ℵ1} in [989Ba]. For the time being, we failed to answer the following Question:

Question 7.2. Does ω_{1}ω ⟶ (ω_{1}ω, 3)^{2} imply ω_{1}ω^{2} ⟶ (ω_{1}ω^{2}, 3)^{2}?

Regarding weakly scattered orders, the following questions seems to be central.

Question 7.3. Is it consistent that there is a regular κ such that for all weakly κ-scattered linear order types φ of size κ there is a weakly κ-scattered linear order type τ ⩾ φ of size κ such that τ ⟶ (τ, 3)^{2}?

Question 7.4. Is it consistent that there is a regular κ such that for all κ-scattered linear orders φ of size κ there is a κ-scattered linear order τ ⩾ φ of size κ such that τ ⟶ (τ, 3)^{2}?

The obvious candidate for κ here is ℵ_{0}, but note that even the analogous question referring to ordinals is unanswered. Another obvious question is whether the analogue of Theorem 3.1 attained by replacing “weakly κ-scattered” by “κ-scattered” is consistently true. This question is of interest both for successor cardinals and inaccessible cardinals.

Question 7.5. Is it consistent that there is an uncountable, regular cardinal κ such that, for every κ-scattered linear order φ of size κ, there is a κ-scattered linear order τ of size κ such that τ ⟶ (φ, n)^{2} for all n < ω?

A question which may be cumbersome to answer, is the following:

Question 7.6. Are all consistent negative partition relations for σ-scattered orders of cardinality ℵ_{1} for two colours implied by the conclusion of Theorem 5.11?

Finally, we ask whether Theorem 6.2 is optimal in terms of the numbers of colours. In particular, we ask the following.

Question 7.7. Do the axioms of ZFC imply that there is a κ-scattered order type φ such that, for every κ-scattered order type ψ, ψ−̸→[φ]_{κ,<κ}^{1}?

References

[XXXCh] William Chen. Variations of the stick principle. Eur. J. Math., doi:https://doi.org/10.1007/s40879-017-0167-z,

         https://link.springer.com/article/10.1007/s40879-017-0167-z. available in cyberspace.

[017Br] Jörg Brendle. Personal communication. February 2017.

[016L] Philipp Moritz Lücke, Philipp Schlicht and Thilo Volker Weinert. Choiceless Ramsey theory for linear orders. Order,

         33, 2016, doi:10.1007/s11083-016-9405-0, https://link.springer.com/article/10.1007/s11083-016-9405-0.

[015Sh] Saharon Shelah. Personal communication. 2015.

[014Ga] Fred Galvin. Personal communication. 2014.

[014LH] Chris Lambie-Hanson. Squares and covering matrices. Ann. Pure Appl. Logic, 165(2):673–694, 2014,

         doi:10.1016/j.apal.2013.10.001, http://dx.doi.org/10.1016/j.apal.2013.10.001.

[012A^{&}] Uri Abraham, Robert Bonnet, James William Radford Cummings, Mirna Džamonja and Katherine Thompson. A scattering of orders. Trans. Amer. Math. Soc., 364(12):6259–6278, 2012, doi:10.1090/S0002-9947-2012-05466-3,

         http://dx.doi.org/10.1090/S0002-9947-2012-05466-3.

[006BiP] Joan Bagaria i Pigrau. Axioms of generic absoluteness. In Logic Colloquium ’02, volume 27 of Lect. Notes Log., pages 28–47. Assoc. Symbol. Logic, La Jolla, CA, 2006.

[006Br] Jörg Brendle. Cardinal invariants of the continuum and combinatorics on uncountable cardinals. Ann. Pure Appl. Logic, 144(1-3):43–72, 2006, doi:10.1016/j.apal.2006.05.003, http://dx.doi.org/10.1016/j.apal.2006.05.003.

[006DT] Mirna Džamonja and Katherine Thompson. A poset hierarchy. Cent. Eur. J. Math., 4(2):225–241 (electronic), 2006,

         doi:10.1007/s11533-006-0001-1, http://dx.doi.org/10.1007/s11533-006-0001-1.

[005Ha] Egbert Harzheim. Ordered sets, volume 7 of Advances in Mathematics (Springer). Springer, New York, 2005.

[003KS] Péter Komjáth and Saharon Shelah. A partition theorem for scattered order types. Combin. Probab. Comput., 12(5-6):621–626, 2003, doi:10.1017/S0963548303005686, http://dx.doi.org/10.1017/S0963548303005686. Special issue on Ramsey theory.

[999DS] Mirna Džamonja and Saharon Shelah. ♣ does not imply the existence of a Suslin tree. Israel J. Math., 113:163–204,

         1999, doi:10.1007/BF02780176, http://dx.doi.org/10.1007/BF02780176.

[998La] Jean Ann Larson. An ordinal partition from a scale. In Set theory (Curaçao, 1995; Barcelona, 1996), pages 109–125. Kluwer Acad. Publ., Dordrecht, 1998.

[997F] Sakaé Fuchino, Saharon Shelah and Lajos Soukup. Sticks and clubs. Ann. Pure Appl. Logic, 90(1-3):57–77, 1997,

doi:10.1016/S0168-0072(97)00030-4, http://dx.doi.org/10.1016/S0168-0072(97)00030-4.

[995CS] James William Radford Cummings and Saharon Shelah. Cardinal invariants above the con-

tinuum.  Ann. Pure Appl. Logic,  75(3):251–268,  1995,  doi:10.1016/0168-0072(95)00003-Y,

http://dx.doi.org/10.1016/0168-0072(95)00003-Y.

[989Ba] James Earl Baumgartner. Remarks on partition ordinals. In Set theory and its applications (Toronto, ON, 1987), volume 1401 of Lecture Notes in Math., pages 5–17. Springer, Berlin, 1989, doi:10.1007/BFb0097328,

http://dx.doi.org/10.1007/BFb0097328.

[989To] Stevo Todorčević. Partition problems in topology, volume 84 of Contemporary Mathematics. American Mathematical Society, Providence, RI, 1989, doi:10.1090/conm/084, http://dx.doi.org/10.1090/conm/084.

[987SS] Saharon Shelah and Lee Stanley. A theorem and some consistency results in partition calculus. Ann. Pure Appl. Logic, 36(2):119–152, 1987, doi:10.1016/0168-0072(87)90015-7, http://dx.doi.org/10.1016/0168-0072(87)90015-7.

[987Ta] Joji Takahashi. Two negative partition relations. Period. Math. Hungar., 18(1):1–6, 1987, doi:10.1007/BF01849028,

http://dx.doi.org/10.1007/BF01849028.

[983Tr] John Kenneth Truss. The noncommutativity of random and generic extensions. J. Symbolic Logic, 48(4):1008–1012

(1984), 1983, doi:10.2307/2273665, http://dx.doi.org/10.2307/2273665.

[982Ro] Joseph Goeffrey Rosenstein. Linear orderings, volume 98 of Pure and Applied Mathematics. Academic Press Inc. [Harcourt Brace Jovanovich Publishers], New York, 1982.

[978B] Samuel Alexander Broverman, John Norman Ginsburg, Kenneth Kunen and Franklin D. Tall. Topologies determined by σ-ideals on ω_{1}. Canad. J. Math., 30(6):1306–1312, 1978, doi:10.4153/CJM-1978-107-7,

http://dx.doi.org/10.4153/CJM-1978-107-7.

[976Os] Adam J. T. M. Ostaszewski. A perfectly normal countably compact scattered space which is not strongly zerodimensional. J. London Math. Soc. (2), 14(1):167–177, 1976.

[974La] Jean Ann Larson. A short proof of a partition theorem for the ordinal ω^{ω}. Ann. Math. Logic, 6:129–145, 1973–1974.

[972EM] Paul Erdős and Eric Charles Milner. A theorem in the partition calculus. Canad. Math. Bull., 15:501–505, 1972,

http://www.renyi.hu/~p_erdos/1972-03.pdf.

[971E] Paul Erdős, Eric Charles Milner and Richard Rado. Partition relations for η_{α}-sets. J. London Math. Soc. (2), 3:193–204,

         1971, http://www.renyi.hu/~p_erdos/1971-16.pdf.

[971EH] Paul Erdős and Andras Hajnal. Ordinary partition relations for ordinal numbers. Period. Math. Hungar., 1(3):171–185,

         1971, http://www.renyi.hu/~p_erdos/1971-15.pdf.

[971La] Richard Laver. On Fraïssé’s order type conjecture. Ann. of Math. (2), 93:89–111, 1971.

[965E] Paul Erdős, Andras Hajnal and Richard Rado. Partition relations for cardinal numbers. Acta Math. Acad. Sci. Hungar., 16:93–196, 1965.

[965MR] Eric Charles Milner and Richard Rado. The pigeon-hole principle for ordinal numbers. Proc. London Math. Soc. (3), 15:750–768, 1965.

[963EH] Paul Erdős and Andras Hajnal. On a classification of denumerable order types and an application to the partition calculus. Fund. Math., 51:117–129, 1962/1963, http://www.renyi.hu/~p_erdos/1962-06.pdf.

[956ER] Paul Erdős and Richard Rado. A partition calculus in set theory. Bull. Amer. Math. Soc., 62:427–489, 1956,

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

[956Gi] Leonard Gillman. Some remarks on η_{α}-sets. Fund. Math., 43:77–82, 1956.

[949Si] Wacław Franciszek Sierpiński. Sur une propriété des ensembles ordonnés. Fund. Math., 36:56–67, 1949.

[933Si] Wacław Franciszek Sierpiński. Sur un problème de la théorie des relations. Ann. Scuola Norm. Sup. Pisa Cl. Sci. (2),

         2(3):285–287, 1933, http://www.numdam.org/item?id=ASNSP_1933_2_2_3_285_0.

[914Ha] Felix  Hausdorff.  Grundzüge  der  Mengenlehre.  Veit  and  Company,  Leipzig,  1914,

         https://archive.org/details/grundzgedermen00hausuoft.

[913Sc] Arthur Moritz Schoenflies. Entwicklung der Mengenlehre und ihrer Anwendungen. 2nd edition, Teubner, Leipzig, 1913.

[908Ha] Felix Hausdorff. Grundzüge einer Theorie der geordneten Mengen. Math. Ann., 65(4):435–505, 1908,

         doi:10.1007/BF01451165, http://dx.doi.org/10.1007/BF01451165.

Department of Mathematics, Bar-Ilan University, Ramat Gan, 5290002, Israël

  E-mail address: lambiec@macs.biu.ac.il

Department of Mathematics, Ben-Gurion-University of the Negev, Beersheba, 8410501, Israël

  E-mail address: aleph omega@posteo.net