Scholarlink

<p>Suppose you have an uncomputable set <i>X</i> and you want to find a set <i>A</i>, all of whose infinite subsets compute <i>X</i>. There are several ways to do this, but all of them seem to produce a set <i>A</i> which is fairly sparse. We show that this is necessary in the following technical sense: if <i>X</i> is uncomputable and <i>A</i> is a set of positive lower density then <i>A</i> has an infinite subset which does not compute <i>X</i>. We also prove an analogous result for PA degree: if <i>X</i> is uncomputable and <i>A</i> is a set of positive lower density then <i>A</i> 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.</p>

错误：搜索内容不能为空，请输入英文关键词
错误：关键词超出字数限制，请精简
高级检索

Coding information into all infinite subsets of a dense set

  • 期刊论文

  • 发表日期：

    2026年5月25日

查看全文
  • Matthew Harrison-Trainor,
  • Lu Liu,
  • Patrick Lutz

摘要

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.