В предыдущей статье мы рассуждали на тему бесконечности, пытаясь понять, что это такое и какие её виды бывают. Там же мы ввели понятие счётного множества и множества мощности континуум. В двух словах: счётное множество — это множество, элементы которого можно пересчитать, используя натуральные числа (если говорить по-умному, то построить изоморфизм во множество натуральных чисел). Множество мощности континуум — это множество, которое равномощно множеству всех подмножеств натуральных чисел. Чуть больше двух слов, однако сути это не меняет. На самом деле, почти весь математический анализ и многие другие разделы математики никогда не заглядывают в глубину кардинальной шкалы дальше этих двух мощностей. Но даже здесь есть множество интересных нюансов, о которых мы сегодня поразмышляем.
В этот раз помимо Георга Кантора мы вспомним ещё одного гения математической мысли, одного из последних математиков-универсалов Давида Гильберта.
Чтобы перечислить все заслуги этого человека в математике, не хватит и ста статей. Здесь же мы лишь вспомним придуманный им парадокс "Гранд-отель". Строго говоря, это не один парадокс, а целый набор парадоксов. А если говорить ещё более строго, то это и не парадокс вовсе, а иллюстрация свойств счётных множеств. Уже интересно, не правда ли? Итак, в чём заключается этот "парадокс"?
Давайте представим себе отель со счётным числом номеров. Не будем думать о том, где такой отель может поместиться, или о том, что сила гравитации, создаваемая шкафчиком с ключами от всех номеров, может разорвать вклочья Солнечную систему. Иными словами, физическая сторона вопроса нас не интересует. Предположим, что в сезон отпусков этот "Гранд-отель" забит полностью так, что все номера заняты. Заметьте, что я намеренно не пишу, что нет свободных мест: как оказывается, в случае бесконечного количества номеров это разные вещи.
Итак, все номера заняты, администратор подсчитывает свою бесконечную прибыль, и тут приезжает ещё один посетитель, которому нужен номер. Отказать ему нельзя, ведь это известный критик и вообще большая шишка. Что же делать бедному администратору? Слегка поразмыслив, он решает проделать следующую процедуру: он просит постояльца из номера 1 переселиться в номер 2, постояльца из второго номера любезный администратор переселяет в номер 3, постояльца в третьем номере просят переселиться в номер 4 и так далее. В итоге, каждый постоялец переселяется в комнату с порядковым номером на единицу больше. Такая операция возможна, поскольку, как мы помним, для любого натурального числа N существует натуральное число N + 1, а значит, необходимая комната всегда найдётся. После проведение сего действия комната с номером 1 освобождается, и туда спокойно заселяется наш новый постоялец. И вновь все номера заняты. Но существуют ли ещё свободные места?
Ситуация усугубляется: критику настолько понравилось обслуживание в "Гранд-отеле", что он позвонил своим друзьям и порекомендовал им приехать к нему, чтобы тоже поселиться здесь и провести выходные. Спустя некоторое время на пороге заведения появляются одиннадцать друзей (Оушена) критика и просят выделить им номера. Но администратор не из робкого десятка, более того, он бывший математик, поэтому он понимает, что может проделать предыдущую процедуру 11 раз, освободив тем самым ровно 11 номеров. Однако он также понимает, что может немного оптимизировать процесс и просто разместить каждого посетителя из номера n в номер n + 11, переселив каждого посетителя лишь единожды. Понятно, что это также возможно, поскольку, обобщив упомянутое выше правило, можно утверждать, что для любого натурального числа N и для любого другого натурального числа M найдётся натуральное число N + M. Как бы то ни было, ещё 11 свободных номеров находятся, постояльцы заселены, администратор счастлив, а в отеле вновь все номера заняты. Но найдутся ли опять свободные места?
Дальше больше. Отзыв критика в социальных сетях вызвал бурю интереса к отелю. Толпы людей со всей страны ринулись к нему. В итоге, счётное число постояльцев требуют номера. Администратор не хочет терять бесконечное количество прибыли, однако, как мы помним, все номера заняты. Но даже эта ситуация не сломила нашего метродотеля, он придумывает гениальный план. Теперь он просит постояльца из первого номера переселиться в номер 2, постояльца из номера 2 переселяют в номер 4, клиенту, живущему в номере 3, предоставляют шестой номер, человека из четвёртого номера переселяют в номер 8, и вообще, каждого посетителя из номера n переселяют в номер 2n. И вновь бесконечность количества комнат данного отеля позволяет это сделать (для любого натурального числа N существует натуральное число 2N). По окончанию данной процедуры в каждом чётном номере будет жить постоялец в то время, как все нечётные номера будут пустовать. Очевидно, что нечётные номера образуют счётное множество, туда-то администратор и заселяет новых жильцов. К концу дня все новые клиенты расселены, прибыль получена, а в отеле уже в который раз все номера заняты. И я снова спрашиваю Вас: найдутся ли свободные места?
Ничто не предвещало беды, однако бедный администратор с самого утра что-то предчувствовал. И не зря. В этот день, когда его отель всё ещё был битком набит постояльцами, во всём мире был упразднён визовый режим, и люди, узнав о замечательном "Гранд-отеле", решили провести свой отпуск именно там. Даже наш кремень-администратор слегка забеспокоился, когда во двор отеля въехало счётное число автобусов, в каждом из которых сидело счётное число человек, жаждущих свой номер в этом чудесном заведении. Приняв две таблетки валидола, глава отеля пораскинул мозгами и нашёл решение проблемы. Для начала он снова переселил всех постояльцев отеля. Теперь каждый постоялец, живущий в номере n, переехал в номер 2^n (как бы это ни было невероятным, но для любого натурального числа N существует натуральное число 2^N). После этого в отеле остались заняты лишь комнаты с номерами, равными степеням двойки (2, 4, 8, 16, 32,...). После этого наш гений-администратор вспоминает основную теорему арифметики, которая гласит, что любое натуральное число может быть однозначно представлено в виде произведения степеней простых чисел (с точностью до перестановки сомножителей). Например, 80 = 2^4 * 5^1, а 450 = 2^1 * 3^2 * 5^2. Очевидно, что занятые номера имеют представление в виде 2^n, поэтому можно селить новых гостей в комнаты с теми номерами, которые в таком виде не представимы. Например, свободны все комнаты, номера которых являются степенями других простых чисел (3^n, 5^n, 7^n,...). Метродотель прекрасно это понимает и для начала присваивает каждому автобусу уникальное простое число. Как мы помним, простых чисел бесконечно много (а именно, счётно), поэтому данная операция вполне возможна. После этого он независимо нумерует всех пассажиров в каждом автобусе и заселяет постояльца с номером n из автобуса с номером p в комнату p^n. Так, он заселяет в отель всех новых гостей, и автобусы покидают двор "Гранд-отеля", оставляя после себя бесконечное количество выхлопных газов. И вот уже в который раз все новые клиенты получили свои комнаты, администратор купается в деньгах, а в отеле опять нет... Постойте-ка! В этот раз в отеле ЕСТЬ свободные места! Действительно, до сих пор пустуют комнаты с номерами 6, 10, 21, да и вообще все комнаты, номера которых не являются степенями простых чисел. А знаете, сколько таких комнат? Правильно, их бесконечно много. Таким образом, наш администратор не только поселил счётное множество счётных множеств посетителей в заполненный полностью "Гранд-отель", а ещё и освободил счётное число мест. Браво, маэстро!
Данная абстракция с посетителями и отелем может быть формально описана следующим образом:
1) объединение счётного множества с любым конечным множеством оставляет его счётным
2) объединение двух счётных множеств счётно
3) объединение счётного числа счётных множеств счётно
Используя эти четыре утверждения, легко понять, что может быть счётным. Мы уже знаем, что множество целых чисел счётно, однако теперь это можно доказать, используя утверждения 2) (приписываем к натуральным числам натуральные числа со знаком минус) и 1) (добавляем ноль). Кроме того, теперь становится ясно, что и множество рациональных чисел счётно. Напомню, что рациональные числа, это все дроби вида m / n, где m — целое число, а n — натуральное (например, 3/5, 10, -2, 0.5 = 1/2). Из определения видно, что всех рациональных чисел уж явно не больше, чем всевозможных пар вида (m, n). Для каждого фиксированного натурального n таких пар не более, чем счётно, значит, множество этих пар является счётным набором счётных множеств, то есть по утверждению 3) оно является счётным. Из этого следует, что рациональных чисел не более, чем счётно. Но их и не менее, чем счётно, так как они в себя включают натуральные. Значит, их ровно счётно. Если представить себе, насколько густо рациональные числа покрывают числовую прямую (по сравнению с теми же целыми числами, между которыми существует целый пустой интервал единичной длины), этот факт становится поразительным.
Где на этом моменте у некоторых читателей может возникнуть иллюзия, что посчитать можно вообще всё. Действительно, кажется, что наш маэстро-администратор для любого бесконечного числа посетителей сможет провернуть какой-нибудь умный трюк и расселить их всех в своём бездонном отеле. Однако я уже вижу его снисходительную ухмылку. Да и Вашу тоже, ведь мы помним, что существуют множества несчётные, например, множество всех подмножеств счётного множества, то есть множество мощности континуум. Вопрос заключается лишь в том, сможем ли мы хоть одно такое множество придумать. Что ж давайте попробуем.
Давайте рассмотрим нашу любимую вещественную прямую, а точнее даже лишь её отрезок [0; 1]. Теперь мы будем учитывать все вещественные числа, а не только лишь рациональные. Напомню, что вещественным числом мы называем любую бесконечную десятичную дробь. Например, таковой дробью является число π = 3.1415926... Отмечу, что записать это число полностью невозможно также, как и любое другое иррациональное число, то есть вещественное число, которое не является рациональным. В отличие от них любое рациональное число можно записать в виде десятичной бесконечной периодической дроби. Например, 1/3 = 0.333333... = 0.(3) (читается как "ноль целых и три в периоде"). Если период имеет вид (0), то его обычно опускают. С периодом связан один забавный нюанс вещественных чисел. Дело в том, что, например, следующие два числа равны, хоть и имеют различную запись: 0.99999999... = 1.00000000..., то есть 0.(9) = 1.(0). И вообще, любой период из девяток можно заменить периодом из нулей, прибавив единицу к первому непериодическому разряду числа. В дальнейшем мы учтём этот факт. Итак, давайте докажем следующую теорему:
Теорема (Кантор): отрезок числовой вещественной прямой [0; 1] мощнее счётного множества.
Доказательство: воспользуемся доказательством от противного. Допустим, что единичный отрезок является счётным множеством. В таком случае мы можем пересчитать все его элементы, присвоив каждому из них свой порядковый номер, являющийся натуральным числом. Каждый элемент отрезка имеет вид 0.abcdef..., то есть они отличаются лишь своей дробной частью, целая часть у всех этих чисел равна нулю (1 = 0.(9)). Давайте выпишем все эти числа вместе с их порядковыми номерами в столбик. Если число имеет две различные записи, то выберем из них ту, которая имеет в периоде девятки. Получим вот такую таблицу:
Здесь каждый х обозначает цифру от 0 до 9, первый индекс обозначает номер числа, а второй — номер цифры в этом числе, начиная от точки. Если наш отрезок был счётен, то в этой таблице выписаны абсолютно все его элементы. Однако мы сейчас покажем, что найдётся по крайней мере ещё одно число из отрезка [0; 1], которого в этой таблице нет. Строить мы его будем цифра за цифрой. Это число будет иметь ноль целых. Первую цифру после точки в нём мы выберем не равной цифре x_11, а также не равной нулю и не равной девяти. Нетрудно видеть, что у нас есть как минимум семь вариантов выбора. Вторую цифру мы возьмём не равной цифре х_22, а также не равной нулю и не равной девяти. И вновь у нас есть минимум семь вариантов. Третья цифра, как Вы уже догадались не равна х_33, нулю и девяти и так далее. После того, как мы выберем все цифры, у нас на руках окажется число из отрезка [0; 1], так как его целая часть равна нулю. С другой стороны, оно не равно ни одному из представленных в таблице чисел, поскольку оно отличается от каждого из них по крайней мере в одной цифре. Заметим, что проблем с неоднозначной записью у нас не может быть, так как мы из записи нашего "беглеца" исключили как девятки, так и нули.
В итоге, занумеровав "все" числа из отрезка [0; 1], мы потеряли по крайней мере ещё одно число. Из этого напрямую следует, что такая нумерация в принципе невозможна. Значит, отрезок [0; 1] не является счётным. Кроме того, он не может быть менее, чем счётен, так как в нём содержатся числа вида 1/n, где n — натуральное, то есть он содержит в себе счётное подмножество. В таком случае, он мощнее счётного множества.
Итак, наш отрезок несчётен. Оказывается, что чисел в этом небольшом отрезочке намного больше, чем "Гранд-отель" нашего выдающегося администратора может в себя вместить посетителей. В частности, чисел в нём намного больше, чем всех рациональных чисел на всей бесконечной числовой прямой. Но вот вопрос: а какова же его мощность? Имеет ли он мощность континуума или он менее мощен? А может быть, чисел в нём больше, чем всех подмножеств натуральных чисел? Чтобы это понять, нам придётся немного по-другому взглянуть на множество всех подмножеств.
Введём понятие характеристической функции. Рассмотрим любое множество А и любое его подмножество В⊂ А. Быть подмножеством, означает включать в себя некоторые элементы. Давайте мы определим на А следующую функцию, называемую характеристической функцией (или индикатором) подмножества В. Эта функция будет принимать на вход элемент множества А и возвращать одно из двух чисел 0 или 1. При этом, если элемент принадлежит подмножеству В, то функция будет иметь значение 1, а иначе — 0. Фактически эту функцию можно рассматривать как вопросно-ответную систему, которая отвечает на вопрос, является ли элемент членом подмножества В (1) или нет (0). Интересный факт: для каждого подмножества найдётся одна и только одна характеристическая функция. Ещё более интересный факт заключается в том, что имея на руках характеристическую функцию, мы однозначно можем восстановить подмножество, по которому её построили. Таким образом, существует изоморфизм между множеством всех подмножеств (булеаном) и множеством всех характеристических функций. Если хорошенько подумать, то множество всех характеристических функций — это просто множество ВСЕХ функций из множества А во множество { 0, 1 }.
Теперь давайте подумаем, как можно записать характеристическую функцию счётного множества? Допустим, мы уже занумеровали все элементы рассматриваемого множества. Затем мы выбрали какое-то его подмножество. Тогда мы можем описать характеристическую функцию в виде последовательности нулей и единиц, где на каждом месте, соответствующем номеру конкретного элемента, стоит ноль, если элемент не включён в подмножество, и один, если включён. Например, следующая последовательность является записью характеристической функции чётных натуральных чисел: 01010101010101..., а вот так примерно выглядит характеристическая функция простых чисел: 011010100010100010... Суммируя всё вышесказанное, получим, что существует изоморфизм между всеми последовательностями из нулей и единиц и булеаном счётного множества. Замечательно.
Далее. Мы знаем, что любое число в десятичной системе счисления можно также переписать в двоичной системе, то есть, используя лишь нули и единицы. Давайте перепишем все вещественные числа единичного отрезка в двоичной системе. И вновь мы можем считать, что они отличаются лишь в дробной части. И вот, что интересно: дробная часть всех таких чисел будет представлять собой последовательность из нулей и единиц. Более того, перебрав все числа отрезка, мы переберём все двоичные последовательности. Остаётся лишь сказать, что любая такая последовательность представляет собой описание подмножества счётного множества. Вот только опять у нас на пути встаёт проблема неоднозначной записи. Получается, что две различные, вообще говоря, двоичные последовательности могут быть сопоставлены одному и тому же числу. Например, 0.5 = 0.100000... = 0.011111... (можете проверить). То есть мы не можем в лоб взять и построить изоморфизм. А вот это уже проблема.
Но, отчаиваться рано. Давайте подумаем, а сколько таких "проблемных" чисел у нас существует? Все такие числа в двоичной записи имеют период либо из нулей, либо из единиц. Таким образом, в одной из своих записей они имеют вид 0.{какое-то конечное число цифр}1(0). Пусть период начинается на цифре с номером n + 1, тогда найдётся ровно 2^n вариантов такого вида дробей, потому что на месте первой цифры может стоять либо единица, либо ноль, на втором месте также может стоять либо единица, либо ноль и так далее, вплоть до цифры с номером n. Итого, их конечное число. Причём подобные рассуждения верны для любого номера n. Тогда все такие числа можно перенумеровать сквозным счётом. Как именно? Дроби 0.1(0) присваиваем номер 1. Далее на очереди дроби 0.01(0) и 0.11(0). Они получают номера 2 и 3 соответственно. Дробям 0.001(0), 0.011(0), 0.101(0) и 0.111(0) мы дадим номера 4, 5, 6 и 7. Данный процесс позволит пересчитать все "проблемные" числа, используя лишь натуральные номера, потому как для каждой следующей группы дробей нам понадобится лишь ещё 2^n натуральных чисел, очевидно, что на каждом шаге в нашей "бесконечной коробке" с номерами они найдутся.
Итак, все "двуличные" числа учтены и занумерованы. Теперь давайте построим вспомогательный изоморфизм из множества записей чисел отрезка [0; 1], во множество самих таких чисел. Здесь множество записей, вообще говоря, более обширно, так как у некоторых чисел есть две записи. Короче говоря, нам необходимо показать, что, отбросив лишние варианты записи, мы получим множество той же мощности, что и изначально. Делается это просто. В отрезке найдём любое счётное множество, например, множество чисел вида 1/n. А дальше мы делаем вот что: числу вида 1/n мы в соответствие ставим запись числа вида 1/2n с периодом из нулей, числу вида 1/(2n + 1) мы ставим в соответствие n-ую лишнюю запись, а всем оставшимся "непроблемным" числам мы просто сопоставим их собственную однозначную запись. И вот он изоморфизм. Вуаля! Выяснилось, что мощность множества ВСЕХ двоичных дробей и отрезка [0; 1], одинакова. Теперь мы можем с уверенностью сказать, что отрезок [0; 1] имеет мощность континуума.
Надеюсь, хоть кто-то дочитал эту статью до конца. Вышло длинно, в некоторых местах слишком витиевато, зато по возможности математически корректно. Спасибо за внимание!