zbMATH — the first resource for mathematics

\(\Pi_1^0\) classes in mathematics. (English) Zbl 0941.03044
Ershov, Yu. L. (ed.) et al., Handbook of recursive mathematics. Vol. 2: Recursive algebra, analysis and combinatorics. Amsterdam: Elsevier. Stud. Logic Found. Math. 139, 623-821 (1998).
A survey (including some new results) of the occurrences and uses of \(\Pi^0_1\) classes in areas such as logic, nonmonotonic logic, algebra, analysis, and combinatorics. More specifically, a typical result here represents \(\Pi^0_1\) classes by solutions to problems in one of these areas of application. E.g., given a recursive graph, its set of \(k\)-colorings forms a recursively bounded \(\Pi^0_1\) class. The representation result, loosely stated, is that every recursively bounded \(\Pi^0_1\) class arises in this manner. Such a representation then allows the general machinery of \(\Pi^0_1\) classes to be brought to bear on, in this case, recursive graph theory. Polynomial-time versions of these ideas are also treated.
For the entire collection see [Zbl 0905.03002].

03D45 Theory of numerations, effectively presented structures
03-02 Research exposition (monographs, survey articles) pertaining to mathematical logic and foundations
03D15 Complexity of computation (including implicit computational complexity)
03D30 Other degrees and reducibilities in computability and recursion theory
03D35 Undecidability and degrees of sets of sentences