Linearization of definable order relations. (English) Zbl 0942.03055

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 L. A. Harrington, D. Marker and 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 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 S. Shelah, Isr. J. Math 47, 139-153 (1984; Zbl 0561.03026)];
\(\bullet\) definable orders in the Solovay model [R. M. Solovay, Ann. Math., II. Ser. 92, 1-56 (1970; Zbl 0207.00905)].


03E15 Descriptive set theory
03E35 Consistency and independence results
06A05 Total orders
06A06 Partial orders, general
Full Text: DOI arXiv


[1] S.D. Friedman, B. Velickovic, Nonstandard models and analytic equivalence relations, Proc. Amer. Math. Soc. to appear. · Zbl 0864.03033
[2] Harrington, L.A.; Kechris, A.S.; Louveau, A., A glimm – effros dichotomy for Borel equivalence relations, J. amer. math. soc., 3, 903-928, (1990) · Zbl 0778.28011
[3] Harrington, L.A.; Marker, D.; Shelah, S., Borel orderings, Trans. amer. math. soc., 310, 293-302, (1988) · Zbl 0707.03042
[4] L.A. Harrington, S. Shelah, Counting equivalence classes for co-κ-Souslin equivalence relations, D. van Dalen et al. (Eds.), Proc. Conf. in Prague (LC‘80), North-Holland, Amsterdam, 1982, pp. 147-152. · Zbl 0513.03024
[5] G. Hjorth, A remark on Φ11 equivalence relations, Handwritten note.
[6] Hjorth, G., Thin equivalence relations and effective decompositions, J. symbolic logic, 58, 1153-1164, (1993) · Zbl 0793.03051
[7] Hjorth, G.; Kechris, A.S., Analytic equivalence relations and ulm – type classification, J. symbolic logic, 60, 1273-1299, (1995) · Zbl 0847.03023
[8] Kanovei, V., An ulm – type classification theorem for equivalence relations in Solovay model, J. symbolic logic, 62, 1333-1351, (1997) · Zbl 0895.03020
[9] Kanovei, V., Two dichotomy theorems on colourability of non-analytic graphs, Fund. math., 154, 183-201, (1997) · Zbl 0883.03035
[10] Kanovei, V., Ulm classification of analytic equivalence relations in generic universes, Math. log. quart., 44, 287-303, (1998) · Zbl 0921.03048
[11] Kanovei, V., When a partial Borel order is Borel linearizable, Fund. math., 155, 301-309, (1998) · Zbl 0909.03041
[12] Kechris, A., Classical descriptive set theory, (1995), Springer Berlin · Zbl 0819.04002
[13] Louveau, A., Two results on Borel orders, J. symbolic logic, 54, 865-874, (1989) · Zbl 0687.03028
[14] Shelah, S., On co-κ-souslin relations, Israel J. math., 47, 139-153, (1984) · Zbl 0561.03026
[15] Solovay, R.M., A model of set theory in which every set of reals is Lebesgue measurable, Ann. math., 92, 1-56, (1970) · Zbl 0207.00905
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.