×

Fine hierarchies and Boolean terms. (English) Zbl 0824.03022

Summary: 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 finite 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.

MSC:

03D55 Hierarchies of computability and definability
03E15 Descriptive set theory
03D15 Complexity of computation (including implicit computational complexity)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Determinateness and the separation property 45 pp 143– (1980)
[2] DOI: 10.1007/BFb0069298 · doi:10.1007/BFb0069298
[3] Set theory (1967)
[4] The difference and truth-table hierarchies for NP (1986)
[5] Recursion-theoretic hierarchies (1978) · Zbl 0371.02017
[6] DOI: 10.1016/0012-365X(78)90145-0 · Zbl 0377.02036 · doi:10.1016/0012-365X(78)90145-0
[7] Grundzüge der Mengenlehre (1914) · JFM 45.0123.01
[8] Algebra and Logic 7 pp 15– (1968)
[9] Logic and machines: Decision problems and complexity 171 pp 24– (1986)
[10] Structural complexity 1 11 (1988)
[11] The theory of models (1965)
[12] Algebra and Logic 30 pp 568– (1991)
[13] Algebra and Logic 30 pp 705– (1991)
[14] Trudy Matematicheskaga Instituta Akademiya Nauk SSSR 12 pp 165– (1989)
[15] Siberian Mathematical Journal 25 pp 164– (1984)
[16] Algebra and Logic 22 pp 666– (1983)
[17] Trudy Matematicheskogo Instituta Sbornik Obzornykh Akademiya Nauk SSSR pp 135– (1982)
[18] Theory of recursive functions and effective computability (1967) · Zbl 0183.01401
[19] Uspekhi Matematicheskikh Nauk 65 pp 71– (1955)
[20] Descriptive set theory (1980) · Zbl 0433.03025
[21] DOI: 10.1007/BFb0071692 · doi:10.1007/BFb0071692
[22] Proceedings of the 1985 international conference on fundamentals of computation theory 199 pp 485– (1985)
[23] Comtemprory Mathematics 131 pp 657– (1992)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.