๐ฎ
๐ฎ
The Ethereal
Coding information into all infinite subsets of a dense set
June 02, 2023 ยท The Ethereal ยท ๐ arXiv.org
"No code URL or promise found in abstract"
Evidence collected by the PWNC Scanner
Authors
Matthew Harrison-Trainor, Lu Liu, Patrick Lutz
arXiv ID
2306.01226
Category
math.LO: Logic
Cross-listed
cs.IT
Citations
1
Venue
arXiv.org
Last Checked
5 months ago
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 also prove an analogous result for PA degree: if $X$ is uncomputable and $A$ is a set of positive lower density then $A$ has an infinite subset which is not of PA degree. We will show that these theorems are 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, Liu, and others on the reverse math of Ramsey's theorem for pairs.
Community Contributions
Found the code? Know the venue? Think something is wrong? Let us know!
๐ Similar Papers
In the same crypt โ Logic
๐ฎ
๐ฎ
The Ethereal
Dialectical Rough Sets, Parthood and Figures of Opposition-1
๐ฎ
๐ฎ
The Ethereal
Approximations from Anywhere and General Rough Sets
๐ฎ
๐ฎ
The Ethereal
Undecidability of the Lambek calculus with subexponential and bracket modalities
๐ฎ
๐ฎ
The Ethereal
A family of neighborhood contingency logics
๐ฎ
๐ฎ
The Ethereal