scientific article; zbMATH DE number 3559552

From MaRDI portal
Publication:4132513





Let \(\Omega\) be the set of all infinite binary sequences. Let further \(\mathcal D\) be the class of all \(A\subseteq\Omega\) which are unions of Turing degrees and measurable by the universal enumerable (semicomputable) measure [\textit{A. K. Zvonkin} and \textit{L. A. Levin}, Uspehi mat. Nauk 25, Nr. 6(156), 85-127 (1970; Zbl 0222.02027)]. A set is called negligible iff the universal enumerable measure of \(A\) is \(0\). The preorder ``\(A\leq B\leftrightarrow A\smallsetminus B\) negligible on \(\mathcal D\) is introduced and the quotient \(L=_{df}\mathcal D/_\equiv\) is investigated, \((A\equiv B\leftrightarrow A\leq B\wedge B\leq A)\). lt turns out that [\(L,\leq\)] is a Boolean algebra whose operations are induced by set-theoretic union and intersection. Further four elements of \(L\) are known: \(0, 1\), the set a defined by all computable sequences, and the set b defined by all sequences random in the sense of Kolmogorov and Martin-Löf and those sequences Turing-equivalent to them. The following result guarantees the existence of a further element of \(L\): There exist an effective operator \(F\) and a set \(B\subseteq\Omega\) such that \(B\) is included in the domain of \(F\) (and coincides with it except for a set of measure 0), \(\mu(B)>0\), and \(\mu(G(F(B))) =0\) for every effective operator \(G\) (\(\mu\) is the Lebesgue measure). Moreover, \(F(B)\) does not contain computable sequences.











This page was built for publication:

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