Archive for Mathematical Logic 50 (3-4):341-352 (2011)

We use certain strong Q-reducibilities, and their corresponding strong positive reducibilities, to characterize the hyperimmune sets and the hyperhyperimmune sets: if A is any infinite set then A is hyperimmune (respectively, hyperhyperimmune) if and only if for every infinite subset B of A, one has ${\overline{K}\not\le_{\rm ss} B}$ (respectively, ${\overline{K}\not\le_{\overline{\rm s}} B}$ ): here ${\le_{\overline{\rm s}}}$ is the finite-branch version of s-reducibility, ≤ss is the computably bounded version of ${\le_{\overline{\rm s}}}$ , and ${\overline{K}}$ is the complement of the halting set. Restriction to ${\Sigma^0_2}$ sets provides a similar characterization of the ${\Sigma^0_2}$ hyperhyperimmune sets in terms of s-reducibility. We also show that no ${A \geq_{\overline{\rm s}}\overline{K}}$ is hyperhyperimmune. As a consequence, ${\deg_{\rm s}(\overline{K})}$ is hyperhyperimmune-free, showing that the hyperhyperimmune s-degrees are not upwards closed
Keywords Hyperimmune set  Hyperhyperimmune set  s-reducibility  Q-reducibility
Categories (categorize this paper)
DOI 10.1007/s00153-010-0216-5
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

PhilArchive copy

Upload a copy of this paper     Check publisher's policy     Papers currently archived: 63,194
External links

Setup an account with your affiliations in order to access resources via your University's proxy server
Configure custom proxy (use this if your affiliation does not provide a proxy)
Through your library

References found in this work BETA

Computability and Recursion.Robert I. Soare - 1996 - Bulletin of Symbolic Logic 2 (3):284-321.
Reducibility and Completeness for Sets of Integers.Richard M. Friedberg & Hartley Rogers - 1959 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 5 (7-13):117-125.
Computability Theory.S. Barry Cooper - 2004 - Chapman & Hall.
Reducibility and Completeness for Sets of Integers.Richard M. Friedberg & Hartley Rogers - 1959 - Mathematical Logic Quarterly 5 (7‐13):117-125.

View all 11 references / Add more references

Citations of this work BETA

Agreement Reducibility.Rachel Epstein & Karen Lange - 2020 - Mathematical Logic Quarterly 66 (4):448-465.

Add more citations

Similar books and articles

Baire Reductions and Good Borel Reducibilities.Luca Motto Ros - 2010 - Journal of Symbolic Logic 75 (1):323-345.
Ethical Immunity in Business: A Response to Two Arguments. [REVIEW]Andrew Piker - 2002 - Journal of Business Ethics 36 (4):337 - 346.
A Vindication of Strong Aesthetic Supervenience.Robert Fudge - 2005 - Philosophical Papers 34 (2):149-171.
Classifying Positive Equivalence Relations.Claudio Bernardi & Andrea Sorbi - 1983 - Journal of Symbolic Logic 48 (3):529-538.
Q 1-Degrees of C.E. Sets.R. Sh Omanadze & Irakli O. Chitaia - 2012 - Archive for Mathematical Logic 51 (5-6):503-515.
Parliamentary Immunity: Protecting Democracy or Protecting Corruption?Simon Wigley - 2003 - Journal of Political Philosophy 11 (1):23–40.
The Price of Non-Reductive Moral Realism.Ralph Wedgwood - 1999 - Ethical Theory and Moral Practice 2 (3):199-215.


Added to PP index

Total views
15 ( #673,630 of 2,448,316 )

Recent downloads (6 months)
1 ( #450,727 of 2,448,316 )

How can I increase my downloads?


My notes