Remote Access Proceedings of the American Mathematical Society
Green Open Access

Proceedings of the American Mathematical Society

ISSN 1088-6826(online) ISSN 0002-9939(print)



Difference randomness

Authors: Johanna N. Y. Franklin and Keng Meng Ng
Journal: Proc. Amer. Math. Soc. 139 (2011), 345-360
MSC (2010): Primary 03D32
Published electronically: July 30, 2010
MathSciNet review: 2729096
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: In this paper, we define new notions of randomness based on the difference hierarchy. We consider various ways in which a real can avoid all effectively given tests consisting of $ n$-r.e. sets for some given $ n$. In each case, the $ n$-r.e. randomness hierarchy collapses for $ n\geq 2$. In one case, we call the resulting notion difference randomness and show that it results in a class of random reals that is a strict subclass of the Martin-Löf random reals and a proper superclass of both the Demuth random and weakly 2-random reals. In particular, we are able to characterize the difference random reals as the Turing incomplete Martin-Löf random reals. We also provide a martingale characterization for difference randomness.

References [Enhancements On Off] (What's this?)

Similar Articles

Retrieve articles in Proceedings of the American Mathematical Society with MSC (2010): 03D32

Retrieve articles in all journals with MSC (2010): 03D32

Additional Information

Johanna N. Y. Franklin
Affiliation: Department of Pure Mathematics, University of Waterloo, 200 University Avenue West, Waterloo, Ontario, Canada N2L 3G1
Address at time of publication: Department of Mathematics, 6188 Kemeny Hall, Dartmouth College, Hano- ver, New Hampshire 03755

Keng Meng Ng
Affiliation: Department of Mathematics, University of Wisconsin, 480 Lincoln Drive, Madison, Wisconsin 53706

Received by editor(s): March 3, 2010
Received by editor(s) in revised form: March 26, 2010
Published electronically: July 30, 2010
Additional Notes: The authors thank Richard Shore and André Nies for their helpful comments.
Communicated by: Julia Knight
Article copyright: © Copyright 2010 American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.