×

\(\Pi_1^0\) classes – structure and applications. (English) Zbl 0962.03040

Cholak, Peter A. (ed.) et al., Computability theory and its applications. Current trends and open problems. Proceedings of a 1999 AMS-IMS-SIAM joint summer research conference, Boulder, CO, USA, June 13-17, 1999. Providence, RI: American Mathematical Society (AMS). Contemp. Math. 257, 39-59 (2000).
Summary: We present results and open problems on \(\Pi^0_1\) classes, which are effectively closed sets of reals. These include applications of \(\Pi^0_1\) classes to various mathematical problems in analysis, combinatorics, and the theory of orderings in which the complexity of solutions to the problems is considered. This complexity can be measured in terms of Turing degrees, and in the sense of index sets for certain properties of the solution set. Such questions are closely related to the strength of the statement that solutions exist, in the sense of “reverse mathematics.” Effective Ramsey theory is given special attention. The lattice structure of the \(\Pi^0_1\) classes is compared with the structure of the \(\Pi^0_1\) subsets of \(\omega\) and several open problems are given on the lattice of \(\Pi_1^0\) classes of sets.
For the entire collection see [Zbl 0945.00017].

MSC:

03D80 Applications of computability and recursion theory
03D30 Other degrees and reducibilities in computability and recursion theory
03D25 Recursively (computably) enumerable sets and degrees
03C62 Models of arithmetic and set theory
03E15 Descriptive set theory
03F35 Second- and higher-order arithmetic and fragments
03F60 Constructive and recursive analysis
PDFBibTeX XMLCite