ERDOS-SZEKERES-TYPE STATEMENTS: RAMSEY FUNCTION AND DECIDABILITY IN DIMENSION 1

摘要

A classical and widely used lemma of Erdos and Szekeres asserts that for every n there exists N such that every N-term sequence a of real numbers contains an n-term increasing subsequence or an n-term nonincreasing subsequence; quantitatively, the smallest N with this property equals (n - 1)(2) + 1. In the setting of the present paper, we express this lemma by saying that the set of predicates Phi = {x(1) < x(2), x(1) > x(2)} is Erdos-Szekeres with Ramsey function ES Phi (n) = (n - 1)(2) + 1.