Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTuring Degrees and Randomness for Continuous Measures
122
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We study degree-theoretic properties of reals that are not random with respect to any continuous probability measure (NCR). To this end, we introduce a family of generalized Hausdorff measures based on the iterates of the dissipation function of a continuous measure and study the effective nullsets given by the corresponding Solovay tests. We introduce two constructions that preserve non-randomness with respect to a given continuous measure. This enables us to prove the existence of NCR reals in a number of Turing degrees. In particular, we show that every $Delta^0_2$-degree contains an NCR element.
rate research
Read More
We investigate which infinite binary sequences (reals) are effectively random with respect to some continuous (i.e., non-atomic) probability measure. We prove that for every n, all but countably many reals are n-random for such a measure, where n indicates the arithmetical complexity of the Martin-Lof tests allowed. The proof is based on a Borel determinacy argument and presupposes the existence of infinitely many iterates of the power set of the natural numbers. In the second part of the paper we present a metamathematical analysis showing that this assumption is indeed necessary. More precisely, there exists a computable function G such that, for any n, the statement `All but countably many reals are G(n)-random with respect to a continuous probability measure cannot be proved in $ZFC^-_n$. Here $ZFC^-_n$ stands for Zermelo-Fraenkel set theory with the Axiom of Choice, where the Power Set Axiom is replaced by the existence of n-many iterates of the power set of the natural numbers. The proof of the latter fact rests on a very general obstruction to randomness, namely the presence of an internal definability structure.
The Posner-Robinson Theorem states that for any reals $Z$ and $A$ such that $Z oplus 0 leq_mathrm{T} A$ and $0 <_mathrm{T} Z$, there exists $B$ such that $A equiv_mathrm{T} B equiv_mathrm{T} B oplus Z equiv_mathrm{T} B oplus 0$. Consequently, any nonzero Turing degree $operatorname{deg}_mathrm{T}(Z)$ is a Turing jump relative to some $B$. Here we prove the hyperarithmetical analog, based on an unpublished proof of Slaman, namely that for any reals $Z$ and $A$ such that $Z oplus mathcal{O} leq_mathrm{T} A$ and $0 <_mathrm{HYP} Z$, there exists $B$ such that $A equiv_mathrm{T} mathcal{O}^B equiv_mathrm{T} B oplus Z equiv_mathrm{T} B oplus mathcal{O}$. As an analogous consequence, any nonhyperarithmetical Turing degree $operatorname{deg}_mathrm{T}(Z)$ is a hyperjump relative to some $B$.
We study pairs of reals that are mutually Martin-L{o}f random with respect to a common, not necessarily computable probability measure. We show that a generalized version of van Lambalgens Theorem holds for non-computable probability measures, too. We study, for a given real $A$, the emph{independence spectrum} of $A$, the set of all $B$ so that there exists a probability measure $mu$ so that $mu{A,B} = 0$ and $(A,B)$ is $mutimesmu$-random. We prove that if $A$ is r.e., then no $Delta^0_2$ set is in the independence spectrum of $A$. We obtain applications of this fact to PA degrees. In particular, we show that if $A$ is r.e. and $P$ is of PA degree so that $P otgeq_{T} A$, then $A oplus P geq_{T} 0$.
We define the bounded jump of A by A^b = {x | Exists i <= x [phi_i (x) converges and Phi_x^[A|phi_i(x)](x) converges} and let A^[nb] denote the n-th bounded jump. We demonstrate several properties of the bounded jump, including that it is strictly increasing and order preserving on the bounded Turing (bT) degrees (also known as the weak truth-table degrees). We show that the bounded jump is related to the Ershov hierarchy. Indeed, for n > 1 we have X <=_[bT] 0^[nb] iff X is omega^n-c.e. iff X <=_1 0^[nb], extending the classical result that X <=_[bT] 0 iff X is omega-c.e. Finally, we prove that the analogue of Shoenfield inversion holds for the bounded jump on the bounded Turing degrees. That is, for every X such that 0^b <=_[bT] X <=_[bT] 0^[2b], there is a Y <=_[bT] 0^b such that Y^b =_[bT] X.
We study the question, ``For which reals $x$ does there exist a measure $mu$ such that $x$ is random relative to $mu$? We show that for every nonrecursive $x$, there is a measure which makes $x$ random without concentrating on $x$. We give several conditions on $x$ equivalent to there being continuous measure which makes $x$ random. We show that for all but countably many reals $x$ these conditions apply, so there is a continuous measure which makes $x$ random. There is a meta-mathematical aspect of this investigation. As one requires higher arithmetic levels in the degree of randomness, one must make use of more iterates of the power set of the continuum to show that for all but countably many $x$s there is a continuous $mu$ which makes $x$ random to that degree.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
