On distributivity of the upper semilattices of the degrees below \(0'\) (Q1902712)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On distributivity of the upper semilattices of the degrees below \(0'\) |
scientific article |
Statements
On distributivity of the upper semilattices of the degrees below \(0'\) (English)
0 references
3 December 1995
0 references
Let \(D^r_1\) and \(D^r_2\) denote the upper semilattices of the recursively enumerable (r.e.) \(r\)-degrees and of the \(r\)-degrees of differences of r.e. sets, respectively, where \(r\) is one of the reducibilities which have been studied in recursive function theory. Numerous differences in the structure of these upper semilattices in the case of Turing reducibility give rise to the interest for studying the structure of \(D^r_2\) for other reducibilities \(r\). We prove here that the structures \(D^r_2\) are not distributive for any reducibility \(r\) intermediate between bd and T.
0 references
distributivity
0 references
recursively enumerable \(r\)-degrees
0 references
upper semilattices
0 references
\(r\)-degrees
0 references
\(r\)-degrees of differences of r.e. sets
0 references
reducibilities
0 references