An important theorem of geometric measure theory (first proved by Besicovitch and Davies for Euclidean space) says that every analytic set of non-zero $s$-dimensional Hausdorff measure $mathcal H^s$ contains a closed subset of non-zero (and indeed fi
nite) $mathcal H^s$-measure. We investigate the question how hard it is to find such a set, in terms of the index set complexity, and in terms of the complexity of the parameter needed to define such a closed set. Among other results, we show that given a (lightface) $Sigma^1_1$ set of reals in Cantor space, there is always a $Pi^0_1(mathcal{O})$ subset on non-zero $mathcal H^s$-measure definable from Kleenes $mathcal O$. On the other hand, there are $Pi^0_2$ sets of reals where no hyperarithmetic real can define a closed subset of non-zero measure.
We study the randomness properties of reals with respect to arbitrary probability measures on Cantor space. We show that every non-computable real is non-trivially random with respect to some measure. The probability measures constructed in the proof
may have atoms. If one rules out the existence of atoms, i.e. considers only continuous measures, it turns out that every non-hyperarithmetical real is random for a continuous measure. On the other hand, examples of reals not random for any continuous measure can be found throughout the hyperarithmetical Turing degrees.
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. W
e 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 show that if a real $x$ is strongly Hausdorff $h$-random, where $h$ is a dimension function corresponding to a convex order, then it is also random for a continuous probability measure $mu$ such that the $mu$-measure of the basic open cylinders sh
rinks according to $h$. The proof uses a new method to construct measures, based on effective (partial) continuous transformations and a basis theorem for $Pi^0_1$-classes applied to closed sets of probability measures. We use the main result to give a new proof of Frostmans Lemma, to derive a collapse of randomness notions for Hausdorff measures, and to provide a characterization of effective Hausdorff dimension similar to Frostmans Theorem.
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 co
nditions 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.
