Вы всё ещё верите в аксиому выбора?

[57ded]

Вам сюда.

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

Утверждение Рассмотрим следующую задачу. Счётное множество мудрецов выстроены в натуральный ряд (лицом в сторону возрастания ряда, так что каждый видит перед собой бесконечное число мудрецов). Каждый из

Comments

Кровожадно

[m_ustinov]

Ну это не фокус. Вот если бы выжило только конечное число мудрецов...

Re: Кровожадно

[57ded]

Интересно. Но не знаю, как решать (и возможно ли).
Также пока не придумал, как быть с теми задачами, что я сформулировал в конце поста. Может придумаем или
a_shen прочтёт и что-то вумное скажет.
Главное, удалось продемонстрировать несостоятельность аксиомы выбора :)

А давайте их всех казним

[yurymakarychev]

Пусть A_n множество таких раскрасок шляп ( = последовательностей 0 и 1), что палач казнит первых n мудрецов. Понятно, что

a) A_n - замкнуто. Действительно, проверим, что дополнение к A_n открыто. Рассмотрим раскраску x, при которой один из первых n мудрецов остаётся цел и невредим. Предположим, машина Тьюринга этого мудреца смотрит на шляпы только первых N мудрецов ("на входе" x). Тогда, как бы мы не поменяли цвета шляп у мудрецов N+1, N+2, ..., наш мудрец всё равно останется жив. Таким образом, некоторая окрестность x тоже лежит в дополнении к A_n.

б) A_n - не пустое множество. Оденем на всех мудрецов N+1, N+2, ... белые шляпы. Посмотрим, на предсказание МТ N-ого мудреца, и покрасим его шляпу в противоположенный цвет. Повторим эту процедуру для N-1, N-2, ..., 1-ого мудреца. Все они будут казнены :-(

Теперь рассмотрим пересечение всех A_n. В живых никто не останется...

Re: А давайте их всех казним

[57ded]

Хорошо.
Только вычислимо всех казнить не получится :)
Потому что эти гады могут сломать любую вычислимую стратегию. Причём сломать в бесконечном числе мест. Так что задача от Миши полностью решена.