Classes bounded by incomplete sets (Q1602854): Difference between revisions
From MaRDI portal
Added link to MaRDI item. |
Removed claim: reviewed by (P1447): Item:Q465141 |
||
Property / reviewed by | |||
Property / reviewed by: Sh. T. Ishmukhametov / rank | |||
Revision as of 05:11, 15 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | Classes bounded by incomplete sets |
scientific article |
Statements
Classes bounded by incomplete sets (English)
0 references
24 June 2002
0 references
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\).
0 references
computably enumerable degrees
0 references
\(m\)-reducible
0 references
bounded class
0 references
effectively simple sets
0 references
Turing reducible
0 references