Back to Search
Start Over
Coding information into all infinite subsets of a dense set
- Publication Year :
- 2023
-
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.<br />Comment: 37 pages. Paper updated to fix typos
- Subjects :
- Mathematics - Logic
Computer Science - Information Theory
03D28, 03D32, 68Q30
Subjects
Details
- Database :
- arXiv
- Publication Type :
- Report
- Accession number :
- edsarx.2306.01226
- Document Type :
- Working Paper