Index sets for \(\Pi^0_1\) classes

DOI10.1016/S0168-0072(97)00052-3zbMath0926.03042MaRDI QIDQ1295386

Douglas Cenzer, Jeffery B. Remmel

Publication date: 23 November 1999

Published in: Annals of Pure and Applied Logic (Search for Journal in Brave)

zbMATH Keywords

index set; logical theories; \(\Pi_1^0\) class; measure and category; combinatorial questions; boundedness of trees; effective enumeration

Mathematics Subject Classification ID

03D80: Applications of computability and recursion theory

03D25: Recursively (computably) enumerable sets and degrees

03D55: Hierarchies of computability and definability

Related Items

Computable elements and functions in effectively enumerable topological spaces, RANK AND RANDOMNESS, Index Sets for Finite Normal Predicate Logic Programs with Function Symbols, Enumerations of <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" altimg="si1.gif" overflow="scroll"><mml:msubsup><mml:mi mathvariant="normal">Π</mml:mi><mml:mn>1</mml:mn><mml:mn>0</mml:mn></mml:msubsup></mml:math> Classes: Acceptability and Decidable Classes, Logic programming with infinite sets, PAC learning, VC dimension, and the arithmetic hierarchy, Effectively closed sets and enumerations, Index sets in computable analysis, A rank one cohesive set, Effectively closed sets and graphs of computable real functions., A connection between the Cantor-Bendixson derivative and the well-founded semantics of finite logic programs, Rice’s Theorem in Effectively Enumerable Topological Spaces

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Graph colorings and recursively bounded \(\Pi ^ 0_ 1\)-classes
• On the complexity of finding the chromatic number of a recursive graph. II: The unbounded case
• Index sets in the hyperarithmetical hierarchy
• Members of countable \(\Pi ^ 0_ 1\) classes
• Index sets of classes of hyper-hypersimple sets
• Countable thin \(\Pi^0_1\) classes
• Classical recursion theory. Vol. II
• Recursive and r.e. quotient Boolean algebras
• On the complexity of finding the chromatic number of a recursive graph. I: The bounded case
• Fine hierarchy and definable index sets
• Degrees of members of \(\Pi_ 1^ 0\) classes
• Hierarchies of number-theoretic predicates
• Degrees of formal systems
• On the Borel class of the derived set operator. II
• A topological analog to the Rice-Shapiro index theorem
• The index set {e: W_e ≡₁X}.
• Hyperarithmetical Index Sets in Recursion Theory
• On the Effectiveness of the Schroder-Bernstein Theorem
• Π₀¹-classes and Rado's selection principle
• Effective coloration
• Index sets of finite classes of recursively enumerable sets
• Axiomatizable theories with few axiomatizable extensions
• Hierarchies of Boolean algebras
• Effective Matchmaking (Recursion Theoretic Aspects of a Theorem of Philip Hall)
• ∏ 0 1 Classes and Degrees of Theories