Infinite subsets of random sets of integers

DOI10.4310/MRL.2009.V16.N1.A10zbMATH Open1179.03061arXiv1408.2881MaRDI QIDQ1012969FDOQ1012969

Authors: Bjørn Kjos-Hanssen 

Publication date: 28 April 2009

Published in: Mathematical Research Letters (Search for Journal in Brave)

Abstract: There is an infinite subset of a Martin-L"of random set of integers that does not compute any Martin-L"of random set of integers. To prove this, we show that each real of positive effective Hausdorff dimension computes an infinite subset of a Martin-L"of random set of integers, and apply a result of Miller.

Full work available at URL: https://arxiv.org/abs/1408.2881

Recommendations

• A strong law of computationally weak subsets
• Extracting randomness within a subset is hard
• Cone avoiding closed sets
• scientific article; zbMATH DE number 1929969
• Subclasses of the weakly random reals

zbMATH Keywords

algorithmic randomnessreverse mathematicseffective Hausdorff dimensionSRTWWKLMartin-Löf

Mathematics Subject Classification ID

Algorithmic randomness and dimension (03D32) Foundations of classical theories (including reverse mathematics) (03B30) Second- and higher-order arithmetic and fragments (03F35)

Cited In (23)

• On the logical strengths of partial solutions to mathematical problems
• Effectively closed sets of measures and randomness
• Fixed point theorems on partial randomness
• Reconstructing infinite sets of integers
• On constant-multiple-free sets contained in a random set of integers
• Energy randomness
• Cone avoiding closed sets
• A strong law of computationally weak subsets
• On zeros of Martin-Löf random Brownian motion
• Computable Measure Theory and Algorithmic Randomness
• Extracting randomness within a subset is hard
• The coding power of a product of partitions
• Members of Random Closed Sets
• Schnorr randomness for noncomputable measures
• Martin-Löf random generalized Poisson processes
• Martin-Löf randomness and Galton-Watson processes
• The largest super-increasing subset of a random set
• Fixed Point Theorems on Partial Randomness
• Cohesive avoidance and strong reductions
• The weakness of being cohesive, thin or free in reverse mathematics
• Ramsey-type graph coloring and diagonal non-computability
• Open questions about Ramsey-type statements in reverse mathematics
• On the computability of perfect subsets of sets with positive measure

This page was built for publication: Infinite subsets of random sets of integers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1012969)