Fine hierarchies and Boolean terms
- 12 March 1995
- journal article
- Published by Cambridge University Press (CUP) in The Journal of Symbolic Logic
- Vol. 60 (1) , 289-317
- https://doi.org/10.2307/2275522
Abstract
We consider fine hierarchies in recursion theory, descriptive set theory, logic and complexity theory. The main results state that the sets of values of different Boolean terms coincide with the levels of suitable fine hierarchies. This gives new short descriptions of these hierarchies and shows that collections of sets of values of Boolean terms are almost well ordered by inclusion. For the sake of completeness we mention also some earlier results demonstrating the usefulness of fine hierarchies.Keywords
This publication has 14 references indexed in Scilit:
- Some results in the wadge hierarchy of borel setsPublished by Springer Nature ,2006
- On the boolean closure of NPPublished by Springer Nature ,2005
- Computing degrees of definable classes of sentencesContemporary Mathematics, 1992
- Fine hierarchy and definable index setsAlgebra and Logic, 1991
- Refined hierarchy of formulasAlgebra and Logic, 1991
- Index sets in the hyperarithmetical hierarchySiberian Mathematical Journal, 1985
- Equivalence relations, invariants, and normal forms, IIPublished by Springer Nature ,1984
- Hierearchies of hyperarithmetical sets and functionsAlgebra and Logic, 1983
- Convex subsets of 2n and bounded truth-table reducibilityDiscrete Mathematics, 1978
- Wadge degrees and descriptive set theoryPublished by Springer Nature ,1978