Relative randomness and cardinality
type: Item
instance of: scholarly article
title: Relative randomness and cardinality
zbMATH Open document ID: 1231.03038
DOI: 10.1215/00294527-2010-012
author: George Barmpalias
published in: Notre Dame Journal of Formal Logic
publication date: 2010-07-20T00:00:00Z
review text: The paper studies the notion of lowness for the class of Martin-Löf random sets. A set \(B\) is low for Martin-Löf random, if every Martin-Löf random set is also Martin-Löf random relative to \(B\). This notion was introduced by \textit{A. Kučera} and \textit{S. A. Terwijn} [J. Symb. Log. 64, No. 4, 1396--1402 (1999; Zbl 0954.68080)]. Here, it is shown that if \(B\) is \(\Delta^0_2\) then \(B\) is low for Martin-Löf random iff \({\mathcal C}^B\) is countable, where \({\mathcal C}^B\) is the class of those sets \(A\) with the property that every set Martin-Löf random relative to \(B\) is also Martin-Löf random relative to \(A\).
reviewed by: Heribert Vollmer
Mathematics Subject Classification ID: 03D32
Mathematics Subject Classification ID: 68Q30
zbMATH DE Number: 5758437
zbMATH Keywords: algorithmic randomness
zbMATH Keywords: Martin-Löf randomness
zbMATH Keywords: relative randomness
zbMATH Keywords: lowness
MaRDI profile type: Publication
full work available at URL: https://doi.org/10.1215/00294527-2010-012
OpenAlex ID: W1998078201
Recommended article: On relative randomness
Recommended article: Randomness notions and partial relativization
Recommended article: Randomness relative to Cantor expansions
Recommended article: Prompt enumerations and relative randomness
Recommended article: Randomness and recursive enumerability
Recommended article: Randomness, evenness, and Rényi's index
Recommended article: Incompleteness, Approximation and Relative Randomness
Recommended article: Randomness and Solovay degrees
Recommended article: Relative randomness and real closed fields
Recommended article: Finite-dimensional randomness
description: scientific article; zbMATH DE number 5758437