×

zbMATH — the first resource for mathematics

Generalized r-cohesiveness and the arithmetical hierarchy: A correction to “Generalized cohesiveness”. (English) Zbl 1011.03033
The paper under review is connected with the authors’ paper “Generalized cohesiveness” [J. Symb. Log. 64, 489-516 (1999; Zbl 0935.03050)]. The main result of the present paper for \(n = 2\) refutes a result previously claimed by the authors, and for \(n \geq 3\) answers a question raised in the mentioned paper. To explain the result, let, for \(X \subseteq \omega\), \([X^n]\) denote the class of all subsets of \(X\). An infinite set \(A \subseteq \omega\) is called \(n\)-r-cohesive iff for each computable function \(f: [\omega]^{n} \rightarrow \{ 0,1 \}\) there is a finite set \(F\) such that \(f\) is constant on \([A- f^n]\). It is shown that for each \(n \geq 2\) there is no \(\Pi_{n}^{0}\) set \(A \subseteq \omega\) which is \(n\)-r-cohesive.
MSC:
03D55 Hierarchies of computability and definability
03D28 Other Turing degree structures
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] Proceedings of the London Mathematical Society 30 pp 264– (1930)
[2] Ramsey’s theorem and recursion theory 37 pp 268– (1972)
[3] Recursively enumerable sets and degrees (1987)
[4] Generalized cohesiveness 64 pp 489– (1999) · Zbl 0935.03050
[5] Ramsey’s theorem for computably enumerable colorings 66 pp 873– (2001)
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. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.