Back to Search
Start Over
Rank and randomness
- Publication Year :
- 2017
- Publisher :
- arXiv, 2017.
-
Abstract
- We show that for each computable ordinal $\alpha > 0$ it is possible to find in each Martin-Löf random ${\rm{\Delta }}_2^0 $ degree a sequence R of Cantor-Bendixson rank α, while ensuring that the sequences that inductively witness R’s rank are all Martin-Löf random with respect to a single countably supported and computable measure. This is a strengthening for random degrees of a recent result of Downey, Wu, and Yang, and can be understood as a randomized version of it.
- Subjects :
- Sequence
Degree (graph theory)
Logic
010102 general mathematics
Algorithmic randomness
Mathematics - Logic
0102 computer and information sciences
01 natural sciences
Measure (mathematics)
Combinatorics
Philosophy
Mathematics::Logic
010201 computation theory & mathematics
FOS: Mathematics
Rank (graph theory)
0101 mathematics
Logic (math.LO)
Randomness
Mathematics
Subjects
Details
- ISSN :
- 00224812
- Database :
- OpenAIRE
- Accession number :
- edsair.doi.dedup.....32cd2280c42ac3225962488880de86d8
- Full Text :
- https://doi.org/10.48550/arxiv.1707.00378