Index sets and Boolean operations

Miller, Douglas E.

doi:10.1090/S0002-9939-1982-0643751-5

Index sets and Boolean operations
HTML articles powered by AMS MathViewer

by Douglas E. Miller PDF

Proc. Amer. Math. Soc. 84 (1982), 568-572 Request permission

Abstract:

Hay’s thesis asserts that every naturally defined class of sets of natural numbers contains an index set which is $1$-complete for that class and that every index set is $1$-complete for some naturally defined class. We formalize "naturally defined" as "effective Boolean" and establish the thesis as a Metatheorem.

References

Completely enumerated sets

9

On a hierarchy of sets

7

Louise Hay, Index sets universal for differences of arithmetic sets, Z. Math. Logik Grundlagen Math. 20 (1974), 239–254. MR 429518, DOI 10.1002/malq.19740201309
Louise Hay, A noninitial segment of index sets, J. Symbolic Logic 39 (1974), 209–224. MR 354333, DOI 10.2307/2272633
Louise Hay, Alfred B. Manaster, and Joseph G. Rosenstein, Small recursive ordinals, many-one degrees, and the arithmetical difference hierarchy, Ann. Math. Logic 8 (1975), 297–343. MR 403939, DOI 10.1016/0003-4843(75)90005-4
Peter G. Hinman, Recursion-theoretic hierarchies, Perspectives in Mathematical Logic, Springer-Verlag, Berlin-New York, 1978. MR 499205

Memoir on the analytical operations and projective sets

18

20

Piergiorgio Odifreddi, Strong reducibilities, Bull. Amer. Math. Soc. (N.S.) 4 (1981), no. 1, 37–86. MR 590818, DOI 10.1090/S0273-0979-1981-14863-1
Hartley Rogers Jr., Theory of recursive functions and effective computability, McGraw-Hill Book Co., New York-Toronto, Ont.-London, 1967. MR 0224462