мимоходом, математическое

[avva]

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

Аня и Борис играют следующим образом: сначала они выбирают какое-то подмножество отрезка [0,1], назовем его S. Затем, начиная с последовательности 0, 1, ... они на каждом шагу выбирают число, находящееся между двумя предыдущими. Например: 0, 1, А-0.5, Б-0.9, А-0.73, Б-0.742, А-0.739991 итд. Вырастающая таким образом последовательность сходится к какому-то числу x. Если x лежит внутри S, то Аня победила, если нет - Борис.

С одной стороны, если S - весь отрезок [0,1], to Аня тривиальным образом побеждает в любой игре. С другой стороны, если S - счетное множество {s_1, s_2, s_3, ...}, то у Бориса есть выигрышная стратегия: на шаге номер n он выбирает число s_n, если оно лежит в разрешенных границах, или наугад, если не лежит; в итоге в любом случае предел последовательности не может быть s_n. Так как он делает это для каждого n, предел последовательности не лежит в S и он выиграл. Вывод: [0,1] не может быть счетным множеством.

На первый взгляд это кажется остроумным способом доказать несчетность отрезка, хотя интуитивно сразу ясно, что он не более прост, чем каноническое доказательство Кантора. Но если присмотреться, то видно, что на самом деле "игра" тут вещь наносная, ненужная. Есть доказательства или понятия, которые выигрывают оттого, что их формулируют в терминах стратегии какой-то простой игры, но это - не одно из них. Можно ведь то же самое сказать так: предположим, что [0,1] можно пересчитать как {s_1, s_2, ...}. Начнем делить отрезок пополам, каждый раз выбирая ту половину, в которой нет следующего из чисел s_1, s_2, ... Продолжая таким образом, получим последовательность вложенных отрезков, сходящихся к одной точке, которая не может быть ни одной из s_1, s_2, ... - противоречие. Это то же самое доказательство, но внезапно куда-то исчезла Аня и вообще "игра". Они не были на самом деле нужны. В конечном итоге все это частные случаи доказательства того, что любое совершенное множество несчетно. Но стандартное доказательство этого факта требует знакомства с началами топологии, и его не объяснить "на пальцах".

Comments

[ush.livejournal.com]

А если не сходится?

[avva.livejournal.com]

Сходится, но это надо отдельно доказывать.

[ush.livejournal.com]

Аня монотонно идёт от нуля к 1/2, Борис от единицы к 2/3. Ни пса не сойдётся.

[avva.livejournal.com]

Да, Вы правы, я плохо сформулировал - давайте скажем, что x - предел выборов Ани. Эти выборы - монотонная последовательность, ограниченная сверху, она сходится. Все остальное без изменений.

[migmit.vox.com (from livejournal.com)]

Это называется "игра Банаха-Мазура". Гипотеза о том, что, каким бы ни было множество S, у одного из игроков есть выигрышная стратегия - очень сильное утверждение, противоречащее аксиоме выбора. Когда мы разбирали эту гипотезу на семинаре, у нас вообще сложилось ощущение, что ZF с этой гипотезой должна бы стать противоречивой, потому что доказывается, похоже, всё вообще и всё примерно одинаково. Вроде бы, однако, не становится.

[master-nemo.livejournal.com]

+0,9

to avva: не к вам претензия (да и не претензия вообще) просто наблюдение: очень забавно выглядит когда говорится о чем-то математическом на примере игры и вот мы слушаем и... кроме имен персонажей все остальное совпадает с доказательством соответствующей теоремы на лекции ВУЗе.... я все понимаю что игра эта для студентов среднего возраста, но просто звучит потрясающе... "Сказка детская, пятьсот рублей..."© выбираем подмножество на отрезке.....

а вообще спасибо! как-то оно по другому выглядит когда её не к экзамену готовишь :)))

[slobin.livejournal.com]

Я про эту штуку слышал под названием "аксиома детерминированности". Что она вроде бы несовместна с аксиомой выбора, но зато может использоваться вместо неё. Доказательства получаются совершенно в другом стиле, но математика не разваливается. Но я чайник, знаю об этом только на уровне популярных брошюрок. :-(

... Как же его нет, когда я сам его неоднократно испытывал? ...

[migmit.vox.com (from livejournal.com)]

Ага, точно. Я забыл название аксиомы.

офф-топ

[sciuro.livejournal.com]

Я что-то не могу найти твой пост, где тебе насоветовали про покупку фотоаппарата. Можешь дать ссылку, если ее не очень трудно раскопать?

Re: офф-топ

[avva.livejournal.com]

http://avva.livejournal.com/1787773.html

Re: офф-топ

[sciuro.livejournal.com]

А что ты купил в результате? доволен ли?

Re: офф-топ

[avva.livejournal.com]

Nikon D40x, да, очень доволен.

Re: офф-топ

[sciuro.livejournal.com]

Спасибо!

[faceted-jacinth.livejournal.com]

Чего-то тут не договорено, из-за чего у меня возникают странные сомнения.

А если в какой-то момент числа S заканчиваются? То есть Алиса выбирает очередное так, что все остальные (кроме уже выбранных Бобом) меньше? Видимо, надо дополнительно требовать всюду-плотности множества S. Что уже не так очевидно само по себе.

[avva.livejournal.com]

зачем, тогда боб просто выбирает наугад, его условие уже выполнено.

[faceted-jacinth.livejournal.com]

Он не может выбрать число вне отрезка. Под "выбирает наугад" подразумевается, что если s_n вне отрезка, то он выбирает какое-нибудь ещё не выбранное s_(n + m) из отрезка. Он может это сделать только если такие числа остались. Чтобы они остались, множество S должно быть всюду плотным (между любыми двумя элементами есть третий).

Иначе если рассмотреть множество всех рациональных чисел от 0 до 1/2 плюс ещё 3/4, плюс 1, то Алиса первым ходом выбирает 3/4 и выигрывает.

[faceted-jacinth.livejournal.com]

А, нет, извините, я туплю. Они числа из всего отрезка выбирают.

[shmel39.livejournal.com]

Интересно. Но по очевидности это доказательство не лучше и не хуже канонического, ИМХО.

[akater.livejournal.com]

Интересно, Вы с работами А. А. Зенкина, посвящёнными идеям Кантора, знакомы? И если да, то какое имеете мнение?

[avva.livejournal.com]

Знаком, это полная чепуха, не заслуживающая внимания.

[avva.livejournal.com]

Вот зато небезлюбопытная статья:

http://www.math.ucla.edu/~asl/bsl/0401/0401-001.ps