Randomness related to usual mathematical notions
by
Veronica Becher
University of Buenos Aires,
Coauthors: Serge Grigorieff

From any given countable partially ordered set D endowed with a computable partial order, we consider the limit space of equivalence classes of increasing sequences over D, relative to the equivalence relation associated to asymptotic equality.

In particular, the space of the real numbers is obtained in the two classical ways: as the limit space of its Dedekind cuts, and as the Cauchy completion of the rational numbers. More generally, the Cauchy completion of any metric space can be obtained.

We give general theorem that yields n-random reals arising from subsets of A of the limit space satisfying two hypothesis. One is a definability hypothesis over A, and the other is a hardness hypothesis: A should be hard for the class of Sigma^0_n subsets of the Cantor space with respect to effective Wadge reductions. Mutatis mutandis the theorem also holds for the Pi^1_1 version of Martin Löf randomness.

We develop many applications of the theorem and state natural examples of n-random and Pi^1_1-random reals.

PDF

Date received: March 2, 2008