z-logo
open-access-imgOpen Access
On the role of the collection principle for Σ⁰₂-formulas in second-order reverse mathematics
Author(s) -
Chai Tai Chong,
Steffen Lempp,
Yang Yue
Publication year - 2009
Publication title -
proceedings of the american mathematical society
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.968
H-Index - 84
eISSN - 1088-6826
pISSN - 0002-9939
DOI - 10.1090/s0002-9939-09-10115-6
Subject(s) - algorithm , annotation , artificial intelligence , computer science
We show that the principle  P A R T \mathsf {PART} from Hirschfeldt and Shore is equivalent to the Σ 2 0 \Sigma ^0_2 -Bounding principle  B Σ 2 0 B\Sigma ^0_2 over  R C A 0 \mathsf {RCA}_0 , answering one of their open questions. Furthermore, we also fill a gap in a proof of Cholak, Jockusch and Slaman by showing that D 2 2 D^2_2 implies  B Σ 2 0 B\Sigma ^0_2 and is thus indeed equivalent to Stable Ramsey’s Theorem for Pairs ( S R T 2 2 \mathsf {SRT}^2_2 ). This also allows us to conclude that the combinatorial principles I P T 2 2 \mathsf {IPT}^2_2 , S P T 2 2 \mathsf {SPT}^2_2 and  S I P T 2 2 \mathsf {SIPT}^2_2 defined by Dzhafarov and Hirst all imply  B Σ 2 0 B\Sigma ^0_2 and thus that S P T 2 2 \mathsf {SPT}^2_2 and  S I P T 2 2 \mathsf {SIPT}^2_2 are both equivalent to  S R T 2 2 \mathsf {SRT}^2_2 as well. Our proof uses the notion of a bi-tame cut, the existence of which we show to be equivalent, over  R C A 0 \mathsf {RCA}_0 , to the failure of  B Σ 2 0 B\Sigma ^0_2 .

The content you want is available to Zendy users.

Already have an account? Click here to sign in.
Having issues? You can contact us here