2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Элиминация кванторов Рамсея. Множество свидетелей.
Сообщение02.06.2013, 18:27 


01/04/12
13
Читаю статью "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 в ограниченном доступе, так что прикладываю сюда ее скан, чтобы показать оригинал статьи.
Изображение
Изображение
Есть идеи?
Заранее спасибо!

 Профиль  
                  
 
 Re: Элиминация кванторов Рамсея. Множество свидетелей.
Сообщение02.06.2013, 23:01 


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

 Профиль  
                  
 
 Re: Элиминация кванторов Рамсея. Множество свидетелей.
Сообщение03.06.2013, 04:09 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Элиминация кванторов Рамсея. Множество свидетелей.
Сообщение03.06.2013, 08:33 


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

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

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

 Профиль  
                  
 
 Re: Элиминация кванторов Рамсея. Множество свидетелей.
Сообщение03.06.2013, 08:39 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Элиминация кванторов Рамсея. Множество свидетелей.
Сообщение03.06.2013, 08:45 


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

 Профиль  
                  
 
 Re: Элиминация кванторов Рамсея. Множество свидетелей.
Сообщение03.06.2013, 08:48 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Элиминация кванторов Рамсея. Множество свидетелей.
Сообщение03.06.2013, 08:55 


01/04/12
13
Xaositect
Да, понятно. Спасибо.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 8 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group