Immunity and Hyperimmunity for Sets of Minimal Indices

Notre Dame Journal of Formal Logic 49 (2):107-125 (2008)

Abstract
We extend Meyer's 1972 investigation of sets of minimal indices. Blum showed that minimal index sets are immune, and we show that they are also immune against high levels of the arithmetic hierarchy. We give optimal immunity results for sets of minimal indices with respect to the arithmetic hierarchy, and we illustrate with an intuitive example that immunity is not simply a refinement of arithmetic complexity. Of particular note here are the fact that there are three minimal index sets located in Π3 − Σ3 with distinct levels of immunity and that certain immunity properties depend on the choice of underlying acceptable numbering. We show that minimal index sets are never hyperimmune; however, they can be immune against the arithmetic sets. Lastly, we investigate Turing degrees for sets of random strings defined with respect to Bagchi's size-function s
Keywords sets of minimal indices   sets of random strings   immune sets   hyperimmune sets   Goedel numberings   Kolmogorov numberings
Categories (categorize this paper)
DOI 10.1215/00294527-2008-001
Options
Edit this record
Mark as duplicate
Export citation
Find it on Scholar
Request removal from index
Revision history

Download options

Our Archive


Upload a copy of this paper     Check publisher's policy     Papers currently archived: 45,434
Through your library

References found in this work BETA

1-Reducibility Inside an M-Degree with Maximal Set.E. Herrmann - 1992 - Journal of Symbolic Logic 57 (3):1046-1056.

Add more references

Citations of this work BETA

An Incomplete Set of Shortest Descriptions.Frank Stephan & Jason Teutsch - 2012 - Journal of Symbolic Logic 77 (1):291-307.

Add more citations

Similar books and articles

Presburger Sets and P-Minimal Fields.Raf Cluckers - 2003 - Journal of Symbolic Logic 68 (1):153-162.
On the Weak Kleene Scheme in Kripke's Theory of Truth.James Cain & Zlatan Damnjanovic - 1991 - Journal of Symbolic Logic 56 (4):1452-1468.
Definable Sets in Boolean Ordered o-Minimal Structures. II.Roman Wencel - 2003 - Journal of Symbolic Logic 68 (1):35-51.
Dp-Minimality: Basic Facts and Examples.Alfred Dolich, John Goodrick & David Lippel - 2011 - Notre Dame Journal of Formal Logic 52 (3):267-288.
On the Immunity Principle: A View From a Robot.Jonathan Cole & Oliver Sacks - 2000 - Trends in Cognitive Sciences 4 (5):167.
Hyperimmunity in 2sp ℕ.Stephen Binns - 2007 - Notre Dame Journal of Formal Logic 48 (2):293-316.
Sets and Point-Sets: Five Grades of Set-Theoretic Involvement in Geometry.John P. Burgess - 1988 - PSA: Proceedings of the Biennial Meeting of the Philosophy of Science Association 1988:456 - 463.
Quasi-o-Minimal Structures.Oleg Belegradek, Ya'acov Peterzil & Frank Wagner - 2000 - Journal of Symbolic Logic 65 (3):1115-1132.

Analytics

Added to PP index
2010-08-24

Total views
27 ( #335,586 of 2,280,327 )

Recent downloads (6 months)
4 ( #308,912 of 2,280,327 )

How can I increase my downloads?

Downloads

My notes

Sign in to use this feature