Тема: Метаматематика

[Mrrl›]

Цитата из: Мёнин on 29-03-2006, 18:50:03

Цитата из: Mrrl on 28-03-2006, 23:39:03
Согласно записи, число 0,abcde... - это такое число x, для которого

0,a <= x < 0,a+0,1
0,ab <= x < 0,ab+0,01
0,abc <= x < 0,abc+0,001
...


Первый раз слышу.



Например, это написано в учебниках

Кудрявцев, "Краткий курс математического анализа", т.1, стр 88 (Москва, Физматлит, 2004)
Зорич, "Математический анализ", т.1, стр. 73 (МЦНМО, 2002)

и еще в паре переводных учебников (это то, что я нашел в ближайшем книжном).


               

               

[Симагин Гендо›]

Кстати, по поводу недетерминированных игр. Кому-нибудь интересно послушать про недетерминированную игру, не имеющую отношения к аксиоме выбора?

               

               

[Mrrl›]

Послушать всегда интересно. А имеет ли она отношение к этой теме - посмотрим.

               

               

[Симагин Гендо›]

Ну, вообще-то, строгого доказательства недетерминированности не существует (по крайней мере, оно мне неизвестно).
Суть задачи в следующем.
Есть каркас куба, по нему ползают два паука и таракан. МАсимальная скорость всех участников одинаковая.
В начале таракан находжится в одном углу, пауки в противоположном. Все участники являются точками.
Все друг друга видят. Цель пауков поймать таракана. У таракана, соответственно, цель убежать.
Вопрос - кто побеждает при правильной стратегии?
Автор задачи думал, что побеждают пауки, но он был неправ. А для доказательства недетерминированности необходимо определить, какие стратегии в данной игре допустимы. Что представляет собой достаточно сложную проблему теории функций.

               

               

[Mrrl›]

В теме "математические задачи" в ИР подобная задача  (http://tolkien.ru/forum/index.php?topic=22702.msg286452#msg286452) рассматривалась - но про тетраэдр (да и этой задаче, в общем, место там же). И как я понимаю, после ее решения остается такой вопрос: если паук и таракан находятся на смежных ребрах на одинаковом расстоянии от вершины, причем паук старается, чтобы это расстояние так и оставалось одинаковым (не больше, но и не меньше) - то может ли таракан через эту вершину ускользнуть? Обычно считается, что нет, т.е. время реакции паука намного меньше размеров паука и таракана (несмотря на то, что они "являются точками"). Как-то так.
Или есть еще проблемы, которых я не вижу?

               

               

[Симагин Гендо›]

Цитата из: Mrrl on 01-04-2006, 16:51:57
 И как я понимаю, после ее решения остается такой вопрос: если паук и таракан находятся на смежных ребрах на одинаковом расстоянии от вершины, причем паук старается, чтобы это расстояние так и оставалось одинаковым (не больше, но и не меньше) - то может ли таракан через эту вершину ускользнуть?


Если паук движется симметрично таракану, то таракан, конечно, не убежит. Проблема в том, что паук не имеет права это делать!
Если паук имеет право двигаться симметрично таракану, то то же право имеет и таракан (участники игры равноправны). И если паук и таракан оба используют данную стратегию, они движутся или нет?
Поскольку по стратегии нельзя однозначно установить, как будут происходить события, стратегия недопустима.
Возникает резонный вопрос - а какие стратегии в играх данного типа допустимы?
Есть 2 очевидных класса.
Класс I. Для каждого момента t и возможных положений сторон сторона определяет положительное число s (зависящее от ситуации), и некоторый маршрут для промежутка времени (t, t+s). И использует данный маршрут, не обращая внимания на действия противоположныной стороны. По истечении промежутка производится очередная оценка ситуации, и т. д.
Класс 2. Выбирается некоторая функция v, зависящая от положений сторон, и в каждый момент времени происходит движение со скоростью, равной v.

Можно доказать, что если возможные стратегии поведения исчерпываются двумя данными типами, и их всевозможными комбинациями, то в данной задаче ни у одной из сторон нет выигрывающей стратегии. Но существуют ли допустимые стратегии, отличные от комбинаций рассматриваемых? И если существуют, то верно ли для них доказательство недетерминированности, или нет?

               

               

[Арвинд›]

Цитата из: Симагин Гендо on 31-03-2006, 21:47:35
Кому-нибудь интересно послушать про недетерминированную игру, не имеющую отношения к аксиоме выбора?

Задача, возможно, подходит в эту тему как еще одна интересная математическая конструкция с неочевидным отношением к реальному миру.
Интересно было бы понять идею доказательства несуществования выигрышной стратегии. Возможно, выигрышную стратегию можно построить, если обрубить идеальную математическую модель каким-то физическим ограничением, чтобы не допустить ухода в бесконечно малые. Например, ввести массы паука и таракана (запретив им, соответственно, менять скорость мгновенно). Или добавить ограничение на скорость оценки ситуации и принятия решения...

               

               

[Mrrl›]

Цитата из: Симагин Гендо on 01-04-2006, 21:50:22
Если паук движется симметрично таракану, то таракан, конечно, не убежит. Проблема в том, что паук не имеет права это делать!
Если паук имеет право двигаться симметрично таракану, то то же право имеет и таракан (участники игры равноправны). И если паук и таракан оба используют данную стратегию, они движутся или нет?
Поскольку по стратегии нельзя однозначно установить, как будут происходить события, стратегия недопустима.



Если в выигрышной стратегии паука записано "держаться сииметрично таракану", а у таракана - "держаться сииметрично пауку", то можно принять, например, что они не движутся. И в данном случае (каркас куба) если таракан решил остановиться, то пауку надо сидеть, караулить и ждать, пока второй паук не доберется до установленного места. А потом со всех ног бежать к таракану.

К сожалению, пауку надо держаться симметрично таракану, а таракану - пытаться нарушить симетрию. И вопрос в том, как происходят события в этом случае.

Цитата из: Симагин Гендо on 01-04-2006, 21:50:22
Класс I. Для каждого момента t и возможных положений сторон сторона определяет положительное число s (зависящее от ситуации), и некоторый маршрут для промежутка времени (t, t+s). И использует данный маршрут, не обращая внимания на действия противоположныной стороны. По истечении промежутка производится очередная оценка ситуации, и т. д.



Можно вообще рассмотреть дискретную модель. В каждый момент игроки оценивают ситуацию и одновременно сдвигаются на допустимую величину. Тогда игра переходит в разряд игр, частным случаем которых являются игры с матрицами и седлыми точками - не помню, как они называются. Тогда выигрышной стратегии действительно нет, и таракан может продержаться в среднем C*2^m шагов, где m - число шагов, которые нужно потратить, чтобы пройти ребро куба. Оценка взята с потолка - возможно, я ошибаюсь.

Цитата из: Симагин Гендо on 01-04-2006, 21:50:22
Класс 2. Выбирается некоторая функция v, зависящая от положений сторон, и в каждый момент времени происходит движение со скоростью, равной v.



Допустим, паук и таракан сидят на прямой в точках p0=0, q0=2. Стратегия паука - vp=sign(q-p-1), стратегия таракана - vq=-0.5 (т.е. паук старается держаться на 1 левее, чем таракан). И что же будет происходить? По-моему, система решений не имеет.


               

               

[Mrrl›]

Буду собирать здесь ссылки на результаты, относящиеся к аксиоме детерминированности.



Построение недетерминированной игры в рамках ZF+AC
http://en.wikipedia.org/wiki/Axiom_of_determinacy[/url]
(там они перебирают стратегии игроков одну за другой, для каждой рассматривают все последовательности, которые могут получиться, если один игрок придерживается этой стратегии, а другой - какой угодно, убеждаются, что для одной из этих последовательностей они еще не решили, кто выиграет, и решают, что выиграет не тот игрок, стратегию которого рассматривали).

Доказательство того, что все множества измеримы (ZF+AD)
http://seminariomatematico.dm.unito.it/rendiconti/61-4/393.pdf

Доказательство счетной аксиомы выбора (в ZF+AD) и еще куча утверждений. Правда, статья очень сложная - я не понял почти ничего.
[url]http://www.illc.uva.nl/Publications/ResearchReports/PP-2005-19.text.pdf


Разыскиваются:
- доказательство континуум-гипотезы в ZF+AD.
"В ZF+AD континуум-гипотезу можно доказать в ее исходной формулировке - что любое бесконечное подмножество множества вещественных чисел является либо счетным, либо равномощным всему множеству вещественных чисел. Однако, сказать, что c=aleph_1, нельзя, поскольку континуум не может быть вполне упорядочен, и поэтому не равномощен вообще никакому aleph"



               

               

[Mrrl›]

Цитата из: Арвинд on 31-03-2006, 01:39:53

Цитата из: Mrrl on 31-03-2006, 01:07:36
если какое-то множество нельзя вполне упорядочить, то то же верно и для больших его по мощности.

Похоже на правду (спать пора, голова не работает).
Учитывая т. Кантора-Бернштейна или как её там. Во множестве большей мощности можно найти подмножество, эквивалентное рассматриваемому неупорядоченному множеству... Порядок индуцируется... Да, все правильно.



Ха-ха... Оказывается, теорема Кантора-Бернштейна говорит, что если существуют инъективные отображения из A в B и из B в A, то существует биекция между A и B. А вот утверждение, что из двух множеств мощность одного больше или равна мощности другого, эквивалентно аксиоме выбора! (Например, так написано здесь (http://en.wikipedia.org/wiki/Axiom_of_choice)). Так что надо начинать думать сначала.


               

               

[Mrrl›]

Не знает ли кто-нибудь ссылки на конструкцию "выворачивания сферы"?

               

               

[Мунин›]

Выворачивания или удвоения? Удвоение недавно описывалось, щас найду.

               

               

[Мунин›]

http://community.livejournal.com/ru_math/327175.html
если об этом речь.

               

               

[Mrrl›]

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

               

               

[Мунин›]

Хм. Могу в ru_math спросить :-)

               

               

[Мунин›]

http://community.livejournal.com/ru_math/346846.html

               

               

[Снорри›]

Сэнсэй, было предложение переехать с этой темой в Савешник. Пока никто не против, как я смотрю (в "Терминах" уже даже словарик неплохой подобрался, и ссылок собрали с миру по нитке), но за тобой - два голоса: один как от модератора Философии, второй - как от Саветника. Что скажешь?

P.S. Я тут немножко в Философии похороводил у тебя за спиной, пока ты отворачивался.
Надеюсь, я не сильно все испортил

               

               

[Мунин›]

О Многочисленный, позволь мне дважды (sic!) смиренно (не надеюсь, что мудро) промолчать, ибо я ни Философию не модерирую, ни в Савете не саветую. Меня сюда Эотан позвал, и как я понял, на один только вопрос. И вообще у меня в последнее время непонятки с тем, что мне в жизни интересно... знаю только одно: мне интересно лицезреть тебя вживую, но шансов ничтожно мало.

               

               

[Симагин Гендо›]

Цитата из: Арвинд on 02-04-2006, 13:43:14
Интересно было бы понять идею доказательства несуществования выигрышной стратегии.


Идея следующая: двое игроков дают свои стратегии некоему судье, и он по этим стратегиям определяет ход игры, и кто победил. Если для любой стратегии одного из игроков найдётся контрстратегия другого, и наоборот, это означает, что выигрывающей стратегии ни у кого нет.

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

Цитата:
Возможно, выигрышную стратегию можно построить, если обрубить идеальную математическую модель каким-то физическим ограничением, чтобы не допустить ухода в бесконечно малые.


Ну, это будет уже совсем другой класс задач. (Существует ряд известных задач этого типа, но для некоторых из них удаётся построить корректные выигрышные стратегии класса 1.)

Цитата из: Mrrl on 02-04-2006, 17:07:12
Если в выигрышной стратегии паука записано "держаться сииметрично таракану", а у таракана - "держаться сииметрично пауку", то можно принять, например, что они не движутся.


Это нельзя принять, т. к. в правилах этого нет. Если при разборе один игрок утверждает, что они покоятся, а другой - что движутся к соседней вершине, кто из игроков прав? Таким образом, время ловли получается неопределённым. Для других вариантов правил игры при обоюдно симметричной стратегии может быть вообще непонятно, кто победил - хищник или жертва.

Цитата:
Можно вообще рассмотреть дискретную модель.


И это будет уже совсем другая игра. Одна из особенностей стратегий класса 1 - в них время s может быть сколь угодно мало.

Цитата:
Допустим, паук и таракан сидят на прямой в точках p0=0, q0=2. Стратегия паука - vp=sign(q-p-1), стратегия таракана - vq=-0.5 (т.е. паук старается держаться на 1 левее, чем таракан). И что же будет происходить?


Естественно, функция скорости должна подчиняться таким ограничениям, чтобы выполнялась теорема существования и единственности. Для одномерного случая такие функции вряд ли применимы, но для двух и более измерений существует, например, стратегия "бежать с максимальной скоростью прямо на оппонента". Собственно, требования существования и единственности должны выполняться для любых корректных стратегий. И вопрос: для каких стратегий они выполнены?

               

               

[Mrrl›]

Цитата из: Симагин Гендо on 11-04-2006, 22:06:39

Цитата:
Можно вообще рассмотреть дискретную модель.


И это будет уже совсем другая игра. Одна из особенностей стратегий класса 1 - в них время s может быть сколь угодно мало.




Если ограничений на s нет, то может оказаться, что выигрывает тот, у кого используемое s меньше. Нехорошо. А если ограничение есть - то можно переписать стратегию, используя минимально возможное значение s. Более точно - на каждом шаге можно выбрать s из полуинтервала [smin, 2*smin). И если начнется игра "кто выберет момент для очередной оценки ситуации на эпсилон позже момента, выбранного другим - тот и победил", то тоже может быть грустно. А тут еще встречная стратегия может иметь вид "четверть секунды стоим, чтобы сбить с толку оппонентов, если они проснутся именно в этот интервал времени, а потом бежим к вон той вершине"... все равно придется бросать кубик.
  Дискретная игра немного понятнее.

Цитата:

Цитата:
Допустим, паук и таракан сидят на прямой в точках p0=0, q0=2. Стратегия паука - vp=sign(q-p-1), стратегия таракана - vq=-0.5 (т.е. паук старается держаться на 1 левее, чем таракан). И что же будет происходить?


Естественно, функция скорости должна подчиняться таким ограничениям, чтобы выполнялась теорема существования и единственности. Для одномерного случая такие функции вряд ли применимы, но для двух и более измерений существует, например, стратегия "бежать с максимальной скоростью прямо на оппонента". Собственно, требования существования и единственности должны выполняться для любых корректных стратегий. И вопрос: для каких стратегий они выполнены?



Говорят, что достаточно выполнения условия Липшица: если для двух состояний (a,b1,b2) и (a',b1',b2') имеем
max(d(a,a'),d(b1,b1'),d(b2,b2'))=m (можно взять и другие метрики), то вычисленные скорости v, v' отличаются не более чем на C*m для некоторого C. Правда, это относится к уравнениям на прямой. А на графе придется подумать, как должно выглядеть условие на вершине (когда перед игроком стоит выбор - куда бежать).

Любопытный вариант. Тем, что игроки не видят скоростей друг друга (и не могут их вычислить, т.к. нет памяти), так что игра по-прежнему не с полной информацией. Какие уж тут стратегии.