A \(\Delta_2^0\) set with no infinite low subset in either it or its complement (Q2758065)
From MaRDI portal
 | This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use this page instead for the normal view: A \(\Delta_2^0\) set with no infinite low subset in either it or its complement |
scientific article; zbMATH DE number 1679338
| Language | Label | Description | Also known as |
|---|---|---|---|
| English | A \(\Delta_2^0\) set with no infinite low subset in either it or its complement |
scientific article; zbMATH DE number 1679338 |
Statements
18 July 2002
0 references
computability
0 references
recursion theory
0 references
reverse mathematics
0 references
low
0 references
Ramsey
0 references
A \(\Delta_2^0\) set with no infinite low subset in either it or its complement (English)
0 references
The authors use a priority argument to prove the existence of the set in the title. Their argument can be relativised to construct a \(\Delta^0_3\) set with no infinite low\(_2\) set in either it or its complement, answering an open question posed by \textit{P. A. Cholak, C. G. Jockusch}, and \textit{T. A. Slaman} [J. Symb. Log. 66, 1-55 (2001; Zbl 0977.03033)]. This work has consequences in the program of reverse mathematics cofounded by \textit{S. G. Simpson} [Subsystems of second order arithmetic, Berlin: Springer (1999; Zbl 0909.03048)]. It shows that every \(\omega\)-model of \(\text{RCA}_0\) plus Ramsey's Theorem for stable two-colorings of pairs must contain a nonlow set. Consequently, the \(\omega\)-model of WKL\(_0\) consisting only of low sets does not model the Stable Ramsey's Theorem for pairs and two colors.
0 references
