Another well known result of Ramsey theory is Van der Waerden's theorem:
If is colored with finitely many colors, then one of the colors contains arithmetic progressions of arbitrary finite length.Using a method of Shelah, Van der Waerden's theorem is known to be provable in . The so-called ``density version'' of Van der Waerden's theorem is due to Szemerédi:
If is such thatEssentially nothing is known about the strength of Szemerédi's theorem. In particular it is unknown whether Szemerédi's theorem is provable in .
then A contains arithmetic progressions of arbitrary finite length.