{
  "id": "1808.10102",
  "version": "v1",
  "published": "2018-08-30T03:42:12.000Z",
  "updated": "2018-08-30T03:42:12.000Z",
  "title": "Effective Randomness for Continuous Measures",
  "authors": [
    "Jan Reimann",
    "Theodore A. Slaman"
  ],
  "categories": [
    "math.LO"
  ],
  "abstract": "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-L\\\"of 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.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2018-08-30T03:42:12.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "03D32",
      "03E45"
    ],
    "keywords": [
      "effective randomness",
      "continuous measures",
      "probability measure",
      "natural numbers",
      "power set axiom"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}