Noam Greenberg, Matthew Harrison-Trainor, Ludovic Patey, Dan Turetsky
Published 2020-11-06Version 1
A set is introreducible if it can be computed by every infinite subset of itself. Such a set can be thought of as coding information very robustly. We investigate introreducible sets and related notions. Our two main results are that the collection of introreducible sets is $\Pi^1_1$-complete, so that there is no simple characterization of the introreducible sets; and that every introenumerable set has an introreducible subset.
Coding information into all infinite subsets of a dense set
$\mathsf{RT}_2^2$ does not imply $\mathsf{WKL}_0$
A Remark on a Theorem of Erdos
![QR code for arXiv:2011.03386 [math.LO]](http://oss.arxitics.com/images/favicon.svg)