Open Access
2010 Relative Randomness and Cardinality
George Barmpalias
Notre Dame J. Formal Logic 51(2): 195-205 (2010). DOI: 10.1215/00294527-2010-012

Abstract

A set B N is called low for Martin-Löf random if every Martin-Löf random set is also Martin-Löf random relative to B. We show that a Δ 2 0 set B is low for Martin-Löf random if and only if the class of oracles which compress less efficiently than B, namely, the class 𝒞 B = { A   |   n   K B ( n ) + K A ( n ) } is countable (where K denotes the prefix-free complexity and + denotes inequality modulo a constant. It follows that Δ 2 0 is the largest arithmetical class with this property and if 𝒞 B is uncountable, it contains a perfect Π 1 0 set of reals. The proof introduces a new method for constructing nontrivial reals below a Δ 2 0 set which is not low for Martin-Löf random.

Citation

Download Citation

George Barmpalias. "Relative Randomness and Cardinality." Notre Dame J. Formal Logic 51 (2) 195 - 205, 2010. https://doi.org/10.1215/00294527-2010-012

Information

Published: 2010
First available in Project Euclid: 11 June 2010

zbMATH: 1231.03038
MathSciNet: MR2667906
Digital Object Identifier: 10.1215/00294527-2010-012

Subjects:
Primary: 03F60
Secondary: 03D30

Keywords: Cardinality , randomness , relative randomness

Rights: Copyright © 2010 University of Notre Dame

Vol.51 • No. 2 • 2010
Back to Top