Hostname: page-component-586b7cd67f-rdxmf Total loading time: 0 Render date: 2024-11-25T23:54:24.168Z Has data issue: false hasContentIssue false

Contiguity and distributivity in the enumerable Turing degrees — Corrigendum

Published online by Cambridge University Press:  12 March 2014

Rodney G. Downey
Affiliation:
Department of Mathematics, Victoria University, Box 600, Wellington 6001, New Zealand, E-mail: [email protected]
Steffen Lempp
Affiliation:
Department of Mathematics, University of Wisconsin, Madison, WI 53706, USA, E-mail: [email protected]

Extract

A computably enumerable Turing degree a is called contiguous iff it contains only a single computably enumerable weak truth table degree (Ladner and Sasso [2]). In [1], the authors proved that a nonzero computably enumerable degree a is contiguous iff it is locally distributive, that is, for all a1, a2, c with a1a2 = a and ca, there exist ci, ≤ ai with c1c2 = c.

To do this we supposed that W was a computably enumerable set and ∪ a computably set with a Turing functional Φ such that ΦW = U. Then we constructed computably enumerable sets A0, A1 and B together with functionals Γ0, Γ1, Γ, and Δ so that

and so as to satisfy all the requirements below.

That is, we built a degree-theoretical splitting A0, A1 of W and a set BTW such that if we cannot beat all possible degree-theoretical splittings V0, V1 of B then we were able to witness the fact that UWW (via Λ).

After the proof it was observed that the set U of the proof (page 1222, paragraph 4) needed only to be Δ20. It was then claimed that a consequence to the proof was that every contiguous computably enumerable degree was, in fact, strongly contiguous, in the sense that all (not necessarily computably enumerable) sets of the degree had the same weak truth table degree.

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 2002

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

References

REFERENCES

[1]Downey, R. and Lempp, S., Contiguity and distributivity in the enumerable degrees, this Journal, vol. 62 (1997), pp. 12151240.Google Scholar
[2]Ladner, R. E. Jr., and Jr.Sasso, L. P., The weak truth table degrees of recursively enumerable sets, Annals of Mathematical Logic, vol. 8 (1975), pp. 429448.CrossRefGoogle Scholar
[3]Nies, A., personal communication, 01 2001.Google Scholar