A necessary and sufficient condition for embedding principally decomposable finite lattices into the computably enumerable degrees (Q1964021)
From MaRDI portal
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
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
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
0 references