Index sets for \(\Pi^0_1\) classes (Q1295386): Difference between revisions

The authors present an effective enumeration of the \(\Pi_1^0\) classes and then investigate the index sets corresponding to various properties of \(\Pi_1^0\) classes. The paper deals with index sets arising in a wide range of contexts, from measure and category to logical theories to combinatorial questions. Particular attention is paid to boundedness of trees, with a couple of new versions of boundedness being introduced.

0 references

reviewed by

Leon Harkleroad

0 references

zbMATH Keywords

index set

0 references

\(\Pi_1^0\) class

0 references

effective enumeration

0 references

measure and category

0 references

logical theories

0 references

combinatorial questions

0 references

boundedness of trees

0 references

MaRDI profile type

MaRDI publication profile

0 references

cites work

Effective coloration

0 references

On the complexity of finding the chromatic number of a recursive graph. I: The bounded case

0 references

On the complexity of finding the chromatic number of a recursive graph. II: The unbounded case

0 references

Members of countable \(\Pi ^ 0_ 1\) classes

0 references

Countable thin \(\Pi^0_1\) classes

0 references

On the Borel class of the derived set operator. II

0 references

Q5551157

0 references

Hierarchies of Boolean algebras

0 references

Q4249726

0 references

Q4764107

0 references

Index sets of finite classes of recursively enumerable sets

0 references

A topological analog to the Rice-Shapiro index theorem

0 references

The index set {e: We ≡1X}.

0 references

Q4146722

0 references

Π01-classes and Rado's selection principle

0 references

∏ 0 1 Classes and Degrees of Theories

0 references

Degrees of members of \(\Pi_ 1^ 0\) classes

0 references

Hierarchies of number-theoretic predicates

0 references

Q3269140

0 references

Q5605137

0 references

Hyperarithmetical Index Sets in Recursion Theory

0 references

Effective Matchmaking (Recursion Theoretic Aspects of a Theorem of Philip Hall)

0 references

Axiomatizable theories with few axiomatizable extensions

0 references

Classical recursion theory. Vol. II

0 references

On the Effectiveness of the Schroder-Bernstein Theorem

0 references

Graph colorings and recursively bounded \(\Pi ^ 0_ 1\)-classes

0 references

Index sets in the hyperarithmetical hierarchy

0 references

Index sets of classes of hyper-hypersimple sets

0 references

Fine hierarchy and definable index sets

0 references

Degrees of formal systems

0 references

Q4040892

0 references

Recursive and r.e. quotient Boolean algebras

0 references

Identifiers

zbMATH Open document ID

0926.03042

0 references

DOI

10.1016/S0168-0072(97)00052-3

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:1295386

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