On splits of computably enumerable sets

DOI10.1007/978-3-319-50062-1_31MaRDI QIDQ2970977zbMATH OpenOpenAlexFDO

Authors Peter A. Cholak

Publication date 4 April 2017

Published in Computability and Complexity (Search for Journal in Brave)

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

Mathematics Subject Classification ID

Recursively (computably) enumerable sets and degrees (03D25)

Abstract: Our focus will be on the computably enumerable (c.e.) sets and trivial, non-trivial, Friedberg, and non-Friedberg splits of the c.e. sets. Every non-computable set has a non-trivial Friedberg split. Moreover, this theorem is uniform. V. Yu. Shavrukov recently answered the question which c.e. sets have a non-trivial non-Friedberg splitting and we provide a different proof of his result. We end by showing there is no uniform splitting of all c.e. sets such that all non-computable sets are non-trivially split and, in addition, all sets with a non-trivial non-Friedberg split are split accordingly.

Recommendations

• Splitting theorems and the jump operator
• Splitting theorems and low degrees
• Non-uniformity and generalised Sacks splitting
• Friedberg splittings of recursively enumerable sets
• Non-cupping, measure and computably enumerable splittings

Cites work

• Automorphisms of the lattice of recursively enumerable sets: Orbits
• Diagonals and -maximal sets
• Diagonals and semihyperhypersimple sets
• Friedberg splittings in Σ₃⁰ quotient lattices of
• Recursion, metarecursion, and inclusion
• Some orbits for \({\mathcal E}\)
• Three theorems on recursive enumeration. I. Decomposition. II. Maximal set. III. Enumeration without duplication
• \(\mathcal{D}\)-maximal sets

Cited in

(4)

• scientific article; zbMATH DE number 60040 (Why is no real title available?)
• Splittings of effectively speedable sets and effectively levelable sets
• Non-cupping, measure and computably enumerable splittings
• Implicit measurements of dynamic complexity properties and splittings of speedable sets

This page was built for publication: On splits of computably enumerable sets

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