On the T-degrees of partial functions
Paolo Casalegno · Journal of Symbolic Logic · 1985
Abstract Let 〈 , ≤ 〉 be the usual structure of the degrees of unsolvability and 〈 , ≤ 〉 the structure of the T-degrees of partial functions defined in [7]. We prove that every countable distributive lattice with a least element can be isomorphically embedded as an initial segment of 〈 , ≤ 〉: as a corollary, the first order theory of 〈 , ≤ 〉 is recursively isomorphic to that of 〈 , ≤ 〉. We also show that 〈 , ≤ 〉 and 〈 , ≤ 〉 are not elementarily equivalent.