Premium
Recursively Enumerable m ‐ and tt ‐Degrees III: Realizing all Finite Distributive Lattices
Author(s) -
Cholak Peter,
Downey Rod
Publication year - 1994
Publication title -
journal of the london mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.441
H-Index - 62
eISSN - 1469-7750
pISSN - 0024-6107
DOI - 10.1112/jlms/50.3.440
Subject(s) - library science , mathematics , computer science
In [1], Degtev constructed a non-zero r.e. tt-degree containing a single r.e. m-degree, and it is certainly possible to construct an r.e. tt-degree with no greatest m-degree (Downey, [4]) and hence an r.e. tt-degree can also have infinitely many r.e. m-degrees (Fischer [8]). Odifreddi [12, Problem 10, 13], asked if each r.e. tt-degree had to either contain one or infinitely many r.e. m-degrees. The second author in Downey [5] showed that it is possible to construct an r.e. m-degree with exactly 3 r.e. m-degrees. He also claimed that one could use the techniques of [5] to construct an r.e. tt-degrees with exactly 2 − 1 r.e. m-degrees and hence arbitrarily large numbers of r.e. m-degrees.