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

    Identifiers

    0 references
    0 references
    0 references
    0 references