Artykuły w formacie PDF dostępne są dla subskrybentów, którzy zapłacili za dostęp online, po podpisaniu licencji Licencja użytkownika instytucjonalnego. Czasopisma do 2009 są ogólnodostępne (bezpłatnie).

Brown’s lemma in second-order arithmetic

Tom 238 / 2017

Emanuele Frittaion Fundamenta Mathematicae 238 (2017), 269-283 MSC: Primary 03B30; Secondary 11B75. DOI: 10.4064/fm221-9-2016 Opublikowany online: 23 February 2017

Streszczenie

Brown’s lemma states that in every finite coloring of the natural numbers there is a homogeneous piecewise syndetic set. We show that Brown’s lemma is equivalent to $\mathsf {I}\Sigma ^0_2$ over $\mathsf {RCA}_0^*$. We show in contrast that (infinite) van der Waerden’s theorem is equivalent to $\mathsf {B}\Sigma ^0_2$ over $\mathsf {RCA}_0^*$. We finally consider the finite version of Brown’s lemma and show that it is provable in $\mathsf {RCA}_0$ but not in $\mathsf {RCA}_0^*$.

Autorzy

  • Emanuele FrittaionMathematical Institute
    Tohoku University
    Tohoku, Japan
    e-mail

Przeszukaj wydawnictwa IMPAN

Zbyt krótkie zapytanie. Wpisz co najmniej 4 znaki.

Przepisz kod z obrazka

Odśwież obrazek

Odśwież obrazek