Linearization of definable order relations

DOI10.1016/S0168-0072(99)00013-5MaRDI QIDQ1964145zbMATH OpenFDO

Authors Vladimir Kanovei

Publication date 15 August 2000

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/9706204

zbMATH Keywords

linear orderlinearizationnon-Borel partial ordersSolovay modelSouslin relation

Mathematics Subject Classification ID

Descriptive set theory (03E15) Consistency and independence results (03E35) Total orders (06A05) Partial orders, general (06A06)

Abstract: We prove that if $leq$ is an analytic partial order then either $leq$ can be extended to a (boldface) $Delt{a}_2^1$ linear order similar to an antichain in $2^{<omeg{a}_1}$ ordered lexicographically or a certain Borel partial order $le{q}_0$ embeds in $leq.$ Some corollaries for analytic equivalence relations are given, for instance, if $E$ is a $Sigm{a}_1^1[z]$ equivalence relation such that $E_0$ does not embed in $E$ then $E$ is determined by intersections with E-invariand Borel sets coded in $L[z]$.

Review text

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)].

Recommendations

• When a partial Borel order is linearizable
• Linear extensions of partial orders and reverse mathematics
• On the quasi-ordering of Borel linear orders under embeddability
• Borel Orderings
• Two results on borel orders

Cites work

• A Glimm-Effros Dichotomy for Borel Equivalence Relations
• A model of set-theory in which every set of reals is Lebesgue measurable
• An Ulm-type classification theorem for equivalence relations in Solovay model
• Analytic equivalence relations and Ulm-type classifications
• Borel Orderings
• scientific article; zbMATH DE number 3809544 (Why is no real title available?)
• scientific article; zbMATH DE number 722611 (Why is no real title available?)
• scientific article; zbMATH DE number 1083160 (Why is no real title available?)
• Nonstandard models and analytic equivalence relations
• On co-\(\kappa\)-Souslin relations
• Thin equivalence relations and effective decompositions
• Two results on borel orders
• Ulm Classification of Analytic Equivalence Relations in Generic Universes
• When a partial Borel order is linearizable

Cited in

(11)

• Codings on linear orders and algorithmic independence of natural relations
• On countable cofinality and decomposition of definable thin orderings
• A note on the expressive power of linear orders
• Borel Orderings
• Linear Orders in the Pushdown Hierarchy
• Glimm-Effros for coanalytic equivalence relations
• Relations Intrinsically Recursive in Linear Orders
• scientific article; zbMATH DE number 68156 (Why is no real title available?)
• When a partial Borel order is linearizable
• An infinity which depends on the axiom of choice
• scientific article; zbMATH DE number 1827968 (Why is no real title available?)

This page was built for publication: Linearization of definable order relations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1964145)