Computing sets from all infinite subsets

International audienceA 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 Π 1 1-complete, so that there is no simple characterization of the introreducible sets; and that every introenumerable set has an introreducible subset