Theodore A. Slaman

We show that if E E is a countable Borel equivalence relation on R n \mathbb {R}^n , then there is a closed subset A ⊆ [ 0 , 1 ] n A \subseteq [0,1]^n of Hausdorff dimension n n so that E ↾ A E \restriction A is smooth. More generally, if ≤ Q \leq _Q is a locally countable Borel quasi-order on 2 ω 2^\omega and g g is any gauge function of lower order than the identity, then there is a closed set A A so that A A is an antichain in ≤ Q \leq _Q and H g ( A ) > 0 H^g(A) > 0 .

We investigate natural variations of behaviourally correct learning and explanatory learning -- two learning paradigms studied in algorithmic learning theory -- that allow us to ``learn'' equivalence relations on Polish spaces. We give a characterization of the learnable equivalence relations in terms of their Borel complexity and show that the behaviorally correct and explanatory learnable equivalence relations coincide both in uniform and non-uniform versions of learnability and provide a characterization of the learnable equivalence relations in terms of their Borel complexity. We also show that the set of uniformly learnable equivalence relations is $\pmbΠ^1_1$-complete in the codes and study the learnability of several equivalence relations arising naturally in logic as a case study.

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 n , all but countably many reals are n n -random for such a measure, where n n indicates the arithmetical complexity of the Martin-Löf tests allowed. The proof rests upon an application of Borel determinacy. Therefore, the proof 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 G such that, for any n n , the statement “All but countably many reals are G ( n ) G(n) -random with respect to a continuous probability measure” cannot be proved in Z F C n − \mathsf {ZFC}^-_n . Here Z F C n − \mathsf {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 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.

In this article, we will show that .

We generalize the classical theorem by Jarnik and Besicovitch on the irrationality exponents of real numbers and Hausdorff dimension. Let a be any real number greater than or equal to 2 and let b be any non-negative real less than or equal to 2/a. We show that there is a Cantor-like set with Hausdorff dimension equal to b such that, with respect to its uniform measure, almost all real numbers have irrationality exponent equal to a. We give an analogous result relating the irrationality exponent and the effective Hausdorff dimension of individual real numbers. We prove that there is a Cantor-like set such that, with respect to its uniform measure, almost all elements in the set have effective Hausdorff dimension equal to b and irrationality exponent equal to a. In each case, we obtain the desired set as a distinguished path in a tree of Cantor sets.