Index sets in the arithmetical Hierarchy

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

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

Links

PhilArchive



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

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

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
2014-01-16

Downloads
11 (#837,886)

6 months
1 (#417,896)

Historical graph of downloads
How can I increase my downloads?

Citations of this work

No citations found.

Add more citations

References found in this work

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