Skip to Main content Skip to Navigation
Preprints, Working Papers, ...

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 Π 1 1-complete, so that there is no simple characterization of the introreducible sets; and that every introenumerable set has an introreducible subset.
Document type :
Preprints, Working Papers, ...
Complete list of metadatas

Cited literature [21 references]  Display  Hide  Download

https://hal.archives-ouvertes.fr/hal-02992972
Contributor : Ludovic Patey <>
Submitted on : Friday, November 6, 2020 - 3:51:54 PM
Last modification on : Monday, December 14, 2020 - 6:11:01 PM

File

Introreducibility.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02992972, version 1

Citation

Noam Greenberg, Matthew Harrison-Trainor, Ludovic Patey, Dan Turetsky. Computing sets from all infinite subsets. 2020. ⟨hal-02992972⟩

Share

Metrics

Record views

8

Files downloads

12