Математический парадокс, аксиома выбора

natunchik

http://cornellmath.wordpress.com/2007/09/13/the-axiom-of-cho...
Вкраце: царь собрал счётное количество мудрецов, выстроил в колонну лицом в бесконечность, надел на каждого красный или синий колпак (так что мудрец не видит цвет своего колпака и тех, кто за ним, но видит колпаки всех кто перед ним (и да, они умеют видеть счётное количество колпаков и объявил, что выдаст призы тем, кто сможет угадать цвет своего колпака. Перед этим те могли посовещаться. А ещё у них помимо способности видеть счётные множества есть аксима выбора и дофига памяти.
Предлагается решение: мудрецы бьют все счётные последовательности цветов колпаков на классы эквивалентности так: две последовательности эквивалентны, если отличаются в конечном количестве позиций. При помощи аксимы выбора они из каждого класса выбрали и запомнили Представителя — всё заранее.
Далее, каждый мудрец смотрит перед собой, определяет класс последовательности, которую видит (естественно учитывая своё положение и называет тот цвет, который в ней на его месте. Получается чёрная магея: во-первых, все мудрецы определяют класс одинаково (потому что каждый не видит конечный начальный отрезок во-вторых, Представитель отличается от реально предложенной им последовательности не более чем в конечном количестве позиций, так что все, кроме конечного количества мудрецов, угадают свой цвет правильно.
Ещё более стрёмная фишка: царь может использовать не два цвета колпаков, а счётное или континуум цветов, на решение это не влияет.
Вот тут меня начинают грызть дикие сомнения. В изменение вероятности с ненулевой до почти единицы я могу поверить, ну, это чем-то напоминает удвоение сферы Банахом-Тарским, оно даже понятно в общем-то, магия и магия, ничего особенного. Но вот в "умножение на чётную бесконечность" поверить намного тяжелее, а тем более в "умножение на континуум" (с учётом того, что самих мудрецов всего лишь чётное количество). Это подозрительно!
Я пока нашёл одно подозрительное место в рассуждениях (на него же, но другими словами указывает некий Барак там в комментах, но зачем-то начинает говорить о левых вероятностях, на что Теренс Тао выражает довольно обоснованное сомнение, что эти рассуждения можно довести до формальной строгости).
Ни один мудрец не может наверняка (или просто, если цветов бесконечность) угадать цвет своей шапки. Ну, в смысле, если царь знает их стратегию (можно считать, что знает, так как "гарантированное освобождение" подразумевает, что у него не должно быть даже шанса угадать) - способ разбиения и всё остальное, то он может обломать любого заданного наперёд мудреца (и всех до него).
Если мы говорим о натуральных числах as defined в арифметике, то если некоторое утверждение верно для каждого числа, то оно обычно верно и для всех чисел. Не всегда, Гёдель нашёл такое утверждение, которое было недоказуемо для всех чисел (но считал, что оно тем не менее истинно, кстати). Не знаю, насколько натянута аналогия, но всё же.
Однако мудрецы, насколько я понимаю, настойчиво предлагают смотреть на натуральные числа как на множество, в рамках теории множеств. А там можно делать (насколько я понимаю) всякие интересные вещи, например, переставить мудрецов так: вначале поставить всех с нечётными номерами, затем всех с чётными. Это ж ведь останется почти тот же самый натуральный ряд, с отношением порядка, определённым для всех элементов кроме первого оператором "предыдущий" (который нужен для индукции) етс.
Но теперь мы можем ткнуть пальцами в мудреца, у которого раньше был номер два, и воскликнуть: "вот, он один из тех, про которого нам хотят сказать, что он всегда угадывает" (раз не попадает в конечный начальный отрезок тех, которые могут ошибиться). Except we can't, потому что внезапно обнаруживается, что привычная индукция (которой мы как бы пользовались в наших начальных рассуждениях) превращается в трансфинитную, и у неё, сюрприз-сюрприз, перестаёт выполняться инвариант: этот тыкнутый мудрец _не может_ выбрать тот же класс эквивалентности, что и мудрец, стоящий первым, потому что перед ним уже не конечное количество мудрецов стоит. На самом деле даже как-то довольно стройно получается: пока мудрецы могут выбрать класс эквивалентности, они могут ошибиться, а те, кто не может ошибиться (по предположению) - не могут и выбрать; это внушает надежду в победу здравого смысла.
Или можно так сказать: пусть царь наденет красные колпаки на чётных мудрецов, синие на нечётных, а потом поставит красных вперёд. Это допустимая раскраска множества натуральных чисел? По-моему, да. Я не очень понимаю, как можно её и подобные ей запретить, но чтобы при этом мощность множества получающихся раскрасок осталась континуумом (как должно быть, ведь каждая раскраска это двоичное представление какого-то вещественного числа).
Вот как-то так. Но это всё как-то неубедительно, я даже сам себя ещё не убедил.
Кто что думает?

lilya-sati

Однако мудрецы, насколько я понимаю, настойчиво предлагают смотреть на натуральные числа как на множество, в рамках теории множеств. А там можно делать (насколько я понимаю) всякие интересные вещи, например, переставить мудрецов так: вначале поставить всех с нечётными номерами, затем всех с чётными. Это ж ведь останется почти тот же самый натуральный ряд, с отношением порядка, определённым для всех элементов кроме первого оператором "предыдущий" (который нужен для индукции) етс.
Но теперь мы можем ткнуть пальцами в мудреца, у которого раньше был номер два, и воскликнуть: "вот, он один из тех, про которого нам хотят сказать, что он всегда угадывает" (раз не попадает в конечный начальный отрезок тех, которые могут ошибиться).
Взяли новый порядок - и понятие начального отрезка изменится (в частности, он не всегда будет конечным так что всё будет как раньше (ни про кого нельзя с гарантии сказать, что он угадает). Начальный отрезок - это {x: x<y}.
В чём парадокс, не осилил. И вообще, почему как парадокс, так сразу аксиому выбора упоминают как корень всех зол?

natunchik

В чём парадокс, не осилил. И вообще, почему как парадокс, так сразу аксиому выбора упоминают как корень всех зол?
Так осиль же, прежде чем писать! Авторы парадокса утверждают, что все мудрецы (за исключением конечного числа) обязательно угадают, какую бы сложную задачу перед ними ни ставили. В этом парадокс.
Я же пытаюсь убедить себя, что в их рассуждениях ошибка, что авторы хотели как обычно показать, что "ах, аксиома выбора такая взбалмошная, к таким результатам приводит", но ошиблись, причём этого почти никто не заметил, поскольку все верят в глючность аксиомы выбора. Но убедить себя до конца у меня не получается, поэтому интересно мнение окружающих, как они думают, есть ли ошибка, если нет, то почему, если да, то как доказать так, чтобы не было сомнений ваще.

Nefertyty

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

Suveren

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

Nefertyty

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

katrinmania

Brodnik

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

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

blackout

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

blackout

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

toxin

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

lilya-sati

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

lilya-sati

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

iri3955

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

Vlad128

Этот "парадокс" с первых же строк напоминает аксиому детерминированности, так что ничего удивительного.

svetik5623190

Математический парадокс, аксиома выбора.
И ты, Брут...

svetik5623190

царь собрал счётное количество мудрецов, выстроил в колонну лицом в бесконечность
это условие предполагает, что бесконечность - одна. Выстроить в колонну лицом в бесконечность - значит здесь имхо упорядочить по порядковому типу [math]$\omega_0$[/math], то есть естественным порядком натуральных чисел.
Если же делать так:
переставить мудрецов так: вначале поставить всех с нечётными номерами, затем всех с чётными.

то получится другой трансфинит, [math]$2\omega_0$[/math], в нём "две бесконечности", причём у нечётных обе спереди, а у чётных одна - спереди, а вторая - сзади, так к какой же из них стоят лицом чётные?
Я уж не говорю про то, что вот это:
Это ж ведь останется почти тот же самый натуральный ряд, с отношением порядка, определённым для всех элементов кроме первого оператором "предыдущий" (который нужен для индукции) етс.
вообще не верно, потому что предыдущего в таком упорядочении нет не только у числа (муднеца) 1, но и у 2. Да и для индукции нужен вообще не предыдущий, а последующий - с этим здесь всё в порядке.
Короче, моё мнение: хуйня. Подмена понятий - раз, фактическая ошибка - два. Никакого парадокса не вижу.
Моя замута на тему аксиомы выбора была имхо прикольнее (но тоже оказалась хуйнёй а тут чуваки просто так фигню какую-то сморозили, аксиома выбора как будто вообще не по существу. Ну или я что-то может просто не понял в написанном.

svetik5623190

Я не верю в глючность аксиомы выбора. По-моему, её глючность в массовом сознании - это результат работы говнопопуляризаторов теории множеств.
Это ты лично мне льстишь или так, вообще? ;)
Кстати, а что понимаешь под глючностью?

svetik5623190

царь собрал счётное количество мудрецов, ..... и объявил, что выдаст призы тем, кто сможет угадать цвет своего колпака.
А вообще, чтобы гарантированно разорить царя, мудрецам следует делать так. Зовёт мудрец царя и говорит: я знаю, какой у меня колпак. Царь спрашивает - ну, и какой же? Тогда мудрец подбрасывает в кармане монетку и отвечает наобум с вероятностью одна вторая.
Поскольку цветов только два, то шапок хотя бы одного из цветов окажется бесконечное число. По закону больших чисел половина из мудрецов в шапках этого цвета получат приз, все остальные уж по крайней мере ничего не потеряют (ведь нет же наказания за неверный ответ).
Итого получается, что вероятность того, что царь выдаст только конечное число призов, равна нулю.

vitamin8808

 
напомнило...

lilya-sati


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

Это я вообще. Ваша популяризаторская работа ещё не имела большого воздействия на массы, поэтому трудно говорить о её влиянии на массовое сознание :)
Из настоящих говнопопуляризаторов пока только Непейвода вспоминается. Хотя есть и другие (с менее заметными глюками, поэтому ещё более опасные). Например в книге Ященко "Парадоксы теории множеств" автор иногда чрезмерные вольности себе позволяет (хотя я не знаю, относить его к говнопопуляризаторам или нет).
Кстати, а что понимаешь под глючностью?
Глючность (в самом общем виде) - не соответствие реальности.

lilya-sati

Ваша популяризаторская работа ещё не имела большого воздействия на массы, поэтому трудно говорить о её влиянии на массовое сознание
как и о говнистости/неговнистости

svetik5623190

Глючность (в самом общем виде) - не соответствие реальности.
Не надо путать реальность в материальном и интеллектуальном мире, вот и всё. Аксиома выбора - очевидно лишь математическое знание, то есть высказывание о предметах интеллектуального мира.
Вопрос о том, как использовать знания об интеллектуальном мире для работы в физическом мире - то есть вопрос о выборе способа моделирования - совершенно отдельный вопрос, к аксиоме выбора не относящийся.
Имхо.
Оставить комментарий
Имя или ник:
Комментарий: