Sets with no subsets of higher weak truth-table degree

• Autorzy: Cintioli P.

Identyfikatory

DOI

10.4467/20842589RM.18.001.8834

• Języki publikacji: EN

Abstrakty

EN

We consider the weak truth-table reducibility ≤wtt and we prove the existence of wtt-introimmune sets in ∆0 2. This closes the gap on the existence of arithmetical r-introimmune sets for all the known reducibilities ≤r strictly contained in the Turing reducibility

Słowa kluczowe

EN

weak truth-table reducibility; introimmune sets

• Wydawca: Wydawnictwo Uniwersytetu Jagiellońskiego
• Czasopismo: Reports on Mathematical Logic
• Rocznik: 2018
• Tom: Vol. 53
• Strony: 3--17
• Opis fizyczny: Bibliogr. 12 poz.

Twórcy

autor

Cintioli P.

• Dipartimento di Matematica e Informatica Universit`a di Camerino Via Madonna delle Carceri 9, 62032 Camerino, Italy

Bibliografia

• [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´aˇs, 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.

Uwagi

Opracowanie rekordu w ramach umowy 509/P-DUN/2018 ze środków MNiSW przeznaczonych na działalność upowszechniającą naukę (2018).