Splitting theorems in recursion theory

DOI10.1016/0168-0072(93)90234-5zbMath0792.03028OpenAlexW2070295070MaRDI QIDQ1314544

Michael Stob, Rodney G. Downey

Publication date: 17 February 1994

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(93)90234-5

zbMATH Keywords

r.e. degreelattice of r.e. setsdefinability of the jump operatorPost's Programsplitting of r.e. setssplitting theorems in classical recursion theory

Mathematics Subject Classification ID

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

Related Items (18)

Maximal contiguous degrees ⋮ Infimum properties differ in the weak truth-table degrees and the Turing degrees ⋮ Splittings of effectively speedable sets and effectively levelable sets ⋮ Lattice embeddings below a nonlow\(_ 2\) recursively enumerable degree ⋮ Some properties of \(r\)-maximal sets and \(Q_{1,N}\)-reducibility ⋮ Nonuniformity of downward density in \(n\)-computably enumerable Turing degrees ⋮ A Survey of Results on the d-c.e. and n-c.e. Degrees ⋮ There Are No Maximal d.c.e. wtt-degrees ⋮ Introduction to Autoreducibility and Mitoticity ⋮ Friedberg splittings of recursively enumerable sets ⋮ Contiguity and distributivity in the enumerable Turing degrees ⋮ Completely mitotic c.e. degrees and non-jump inversion ⋮ On the bounded quasi‐degrees of c.e. sets ⋮ Implicit measurements of dynamic complexity properties and splittings of speedable sets ⋮ Turing computability: structural theory ⋮ Non-cupping, measure and computably enumerable splittings ⋮ Splitting theorems and the jump operator ⋮ Some orbits for \({\mathcal E}\)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Working below a \(low_ 2\) recursively enumerable degree
• Friedberg splittings of recursively enumerable sets
• Lattice nonembeddings and initial segments of the recursively enumerable degrees
• Invariance of properties under automorphisms of the lattice of recursively enumerable sets
• The intervals of the lattice of recursively enumerable sets determined by major subsets
• Subsets of hypersimple sets
• Structural interactions of the recursively enumerable T- and W-degrees
• Completely mitotic r. e. degrees
• Intervals and sublattices of the r.e. weak truth table degrees. I: Density
• Classification of degree classes associated with r.e. subspaces
• \(\Delta\)\( ^ 0_ 2\) degrees and transfer theorems
• A non-inversion theorem for the jump operator
• Logic year 1979--80, The University of Connecticut, USA
• Splitting properties and jump classes
• The d.r.e. degrees are not dense
• Automorphisms of the lattice of recursively enumerable sets: Orbits
• Recursion theory week. Proceedings of a conference held in Oberwolfach, Germany, March 19-25, 1989
• Classical recursion theory. Vol. II
• Array nonrecursive degrees and lattice embeddings of the diamond
• Minimal pairs in initial segments of the recursively enumerable degrees
• Three theorems on the degrees of recursively enumerable sets
• Automorphisms of the lattice of recursively enumerable sets. I: Maximal sets
• Interpolation and embedding in the recursively enumerable degrees
• On the degrees less than 0'
• Automorphisms of the lattice of recursively enumerable sets. Part II: Low sets
• Decomposition and infima in the computably enumerable degrees
• Index sets and degrees of unsolvability
• An Algebraic Decomposition of the Recursively Enumerable Degrees and the Coincidence of Several Degree Classes with the Promptly Simple Degrees
• On Pairs of Recursively Enumerable Degrees
• Characterization of Recursively Enumerable Sets with Supersets Effectively Isomorphic to all Recursively Enumerable Sets
• A jump class of noncappable degrees
• The jump is definable in the structure of the degrees of unsolvability
• Pseudo Jump Operators. I: The R. E. Case
• The undecidability of the recursively enumerable degrees
• Pseudo-jump operators. II: Transfinite iterations, hierarchies and minimal covers
• The Degrees of R.E. Sets Without the Universal Splitting Property
• An extension of the nondiamond theorem in classical and α-recursion theory
• The universal splitting property. II
• Anti‐Mitotic Recursively Enumerable Sets
• Splitting properties of r.e. sets and degrees
• D.R.E. Degrees and the Nondiamond Theorem
• Lattice embeddings into the recursively enumerable degrees
• Degrees of Splittings and Bases of Recursively Enumerable Subspace
• T-Degrees, Jump Classes, and Strong Reducibilities
• Σ₂-collection and the infinite injury priority method
• Degree theoretical splitting properties of recursively enumerable sets
• Bounding minimal pairs
• Decomposition of Recursively Enumerable Degrees
• Recursively enumerable generic sets
• Branching Degrees above low Degrees
• Jumps of Hemimaximal Sets
• Diagonals and semihyperhypersimple sets
• A Splitting Theorem for the N-R.E. Degrees
• Automorphisms of the Lattice of Recursively Enumerable Sets: Promptly Simple Sets
• Post's program and incomplete recursively enumerable sets.
• The theory of the recursively enumerable weak truth-table degrees is undecidable
• The weak truth table degrees of recursively enumerable sets
• On complexity properties of recursively enumerable sets
• A recursively enumerable degree which will not split over all lesser ones
• Determining Automorphisms of the Recursively Enumerable Sets
• Degrees of classes of RE sets
• Computational complexity, speedable and levelable sets
• Jumps of nontrivial splittings of recursively enumerable sets
• Lattice embeddings into the recursively enumerable degrees. II
• Diagonals and -maximal sets
• Highness and bounding minimal pairs
• Automorphisms of the lattice of recursively enumerable sets
• On the Lattice of Recursively Enumerable Sets
• Mitotic recursively enumerable sets
• Degree theoretic definitions of the low₂ recursively enumerable sets
• The Priority Method I
• Lower Bounds for Pairs of Recursively Enumerable Degrees
• Classes of Recursively Enumerable Sets and Degrees of Unsolvability
• Recursion, metarecursion, and inclusion
• Degrees in Which the Recursive Sets are Uniformly Recursive
• Recursively enumerable sets of positive integers and their decision problems

This page was built for publication: Splitting theorems in recursion theory