Computing sets from all infinite subsets

Abstract

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.

30 pages

References in corpus (1)

• The Strength of Some Combinatorial Principles Related to Ramsey's Theorem for Pairs