Classes bounded by incomplete sets
type: Item
instance of: scholarly article
title: Classes bounded by incomplete sets
zbMATH Open document ID: 1002.03033
DOI: 10.1016/S0168-0072(01)00114-2
author: Kejia Ho
author: Frank Stephan
published in: Annals of Pure and Applied Logic
publication date: 2002-06-24T00:00:00Z
review text: By the authors' definition, a class \textbf{K} of computably enumerable (c.e.) degrees is bounded if there exists an incomplete c.e. set \(A\) such that every set in \textbf{K} is m-reducible to \(A\). An example of a bounded class is the class of effectively simple sets. An interesting property is proved: the class of c.e. sets Turing reducible to an incomplete c.e. set \(A\) is bounded iff \(A\) is \(\text{low}_2\).
Mathematics Subject Classification ID: 03D25
zbMATH DE Number: 1758492
zbMATH Keywords: computably enumerable degrees
zbMATH Keywords: \(m\)-reducible
zbMATH Keywords: bounded class
zbMATH Keywords: effectively simple sets
zbMATH Keywords: Turing reducible
reviewed by: Sh. T. Ishmukhametov
MaRDI profile type: Publication
cites work: The theory of the recursively enumerable weak truth-table degrees is undecidable
cites work: A Theorem on Hypersimple Sets
cites work: T-Degrees, Jump Classes, and Strong Reducibilities
cites work: Degree theoretic definitions of the low2 recursively enumerable sets
cites work: Reducibility and Completeness for Sets of Integers
cites work: Semirecursive Sets and Positive Reducibility
cites work: Degrees in Which the Recursive Sets are Uniformly Recursive
cites work: Q4186304
cites work: Recursion theoretic properties of frequency computation and bounded queries
cites work: A note on universal sets
cites work: w tt-Complete Sets are not Necessarily tt-Complete
cites work: One class of partial sets
cites work: Creative sets
cites work: Classical recursion theory. Vol. II
cites work: Q4040892
cites work: On the Degrees of Index Sets. II
full work available at URL: s0168-0072(01)00114-2
OpenAlex ID: W2076082825
Recommended article: A class of hypersimple incomplete sets
Recommended article: Inclusions for Classes of Lacunary Sets
Recommended article: Q3797642
Recommended article: Some classes of bounded sets in metric spaces
Recommended article: Q3724602
Recommended article: Q3974859
Recommended article: Completeness in approximation classes
Recommended article: Q3975495
Recommended article: Bounded and relatively bounded sets
Recommended article: Q4218523
description: scientific article; zbMATH DE number 1758492