Элиминация кванторов Рамсея. Множество свидетелей.

[Nikta]

Читаю статью "On the Role of Ramsey Quantifiers in First Order Arithmetic", есть там доказательство того, что кванторы Рамсея элиминируются в арифметике Пресбургера. Вот непонятно мне там пару моментов в доказательстве.
Собственно, вид это все имеет следующий:
Утверждается, что можно элиминировать квантор Рамсея (существует бесконечное множество, такое что для всех его н-элементных подмножеств выполняется ... ) в арифметике Пресбургера.
Вводится упорядоченная модификация этого квантора, где все элементы подмножеств упорядочены по возрастанию.
Необходимо и достаточно доказать теорему для формулы вида $Q^n_{0,x_1,...x_n}\varphi(x_1,...,x_n,y_1,...,y_k)$, где $\varphi$ -бескванторная формула, которая является булевой комбинацией атомарных формул, которые могут иметь один из следующих видов.
1 $a_1x_1+...+a_nx_n = b_1y_1+...+b_ky_k+c$
2 $a_1x_1+...+a_nx_n > b_1y_1+...+b_ky_k+c$
3 $a_1x_1+...+a_nx_n =_m b_1y_1+...+b_ky_k+c$
Ну, 1-я сводится ко 2-й это понятно.
Далее, утверждается, что если во 2й есть ненулевой коэффициент $a_i>0$, то любое неограниченное множество Х может быть урезано до множества свидетелей для (2). Вот этот шаг не вполне понятен.
Статья на JSTOR'e в ограниченном доступе, так что прикладываю сюда ее скан, чтобы показать оригинал статьи.


Есть идеи?
Заранее спасибо!

[Nikta]

Вижу, что просмотры идут. Буду признательна любым идеям.

[Xaositect]

Имеется в виду следующее: для любого неограниченного множества $X$ найдется подмножество $X'\subset X$ такое, что на $X'$ формула (2) будет либо тождественно истинна, либо тождественно ложна. Построить его можно, например, убрав из $X$ близкие друг к другу элементы - легко доказать, что (2) будет, в зависимости от знака коэффициента при наибольшем иксе, истинна или ложна, если $x_k > x_{k - 1} + D$ при некотором достаточно большом $D$.

[Nikta]

Xaositect
Спасибо за ответ. Саму формулировку я поняла, не могу понять шаг, приводящий к такому выводу.

Т.е., при ненулевом коэффициенте мы имеем формулу такую $a_1x_1+...+a_jx_j > b_1y_1+...+b_ky_k+c$, далее берем подмножество $X'$ такое, что в нем все элементы на расстоянии большем некоторого большого D. Тогда с левой частью-то понятно, а про y из правой-то мы не знаем ничего.

И еще вопрос про формулу (3), у нас остаются все формулы вида(3), мы берем их НОК. Почему любое множество свидетелей для формулы, являющейся булевой комбинацией формул вида (3), будет иметь подмножество, где все элементы обладают одним остатком от деления на M?

[Xaositect]

$D$ может зависеть от $y$. У нас же множество $X$ в кванторе может зависеть от $y$.

Nikta в сообщении #731857 писал(а):

И еще вопрос про формулу (3), у нас остаются все формулы вида(3), мы берем их НОК. Почему любое множество свидетелей для формулы, являющейся булевой комбинацией формул вида (3), будет иметь подмножество, где все элементы обладают одним остатком от деления на M?

By the pigeonhole principle. Если множество бесконечно, то хотя бы один из остатков будет встречаться бесконечное количество раз.

[Nikta]

Xaositect
Пардон, утро... Вылетело из головы, что множество бесконечно...про принцип Дирихле поняла.
То есть мы можем взять, например, $D>y_1+...+y_k$ и скалдывается.

[Xaositect]

Да, только D будет зависеть от $a$ и $b$

[Nikta]

Xaositect
Да, понятно. Спасибо.