Войти в систему

Home
    - Создать дневник
    - Написать в дневник
       - Подробный режим

LJ.Rossia.org
    - Новости сайта
    - Общие настройки
    - Sitemap
    - Оплата
    - ljr-fif

Редактировать...
    - Настройки
    - Список друзей
    - Дневник
    - Картинки
    - Пароль
    - Вид дневника

Сообщества

Настроить S2

Помощь
    - Забыли пароль?
    - FAQ
    - Тех. поддержка



Пишет muda ([info]muda)
@ 2011-08-06 01:19:00


Previous Entry  Add to memories!  Tell a Friend!  Next Entry
Аксиома выбора неверна
(from cornellmath, посредством комментов Хеллера, вольный перевод мой)

При обсуждении корректности Аксиомы Выбора, самый распространенный аргумент, почему ей не следует доверять без оглядки - парадокс Банаха-Тарского. Все же, меня он никогда особенно не тревожил. Аргумент против Аксиомы выбора, который действительно взволновал меня, я впервые услышал в Olivetti Club, нашем научном коллоквиуме. Это расширенная версия одной элементарной логической задачи, так что давайте сначала взглянем на нее.

"100 узников выстроены в ряд так, что каждый может видеть всех, кто находится перед ним. Вертухай надевает либо белую, либо черную шляпу на голову каждого из узников, а затем, начиная с конца линии, спрашивает каждого узника, какого цвета его шляпа (т.е., сначала он спрашивает узника, который видит всех остальных). Каждый узник слышит ответы других и узнает, когда они ошибаются или отвечают правильно. Если все узники могут договориться об одной стратегии заранее, какой будет наилучшая стратегия?"

Ответ к этой задаче вскоре будет дан, но прежде - условие упомянутого обобщения:

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

Интуитивно кажется, что никакой стратегии здесь быть не может, так как никто, кто знает цвет вашей шляпы, не может передать вам информацию, так что, судя по всему, все угадывают вслепую. И всё же, несмотря на это, все, кроме конечного числа узников, могут освободиться.

Мне хотелось бы воздать должное некоторым людям. Я узнал обе эти задачи на одном из докладов Майка О'Коннора, и я так думаю, это он придумал решение для второй задачи, вызывающей столько затруднений. Кроме того, я не могу ее найти, но я слышал, что Крис Хардин написал статью, посвященную подобным задачам.

Прежде всего, давайте разберем решение элементарной задачи. Первому узнику, который угадывает цвет своей шляпы, не повезло; он никак не может знать что-либо о своей шляпе, таким образом у него есть возможность угадать с вероятностью 50%, несмотря ни на что. Тем ни менее, это значит, что он может использовать свою попытку для того, чтобы передать информацию остальным узникам.

Хмм, он мог бы сказать цвет шляпы на узнике, который стоит перед ним. Этот парень мог бы потом ответить верно, но после этого следующий узник окажется в той же самой ситуации, что и первый. Повторение этого процесса дальше гарантировано освободит только 50 узников, освобождая в среднем 75.

Мы можем достичь большего. Вместо того, чтобы просто говорить цвет шляпы на стоящем перед ним, первый узник считает суммарное количество белых шляп на всех узниках. Если оно четное, он говорит "белая", а если оно нечетное, он говорит "черная". Затем следующий узник может посчитать количество белых шляп, которые видит он, и если есть отличия в четности от того, что вычислил первый узник, он узнает, что его шляпа белая. Но теперь следующий узник знает четность количества белых шляп, которые видит первый узник, и цвет шляпы второго узника, так что он может сопоставить эти данные с количеством белых шляп, которые видит он сам, и понять, является ли его шляпа белой. Последнее утверждение повторяется дальше, так что что все, кроме первого узника, угадывают верно.

Интересно, что увеличение количества цветов шляпы здесь не усложнит задачу. Для любого множества цветов шляпы H, узники могут задать Абелеву группу на H. Затем первый узник называет "сумму" всех цветов для шляп, которые он видит. Следующий узник теперь может отнять сумму всех цветов для шляп, которые видит он, от цвета, который назвал первый узник, и узнать тем самым цвет своей собственной шляпы. Опять же, это утверждение повторяется, и таким образом все, кроме первого узника, освобождаются. Для чернобелого случая предыдущее утверждение использовало черный = 0 (mod 2) и белый = 1 (mod 2).

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

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

Затем узники вызывают Аксиому Выбора, чтобы выбрать из каждого класса эквивалентности по одному элементу, насчет которого они договариваются и который запоминают. Теперь, когда они построятся в ряд и получат шляпы, они смогут видеть всю последовательность без конечной её части, и значит, они могут узнать, в каком они классе эквивалентности. Их стратегия, таким образом, отвечать так, как будто они находятся в заранее выбранном элементе из этого класса эквивалентности.

Как это работает? Что ж, последовательность, в которой они находятся, и представительный элемент, который они выбрали, используя Аксиому Выбора, должны быть эквивалентны, так что они одинаковы после правки конечного числа элементов. Следовательно, после конечного числа некорректных ответов, каждый узник чудесным образом угадает цвет своей шляпы.

Это решение также очень устойчиво в том смысле, что большинство попыток усложнить условие не сломают его. Вертухай может знать их план и даже точно знать представительные последовательности, которые они выбрали. В таком случае он может заставить сколь угодно большое конечное число узников ошибиться, но он не сможет достать бесконечного их числа. Кроме того, число цветов шляпы может быть произвольно большим; такое же решение работает совершенно так же.

Последний момент весьма психоделичен. В случае двух цветов вполне логично, что любой узник может угадать цвет своей шляпы и, кроме того, что произвольно большое число узников могут угадать подряд. Фактически, ни в какой конечной точке в процессе оглашения цветов результаты оптимальной стратегии не отличаются от простого угадывания. И все же, если количество цветов несчетно, вероятность, что какой-либо узник случайно угадает цвет своей шляпы, равна нулю. Кто-нибудь может справедливо ожидать, что ни одному узнику не повезёт в процессе случайного угадывания, так что когда в конечном итоге первый такой узник отвечает верно, вертухай должен быть естественно шокирован (хотя шокирован не настолько сильно, насколько он будет шокирован, когда все, кроме конечного числа узников, ответят верно).

По моим ощущениям, это решение сильно тревожит интуитивную верность аксиомы выбора. Конечно, это все в основном является следствием моей интуиции относительно конечных вещей и наивной надежды, что они должны продлеваться до бесконечных. Я думаю, наиболее тревожным является случай несчетного количества цветов, где у любого данного узника нет ни одного шанса назвать цвет своей шляпы, и все же почти все узники отвечают верно.