Проблемы Гильберта (100 лет спустя)

Мы пришли к удивительному выводу: если к множеству, которое эквивалентно N, добавить ещё один элемент, получится множество, которое снова эквивалентно N. Но ведь совершенно ясно, что делегаты-космозоологи представляют собой часть того множества людей, которые разместились в гостинице после приезда нового гостя. Значит, в этом случае часть не «меньше» целого, а «равна» целому!

Итак, из определения эквивалентности (которое не приводит ни к каким «странностям» в случае конечных множеств) следует, что часть бесконечного множества может быть эквивалентна всему множеству.

Возможно, что известный математик Больцано**, который пытался в своих рассуждениях применять принцип взаимно однозначного соответствия, испугался таких непривычных эффектов и поэтому не стал дальше развивать эту теорию. Она показалась ему совершенно абсурдной. Но Георг Кантор*** во второй половине XIX века вновь заинтересовался этим вопросом, стал исследовать его и создал теорию множеств, важный раздел оснований математики.

Продолжим наш рассказ про бесконечную гостиницу.

--------------------

* No (читается: «алеф-нуль») — стандартное обозначение для мощности (числа элементов) множества N.

** Бернард Больцано A781-1848) — чешский математик.

*** Георг Кантор A845-1918) — немецкий математик.

- 8 -

Новый постоялец «не удивился, когда на другое утро ему предложили переселиться в №1000 000. Просто в гостиницу прибыли запоздавшие космозоологи из галактики ВСК-3472, и надо было разместить ещё 999999 жильцов».

Но потом произошла какая-то накладка, и в эту же самую гостиницу приехали на съезд филателисты*. Их тоже было бесконечное множество — по одному представителю от каждой галактики. Как же их всех разместить?

Эта задача оказалась весьма сложной. Но и в этом случае нашёлся выход.

«В первую очередь администратор приказал переселить жильца из №1 в №2.

— А жильца из №2 переселите в №4, из №3 — в №6, вообще, из номера n — в номер 2n.

Теперь стал ясен его план: таким путём он освободил бесконечное множество нечётных номеров и мог расселять в них филателистов. В результате чётные номера оказались занятыми космозоологами, а нечётные — филателистами...

Филателист, стоявший в очереди n-м, занимал номер 2n — 1». И снова всех удалось разместить в гостинице.

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

Далее будем рассматривать только числовые множества — подмножества числовой прямой. Множество всех чисел на этой прямой, т. е. множество действительных чисел, обычно обозначают через R.

Счётные и несчётные множества

Рассмотрим следующую цепочку: N ⊂ Z ⊂ Q ⊂ R. (Z — это множество целых чисел, a Q — множество рациональных чисел, т. е. множество чисел вида p/q, где р и q — целые, q ≠ 0.) Все эти множества бесконечны. Рассмотрим вопрос об их эквивалентности.

-----------------------

* Коллекционеры почтовых марок.

- 9 -

Установим взаимно однозначное соответствие между Z и N: образуем пары вида (n, 2n) и (—n, 2n+1), n ∈ N, а также пару (0,1) (на первое место в каждой паре ставится число из Z, а на второе — из N).

Есть и другой способ установить это соответствие, например, выписать все целые числа в таблицу, как показано на рисунке, и, обходя её по стрелочкам, присваивать каждому целому числу некоторый номер. Таким образом, мы «пересчитаем» все целые числа: каждому z ∈ Z сопоставляется некоторое натуральное число (номер) и для каждого номера есть такое целое число, которому этот номер приписывается. При этом явную формулу выписывать не обязательно.

Таким образом, Z эквивалентно N.

Всякое множество, эквивалентное множеству натуральных чисел, называется счётным. Такое множество можно «пересчитать»: пронумеровать все его элементы натуральными числами.

На первый взгляд, рациональных чисел на прямой «намного больше» чем целых. Они расположены всюду плотно: в любом сколь угодно малом интервале их бесконечно много. Но оказывается, что множество Q также счётно. Докажем сначала счётность Q⁺ (множества всех положительных рациональных чисел).

Выпишем все элементы Q⁺ в такую таблицу: в первой строке — все числа со знаменателем 1 (т. е. целые), во второй — со знаменателем 2 и т. д. (см. рисунок на с. 11). Каждое положительное рациональное число обязательно встретится в этой таблице, и не однажды (например, число 1 = 1/1 = 2/2 = 3/3 = … встречается в каждой строке этой таблицы ).

- 10 -

А теперь мы пересчитаем эти числа: идя по стрелочкам, присваиваем каждому числу номер (или пропускаем это число, если оно уже встречалось нам раньше в другой записи).

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

Итак, мы указали способ пронумеровать все числа из Q⁺, т. е. доказали, что Q⁺ счётно.

Заметим, что этот способ нумерации не сохраняет порядка: из двух рациональных чисел большее может встретиться раньше, а может — и позже.