Sets with no subsets of higher weak truth-table degree
Choose format
RIS BIB ENDNOTESets with no subsets of higher weak truth-table degree
Publication date: 06.09.2018
Reports on Mathematical Logic, 2018, Number 53, pp. 3-17
https://doi.org/10.4467/20842589RM.18.001.8834Authors
Sets with no subsets of higher weak truth-table degree
We consider the weak truth-table reducibility ≤wtt and we prove the existence of wtt-introimmune sets in ∆02. This closes the gap on the existence of arithmetical r-introimmune sets for all the known reducibilities ≤r strictly contained in the Turing reducibility.
[1] K. Ambos-Spies, Problems which Cannot Be Reduced to Any Proper Subproblems, Proc. 28th International Symposium, MFCS 2003, vol. 2747 of Lecture Notes in Computer Science, B. Rovan and P. Vojtáš, editors, Springer, Berlin, 2003, 162– 168.
[2] K. Ambos-Spies. Private communication.
[3] P. Cintioli, Sets without Subsets of Higher Many-One Degree, Notre Dame Journal of Formal Logic 46:2 (2005), 207–216.
[4] P. Cintioli, Low sets without subsets of higher many-one degree, Mathematical Logic Quarterly 57:5 (2011), 517–523. [
5] P. Cintioli and R. Silvestri, Polynomial Time Introreducibility, Theory of Computing Systems 36:1 (2003), 1–15.
[6] R.G. Downey and D.R. Hirschfeldt, Algorithmic Randomness and Complexity, Springer-Verlag, New York, 2010.
[7] C.G. Jockusch Jr., Upward closure and cohesive degrees, Israel Journal of Mathematics 15:3 (1973), 332–335.
[8] P. Odifreddi, Strong reducibilities, Bulletin of the American Mathematical Society 4:1 (1981), 37–86.
[9] P. Odifreddi, Classical Recursion Theory, vol. 125 of Studies in Logic and the Foundations of Mathematics, North Holland Publishing Company, Amsterdam, 1989.
[10] S.G. Simpson, Sets Which Do Not Have Subsets of Every Higher Degree, The Journal of Symbolic Logic 43:1 (1978), 135–138.
[11] R.I. Soare, Sets with no Subset of Higher Degrees, The Journal of Symbolic Logic 34:1 (1969), 53–56.
[12] R.I. Soare, Recursively enumerable sets and degrees, Perspectives in Mathematical Logic, Springer-Verlag, Berlin Heidelberg, 1987.
Information: Reports on Mathematical Logic, 2018, Number 53, pp. 3-17
Article type: Original article
Dipartimento di Matematica e Informatica Universita di Camerino Via Madonna delle Carceri 9, 62032 Camerino, Italy.
Published at: 06.09.2018
Received at: 21.05.2016
Article status: Open
Licence: CC BY-NC-ND
Article financing:
Percentage share of authors:
Classification number:
Article corrections:
-Publication languages:
EnglishView count: 1847
Number of downloads: 1484