# Index sets in the arithmetical Hierarchy

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

## PhilArchive

Upload a copy of this work     Papers currently archived: 86,168

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

# 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.

2014-01-16

15 (#775,443)

6 months
4 (#243,083)