Sets with no subsets of higher weak truth-table degree

Patrizio Cintioli


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.


Received 21 May 2016

This work was supported by the PRIN 2012 project Logic Models and Sets.

AMS subject classification: 03D30 [view classification]

Słowa kluczowe: weak truth-table reducibility, introimmune sets

[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.

Czasopismo ukazuje się w sposób ciągły on-line.
Pierwotną formą czasopisma jest wersja elektroniczna.