Linearization of definable order relations (Q1964145): Difference between revisions

It is well known that every partial quasi-order (PQO) is linearizable, i.e., it can be extended to a linear order on the same domain. However not every Borel PQO is Borel linearizable. For example, if \(E_0\) is an equivalence relation defined on \(2^{\omega}\) as follows: \(\langle a,b\rangle \in E_0\) iff \(a(k)=b(k)\) for all but finite \(k\), then it is not Borel linearizable [see \textit{L. A.~Harrington, D.~Marker} and \textit{S.~Shelah}, Trans. Am. Math. Soc. 310, 293-302 (1988; Zbl 0707.03042)]. Similarly, the anti-lexicographical partial order \(\leq_0\) on \(2^{\omega}\) is not Borel linearizable. In fact, the author proved that \(\leq_0\) is a minimal Borel-nonlinearizable Borel order in the following sense: for every Borel PQO \(\preceq\) on \({\mathcal N}=\omega^{\omega}\) either: (i) \(\preceq\) is Borel linearizable, or (ii) there exists a continuous half-order-preserving 1-1 map \(F\colon \langle 2^{\omega}, \leq_0\rangle\to \langle{\mathcal N}, \preceq\rangle\) such that \(\langle a,b\rangle \not\in E_0\) implies \(F(a)\not\preceq F(b)\) [see \textit{V.~Kanovei}, Fundam. Math 155, 301-309 (1998; Zbl 0909.03041)]. The paper contains similar dichotomical linearization theorems for some non-Borel partial orders, including: \(\bullet\)~analytic and bi-\(\kappa\)-Souslin (\(\kappa>\omega_1\)) orders [see \textit{S.~Shelah}, Isr. J. Math 47, 139-153 (1984; Zbl 0561.03026)]; \(\bullet\)~definable orders in the Solovay model [\textit{R.~M.~Solovay}, Ann. Math., II. Ser. 92, 1-56 (1970; Zbl 0207.00905)].