19 июля 2011 г.

Аксиома выбора и вредный Дед Мороз

На рубеже XIX и XX веков в математике случился кризис, связанный с накоплением сверх критической массы интуитивных понятий и необоснованных аналогий. Преодоление этого кризиса связывали с аксиоматизацией науки, начиная с самых низов. А в сáмом низу находилась как раз построенная к тому моменту канторовская теория множеств. Правда, очень быстро выяснилось, что и тут не обходится без двусмысленностей, и одним из главнейших камней преткновения стала так называемая аксиома выбора.

Это очень интересная проблема. Понять её способен даже школьник средних классов, а вынести мозги она способна кому угодно.

Если излагать немного упрощённо, то аксиома выбора утверждает, что —

Сколько бы непустых множеств нам не предлагали, мы всегда можем выбрать по элементу из каждого.

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

Проиллюстрировать их можно на примере парадокса с вредным Дедом Морозом. Этот конкретный Дед Мороз честно исполняет свои обязанности, однако в силу вредности характера не хочет, чтобы дети в Новый год радовались слишком уж сильно. Своей цели он достигает довольно оригинальным образом: каждый раз, когда нужно дать ребёнку несколько конфет, он даёт их больше положенного, но избыток тут же демонстративно отбирает. Например, если нужно дать две конфеты, он выдаёт три и отбирает одну.

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

Возьмём конкретного ребёнка. За час до наступления Нового года (т.е. до полуночи с 31 декабря на 1 января) Дед Мороз даёт ему три конфеты и отбирает одну. За 1/2 часа (т.е., за 30 минут) до полуночи Дед Мороз даёт ему ещё три конфеты и отбирает одну. Это же действие он выполняет за 1/3 часа (20 минут), за 1/4 часа (15 минут), за 1/5 часа (12 минут) до полуночи, и т.д. В общем, каждый раз за 1/n (при всех натуральных n) часа до полуночи ребёнок получает от Деда Мороза три конфеты и тут же лишается одной. Спрашивается, сколько конфет будет у ребёнка в полночь?

Здравый смысл немедленно подсказывает: в каждый такой момент ребёнок получает две конфеты “чистой прибыли”. А поскольку моментов таких столько же, сколько натуральных чисел, т.е. бесконечно много, то и конфет у ребёнка должно стать немеряно.

Обратим внимание на связь с аксиомой выбора. Во все эти моменты, когда Дед Мороз должен отобрать конфету, множество конфет у ребёнка заведомо не пусто. Как минимум, оно содержит те три конфеты, которые только что были вручены. Есть из чего выбирать, и чего отбирать. А вот как Дед Мороз будет выбирать отбираемую конфету?!

Предположим, что ребёнок, предупреждённый кем-то о вредности дедушки, задумал строго пересчитывать свои конфеты. Каждый раз, получая очередную конфету, он пишет на её фантике номер: 1,2,3,4,5,… Мы полагаем ребёнка достаточно шустрым, чтобы он успевал делать это до следующего поступка дедушки.

Допустим, что Дед Мороз отбирает у ребёнка ту конфету, которая была вручена сáмой последней. Что происходит в этом случае? За час до полуночи ребёнок получил конфеты, которые пометил номерами 1,2,3 — и тут же лишился конфеты № 3. За полчаса до полуночи он получил конфеты с номерами 4,5,6 — и тут же лишился конфеты № 6. За 20 минут до полуночи были получены конфеты 7,8,9 — и тут же утрачена конфета № 9. Продолжая в том же духе, мы получаем, что в полночь у ребёнка останутся конфеты со всеми натуральными номерами, за исключением кратных трём. Таковых действительно бесконечно много, и вроде бы это согласуется со здравым смыслом.

Но не будем торопиться. Пусть теперь Дед Мороз отбирает у ребёнка ту конфету, которая находится у него дольше всего. Что теперь? За час до полуночи приходят конфеты 1,2,3 — уходит № 1, остаются № 2 и № 3 (две штуки). За полчаса до полуночи приходят конфеты 4,5,6 — уходит ранее вручённая № 2, остаются номера с 3 по 6 (четыре штуки). За 20 минут до полуночи приходят конфеты 7,8,9 — уходит ранее вручённая № 3, остаются номера с 4 по 9 (шесть штук). И так далее. Вроде бы количество конфет и растёт, но в полночь внезапно оказывается, что ни одной конфеты у ребёнка нет! Действительно, какой натуральный номер n не возьми — конфета с этим номером была отобрана за 1/n часа до полуночи!

Итак, два разных способа выбора приводят к двум совершенно разным результатам, хотя, казалось бы, арифметически ничего не меняется. А ведь у вредного дедушки есть ещё как минимум две стратегии. Он может забирать конфету с наименьшим номером, превосходящим единицу — и тогда в полночь ребёнок будет владельцем одной-единственной конфеты № 1. Он может забирать конфету с наименьшим номером, превосходящим двойку — и в полночь у ребёнка будут две конфеты, № 1 и № 2.

Недаром Бертран Рассел сказал про аксиому выбора, что сначала она кажется совершенно очевидной, затем становятся видны вытекающие из неё странные выводы, а под конец вообще непонятно, что с ней делать и к чему она может привести.

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

Комментариев нет:

Отправить комментарий