Hostname: page-component-7b7567c8c-wxvwp Total loading time: 0 Render date: 2026-11-17T04:57:14.053Z Has data issue: false hasContentIssue false

Fine hierarchies and Boolean terms

Published online by Cambridge University Press:  12 March 2014

V. L. Selivanov*
Affiliation:
Department of Mathematics, Pedagogical University, Viluiskaya St. 28, 630126 Novosibirsk, Russia, E-mail: vseliv@ngpi.nsk.su

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.

Information

Type
Research Article
Copyright
Copyright © Association for Symbolic Logic 1995

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Article purchase

Temporarily unavailable