On splits of computably enumerable sets

DOI10.1007/978-3-319-50062-1_31zbMATH Open1477.03162arXiv1605.03034OpenAlexW2963763495MaRDI QIDQ2970977FDOQ2970977

Authors: Peter A. Cholak 

Publication date: 4 April 2017

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

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.

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

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

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (4)

• Title not available (Why is that?)
• 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)