Computing sets from all infinite subsets

DOI10.1090/TRAN/8468MaRDI QIDQ5158110zbMATH OpenOpenAlexFDO

Authors Noam Greenberg, Matthew Harrison-Trainor, Ludovic Patey, Dan Turetsky

Publication date 21 October 2021

Published in Transactions of the American Mathematical Society (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2011.03386

zbMATH Keywords

introenumerable setsintroreducible sets

Mathematics Subject Classification ID

Other Turing degree structures (03D28) Other degrees and reducibilities in computability and recursion theory (03D30)

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 $P{i}_1^1$-complete, so that there is no simple characterization of the introreducible sets; and that every introenumerable set has an introreducible subset.

Recommendations

• Mathematical Foundations of Computer Science 2003
• Low sets without subsets of higher many-one degree
• Publication:4934282
• Reducibility on families
• Sets without subsets of higher many-one degree

Cites work

• \(\mathsf{RT}_{2}^{2}\) does not imply \(\mathsf{WKL}_{0}\)
• A minimal pair in the generic degrees
• Asymptotic density and the coarse computability bound
• Borel sets and Ramsey's theorem
• Computability and complexity. Essays dedicated to Rodney G. Downey on the occasion of his 60th birthday
• Cone avoiding closed sets
• Controlling iterated jumps of solutions to combinatorial problems
• Definability in the Turing degrees
• Generic computability, Turing degrees, and asymptotic density
• scientific article; zbMATH DE number 194103 (Why is no real title available?)
• scientific article; zbMATH DE number 722611 (Why is no real title available?)
• Hyperarithmetically Encodable Sets
• Measuring the complexity of reductions between equivalence relations
• On a problem of Kleene’s
• On the strength of Ramsey's theorem
• Pigeons do not jump high
• Recursive Pseudo-Well-Orderings
• Reducibility and Completeness for Sets of Integers
• Retraceable Sets
• Sets with no subset of higher degree
• The Strength of Some Combinatorial Principles Related to Ramsey's Theorem for Pairs
• Uniformly introreducible sets

Cited in

(2)

• Reconstructing infinite sets of integers
• Introenumerability, autoreducibility, and randomness

This page was built for publication: Computing sets from all infinite subsets

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5158110)