Annals of Pure and Applied Logic 37 (2):101-110 (1988)

Abstract
We prove the following results: every recursively enumerable set approximated by finite sets of some set M of recursively enumerable sets with index set in π 2 is an element of M , provided that the finite sets in M are canonically enumerable. If both the finite sets in M and in M̄ are canonically enumerable, then the index set of M is in σ 2 ∩ π 2 if and only if M consists exactly of the sets approximated by finite sets of M and the complement M̄ consists exactly of the sets approximated by finite sets of M̄ . Under the same condition M or M̄ has a non-empty subset with recursively enumerable index set, if the index set of M is in σ 2 ∩ π 2 . If the finite sets in M are canonically enumerable, then the following three statements are equivalent: the index set of M is in σ 2 \ π 2 , the index set of M is σ 2 -complete, the index set of M is in σ 2 and some sequence of finite sets in M approximate a set in M̄ . Finally, for every n ⩾ 2, an index set in σ n \ π n is presented which is not σ n -complete
Keywords No keywords specified (fix it)
Categories (categorize this paper)
DOI 10.1016/0168-0072(88)90023-1
Options
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: 70,130
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

Index Sets Universal for Differences of Arithmetic Sets.Louise Hay - 1974 - Zeitschrift fur mathematische Logik und Grundlagen der Mathematik 20 (13-18):239-254.
Index Sets Universal for Differences of Arithmetic Sets.Louise Hay - 1974 - Mathematical Logic Quarterly 20 (13‐18):239-254.
On the Size of Machines.[author unknown] - 1972 - Journal of Symbolic Logic 37 (1):199-200.

Add more references

Citations of this work BETA

No citations found.

Add more citations

Similar books and articles

The Hausdorff-Ershov Hierarchy in Euclidean Spaces.Armin Hemmerling - 2006 - Archive for Mathematical Logic 45 (3):323-350.
Immunity and Hyperimmunity for Sets of Minimal Indices.Frank Stephan & Jason Teutsch - 2008 - Notre Dame Journal of Formal Logic 49 (2):107-125.
A Hierarchy of Hereditarily Finite Sets.Laurence Kirby - 2008 - Archive for Mathematical Logic 47 (2):143-157.
Fuzzy Logic and Arithmetical Hierarchy III.Petr Hájek - 2001 - Studia Logica 68 (1):129-142.
Monotone Reducibility and the Family of Infinite Sets.Douglas Cenzer - 1984 - Journal of Symbolic Logic 49 (3):774-782.
Index Sets and Parametric Reductions.Rod G. Downey & Michael R. Fellows - 2001 - Archive for Mathematical Logic 40 (5):329-348.
The Arithmetical Hierarchy of Real Numbers.Xizhong Zheng & Klaus Weihrauch - 2001 - Mathematical Logic Quarterly 47 (1):51-66.
Index Sets in Ershov's Hierarchy.Jacques Grassin - 1974 - Journal of Symbolic Logic 39 (1):97-104.
Kleene Index Sets and Functional M-Degrees.Jeanleah Mohrherr - 1983 - Journal of Symbolic Logic 48 (3):829-840.
Fuzzy Logic and Arithmetical Hierarchy, II.Petr Hájek - 1997 - Studia Logica 58 (1):129-141.
A Revision-Theoretic Analysis of the Arithmetical Hierarchy.Gian Aldo Antonelli - 1994 - Notre Dame Journal of Formal Logic 35 (2):204-218.

Analytics

Added to PP index
2014-01-16

Total views
11 ( #852,267 of 2,506,443 )

Recent downloads (6 months)
1 ( #416,997 of 2,506,443 )

How can I increase my downloads?

Downloads

My notes