Relative randomness and cardinality (Q985004)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Relative randomness and cardinality |
scientific article |
Statements
Relative randomness and cardinality (English)
0 references
20 July 2010
0 references
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\).
0 references
algorithmic randomness
0 references
Martin-Löf randomness
0 references
relative randomness
0 references
lowness
0 references