Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userIndependence, Relative Randomness, and PA Degrees
200
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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$.
rate research
Read More
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.
An element $a$ of a lattice cups to an element $b > a$ if there is a $c < b$ such that $a cup c = b$. An element of a lattice has the cupping property if it cups to every element above it. We prove that there are non-zero honest elementary degrees that do not have the cupping property, which answers a question of Kristiansen, Schlage-Puchta, and Weiermann. In fact, we show that if $mathbf b$ is a sufficiently large honest elementary degree, then there is a non-zero honest elementary degree $mathbf a <_{mathrm E} mathbf b$ that does not cup to $mathbf b$. For comparison, we modify a result of Cai to show that in sever
We compare the degrees of enumerability and the closed Medvedev degrees and find that many situations occur. There are nonzero closed degrees that do not bound nonzero degrees of enumerability, there are nonzero degrees of enumerability that do not bound nonzero closed degrees, and there are degrees that are nontrivially both degrees of enumerability and closed degrees. We also show that the compact degrees of enumerability exactly correspond to the cototal enumeration degrees.
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.
Algorithmic randomness theory starts with a notion of an individual random object. To be reasonable, this notion should have some natural properties; in particular, an object should be random with respect to image distribution if and only if it has a random preimage. This result (for computable distributions and mappings, and Martin-Lof randomness) was known for a long time (folklore); in this paper we prove its natural generalization for layerwise computable mappings, and discuss the related quantitative results.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
