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 setlogical theories\(\Pi_1^0\) classmeasure and categorycombinatorial questionsboundedness of treeseffective enumeration

Mathematics Subject Classification ID

Applications of computability and recursion theory (03D80) Recursively (computably) enumerable sets and degrees (03D25) Hierarchies of computability and definability (03D55)

Related Items

A rank one cohesive set, Index Sets for Finite Normal Predicate Logic Programs with Function Symbols, Rice’s Theorem in Effectively Enumerable Topological Spaces, A connection between the Cantor-Bendixson derivative and the well-founded semantics of finite logic programs, PAC learning, VC dimension, and the arithmetic hierarchy, Computable elements and functions in effectively enumerable topological spaces, Effectively closed sets and enumerations, RANK AND RANDOMNESS, Index sets in computable analysis, ORDINAL ANALYSIS OF PARTIAL COMBINATORY ALGEBRAS, 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, Effectively closed sets and graphs of computable real functions., Logic programming with infinite sets

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