Immunity properties and strong positive reducibilities

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


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



    Upload a copy of this work     Papers currently archived: 74,174

External links

Setup an account with your affiliations in order to access resources via your University's proxy server

Through your library

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

15 (#692,229)

6 months
1 (#413,740)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

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

Add more citations

References found in this work

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 - 2003 - 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