Epimorphisms between linear orders joint with R. Carroy and A. Marcone

Epimorphisms between linear orders

joint with R. Carroy and A. Marcone

Basic notions on orders

Definition

I A quasi-order (or preorder) is a reflexive and transitive relation on a non-empty set.

I A linear (or total) order is an antisymmetric and total quasi-order on a non-empty set.

I A linear order will be usually denoted by (self-explaining variations

of) ≤. Its strict part by <: x < y ⇔ x ≤ y ∧ y 6≤ x .

Basic notions on orders

Definition

I A quasi-order (or preorder) is a reflexive and transitive relation on a non-empty set.

I A linear (or total) order is an antisymmetric and total quasi-order on a non-empty set.

I A linear order will be usually denoted by (self-explaining variations

of) ≤. Its strict part by <: x < y ⇔ x ≤ y ∧ y 6≤ x .

Basic notions on orders

Definition

I A quasi-order (or preorder) is a reflexive and transitive relation on a non-empty set.

I A linear (or total) order is an antisymmetric and total quasi-order on a non-empty set.

I A linear order will be usually denoted by (self-explaining variations

of) ≤. Its strict part by <: x < y ⇔ x ≤ y ∧ y 6≤ x .

Well-quasi-orders and better-quasi-orders

Definition

I A sequence (q _n ) _n∈N in a quasi-order Q is bad if n < m ⇒ q _n 6≤ _Q q _m .

I Quasi-order Q is a wqo if it does not contain bad sequences. This is equivalent to say that there are no infinite antichains nor infinite descending sequences in Q.

I If f : [N] ^ω → Q, then f is a Q-array if f ⁻¹ ({q}) is Borel, for all q ∈ Q.

I If Q is a quasi-order and f is a Q-array, f is bad if

∀X f (X ) 6≤ _Q f (X \ {min X }).

I Quasi-order Q is a bqo if it does not contain bad arrays.

Well-quasi-orders and better-quasi-orders

Definition

I A sequence (q _n ) _n∈N in a quasi-order Q is bad if n < m ⇒ q _n 6≤ Q q _m .

I Quasi-order Q is a wqo if it does not contain bad sequences. This is equivalent to say that there are no infinite antichains nor infinite descending sequences in Q.

I If f : [N] ^ω → Q, then f is a Q-array if f ⁻¹ ({q}) is Borel, for all q ∈ Q.

I If Q is a quasi-order and f is a Q-array, f is bad if

∀X f (X ) 6≤ _Q f (X \ {min X }).

I Quasi-order Q is a bqo if it does not contain bad arrays.

Well-quasi-orders and better-quasi-orders

Definition

I A sequence (q _n ) _n∈N in a quasi-order Q is bad if n < m ⇒ q _n 6≤ Q q _m .

I Quasi-order Q is a wqo if it does not contain bad sequences.

This is equivalent to say that there are no infinite antichains nor infinite descending sequences in Q.

I If f : [N] ^ω → Q, then f is a Q-array if f ⁻¹ ({q}) is Borel, for all q ∈ Q.

I If Q is a quasi-order and f is a Q-array, f is bad if

∀X f (X ) 6≤ _Q f (X \ {min X }).

I Quasi-order Q is a bqo if it does not contain bad arrays.

Well-quasi-orders and better-quasi-orders

Definition

I A sequence (q _n ) _n∈N in a quasi-order Q is bad if n < m ⇒ q _n 6≤ Q q _m .

I Quasi-order Q is a wqo if it does not contain bad sequences.

This is equivalent to say that there are no infinite antichains nor infinite descending sequences in Q.

I If f : [N] ^ω → Q, then f is a Q-array if f ⁻¹ ({q}) is Borel, for all q ∈ Q.

I If Q is a quasi-order and f is a Q-array, f is bad if

∀X f (X ) 6≤ _Q f (X \ {min X }).

I Quasi-order Q is a bqo if it does not contain bad arrays.

Well-quasi-orders and better-quasi-orders

Definition

I A sequence (q _n ) _n∈N in a quasi-order Q is bad if n < m ⇒ q _n 6≤ Q q _m .

I Quasi-order Q is a wqo if it does not contain bad sequences.

This is equivalent to say that there are no infinite antichains nor infinite descending sequences in Q.

I If f : [N] ^ω → Q, then f is a Q-array if f ⁻¹ ({q}) is Borel, for all q ∈ Q.

I If Q is a quasi-order and f is a Q-array, f is bad if

∀X f (X ) 6≤ _Q f (X \ {min X }).

I Quasi-order Q is a bqo if it does not contain bad arrays.

Well-quasi-orders and better-quasi-orders

Definition

I A sequence (q _n ) _n∈N in a quasi-order Q is bad if n < m ⇒ q _n 6≤ Q q _m .

I Quasi-order Q is a wqo if it does not contain bad sequences.

This is equivalent to say that there are no infinite antichains nor infinite descending sequences in Q.

I If f : [N] ^ω → Q, then f is a Q-array if f ⁻¹ ({q}) is Borel, for all q ∈ Q.

I If Q is a quasi-order and f is a Q-array, f is bad if

∀X f (X ) 6≤ _Q f (X \ {min X }).

I Quasi-order Q is a bqo if it does not contain bad arrays.

Well-quasi-orders and better-quasi-orders

Definition

I A sequence (q _n ) _n∈N in a quasi-order Q is bad if n < m ⇒ q _n 6≤ Q q _m .

I Quasi-order Q is a wqo if it does not contain bad sequences.

This is equivalent to say that there are no infinite antichains nor infinite descending sequences in Q.

I If f : [N] ^ω → Q, then f is a Q-array if f ⁻¹ ({q}) is Borel, for all q ∈ Q.

I If Q is a quasi-order and f is a Q-array, f is bad if

∀X f (X ) 6≤ _Q f (X \ {min X }).

I Quasi-order Q is a bqo if it does not contain bad arrays.

Basic (but not so trivial) facts about bqo’s

1. If (q n ) is a bad sequence in Q, then f (X ) = q min X is a bad Q-array. So any bqo is a wqo.

2. A finite union of bqo’s is bqo. 3. A finite product of bqo’s is bqo.

4. If P is a qo, Q is a bqo and there is a function f : P → Q such that

f (x ) ≤ _Q f (y ) ⇒ x ≤ _P y , then P is a bqo.

Basic (but not so trivial) facts about bqo’s

1. If (q n ) is a bad sequence in Q, then f (X ) = q min X is a bad Q-array.

So any bqo is a wqo.

2. A finite union of bqo’s is bqo. 3. A finite product of bqo’s is bqo.

4. If P is a qo, Q is a bqo and there is a function f : P → Q such that

f (x ) ≤ _Q f (y ) ⇒ x ≤ _P y , then P is a bqo.

Basic (but not so trivial) facts about bqo’s

1. If (q n ) is a bad sequence in Q, then f (X ) = q min X is a bad Q-array.

So any bqo is a wqo.

2. A finite union of bqo’s is bqo.

3. A finite product of bqo’s is bqo.

4. If P is a qo, Q is a bqo and there is a function f : P → Q such that

f (x ) ≤ _Q f (y ) ⇒ x ≤ _P y , then P is a bqo.

Basic (but not so trivial) facts about bqo’s

1. If (q n ) is a bad sequence in Q, then f (X ) = q min X is a bad Q-array.

So any bqo is a wqo.

2. A finite union of bqo’s is bqo.

3. A finite product of bqo’s is bqo.

4. If P is a qo, Q is a bqo and there is a function f : P → Q such that

f (x ) ≤ _Q f (y ) ⇒ x ≤ _P y , then P is a bqo.

Relations between linear orders

The two following relations between linear orders seem immediately to have a clear interest:

Definition

I K ≤ i L if there is an order preserving injection K → L

I K ≤ s L if there is an order preserving surjection L → K

≤ s is a subrelation of ≤ i :

K ≤ s L ⇒ K ≤ i L

since if f : L → K witnesses K ≤ _s L, then any right inverse g witnesses K ≤ _i L.

The converse implication K ≤ _i L ⇒ K ≤ _s L does not hold in general:

when trying to invert an embedding K → L the obstructions are how to

deal with initial tails, final tails of L and gaps of K .

Relations between linear orders

The two following relations between linear orders seem immediately to have a clear interest:

Definition

I K ≤ i L if there is an order preserving injection K → L

I K ≤ s L if there is an order preserving surjection L → K

≤ s is a subrelation of ≤ i :

K ≤ s L ⇒ K ≤ i L

since if f : L → K witnesses K ≤ _s L, then any right inverse g witnesses K ≤ _i L.

The converse implication K ≤ _i L ⇒ K ≤ _s L does not hold in general:

when trying to invert an embedding K → L the obstructions are how to

deal with initial tails, final tails of L and gaps of K .

Relations between linear orders

The two following relations between linear orders seem immediately to have a clear interest:

Definition

I K ≤ i L if there is an order preserving injection K → L

I K ≤ s L if there is an order preserving surjection L → K

≤ s is a subrelation of ≤ i :

K ≤ s L ⇒ K ≤ i L

since if f : L → K witnesses K ≤ s L, then any right inverse g witnesses K ≤ _i L.

The converse implication K ≤ _i L ⇒ K ≤ _s L does not hold in general:

when trying to invert an embedding K → L the obstructions are how to

deal with initial tails, final tails of L and gaps of K .

Relations between linear orders

The two following relations between linear orders seem immediately to have a clear interest:

Definition

I K ≤ i L if there is an order preserving injection K → L

I K ≤ s L if there is an order preserving surjection L → K

≤ s is a subrelation of ≤ i :

K ≤ s L ⇒ K ≤ i L

since if f : L → K witnesses K ≤ s L, then any right inverse g witnesses K ≤ _i L.

The converse implication K ≤ _i L ⇒ K ≤ _s L does not hold in general:

when trying to invert an embedding K → L the obstructions are how to

deal with initial tails, final tails of L and gaps of K .

Relations between linear orders

The two following relations between linear orders seem immediately to have a clear interest:

Definition

I K ≤ i L if there is an order preserving injection K → L

I K ≤ s L if there is an order preserving surjection L → K

≤ s is a subrelation of ≤ i :

K ≤ s L ⇒ K ≤ i L

since if f : L → K witnesses K ≤ s L, then any right inverse g witnesses K ≤ _i L.

The converse implication K ≤ _i L ⇒ K ≤ _s L does not hold in general:

when trying to invert an embedding K → L the obstructions are how to

deal with initial tails, final tails of L and gaps of K .

The relation of embeddability: ≤ _i

Quite surprisingly, only the relation ≤ i has been extesively studied — at least at our knowledge.

Conjecture. (Fra¨ıss´ e, 1948) Countable linear orders form a wqo under

≤ i .

Theorem. (Laver, 1971) σ-scattered linear orders form a bqo under ≤ i .

The relation of embeddability: ≤ _i

Quite surprisingly, only the relation ≤ i has been extesively studied — at least at our knowledge.

Conjecture. (Fra¨ıss´ e, 1948) Countable linear orders form a wqo under

≤ i .

Theorem. (Laver, 1971) σ-scattered linear orders form a bqo under ≤ i .

The relation of embeddability: ≤ _i

Quite surprisingly, only the relation ≤ i has been extesively studied — at least at our knowledge.

Conjecture. (Fra¨ıss´ e, 1948) Countable linear orders form a wqo under

≤ i .

Theorem. (Laver, 1971) σ-scattered linear orders form a bqo under ≤ i .

Preserving bqo’s

A definition by Louveau and Saint-Raymond (1990).

Let C be a class of structures with morphisms such that: (i) the identity is a morphism; (ii) morphisms are closed under composition.

Given a quasi-order Q, let

Q ^C = {f : C → Q | C ∈ C} be ordered by

f ₀ ≤ f 1 ⇔ ∃C-morphism g : domf 0 → domf 1 s.t. ∀x ∈ domf ₀ f ₀ (x ) ≤ _Q f ₁ g (x ) Say that C preserves bqo’s if Q ^C is bqo whenever Q is a bqo.

Theorem. (Laver, 1971) The class of σ-scattered linear orders under ≤ i

preserves bqo’s.

Theorem. (van Engelen, Miller, Steel, 1987) The class of countable

linear orders under continuous embeddability ≤ c preserves bqo’s.

Preserving bqo’s

A definition by Louveau and Saint-Raymond (1990).

Let C be a class of structures with morphisms such that: (i) the identity is a morphism; (ii) morphisms are closed under composition.

Given a quasi-order Q, let

Q ^C = {f : C → Q | C ∈ C} be ordered by

f ₀ ≤ f 1 ⇔ ∃C-morphism g : domf 0 → domf 1 s.t. ∀x ∈ domf ₀ f ₀ (x ) ≤ _Q f ₁ g (x ) Say that C preserves bqo’s if Q ^C is bqo whenever Q is a bqo.

Theorem. (Laver, 1971) The class of σ-scattered linear orders under ≤ i

preserves bqo’s.

Theorem. (van Engelen, Miller, Steel, 1987) The class of countable

linear orders under continuous embeddability ≤ c preserves bqo’s.

Preserving bqo’s

A definition by Louveau and Saint-Raymond (1990).

Let C be a class of structures with morphisms such that: (i) the identity is a morphism; (ii) morphisms are closed under composition.

Given a quasi-order Q, let

Q ^C = {f : C → Q | C ∈ C}

be ordered by

f ₀ ≤ f 1 ⇔ ∃C-morphism g : domf 0 → domf 1 s.t. ∀x ∈ domf ₀ f ₀ (x ) ≤ _Q f ₁ g (x ) Say that C preserves bqo’s if Q ^C is bqo whenever Q is a bqo.

Theorem. (Laver, 1971) The class of σ-scattered linear orders under ≤ i

preserves bqo’s.

Theorem. (van Engelen, Miller, Steel, 1987) The class of countable

linear orders under continuous embeddability ≤ c preserves bqo’s.

Preserving bqo’s

A definition by Louveau and Saint-Raymond (1990).

Let C be a class of structures with morphisms such that: (i) the identity is a morphism; (ii) morphisms are closed under composition.

Given a quasi-order Q, let

Q ^C = {f : C → Q | C ∈ C}

be ordered by

f ₀ ≤ f 1 ⇔ ∃C-morphism g : domf 0 → domf 1 s.t. ∀x ∈ domf ₀ f ₀ (x ) ≤ _Q f ₁ g (x )

Say that C preserves bqo’s if Q ^C is bqo whenever Q is a bqo.

Theorem. (Laver, 1971) The class of σ-scattered linear orders under ≤ i

preserves bqo’s.

Theorem. (van Engelen, Miller, Steel, 1987) The class of countable

linear orders under continuous embeddability ≤ c preserves bqo’s.

Preserving bqo’s

A definition by Louveau and Saint-Raymond (1990).

Let C be a class of structures with morphisms such that: (i) the identity is a morphism; (ii) morphisms are closed under composition.

Given a quasi-order Q, let

Q ^C = {f : C → Q | C ∈ C}

be ordered by

f ₀ ≤ f 1 ⇔ ∃C-morphism g : domf 0 → domf 1 s.t. ∀x ∈ domf ₀ f ₀ (x ) ≤ _Q f ₁ g (x ) Say that C preserves bqo’s if Q ^C is bqo whenever Q is a bqo.

Theorem. (Laver, 1971) The class of σ-scattered linear orders under ≤ i

preserves bqo’s.

Theorem. (van Engelen, Miller, Steel, 1987) The class of countable

linear orders under continuous embeddability ≤ c preserves bqo’s.

Preserving bqo’s

A definition by Louveau and Saint-Raymond (1990).

Let C be a class of structures with morphisms such that: (i) the identity is a morphism; (ii) morphisms are closed under composition.

Given a quasi-order Q, let

Q ^C = {f : C → Q | C ∈ C}

be ordered by

f ₀ ≤ f 1 ⇔ ∃C-morphism g : domf 0 → domf 1 s.t. ∀x ∈ domf ₀ f ₀ (x ) ≤ _Q f ₁ g (x ) Say that C preserves bqo’s if Q ^C is bqo whenever Q is a bqo.

Theorem. (Laver, 1971) The class of σ-scattered linear orders under ≤ i

preserves bqo’s.

Theorem. (van Engelen, Miller, Steel, 1987) The class of countable

linear orders under continuous embeddability ≤ c preserves bqo’s.

Preserving bqo’s

A definition by Louveau and Saint-Raymond (1990).

Let C be a class of structures with morphisms such that: (i) the identity is a morphism; (ii) morphisms are closed under composition.

Given a quasi-order Q, let

Q ^C = {f : C → Q | C ∈ C}

be ordered by

f ₀ ≤ f 1 ⇔ ∃C-morphism g : domf 0 → domf 1 s.t. ∀x ∈ domf ₀ f ₀ (x ) ≤ _Q f ₁ g (x ) Say that C preserves bqo’s if Q ^C is bqo whenever Q is a bqo.

Theorem. (Laver, 1971) The class of σ-scattered linear orders under ≤ i

preserves bqo’s.

Theorem. (van Engelen, Miller, Steel, 1987) The class of countable

linear orders under continuous embeddability ≤ c preserves bqo’s.

The relation of epimorphism ≤ _s

What is the structure of ≤ s ? Does anything like Laver’s theorem hold for

≤ s ? Basic facts

I K ≤ _s L if and only if L = P

i ∈K L _i

I If K is finite and |K | ≤ |L|, then K ≤ s L

I If L has a least (or a last) element while K does not, then K 6≤ s L

I If K , L do not have maximum and K ≤ _s L, then cof (K ) = cof (L).

Similarly if they do not have minimum.

The relation of epimorphism ≤ _s

What is the structure of ≤ s ? Does anything like Laver’s theorem hold for

≤ s ?

Basic facts

I K ≤ _s L if and only if L = P

i ∈K L _i

I If K is finite and |K | ≤ |L|, then K ≤ s L

I If L has a least (or a last) element while K does not, then K 6≤ s L

I If K , L do not have maximum and K ≤ _s L, then cof (K ) = cof (L).

Similarly if they do not have minimum.

The relation of epimorphism ≤ _s

What is the structure of ≤ s ? Does anything like Laver’s theorem hold for

≤ s ? Basic facts

I K ≤ _s L if and only if L = P

i ∈K L _i

I If K is finite and |K | ≤ |L|, then K ≤ s L

I If L has a least (or a last) element while K does not, then K 6≤ s L

I If K , L do not have maximum and K ≤ _s L, then cof (K ) = cof (L).

Similarly if they do not have minimum.

The relation of epimorphism ≤ _s

What is the structure of ≤ s ? Does anything like Laver’s theorem hold for

≤ s ? Basic facts

I K ≤ _s L if and only if L = P

i ∈K L _i

I If K is finite and |K | ≤ |L|, then K ≤ s L

I If L has a least (or a last) element while K does not, then K 6≤ s L

I If K , L do not have maximum and K ≤ _s L, then cof (K ) = cof (L).

Similarly if they do not have minimum.

The relation of epimorphism ≤ _s

What is the structure of ≤ s ? Does anything like Laver’s theorem hold for

≤ s ? Basic facts

I K ≤ _s L if and only if L = P

i ∈K L _i

I If K is finite and |K | ≤ |L|, then K ≤ s L

I If L has a least (or a last) element while K does not, then K 6≤ s L

I If K , L do not have maximum and K ≤ _s L, then cof (K ) = cof (L).

Similarly if they do not have minimum.

The relation of epimorphism ≤ _s

What is the structure of ≤ s ? Does anything like Laver’s theorem hold for

≤ s ? Basic facts

I K ≤ _s L if and only if L = P

i ∈K L _i

I If K is finite and |K | ≤ |L|, then K ≤ s L

I If L has a least (or a last) element while K does not, then K 6≤ s L

I If K , L do not have maximum and K ≤ _s L, then cof (K ) = cof (L).

Similarly if they do not have minimum.

The structure of ≤ _s on countable orders

Proposition. The relation ≤ s has four minimal elements on infinite orders having countable coinitiality or a minimum, and countable cofinality or a maximum: [ω], [ω + 1], [1 + ω ^∗ ], [ω ^∗ ].

Proposition. Given a countable linear order L:

I L ≤ s η

I L ≤ s 1 + η if and only if L has a minimum

I L ≤ s η + 1 if and only if L has a maximum

I L ≤ _s 1 + η + 1 if and only if L has minimum and maximum Moreover:

I inf([1 + η], [η + 1]) = [1 + η + 1]

I sup([1 + η], [η + 1]) = [η] (this sup can be taken in the class of all

linear orders)

The structure of ≤ _s on countable orders

Proposition. The relation ≤ s has four minimal elements on infinite orders having countable coinitiality or a minimum, and countable cofinality or a maximum: [ω], [ω + 1], [1 + ω ^∗ ], [ω ^∗ ].

Proposition. Given a countable linear order L:

I L ≤ s η

I L ≤ s 1 + η if and only if L has a minimum

I L ≤ s η + 1 if and only if L has a maximum

I L ≤ _s 1 + η + 1 if and only if L has minimum and maximum Moreover:

I inf([1 + η], [η + 1]) = [1 + η + 1]

I sup([1 + η], [η + 1]) = [η] (this sup can be taken in the class of all

linear orders)

The structure of ≤ _s on countable orders

Proposition. The relation ≤ s has four minimal elements on infinite orders having countable coinitiality or a minimum, and countable cofinality or a maximum: [ω], [ω + 1], [1 + ω ^∗ ], [ω ^∗ ].

Proposition. Given a countable linear order L:

I L ≤ _s η

I L ≤ s 1 + η if and only if L has a minimum

I L ≤ s η + 1 if and only if L has a maximum

I L ≤ _s 1 + η + 1 if and only if L has minimum and maximum

Moreover:

I inf([1 + η], [η + 1]) = [1 + η + 1]

I sup([1 + η], [η + 1]) = [η] (this sup can be taken in the class of all

linear orders)

The structure of ≤ _s on countable orders

Proposition. The relation ≤ s has four minimal elements on infinite orders having countable coinitiality or a minimum, and countable cofinality or a maximum: [ω], [ω + 1], [1 + ω ^∗ ], [ω ^∗ ].

Proposition. Given a countable linear order L:

I L ≤ _s η

I L ≤ s 1 + η if and only if L has a minimum

I L ≤ s η + 1 if and only if L has a maximum

I L ≤ _s 1 + η + 1 if and only if L has minimum and maximum Moreover:

I inf([1 + η], [η + 1]) = [1 + η + 1]

I sup([1 + η], [η + 1]) = [η] (this sup can be taken in the class of all

linear orders)

The structure of ≤ _s on countable orders

Proposition. If L is a countable, non-scattered, linear order, then exactly one of the following holds:

1. η ≤ s L

2. L = L 0 + ˆ L with L 0 scattered and η ≤ s ˆ L 3. L = ˆ L + L ₁ , for some L ₁ scattered and η ≤ _s ˆ L

4. L = L 0 + ˆ L + L 1 , for some L 0 , L 1 scattered and η ≤ s ˆ L

In particular, 1 + η + 1 ≤ s L for any countable non-scattered L.

The structure of ≤ _s on countable orders

Proposition. If L is a countable, non-scattered, linear order, then exactly one of the following holds:

1. η ≤ s L

2. L = L 0 + ˆ L with L 0 scattered and η ≤ s ˆ L 3. L = ˆ L + L ₁ , for some L ₁ scattered and η ≤ _s ˆ L

4. L = L 0 + ˆ L + L 1 , for some L 0 , L 1 scattered and η ≤ s ˆ L

In particular, 1 + η + 1 ≤ _s L for any countable non-scattered L.

The structure of ≤ _s on countable orders

Theorem. ≤ s is bqo on countable linear orders.

Sketch of the proof.

• If K is a complete order with minimum and maximum and if K ≤ _i L, then K ≤ _s L. So ≤ _s is a bqo on countable complete orders with minimum and maximum.

• Given L, let ¯ L be obtained by first completing L and then adding a first or a last element, in case L does not have them.

• Define a colouring c L : ¯ L → 3 as follows:

c L (x ) =







0 if x ∈ L

1 if x ∈ {min ¯ L, max ¯ L} \ L 2 otherwise

Denote ≤ col the order on 3 (Linear orders,≤

)

The structure of ≤ _s on countable orders

Theorem. ≤ s is bqo on countable linear orders.

Sketch of the proof.

• If K is a complete order with minimum and maximum and if K ≤ _i L, then K ≤ _s L. So ≤ _s is a bqo on countable complete orders with minimum and maximum.

• Given L, let ¯ L be obtained by first completing L and then adding a first or a last element, in case L does not have them.

• Define a colouring c L : ¯ L → 3 as follows:

c L (x ) =







0 if x ∈ L

1 if x ∈ {min ¯ L, max ¯ L} \ L 2 otherwise

Denote ≤ col the order on 3 (Linear orders,≤

)

The structure of ≤ _s on countable orders

Theorem. ≤ s is bqo on countable linear orders.

Sketch of the proof.

• If K is a complete order with minimum and maximum and if K ≤ _i L, then K ≤ _s L. So ≤ _s is a bqo on countable complete orders with minimum and maximum.

• Given L, let ¯ L be obtained by first completing L and then adding a first or a last element, in case L does not have them.

• Define a colouring c L : ¯ L → 3 as follows:

c L (x ) =







0 if x ∈ L

1 if x ∈ {min ¯ L, max ¯ L} \ L 2 otherwise

Denote ≤ col the order on 3 (Linear orders,≤

)

The structure of ≤ _s on countable orders

Theorem. ≤ s is bqo on countable linear orders.

Sketch of the proof.

• If K is a complete order with minimum and maximum and if K ≤ _i L, then K ≤ _s L. So ≤ _s is a bqo on countable complete orders with minimum and maximum.

• Given L, let ¯ L be obtained by first completing L and then adding a first or a last element, in case L does not have them.

• Define a colouring c L : ¯ L → 3 as follows:

c L (x ) =







0 if x ∈ L

1 if x ∈ {min ¯ L, max ¯ L} \ L 2 otherwise

Denote ≤ col the order on 3 (Linear orders,≤

)

The structure of ≤ _s on countable orders

Theorem. ≤ s is bqo on countable linear orders.

Sketch of the proof.

• If K is a complete order with minimum and maximum and if K ≤ _i L, then K ≤ _s L. So ≤ _s is a bqo on countable complete orders with minimum and maximum.

• Given L, let ¯ L be obtained by first completing L and then adding a first or a last element, in case L does not have them.

• Define a colouring c L : ¯ L → 3 as follows:

c L (x ) =







0 if x ∈ L

1 if x ∈ {min ¯ L, max ¯ L} \ L 2 otherwise

Denote ≤ col the order on 3 (Linear orders,≤

)

The structure of ≤ _s on countable orders

Theorem. ≤ s is bqo on countable linear orders.

Sketch of the proof.

• If K is a complete order with minimum and maximum and if K ≤ _i L, then K ≤ _s L. So ≤ _s is a bqo on countable complete orders with minimum and maximum.

• Given L, let ¯ L be obtained by first completing L and then adding a first or a last element, in case L does not have them.

• Define a colouring c L : ¯ L → 3 as follows:

c L (x ) =







0 if x ∈ L

1 if x ∈ {min ¯ L, max ¯ L} \ L

2 otherwise

Denote ≤ col the order on 3 (Linear orders,≤

)

The structure of ≤ _s on countable orders

Theorem. ≤ s is bqo on countable linear orders.

Sketch of the proof.

• If K is a complete order with minimum and maximum and if K ≤ _i L, then K ≤ _s L. So ≤ _s is a bqo on countable complete orders with minimum and maximum.

• Given L, let ¯ L be obtained by first completing L and then adding a first or a last element, in case L does not have them.

• Define a colouring c L : ¯ L → 3 as follows:

c L (x ) =







0 if x ∈ L

1 if x ∈ {min ¯ L, max ¯ L} \ L 2 otherwise

Denote ≤ col the order on 3 (Linear orders,≤

)

The structure of ≤ _s on countable orders

Theorem. ≤ s is bqo on countable linear orders.

Sketch of the proof.

• If K is a complete order with minimum and maximum and if K ≤ _i L, then K ≤ _s L. So ≤ _s is a bqo on countable complete orders with minimum and maximum.

• Given L, let ¯ L be obtained by first completing L and then adding a first or a last element, in case L does not have them.

• Define a colouring c L : ¯ L → 3 as follows:

c L (x ) =







0 if x ∈ L

1 if x ∈ {min ¯ L, max ¯ L} \ L 2 otherwise

Denote ≤ col the order on 3 (Linear orders,≤

)

The structure of ≤ _s on countable orders

Sketch of proof, continued

• If K , L are linear orders and c K ≤ col c L , then K ≤ s L.

• The theorem of van Engelen, Miller, Steel cannot be directly applied, since if L is non-scattered then ¯ L is uncountable.

• However, if L is countable scattered, then ¯ L is countable and such a theorem can applied: countable scattered linear orders form a bqo under

≤ _s .

• Recall that if L is countable non-scattered, then: L = L 0 + ˆ L + L 1

where L 0 , L 1 are the (possibly empty) scattered tails of L and η ≤ s L (so ˆ

ˆ L ≡ s η). This determines four subclasses of linear orders, according to

whether L 0 , L 1 are empty or not. So it is enough to show that each of

these classes is a bqo.

The structure of ≤ _s on countable orders

Sketch of proof, continued

• If K , L are linear orders and c K ≤ col c L , then K ≤ s L.

• The theorem of van Engelen, Miller, Steel cannot be directly applied, since if L is non-scattered then ¯ L is uncountable.

• However, if L is countable scattered, then ¯ L is countable and such a theorem can applied: countable scattered linear orders form a bqo under

≤ _s .

• Recall that if L is countable non-scattered, then: L = L 0 + ˆ L + L 1

where L 0 , L 1 are the (possibly empty) scattered tails of L and η ≤ s L (so ˆ

ˆ L ≡ s η). This determines four subclasses of linear orders, according to

whether L 0 , L 1 are empty or not. So it is enough to show that each of

these classes is a bqo.

The structure of ≤ _s on countable orders

Sketch of proof, continued

• If K , L are linear orders and c K ≤ col c L , then K ≤ s L.

• The theorem of van Engelen, Miller, Steel cannot be directly applied, since if L is non-scattered then ¯ L is uncountable.

• However, if L is countable scattered, then ¯ L is countable and such a theorem can applied: countable scattered linear orders form a bqo under

≤ _s .

• Recall that if L is countable non-scattered, then: L = L 0 + ˆ L + L 1

where L 0 , L 1 are the (possibly empty) scattered tails of L and η ≤ s L (so ˆ

ˆ L ≡ s η). This determines four subclasses of linear orders, according to

whether L 0 , L 1 are empty or not. So it is enough to show that each of

these classes is a bqo.

The structure of ≤ _s on countable orders

Sketch of proof, continued

• If K , L are linear orders and c K ≤ col c L , then K ≤ s L.

• The theorem of van Engelen, Miller, Steel cannot be directly applied, since if L is non-scattered then ¯ L is uncountable.

• However, if L is countable scattered, then ¯ L is countable and such a theorem can applied: countable scattered linear orders form a bqo under

≤ _s .

• Recall that if L is countable non-scattered, then:

L = L 0 + ˆ L + L 1

where L 0 , L 1 are the (possibly empty) scattered tails of L and η ≤ s L (so ˆ ˆ L ≡ s η).

This determines four subclasses of linear orders, according to

whether L 0 , L 1 are empty or not. So it is enough to show that each of

these classes is a bqo.

The structure of ≤ _s on countable orders

Sketch of proof, continued

• If K , L are linear orders and c K ≤ col c L , then K ≤ s L.

• The theorem of van Engelen, Miller, Steel cannot be directly applied, since if L is non-scattered then ¯ L is uncountable.

• However, if L is countable scattered, then ¯ L is countable and such a theorem can applied: countable scattered linear orders form a bqo under

≤ _s .

• Recall that if L is countable non-scattered, then:

L = L 0 + ˆ L + L 1

where L 0 , L 1 are the (possibly empty) scattered tails of L and η ≤ s L (so ˆ

ˆ L ≡ s η). This determines four subclasses of linear orders, according to

whether L 0 , L 1 are empty or not. So it is enough to show that each of

these classes is a bqo.

The structure of ≤ _s on countable orders

Sketch of proof, continued

• For instance, when both tails are non-empty:

L 0 ≤ s K 0 ∧ L 1 ≤ s K 1 ⇒ L ≤ s K

• Since it has already be shown that ≤ s  (Scattered countable) is bqo, and so such is its square, the map L 7→ (L 0 , L 1 ) witnesses that ≤ s is bqo on countable linear orders with both non-empty scattered tails.

Similarly in the other cases.

The structure of ≤ _s on countable orders

Sketch of proof, continued

• For instance, when both tails are non-empty:

L 0 ≤ s K 0 ∧ L 1 ≤ s K 1 ⇒ L ≤ s K

• Since it has already be shown that ≤ s  (Scattered countable) is bqo, and so such is its square, the map L 7→ (L 0 , L 1 ) witnesses that ≤ s is bqo on countable linear orders with both non-empty scattered tails.

Similarly in the other cases.

The structure of ≤ _s on countable orders

Sketch of proof, continued

• For instance, when both tails are non-empty:

L 0 ≤ s K 0 ∧ L 1 ≤ s K 1 ⇒ L ≤ s K

• Since it has already be shown that ≤ s  (Scattered countable) is bqo, and so such is its square, the map L 7→ (L 0 , L 1 ) witnesses that ≤ s is bqo on countable linear orders with both non-empty scattered tails.

Similarly in the other cases.

Preserving bqo’s

Does ≤ _s preserve bqo’s on countable linear orders?

If the definition is taken verbatim, for sure it does not, since here the

morphisms go in the wrong direction: every increasing ≤ _s -sequence

provide a decreasing sequence in Q countable orders , for any qo Q.

Preserving bqo’s

Does ≤ _s preserve bqo’s on countable linear orders?

If the definition is taken verbatim, for sure it does not, since here the

morphisms go in the wrong direction: every increasing ≤ _s -sequence

provide a decreasing sequence in Q countable orders , for any qo Q.

Preserving bqo’s

A first variation: the domination quasi-order. Define on Q countable orders :

f 0 ≤ ⁰ _s f 1 iff there is an order preserving surjection g : domf 1 → domf 0

such that

∀y f 0 g (y ) ≤ Q f 1 (y )

This notion is too restrictive to preserve bqo’s: already 2 finite orders admits infinite antichains:

01, 0101, 010101, . . .

Preserving bqo’s

A first variation: the domination quasi-order. Define on Q countable orders :

f 0 ≤ ⁰ _s f 1 iff there is an order preserving surjection g : domf 1 → domf 0

such that

∀y f 0 g (y ) ≤ Q f 1 (y )

This notion is too restrictive to preserve bqo’s: already 2 finite orders admits infinite antichains:

01, 0101, 010101, . . .

Preserving bqo’s

A second variation: the Smyth quasi-order. Define on Q countable orders : f 0 ≤ ⁰ _s f 1 iff there is an order preserving surjection g : domf 1 → domf 0

such that

∀x ∈ domf 0 ∃y ∈ domf 1 (g (y ) = x ∧ f ₀ (x ) ≤ _Q f ₁ (y ))

Theorem. Using this definition, the relation ≤ _s on countable linear orders preserves bqo’s.

Proof. Similar to the proof that ≤ s on countable linear orders is bqo.

Preserving bqo’s

A second variation: the Smyth quasi-order. Define on Q countable orders : f 0 ≤ ⁰ _s f 1 iff there is an order preserving surjection g : domf 1 → domf 0

such that

∀x ∈ domf 0 ∃y ∈ domf 1 (g (y ) = x ∧ f ₀ (x ) ≤ _Q f ₁ (y )) Theorem. Using this definition, the relation ≤ _s on countable linear orders preserves bqo’s.

Proof. Similar to the proof that ≤ s on countable linear orders is bqo.

≤ _s on ordinals

Theorem. Let α, β be ordinals. Then

1. If α is a successor ordinal and β is any ordinal, then α ≤ s β ⇔ α ≤ β.

2. If α is a limit ordinal and β is a successor ordinal, then α 6≤ _s β. 3. If α, β are both limit ordinals, with Cantor normal forms

α = ω ^γ

n 0 + . . . + ω ^γ

n k , β = ω ^δ

m 0 + . . . + ω ^δ

m h (that is γ k , δ h > 0), then

α ≤ _s β ⇔ α ≤ β ∧ cof (α) = cof (β) ∧ γ _k ≤ δ h

Corollary. Let β be an ordinal. Then α ≤ _s β for every non-null α ≤ β if and only if β is at most countable and a finite multiple of an

indecomposable ordinal, that is of the form ω ^δ m for some m > 0.

≤ _s on ordinals

Theorem. Let α, β be ordinals. Then

1. If α is a successor ordinal and β is any ordinal, then α ≤ s β ⇔ α ≤ β.

2. If α is a limit ordinal and β is a successor ordinal, then α 6≤ _s β.

3. If α, β are both limit ordinals, with Cantor normal forms α = ω ^γ

n 0 + . . . + ω ^γ

n k , β = ω ^δ

m 0 + . . . + ω ^δ

m h (that is γ k , δ h > 0), then

α ≤ _s β ⇔ α ≤ β ∧ cof (α) = cof (β) ∧ γ _k ≤ δ h

Corollary. Let β be an ordinal. Then α ≤ _s β for every non-null α ≤ β if and only if β is at most countable and a finite multiple of an

indecomposable ordinal, that is of the form ω ^δ m for some m > 0.

≤ _s on ordinals

Theorem. Let α, β be ordinals. Then

1. If α is a successor ordinal and β is any ordinal, then α ≤ s β ⇔ α ≤ β.

2. If α is a limit ordinal and β is a successor ordinal, then α 6≤ _s β.

3. If α, β are both limit ordinals, with Cantor normal forms α = ω ^γ

n 0 + . . . + ω ^γ

n k , β = ω ^δ

m 0 + . . . + ω ^δ

m h (that is γ k , δ h > 0), then

α ≤ _s β ⇔ α ≤ β ∧ cof (α) = cof (β) ∧ γ _k ≤ δ h

Corollary. Let β be an ordinal. Then α ≤ _s β for every non-null α ≤ β if and only if β is at most countable and a finite multiple of an

indecomposable ordinal, that is of the form ω ^δ m for some m > 0.

≤ _s on ordinals

Theorem. Let α, β be ordinals. Then

1. If α is a successor ordinal and β is any ordinal, then α ≤ s β ⇔ α ≤ β.

2. If α is a limit ordinal and β is a successor ordinal, then α 6≤ _s β.

3. If α, β are both limit ordinals, with Cantor normal forms α = ω ^γ

n 0 + . . . + ω ^γ

n k , β = ω ^δ

m 0 + . . . + ω ^δ

m h (that is γ k , δ h > 0), then

α ≤ _s β ⇔ α ≤ β ∧ cof (α) = cof (β) ∧ γ _k ≤ δ h

Corollary. Let β be an ordinal. Then α ≤ _s β for every non-null α ≤ β if and only if β is at most countable and a finite multiple of an

indecomposable ordinal, that is of the form ω ^δ m for some m > 0.

≤ _s on ordinals

Theorem. Let α, β be ordinals. Then

1. If α is a successor ordinal and β is any ordinal, then α ≤ s β ⇔ α ≤ β.

2. If α is a limit ordinal and β is a successor ordinal, then α 6≤ _s β.

3. If α, β are both limit ordinals, with Cantor normal forms α = ω ^γ

n 0 + . . . + ω ^γ

n k , β = ω ^δ

m 0 + . . . + ω ^δ

m h (that is γ k , δ h > 0), then

α ≤ _s β ⇔ α ≤ β ∧ cof (α) = cof (β) ∧ γ _k ≤ δ h

Corollary. Let β be an ordinal. Then α ≤ _s β for every non-null α ≤ β if and only if β is at most countable and a finite multiple of an

indecomposable ordinal, that is of the form ω ^δ m for some m > 0.

Highly surjective orders

The previous fact suggests a definition:

A linear order is highly surjective if, for any linear order K , K ≤ i L ⇒ K ≤ s L

that is, L surjects order-preservingly onto any of its suborders.

Highly surjective countable ordinals form a Π ¹ ₂ set. It is also Σ ¹ ₁ -hard.

We do not know any sharper classification.

Highly surjective orders

The previous fact suggests a definition:

A linear order is highly surjective if, for any linear order K , K ≤ i L ⇒ K ≤ s L

that is, L surjects order-preservingly onto any of its suborders.

Highly surjective countable ordinals form a Π ¹ ₂ set. It is also Σ ¹ ₁ -hard.

We do not know any sharper classification.

Highly surjective orders

The previous fact suggests a definition:

A linear order is highly surjective if, for any linear order K , K ≤ i L ⇒ K ≤ s L

that is, L surjects order-preservingly onto any of its suborders.

Highly surjective countable ordinals form a Π ¹ ₂ set. It is also Σ ¹ ₁ -hard.

We do not know any sharper classification.

Highly surjective orders

Some basic properties. • If L is highly surjective, then L ^∗ is highly surjective.

• If L is highly surjective and M ≡ s L, then M is highly surjective.

• If I is any order and L i is highly surjective for any i ∈ I , then P

i ∈I L i is highly surjective iff P

j ∈J L j ≤ s P

ı∈I L i for every non-empty J ⊆ I .

• If L is strongly surjective, the so are:

I Ln and nL, for any positive integer n

I Lω and ωL

I Lω ^∗ and ω ^∗ L

I Lζ and ζL

I Lη, under the additional hypothesis that L is at most countable

I L ⁿ , for any n ∈ N

Examples of highly surjective orders.

• (ω ^γ n) ^∗ + ω ^δ m for γ, δ countable non-null ordinals and n + m > 0.

• ζ ^α m, for α countable and m > 0.

Highly surjective orders

Some basic properties. • If L is highly surjective, then L ^∗ is highly surjective.

• If L is highly surjective and M ≡ s L, then M is highly surjective.

• If I is any order and L i is highly surjective for any i ∈ I , then P

i ∈I L i is highly surjective iff P

j ∈J L j ≤ s P

ı∈I L i for every non-empty J ⊆ I .

• If L is strongly surjective, the so are:

I Ln and nL, for any positive integer n

I Lω and ωL

I Lω ^∗ and ω ^∗ L

I Lζ and ζL

I Lη, under the additional hypothesis that L is at most countable

I L ⁿ , for any n ∈ N

Examples of highly surjective orders.

• (ω ^γ n) ^∗ + ω ^δ m for γ, δ countable non-null ordinals and n + m > 0.

• ζ ^α m, for α countable and m > 0.

Highly surjective orders

Some basic properties. • If L is highly surjective, then L ^∗ is highly surjective.

• If L is highly surjective and M ≡ s L, then M is highly surjective.

• If I is any order and L i is highly surjective for any i ∈ I , then P

i ∈I L i is highly surjective iff P

j ∈J L j ≤ s P

ı∈I L i for every non-empty J ⊆ I .

• If L is strongly surjective, the so are:

I Ln and nL, for any positive integer n

I Lω and ωL

I Lω ^∗ and ω ^∗ L

I Lζ and ζL

I Lη, under the additional hypothesis that L is at most countable

I L ⁿ , for any n ∈ N

Examples of highly surjective orders.

• (ω ^γ n) ^∗ + ω ^δ m for γ, δ countable non-null ordinals and n + m > 0.

• ζ ^α m, for α countable and m > 0.

Highly surjective orders

Some basic properties. • If L is highly surjective, then L ^∗ is highly surjective.

• If L is highly surjective and M ≡ s L, then M is highly surjective.

• If I is any order and L i is highly surjective for any i ∈ I , then P

i ∈I L i is highly surjective iff P

j ∈J L j ≤ s P

ı∈I L i for every non-empty J ⊆ I .

• If L is strongly surjective, the so are:

I Ln and nL, for any positive integer n

I Lω and ωL

I Lω ^∗ and ω ^∗ L

I Lζ and ζL

I Lη, under the additional hypothesis that L is at most countable

I L ⁿ , for any n ∈ N

Examples of highly surjective orders.

• (ω ^γ n) ^∗ + ω ^δ m for γ, δ countable non-null ordinals and n + m > 0.

• ζ ^α m, for α countable and m > 0.

Highly surjective orders

Some basic properties. • If L is highly surjective, then L ^∗ is highly surjective.

• If L is highly surjective and M ≡ s L, then M is highly surjective.

• If I is any order and L i is highly surjective for any i ∈ I , then P

i ∈I L i is highly surjective iff P

j ∈J L j ≤ s P

ı∈I L i for every non-empty J ⊆ I .

• If L is strongly surjective, the so are:

I Ln and nL, for any positive integer n

I Lω and ωL

I Lω ^∗ and ω ^∗ L

I Lζ and ζL

I Lη, under the additional hypothesis that L is at most countable

I L ⁿ , for any n ∈ N

Examples of highly surjective orders.

• (ω ^γ n) ^∗ + ω ^δ m for γ, δ countable non-null ordinals and n + m > 0.

• ζ ^α m, for α countable and m > 0.

Searching for un uncountable highly surjective order

Question. Is there an uncountable highly surjective linear order?

Theorem. A strongly surjective linear order L is short, that is

ω ₁ 6≤ i L, ω ^∗ ₁ 6≤ i L. Moreover, if it has a minimum it must be an ordinal and if it has a maximum it must be the reverse of an ordinal.

Corollary. The cardinality of a highly surjective linear order cannot

exceed the continuum.

Searching for un uncountable highly surjective order

Question. Is there an uncountable highly surjective linear order?

Theorem. A strongly surjective linear order L is short, that is

ω ₁ 6≤ i L, ω ^∗ ₁ 6≤ i L. Moreover, if it has a minimum it must be an ordinal and if it has a maximum it must be the reverse of an ordinal.

Corollary. The cardinality of a highly surjective linear order cannot

exceed the continuum.

Searching for un uncountable highly surjective order

Question. Is there an uncountable highly surjective linear order?

Theorem. A strongly surjective linear order L is short, that is

ω ₁ 6≤ i L, ω ^∗ ₁ 6≤ i L. Moreover, if it has a minimum it must be an ordinal and if it has a maximum it must be the reverse of an ordinal.

Corollary. The cardinality of a highly surjective linear order cannot

exceed the continuum.

Searching for an uncountable highly surjective order

So one can try to build natural candidates for being uncountable highly surjective orders using θ (the order type of the irrationals) and λ (the order types of the reals.

However, these do not work:

Theorem. The only product ρ 0 · . . . · ρ n , where each ρ i is one of η, θ, λ,

that is highly surjective is η.

Searching for an uncountable highly surjective order

So one can try to build natural candidates for being uncountable highly surjective orders using θ (the order type of the irrationals) and λ (the order types of the reals.

However, these do not work:

Theorem. The only product ρ ₀ · . . . · ρ _n , where each ρ _i is one of η, θ, λ,

that is highly surjective is η.