A necessary and sufficient condition for embedding principally decomposable finite lattices into the computably enumerable degrees (Q1964021)

From MaRDI portal
Revision as of 21:14, 29 July 2023 by Importer (talk | contribs) (‎Created a new Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
A necessary and sufficient condition for embedding principally decomposable finite lattices into the computably enumerable degrees
scientific article

    Statements

    A necessary and sufficient condition for embedding principally decomposable finite lattices into the computably enumerable degrees (English)
    0 references
    0 references
    8 October 2000
    0 references
    \textit{M. Lerman} [Ann. Pure Appl. Logic 94, No. 1-3, 143-180 (1998; Zbl 0924.03075)] introduced the notion of good blocked target arrays (gbtas) and showed that the ranked finite lattices which have gbtas coincide with the ranked finite lattices which are embeddable into the upper semilattice \({\mathcal R}\) of computably enumerable Turing degrees. In this paper it is proved that: 1. A principally decomposable finite lattice is embeddable into \({\mathcal R}\) (preserving \(0\)) iff there is a gbta for every sequence of requirements. 2. A principally decomposable finite lattice is embeddable below every non-zero computably enumerable degree iff there is a gbta for every sequence of requirements.
    0 references
    0 references
    computably enumerable sets
    0 references
    lattice embeddings
    0 references
    good blocked target arrays
    0 references
    principally decomposable finite lattice
    0 references
    computably enumerable degree
    0 references

    Identifiers