Classes bounded by incomplete sets (Q1602854): Difference between revisions
From MaRDI portal
Changed an Item |
Set profile property. |
||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank |
Revision as of 06:03, 5 March 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