Independence, relative randomness, and PA degrees

We study pairs of reals that are mutually Martin-Lรถf random with respect to a common, not necessarily computable probability measure. We show that a generalized version of van Lambalgen's Theorem holds for non-computable probability measures, too. We study, for a given real A, the 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 (mu x mu)-random. We prove that if A is c.e., then no Delta02 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 c.e. and P is of PA degree so that P is not recursive in A, then A + P computes the halting problem.



Work Title Independence, relative randomness, and PA degrees
Open Access
  1. Jan Reimann
  1. Algorithmic Randomness
  2. Peano Arithmetic
License Attribution-NonCommercial-NoDerivs 3.0 United States
Work Type Research Paper
Deposited September 25, 2012




This resource is currently not in any collection.

Work History

Version 1

  • Created
  • Added x0k225d869_version1_no_original_label.pdf
  • Added Creator Jan Reimann
  • Published