Universality of embeddability relations for coloured total orders (Q2492801)

Let \(R\) be a fixed quasi-ordering (i.e.\ a reflexive and transitive binary relation) on \(\mathbb N\). If \(\sqsubseteq\) is a linear order on \(\mathbb N\) and \(\varphi: \mathbb N \to \mathbb N\), we consider the pair \(({\sqsubseteq}, \varphi)\) as a labeled (or colored) linear order, with labels coming from \(R\). Two such labeled linear orders are compared by setting \(({\sqsubseteq}, \varphi) \preceq_R ({\sqsubseteq'}, \varphi')\) if and only if there exists \(g: \mathbb N \to \mathbb N\) which preserves the ordering (i.e.\ \(g(n) \sqsubseteq' g(m)\) whenever \(n \sqsubseteq m\)) and increases the labels (i.e.\ \(\varphi(n) \,R\, \varphi'(g(n))\) for every \(n\)). \(\preceq_R\) is easily seen to be a quasi-ordering. In his celebrated proof of Fraïssé's conjecture, \textit{R. Laver} [Ann.\ Math.\ (2) 93, 89--111 (1971; Zbl 0208.28905)] showed that if \(R\) is a better quasi-ordering then so is \(\preceq_R\), and in particular in this case \(\preceq_R\) contains neither infinite antichains nor infinite descending sequences. It is straightforward to equip the space of all labeled linear orders \(\roman{LO} \times \mathbb N^\mathbb N\) with a Polish topology and to check that \(\preceq_R\) is an analytic (or \(\boldsymbol\Sigma^1_1\)) quasi-ordering on this space. Thus the classification of \(\preceq_R\) under different hypotheses on \(R\) falls within the scope of descriptive set theory. \textit{A. Marcone} and \textit{C. Rosendal} [J. Symb.\ Log.\ 69, 663--673 (2004; Zbl 1072.03027)] showed that if \(R\) contains an infinite antichain then \(\preceq_R\) is a \(\boldsymbol\Sigma^1_1\)-complete quasi-ordering. This means that any analytic quasi-ordering \(\leq\) on any Polish space \(X\) is Borel reducible to \(\preceq_R\), i.e.\ there exists a Borel function \(f: X \to \roman{LO} \times \mathbb N^\mathbb N\) such that \(f(x) \preceq_R f(y)\) if and only if \(x \leq y\). The systematic study of \(\boldsymbol\Sigma^1_1\)-complete quasi-orderings was started by \textit{A. Louveau} and \textit{C. Rosendal} [Trans.\ Am.\ Math.\ Soc.\ 357, 4839--4866 (2005; Zbl 1118.03043)]. In this paper the result of Marcone and Rosendal is extended by showing that the same conclusion holds also under the hypothesis that \(R\) contains an infinite descending sequence (actually Camerlo's proof yields both results at once). Therefore, if \(R\) is not a well quasi-ordering then \(\preceq_R\) contains copies of all possible analytic quasi-orderings and is therefore very rich and complex. The question of what happens when \(R\) is a well quasi-ordering but not a better quasi-ordering is stated as an open problem. The second part of the paper deals with labelings of the rationals. In this case it makes sense to consider also a more restrictive notion of order-preserving maps: a function \(g: \mathbb Q \to \mathbb Q\) is dense order-preserving if, whenever \(g(q_0) < r_0 < r_1 < g(q_1)\), there exists \(q\) with \(q_0 < q < q_1\) and \(r_0 < g(q) < r_1\). This notion was introduced by Marcone and Rosendal and is equivalent to the existence of a continuous strictly increasing extension of \(g\) to the real line. In this paper the results of Marcone and Rosendal are extended: if \(R\) has two incomparable elements then the relation of dense order-preserving embeddability of linear orders colored with \(R\) is a \(\boldsymbol\Sigma^1_1\)-complete quasi-ordering. This yields also an improvement of the applications of these results to continuous embeddability of dendrites (in the sense of continuum theory): the quasi-ordering of continuous embeddability between dendrites with all branching points of order at most \(3\) is \(\boldsymbol\Sigma^1_1\)-complete.