Coding information into all infinite subsets of a dense set

Authors Matthew Harrison-Trainor, Lu Liu, Patrick Lutz

Publication date 1 June 2023

Other Turing degree structures (03D28) Algorithmic randomness and dimension (03D32) Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30)

Abstract: Suppose you have an uncomputable set

X

and you want to find a set

A

, all of whose infinite subsets compute

X

. There are several ways to do this, but all of them seem to produce a set

A

which is fairly sparse. We show that this is necessary in the following technical sense: if

X

is uncomputable and

A

is a set of positive lower density then

A

has an infinite subset which does not compute

X

. We will show that this theorem is sharp in certain senses and also prove a quantitative version formulated in terms of Kolmogorov complexity. Our results use a modified version of Mathias forcing and build on work by Seetapun and others on the reverse math of Ramsey's theorem for pairs.

This page was built for publication: Coding information into all infinite subsets of a dense set

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