We consider sets without subsets of higher m- and -degree, that we call m-introimmune and -introimmune sets respectively. We study how they are distributed in partially ordered degree structures. We show that:
each computably enumerable weak truth-table degree contains m-introimmune -sets;
each hyperimmune degree contains bi-m-introimmune sets.
Finally, from known results we establish that each degree a with covers a degree containing -introimmune sets.
K.Ambos-Spies, Problems which cannot be reduced to any proper subproblems, in: Proc. 28th International Symposium, MFCS 2003, B.Rovan and P.Vojtáš, eds, Lectures Notes in Computer Science, Vol. 2747, Springer, Berlin, 2003, pp. 162–168.
2.
K.Ambos-Spies, Private communication.
3.
E.P.Astor, Asymptotic density, immunity and randomness, Computability4(2) (2015), 141–158. doi:10.3233/COM-150040.
4.
J.L.Balcázar, J.Díaz and J.Gabarró, Structural Complexity II, Vol. 2, Springer-Verlag, 1990.
5.
J.L.Balcázar and U.Schöning, Bi-immune sets for complexity classes, Mathematical System Theory18(1) (1985), 1–10. doi:10.1007/BF01699457.
6.
P.Cintioli, Sets without subsets of higher many-one degree, Notre Dame Journal of Formal Logic46(2) (2005), 207–216. doi:10.1305/ndjfl/1117755150.
7.
P.Cintioli, Low sets without subsets of higher many-one degree, Mathematical Logic Quarterly57(5) (2011), 517–523. doi:10.1002/malq.200920043.
8.
P.Cintioli, Sets with no subsets of higher weak truth-table degree, Reports on Mathematical Logic53 (2018), 3–17.
9.
P.Cintioli and R.Silvestri, Polynomial time introreducibility, Theory of Computing Systems36(1) (2003), 1–15. doi:10.1007/s00224-002-1040-z.
10.
A.N.Degtev, m-Powers of simple sets, Algebra and Logic11 (1972), 74–80. doi:10.1007/BF02219737.
11.
J.C.E.Dekker, A theorem on hypersimple sets, Proc. Amer. Math. Soc.5 (1954), 791–796. doi:10.1090/S0002-9939-1954-0063995-6.
12.
J.C.E.Dekker and J.Myhill, Retraceable sets, Canadian Journal of Mathematics10 (1958), 357–373. doi:10.4153/CJM-1958-035-x.
13.
R.G.Downey, E.J.Griffiths and S.Reid, On Kurtz randomness, Theoretical Computer Science321(2–3) (2004), 249–270. doi:10.1016/j.tcs.2004.03.055.
14.
R.G.Downey and D.R.Hirschfeldt, Algorithmic Randomness and Complexity, Theory and Applications of Computability, Springer, 2010.
15.
C.G.JockuschJr., The degrees of bi-immune sets, Z. Math. Logik Grundlagen Math.15 (1969), 135–140. doi:10.1002/malq.19690150707.
16.
C.G.JockuschJr., Degrees in which the recursive sets are uniformly recursive, Canadian Journal of Mathematics24 (1972), 1092–1099. doi:10.4153/CJM-1972-113-9.
17.
C.G.JockuschJr., Upward closure and cohesive degrees, Israel Journal of Mathematics15 (1973), 332–335. doi:10.1007/BF02787575.
18.
S.A.Kurtz, Randomness and genericity in the degrees of unsolvability, PhD dissertation, University of Illinois at Urbana–Champaign, 1981.
19.
D.A.Martin, Classes of recursively enumerable sets and degrees of unsolvability, Z. Math. Logik Grundlagen Math.12 (1966), 295–310. doi:10.1002/malq.19660120125.
20.
D.A.Martin, Completeness, the recursion theorem, and effectively simple sets, Proc. Amer. Math. Soc.17 (1966), 838–842. doi:10.1090/S0002-9939-1966-0216950-5.
21.
W.Miller, Sets of integers and degrees of unsolvability, Master’s thesis, University of Washington, Seattle, WA, 1967.
22.
A.Nies, Computability and Randomness, Oxford Logic Guides, Vol. 51, Oxford University Press, Oxford, 2009.
P.Odifreddi, Classical Recursion Theory, Studies in Logic and the Foundations of Mathematics, Vol. 125, North-Holland Publishing Co., 1989.
25.
P.Odifreddi, Classical Recursion Theory II, Studies in Logic and the Foundations of Mathematics, Vol. 143, North-Holland Publishing Co., 1999.
26.
S.G.Simpson, Sets which do not have subsets of every higher degree, The Journal of Symbolic Logic43(1) (1978), 135–138. doi:10.2307/2271956.
27.
R.I.Soare, Sets with no subset of higher degree, The Journal of Symbolic Logic34(1) (1969), 53–56. doi:10.2307/2270981.
28.
R.I.Soare, Recursively Enumerable Sets and Degrees: A Study of Computable Functions and Computably Generated Sets, Perspectives in Mathematical Logic, Springer-Verlag, 1987.
29.
Y.Wang, Randomness and complexity, PhD dissertation, University of Heidelberg, 1996.
30.
C.E.M.Yates, Three theorems on the degrees of recursively enumerable sets, Duke Mathematical Journal32 (1965), 461–468. doi:10.1215/S0012-7094-65-03247-3.
