Abstract. Let ¹

COLORING LINEAR ORDERS WITH RADO’S PARTIAL ORDER

RICCARDO CAMERLO AND ALBERTO MARCONE

Abstract. Let ¹

be the preorder of embeddability between countable linear orders colored with elements of Rado’s partial or- der (a standard example of a wqo which is not a bqo). We show that ¹

has fairly high complexity with respect to Borel reducibil- ity (e.g. if P is a Borel preorder then P ≤

¹

), although its exact classification remains open.

1. Introduction

This note is a contribution to the study of the relations of embed- dability for countable colored linear orderings from the point of view of descriptive set theory. Fixing ω as the support of a countable linear or- dering, we can consider the space LO of all linear orderings on ω. This is a standard Borel space (actually a Polish space, see [Kec95]). For our purposes, to color a linear order means assigning to each element of the support an element from a fixed countable set C. A colored linear ordering on ω is thus an element of LO × C

, which is also a standard Borel space.

If Q is a partial order on C we have a natural relation of embed- dability ¹

on LO × C

defined by letting (v, ϕ) ¹

(v

, ϕ

) if and only if there exists g : ω → ω such that:

(1) ∀a, b ∈ ω (a v b ⇐⇒ g(a) v

g(b));

(2) ∀a ∈ ω ϕ(a) Q ϕ

(g(a)).

Then ¹

is a Σ

preorder which is not Borel and it can be studied in the framework of Borel reducibility.

Given binary relations P and P

on standard Borel spaces X and X

respectively, recall that P ≤

P

means that there exists a Borel function f : X → X

such that x P y ⇐⇒ f (x) P

f (y). A Σ

preorder P

is called Σ

-complete if and only if P ≤

P

for any Σ

preorder P .

For preorders of the form ¹

it is known that:

• if Q is a bqo then, by Laver’s celebrated theorem ([Lav71]), ¹

is a bqo as well; in particular it is a wqo and the relation of equality on ω is not reducible to ¹

; thus in this case ¹

is quite far from being a Σ

-complete preorder;

2000 Mathematics Subject Classification. 03E15, 06A05.

Key words and phrases. Borel reducibility. Rado’s partial order. Colored linear orders.

1

• if Q is not a wqo, then ¹

is a Σ

-complete preorder (see [Cam05], a partial result in this direction is in [MR04]).

These results leave unanswered the question of the complexity of the relation ¹

when Q is a wqo but not a bqo.

If α is a countable ordinal then a preorder Q is ω

-wqo if ¹

re- stricted to well-orders of order type strictly less than ω

is a wqo.

Therefore ω-wqo means wqo and a preorder is bqo if and only if it is ω

-wqo for every α (details can be found e.g. in [Mar94]).

In this note we consider Rado’s partial order R defined on the set D = { (n, m) ∈ ω

| n < m } by

(n, m) R (n

, m

) ⇐⇒ (n = n

∧ m ≤ m

) ∨ m < n

.

R is wqo but it is not ω

-wqo. Moreover R embeds into every wqo which is not ω

-wqo ([Rad54]). R is the best known example of a wqo which is not bqo.

We will need witnesses for the fact that R is not ω

-wqo. Let r

∈ D

be defined by letting r

(n) = (i, i + 1 + n) for each n ∈ ω. Note that if i < i

, then r

and r

are incomparable under ¹

: indeed (i

, n) R (i, m) does not hold for any n, m, while (i, i

) R (i

, m) does not hold for any m. Therefore, for i 6= i

, we can fix γ

∈ ω such that r

(γ

) R r

(m) does not hold for any m.

In section 2 we show that for any Borel preorder P , the relation P ≤

¹

holds (by the above observation the result extends to all ¹

where Q is wqo but not ω

-wqo). This shows that ¹

is indeed a quite complex preorder, though the question about its Σ

-completeness remains wide open. The proof is an application of Rosendal’s construction of a cofinal family of Borel preorders ([Ros05]). This involves comparing ¹

with an ω

-chain of Borel preorders on standard Borel spaces obtained by repeatedly applying a jump operation P 7→ P

.

Rosendal ([Ros05]) showed that if P is a Borel preorder satisfying a simple combinatorial condition, then P <

P

. In section 3 we compare ¹

with its jump (¹

)

and show that ¹

≡

(¹

)

(that is ¹

≤

(¹

)

≤

¹

), giving further evidence to the fact that ¹

has high descriptive complexity.

In contrast with the latter property of ¹

, in section 4 we prove the existence of a downward closed class of non-Borel preorders P such that P <

P

.

In the sequel, we will freely use the operations of sum of colored

linear orders, and of multiplication of a colored linear order L by a

linear order L

, indicated by L · L

. Standard coding techniques allow

to represent the result as an element of LO × C

in a Borel way.

2. ¹

is above all Borel preorders

Definition 1. If P is a preorder on a standard Borel space X define P

on X

by setting

~x P

~y ⇐⇒ ∀n ∈ ω ∃m ∈ ω x

P y

.

Remark 2. Notice that P

≤

P

implies P

≤

P

. Moreover P ≤

P

, as witnessed by the map x 7→ ~y where y

= x for every n.

A (colored) linear order L is right indecomposable if it is embeddable in any of its final segments. For example each r

defined above is right indecomposable. An ordinal is right indecomposable if and only if it is additively indecomposable: in this case we adhere to standard terminology and say that the ordinal is indecomposable.

Theorem 3. For any Borel preorder P on some standard Borel space, the relation P ≤

¹

holds.

Proof. Following Rosendal ([Ros05]) define preorders P

with domain X

, for ξ ∈ ω

as follows:

• X

= ω and P

is equality;

• given P

let X

= X

and P

= P

;

• for ξ limit let X

= Q

β<ξ

X

and ~x P

~y ⇐⇒ ∀β < ξ x

P

y

. Rosendal proved that this transfinite sequence is ≤

-cofinal among Borel preorders. Therefore it suffices to show that ∀ξ < ω

P

≤

¹

.

We prove by induction on ξ that there exist an indecomposable countable ordinal α

and a Borel reduction f

of P

to ¹

whose values are colored well-orders of order type α

which are right indecomposable.

Basis step. Let α

= ω and f

(i) = r

.

Successor step. Let ξ ∈ ω

and assume f

, α

satisfy the induction hypothesis. Set α

= α

· ω. Given ~x = (x

, x

, x

, . . .) ∈ X

, define

f

(~x) = X

k

f

(x

)

where (n

)

is an enumeration of ω where each natural number oc- curs infinitely often. Each occurrence of f

(x

) in this definition will be called a segment of f

(~x). Notice that f

(~x) is a right indecom- posable colored well-order of length α

.

Suppose ~x P

~y. For each n ∈ ω there exists m ∈ ω such that f

(x

) ¹

f

(y

). Since each f

(y

) occurs infinitely often in f

(~y), it follows that f

(~x) ¹

f

(~y).

Conversely, suppose g embeds f

(~x) into f

(~y). Since no segment of f

(~x) can be mapped by g cofinally into f

(~y), a final segment of each f

(x

) must be embedded by g into some f

(y

). Since by induction hypothesis f

(x

) is right indecomposable, we have f

(x

) ¹

f

(y

) which implies x

P

y

. Thus ~x P

~y.

Limit step. Let ξ be a limit ordinal. Suppose that, for each β < ξ, α

and f

satisfy the induction hypothesis. Let ρ be an indecomposable

3

countable ordinal larger than each α

. Let {β

}

be an enumeration of ξ with each element occurring infinitely often. Given ~x ∈ X

= Q

β<ξ

X

, define

F

(~x) = f

(x

) + r

(γ

) + r

· ρ

(where r

(γ

) denotes the colored linear order with a single element colored by r

(γ

)),

F (~x) = X

n

F

(~x),

and finally

f

(~x) = F (~x) · ω.

So each f

(~x) is a right indecomposable colored well-order of length α

= ρ · ω

, which is an indecomposable countable ordinal.

Suppose ~x P

~y. Then F

(~x) ¹

F

(~y) for every n, so F (~x) ¹

F (~y) and finally f

(~x) ¹

f

(~y).

Conversely, let g witness f

(~x) ¹

f

(~y). Then a final segment of the first occurrence Φ of F (~x) in the definition of f

(~x) is embedded by g into some occurrence Ψ of F (~y) in f

(~y). Let i ∈ ω be least such that the occurrence of F

(~x) in Φ is embedded by g into Ψ. So for each j ≥ i a final segment of the occurrence of r

· ρ in Φ must be sent by g cofinally into the corresponding occurrence in Ψ. As, for j > i, the occurrence of r

(γ

) in F

(~x) just preceding the occurrence of r

·ρ cannot be sent by g to an element of the occurrence of r

· ρ in F

(~y), it follows that g embeds f

(x

) into f

(y

), witnessing x

P

y

. Since each β ∈ ξ occurs as β

for some j > i, it follows that ~x P

~y. ¤ Corollary 4. If Q is a countable wqo but not an ω

-wqo then, for all Borel preorders P on standard Borel spaces, P ≤

¹

.

Proof. By Rado’s Theorem R embeds into Q and from this it follows

easily that ¹

≤

¹

. ¤

3. A closure property for ¹

The goal of this section is proving the following result:

Theorem 5. (¹

)

≡

¹

.

The proof of Theorem 5 uses the following definition and a couple of lemmas.

Definition 6. If Q is a partial order on a countable set C of colors, define ¹

on LO × C

by L ¹

L

if and only if L · ω ¹

L

· ω.

Remark 7. For any Q the map L 7→ L · ω witnesses that ¹

≤

¹

.

Moreover it is easy to check that L ¹

L

is equivalent to the exis-

tence of k ∈ ω such that L ¹

L

· k.

Lemma 8. If Q is a partial order on a countable set then we have (¹

)

≤

¹

.

Proof. Fix a sequence (n

)

enumerating each natural number infin- itely many times and use the map ~ L 7→ P

k∈ω

(L

· ω). ¤ Lemma 9. Let P be any preorder on LO×D

such that ¹

⊆ P ⊆ ¹

. Then ¹

≤

P . In particular ¹

≤

¹

and thus (by Remark 7)

¹

≡

¹

.

Proof. Given L ∈ LO × D

let L

be the colored linear order obtained from L by replacing each color (n, m) with (2(i + 1)n + 1, 2(i + 1)m + 1) (the underlying linear order is unchanged). Notice that L

¹

M

if and only if L ¹

M.

To show that ¹

≤

P we use the map L 7→ F (L) where F (L) = X

i∈ω

(L

+ r

· Q).

It is immediate that if L ¹

M then F (L) ¹

F (M) and hence F (L) P F (M).

Now assume that F (L) P F (M), which implies F (L) ¹

F (M), so that for some k ∈ ω we have F (L) ¹

F (M) · k via some g. We need to show that L ¹

M. There are two cases:

• First suppose that for some i, j we have r

· Q ¹

M

via a function p = p(n, q) (the domain of r

· Q is ω × Q, and (n, q) has color (2i, 2i + n + 1)). In this case we claim that N ¹

M

for any D-colored countable linear ordering N.

To prove the claim fix N and an order preserving map h : N → Q (here we are looking at N as a linear order). For any a ∈ N let (ϕ(a), ψ(a)) the label assigned by N to a. Define f : N → M

order preserving by f (a) = p(ψ(a), h(a)). Since M

does not use any label of the form (2i, k), the first component of the label of f (a) is greater than 2i + ψ(a) + 1 > ψ(a). Therefore f witnesses N ¹

M

and the claim is proved.

Then for any N ∈ LO ×D

we have N

¹

M

, and hence N ¹

M. In particular L ¹

M.

• Now assume that r

· Q 

M

for all i and j. As g maps F (L) into F (M) · k, for some `, g maps

X

i≥`

(L

+ r

· Q)

into a single copy of F (M). Since r

· Q 

r

· Q when i 6= j (because r

(γ

) is a color used by r

· Q), g maps each r

· Q for i ≥ ` into the copy of r

· Q appearing in F (M). Therefore g maps L

into r

· Q + M

+ r

· Q. Since the colors used by L

have second component greater than 2` + 2, g cannot map any element of L

into either r

· Q or r

· Q.

5

Therefore (the restriction of) g witnesses L

¹

M

, and

hence we have also L ¹

M. ¤

Proof of Theorem 5. We have

¹

≤

(¹

)

by Remark 2

≤

(¹

)

by Lemma 9 and Remark 2

≤

¹

by Lemma 8. ¤

4. A class of non-Borel P ’s such that P <

P

The cofinal sequence (P

) of section 2 is built using the operation P 7→ P

at successor steps, allowing to obtain Borel preorders of increasing complexity. Here we build a ≤

-downward closed class of non-Borel preorders P ’s such that P <

P

.

With a straightforward modification of a construction for equivalence relations due to John Clemens ([Cle01, §3.3]) we define two analytic preorders P

and P

. These preorders have the property that P ≤

P

and P ≤

P

if and only if P is a Borel preorder.

We further show the following: suppose P is an analytic non-Borel preorder such that there exist equivalence relations E, F on standard Borel spaces with P ≤

(E × P

) ⊕ (F × P

); then we have P <

P

. Let B ⊆ ω

be the set of codes for Borel preorders on ω

. B is Π

by [Kec95, Theorem 35.5] and the fact that the set of codes for reflexive and transitive Borel relations is Π

. Fixing a coanalytic rank on B, for each α ∈ ω

let B

⊆ B be the Borel set of elements of rank less than α. Let S ∈ Σ

((ω

)

), S

∈ Π

((ω

)

) be such that, for z ∈ B, (z, y

, y

) is in S if and only if it is in S

if and only if y

is related to y

in the preorder coded by z. Define on (ω

)

the analytic non-Borel preorders P

, P

by:

(z

, y

) P

(z

, y

) ⇐⇒ z

= z

∧ (z

∈ B ∨ (z /

, y

, y

) ∈ S), (z

, y

) P

(z

, y

) ⇐⇒ (z

∈ B ∧ z /

∈ B)∨ /

∨ (z

= z

∧ (z

, y

, y

) ∈ S).

Notice that when z

, z

∈ B each of (z

, y

) P

(z

, y

) and (z

, y

) P

(z

, y

) is equivalent to

z

= z

∧ (z

, y

, y

) ∈ S

,

which is coanalytic. Therefore for each α the restrictions of P

and P

to B

× ω

are coanalytic and thus Borel.

Proposition 10. For any preorder P on a standard Borel space, P is Borel if and only if P ≤

P

and P ≤

P

.

Proof. The proof is a straightforward adaptation of the argument given

by Clemens for equivalence relations.

For the forward implication we can assume that P is defined on ω

; let z be one of its codes. Then x 7→ (z, x) witnesses both P ≤

P

and P ≤

P

.

Conversely, if P ≤

P

all P -equivalence classes are Borel, because this is the case with P

. If P ≤

P

let f witness this. Let A = f

(B × ω

). The complement of A is either empty or is a single equivalence class of P ; hence A is Borel. Consequently, f (A) is analytic and its projection onto the first coordinate must be included in some B

. As noticed above, the restriction of P

to the Borel set B

× ω

is Borel. So the restriction of P to A is Borel reducible to a Borel relation, and thus is itself Borel. It follows that P too is Borel. ¤ Theorem 11. Let P be a non-Borel preorder and E, F be arbitrary equivalence relations on standard Borel spaces. Then P



(E × P

) ⊕ (F × P

).

Proof. Notice that P

is directed. This implies that the image of any reduction of P

to (E × P

) ⊕ (F × P

) is included in some [e]

× (ω

)

or in some [f ]

× (ω

)

, and therefore we have a reduction of P

to either P

or P

.

First assume f is a Borel reduction of P

to P

. Let π : (ω

)

→ ω

be the projection on the first coordinate. Using again the fact that P

is directed we have either that πf (~x) / ∈ B for all ~x or that there exists z ∈ B such that πf (~x) = z for all ~x. In the first case ~x P

~y for all

~x, ~y. In the second case P

Borel reduces to the Borel preorder coded by z. Since P , and thus P

, is not Borel, in either case we reach a contradiction.

A similar argument shows that P



P

and completes the proof.

¤ Corollary 12. If P is a non-Borel preorder such that P ≤

(E ×P

)⊕

(F × P

) for some equivalence relations E, F on standard Borel spaces, then P <

P

. In particular P

<

P

and P

<

P

.

Proof. Immediate by Remark 2 and Theorem 11. ¤ Corollary 13. Let E and F be arbitrary equivalence relations on stan- dard Borel spaces. Then ¹



(E × P

) ⊕ (F × P

).

Proof. By Theorem 5 and Corollary 12. ¤

References

[Cam05] Riccardo Camerlo. Universality of embeddability relations for coloured total orders. Order, 22(3):289–300, 2005.

[Cle01] John D. Clemens. Descriptive set theory, equivalence relations, and clas- sification problems in analysis. PhD thesis, UC Berkeley, 2001.

[Kec95] Alexander S. Kechris. Classical descriptive set theory. Number 156 in Graduate Texts in Mathematics. Springer-Verlag, New York, 1995.

7

[Lav71] Richard Laver. On Fra¨ıss´e’s order type conjecture. Ann. of Math. (2), 93:89–111, 1971.

[Mar94] Alberto Marcone. Foundations of bqo theory. Trans. Am. Math. Soc., 345(2):641–660, 1994.

[MR04] Alberto Marcone and Christian Rosendal. The complexity of continuous embeddability between dendrites. J. Symbolic Logic, 69(3):663–673, 2004.

[Rad54] Richard Rado. Partial well-ordering of sets of vectors. Mathematika, Lond., 1:89–95, 1954.

[Ros05] Christian Rosendal. Cofinal families of Borel equivalence relations and quasiorders. J. Symb. Log., 70(4):1325–1340, 2005.

Dipartimento di Matematica, Politecnico di Torino, Corso Duca degli Abruzzi 24, 10129 Torino — Italy

E-mail address: camerlo@calvino.polito.it

Dipartimento di Matematica e Informatica, Universit` a di Udine, Via delle Scienze 208, 33100 Udine — Italy

E-mail address: marcone@dimi.uniud.it