Null-Additivity in the Theory of Algorithmic Randomness

カテゴリ

研究論文

概要

In this paper, we develop a general framework integrating algorithmic and higher randomness theories.
We clarify the relationship of the notions of {\em triviality} and {\em uniform-lowness} in algorithmic randomness theory and {\em null-additivity} in set theory by effectivizing combinatorial characterizations of transitive additivity in set theory of the real line.
For instance, we show that the following three conditions are equivalent for an infinite binary sequence : (1) is low for Kurtz randomness with respect to uniform relativization; (2) is effectively -additive; (3) is Kurtz random whenever is Kurtz random.
Additionally, we study levels of uniformity associated with lowness for randomness and additivity numbers over various levels of algorithmic/higher randomness theories.
We also clarify the relationship between the Ku\v{c}era-Gács Theorem and strong measure zero sets of reals over Spector pointclasses, and we show an abstract version of the Ku\v{c}era-Gács Theorem stating that for every Spector pointclass , every real is -weak-truth-reducible to a -Martin-Löf random real.

Unified characterizations of lowness properties via Kolmogorov complexity

カテゴリ

研究論文

概要

There are at least two different ways to relativize each randomness notion (hence, there are two different kinds of lowness notions for any pair of randomness notions), one of which is usual oracle relativization and the other is uniform relativization. We characterize such lowness notions relating to Martin-Löf randomness, Schnorr randomness and Kurtz radomness via traceability, and variants of complexity, which clearly reveals unified correspondence among them. For instance, it is shown that an infinite binary sequence is uniformly-low for Martin-Löf randomness versus Schnorr randomness if and only if it is c.e. tt-traceable if and only if it is anticomplex if and only if it is Martin-Löf packing measure zero with respect to all computable dimension functions; and that an infinite binary sequence is uniformly-low for Schnorr randomness versus Kurtz randomness if and only if it is computably i.o. tt-traceable if and only if it is not totally complex if and only if it is Schnorr Hausdorff measure zero with respect to all computable dimension functions. One of the latter equivalences is proved by using Pawlikowski's characterization of strong measure zero in the set theory of the real line.

Inside the Muchnik Degrees II: The Degree Structures induced by the Arithmetical Hierarchy of Countably Continuous Functions

カテゴリ

研究論文

概要

It is known that infinitely many Medvedev degrees exist inside the Muchnik degree of any nontrivial subset of Cantor space. We shed light on the fine structures inside these Muchnik degrees related to learnability and piecewise computability. As for nonempty subsets of Cantor space, we show the existence of a finite--piecewise degree containing infinitely many finite--piecewise degrees, and a finite--piecewise degree containing infinitely many finite--piecewise degrees (where denotes the difference of two sets), whereas the greatest degrees in these three ``finite--piecewise'' degree structures coincide. Moreover, as for nonempty subsets of Cantor space, we also show that every nonzero finite--piecewise degree includes infinitely many Medvedev (i.e., one-piecewise) degrees, every nonzero countable--piecewise degree includes infinitely many finite-piecewise degrees, every nonzero finite--countable--piecewise degree includes infinitely many countable--piecewise degrees, and every nonzero Muchnik (i.e., countable--piecewise) degree includes infinitely many finite--countable--piecewise degrees. Indeed, we show that any nonzero Medvedev degree and nonzero countable--piecewise degree of a nonempty subset of Cantor space have the strong anticupping properties. Finally, we obtain an elementary difference between the Medvedev (Muchnik) degree structure and the finite--piecewise degree structure of all subsets of Baire space by showing that none of the finite--piecewise structures are Brouwerian, where is any of the Wadge classes mentioned above.

Decomposing Borel Functions using the Shore-Slaman Join Theorem

カテゴリ

研究論文

概要

Jayne and Rogers proved that every function from an analytic space into a separable metric space is decomposable into countably many continuous functions with closed domains if and only if the preimage of each set under it is again . Several researchers conjectured that the Jayne-Rogers theorem can be generalized to all finite levels of Borel functions. In this paper, by using the Shore-Slaman join theorem on the Turing degrees, we show the following variant of the Jayne-Rogers theorem at finite and transfinite levels of the hierarchy of Borel functions: For all countable ordinals and with , every function between Polish spaces with small inductive dimension is decomposable into countably many -measurable functions with domains and a sequence such that if and only if, from each set, one can continuously find its preimage.