Hyperhypersimple sets and _ 2 systems

DOI10.1016/0168-0072(89)90043-2MaRDI QIDQ1823933zbMATH OpenOpenAlexFDO

Authors Yanyan Li

Publication date 1989

Published in Annals of Pure and Applied Logic (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0168-0072(89)90043-2

zbMATH Keywords

\(\Delta _ 2\) system\(\Sigma _ 2\) collection\(\Sigma _ 2\) inductionhyperhypersimple setsreverse mathematics

Mathematics Subject Classification ID

Computability and recursion theory on ordinals, admissible sets, etc. (03D60) Second- and higher-order arithmetic and fragments (03F35)

Review text

A reverse-mathematics approach to hyperhypersimple sets - starting from the axioms of Peano arithmetic with the induction schema omitted, how much axiomatic strength need be added to obtain basic results on hyperhypersimplicity? The author shows that \(\Sigma_ 2\) induction is sufficient, but not necessary, to ensure the equivalence of (Yates' simplification of) Post's original definition of hyperhypersimplicity with Lachlan's lattice-theoretic characterization. The paper's main result, obtained using the notion of a \(\Delta_ 2\) system, is that \(\Sigma_ 2\) collection suffices to prove the existence of hyperhypersimple sets.

Recommendations

• Hyperhypersimple supersets in admissible recursion theory
• scientific article; zbMATH DE number 4099278
• A characterization of the δ₂⁰ hyperhyperimmune sets
• scientific article; zbMATH DE number 4033723
• scientific article; zbMATH DE number 4106825

Cites work

• Σ₂-collection and the infinite injury priority method
• Automorphisms of the lattice of recursively enumerable sets. I: Maximal sets
• Finite injury and Σ₁-induction
• scientific article; zbMATH DE number 3882428 (Why is no real title available?)
• scientific article; zbMATH DE number 4150148 (Why is no real title available?)
• scientific article; zbMATH DE number 4106825 (Why is no real title available?)
• scientific article; zbMATH DE number 3689386 (Why is no real title available?)
• scientific article; zbMATH DE number 1303208 (Why is no real title available?)
• scientific article; zbMATH DE number 3348085 (Why is no real title available?)
• Hyperhypersimple α-r.e. sets
• Independence Results on the Global Structure of the Turing Degrees
• Maximal sets and fragments of Peano arithmetic
• Maximal sets in -recursion theory
• On the Lattice of Recursively Enumerable Sets
• Recursively enumerable sets and degrees
• Recursively enumerable sets of positive integers and their decision problems
• Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication

Cited in

(2)

• On large systems of sets with no large weak \(\Delta\)-subsystems
• The degree of a \(\Sigma_ n\) cut

This page was built for publication: Hyperhypersimple sets and \(\Delta _ 2\) systems

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