Мощность множеств

Лекция 6: мощность множеств Дискретная математика, ВШЭ, факультет компьютерных наук (Осень 2014 – весна 2015) Мы уже говорили о том, что множества — и не только конечные, можно сравнивать по «размеру», «количеству элементов», или, как говорят, «мощности» (английский термин — cardinality), и при этом удивительным образом оказывается, что не все бесконечные множества «одинаково бесконечны», среди них тоже бывают большие и меньшие. В этой лекции мы • подробно изучим самые маленькие среди бесконечных множеств (они называются «счётными»; • убедимся, что не все множества бывают счётными, и приведём несколько примеров несчётных множеств одной мощности («мощности континуум»); • наконец, совсем кратко упомянем, что бывают и ещё бо́льшие мощности. 1 Равномощные множества 1.1 Определение равномощности Рассказывая про мощность множеств, обычно начинают с такой байки: как убедиться, кого больше в комнате: людей или стульев, не пересчитывая их? Понятно как: надо попросить всех сесть, и сразу будет видно, останутся ли свободные стулья или люди без мест (или как раз в точности всем хватит места). С математической точки зрения можно сказать: мы пытаемся установить взаимно однозначное соответствие между людьми и стульями, другими словами, объединить их в пары (человек, стул) — таким образом, чтобы каждый человек попал ровно в одну пару (никто не остался без места и не сидел на двух стульях) и чтобы каждый стул попал в одну пару (не было бы пустых и не сидели бы по двое). Если это удастся (такое соответствие существует), то мы заключаем, что людей и стульев одинаковое количество. Кстати, интересный вопрос: может ли так случиться, что сразу это не удалось (скажем, остались лишние стулья), а потом всех попросили пересесть иначе, и лишних стульев не осталось? Мы все уверены, что нет (если, конечно, кто-то не пришёл незаметно или стул не унесли тайно), но почему, и с какого возраста у людей появляется такая убеждённость? Были опыты знаменитого психолога Пиаже, которые вроде бы показывают, что она появляется скорее в некотором возрасте, чем с накоплением жизненного опыта. Так или иначе, этот трюк с людьми и стульями можно произвести и для бесконечных множеств — он становится определением. А именно, мы говорим, что множество A называется равномощным множеству B, если cуществует биекция множества A в множество B.Часто вместо «равномощным» говорят «одинаковой мощности», мы так тоже будем делать, но тут надо быть аккуратным, потому что возникает вопрос: что такое эта самая «мощность», какой природы этот объект, и не очень понятно, как на это отвечать. Мы уже обсуждали пример Галилея, который заметил, что множество натуральных чисел и множество точных квадратов равномощны, потому что есть биекция n 7→ n2 . Аналогичным образом множество натуральных чисел и множество чётных натуральных чисел равномощны, потому что существует биекция n 7→ 2n. А множество положительных действительных чисел и множество отрицательных действительных чисел равномощны, потому что существует биекция n 7→ −n. 1 1.2 Свойства равномощности Следующие свойства, которые для конечных множеств кажутся самоочевидными, в общем случае требуют доказательства. Отношение равномощности симметрично: если A равномощном B, то B равномощно A. В самом деле, как мы уже обсуждали, ко всякой биекции есть обратная функция — тоже биекция. Отношение равномощности рефлексивно: каждое множество равномощно самому себе. В самом деле, тождественная функция, которая отображает каждый элемент какого-то множества A в себя, является биекцией между A и A. Наконец, отношение равномощности транзитивно: если A равномощно B и B равномощно C, то A равномощно C. В самом деле, если у нас есть биекции f : A → B и g : BtoC, то их композиция g ◦ f : A → C тоже будет биекцией. Это можно проверить так: разные элементы A переходят в разные элементы B, потому что f инъекция, и эти разные элементы B переходят в разные элементы C, потому что g инъекция. Таким образом, при a 6= a0 получаем f (a) 6= f (a0 ) и затем g(f (a)) 6= g(f (a0 )), так что g ◦ f — инъекция. Ещё надо проверить, что g ◦ f — сюръекция, то есть что в каждый элемент c ∈ C что-то переходит. Но мы знаем, что g — сюръекция, так что c = g(b) для некоторого b ∈ B; поскольку f — сюръекция, то b = g(a) для некоторого a ∈ A, так что c = g(b) = g(f (a)) = (g ◦ f )(a). Например, мы уже видели, что натуральные числа равномощны чётным натуральным числам, а также равномощны точным квадратам: применяя симметричность и транзитивность, заключаем, что множество чётных натуральных чисел равномощно множеству точных квадратов. Задача 1. Как выглядит соответствующая биекция? (Надо описать, какой точный квадрат соответствует данному чётному натуральному числу, скажем, числу 46.) Таким образом, равномощность множеств обладает всеми свойствами отношения эквивалентности.1 Вот ещё несколько примеров равномощных множеств. Чтобы увидеть, что отрезки [0, 1] и [0, 2] равномощны, достаточно рассмотреть биективную функцию f , заданную формулой f (x) = 2x. Эта функция умножает свой аргумент на 2; обратная биекция, напротив, делит свой аргумент на 2. Чуть более сложный пример: интервал (0, 1) и полупрямая (1, ∞) равномощны. Биекцию между ними устанавливает функция x 7→ 1/x. Задача 2. Равномощны ли интервал (0, 1) и полупрямая (0, ∞)? 1.3 Примеры равномощных множеств Приведём несколько геометрических примеров. Прежде всего заметим, что равные геометрические фигуры равномощны: они совмещаются движением плоскости, которое и устанавливает между ними взаимно однозначное соответствие. Равномощны и подобные фигуры, просто надо вместо движения рассматривать преобразование подобия (с растяжением в нужное число раз). Но даже и сохранение формы для равномощности не нужно. Если взять проволочное кольцо (окружность) и согнуть его так, чтобы оно приняло форму треугольника, то тем самым мы установим биекцию между окружностью и треугольником. При этой биекции начальному положению частицы окружности соответствует положение той же самой частицы в треугольнике после изгибания. Впрочем, построить биекцию между окружностью и треугольником можно и чисто геометрически: 1 Мы из осторожности не говорим «является отношением эквивалентности» и не говорим о соответствующих классах эквивалентности, которые можно было бы назвать «мощностями», потому что не очень понятно, на каком множестве определено отношение равномощности. Хочется сказать, что на множестве всех множеств, потому что про любые два множества можно спросить, равномощны они или нет. Но это самое множество всех множеств так просто рассматривать нельзя, это быстро приведёт к противоречию, как мы скоро увидим. 2 Задача 3. Покажите, что квадрат (с внутренностью) и треугольник (с внутренностью) равномощны. Может показаться, что разрезав проволочный отрезок на две части кусачками, мы установим биекцию и докажем, что отрезок равномощен множеству, состоящему из объединения двух отрезков половинной длины. Но тут физическая интуиция нас обманывает — ну, или математическая интуиция отрывается от реальности. Если мы захотим рассмотреть соответствие, возникающее при разрезании отрезка на два, то окажется, что оно не будет взаимно однозначным. В самом деле, точке разреза соответствуют два конца двух половинок, так что сверху вниз это не функция, а снизу вверх — не инъекция. Тут сказывается разница между отрезками и интервалами (отрезками без концов) — которой в проволочной модели не видно. Эту разницу стоит обсудить подробнее. Если мы удалим из отрезка [0, 1] самую правую точку 1, то получится полуинтервал [0, 1). Какая в нём самая правая точка? Хочется сказать (и многие школьники так и говорят), что это точка 0.99999 . . .. Тем не менее с точки зрения математики дробь 0.99999 . . . — это другая запись того же числа 1. А в полуинтервале [0, 1) самой правой точки, как это ни странно с наглядной точки зрения, нет: если какое-то x меньше 1 на какое-то ε, пусть очень маленькое, то между x и 1 есть ещё другие точки. Например, можно из 1 вычесть не само ε, а ещё меньшее число ε/2, получится точка посередине между x и 1. Если мы хотим быть аккуратными, то надо сказать, что можно установить взаимно однозначное соответствие f : [0, 2] → [0, 1) ∪ [2, 3] по формуле ( f (x) = x, если 0 ≤ x < 1; x + 1, если 1 ≤ x ≤ 2. Разумеется, можно было бы считать точку разреза попавшей в первую половину: множество [0, 2] равномощно и множеству [0, 1] ∪ (2, 3]. Возникает вопрос: а равномощны ли отрезок и полуинтервал (или интервал)? Можно ли построить, скажем, биекцию f : [0, 1] → [0, 1)? Хочется сказать, что да: ясно, что в отрезке [0, 1] не меньше точек, чем в [0, 1), даже одна лишняя, и — с другой стороны — в [0, 1) не меньше точек, чем в отрезке половинной длины [0, 1/2], а мы знаем что отрезки разных длин равномощны (растяжение). Как мы увидим дальше, говоря о теореме Кантора–Бернштейна, это рассуждение можно узаконить, но просто так оно не имеет смысла, потому что понятия «меньше» и «больше» мы для множеств не определяли. Тем не менее отрезок и полуинтервал (а также интервал) равномощны. Мы увидим это, используя свойства счётных множеств (следующий раздел), но уже сейчас можете попытаться придумать искомую биекцию, не заглядывая дальше. Задача 4. Укажите биекцию f : [0, 1] → [0, 1). Если это пока не получается, можно потренироваться на других примерах. Задача 5. Укажите взаимно однозначное соответствие между прямой R и интервалом (0, 1). (Указание: у нас уже было соответствие между их половинами.) Задача 6. Укажите взаимно однозначное соответствие между плоскостью и внутренностью круга (без границы). А вот несколько негеометрических примеров. 3 Задача 7. Установите взаимно однозначное соответствие между бесконечными последовательностями нулей и единиц (бесконечными двоичными дробями без целой части) и подмножествами натурального ряда. Задача 8. Установите взаимно однозначное соответстветствие между бесконечными последовательностями цифр 0, 1 и бесконечными последовательностями цифр 0, 1, 2, 3. Задача 9. (Продолжение) Тот же вопрос для последовательностей цифр 0, 1, 2. 2 Счётные множества 2.1 Определение и простейшие примеры Среди бесконечных множеств выделяют так называемые счётные множества. Как мы увидим дальше, это «самые маленькие» бесконечные множества, а пока формальное определение: счётные множества — это множества равномощные множеству натуральных чисел N. Другими словами, множество A счётно, если существует биекция между N и A. (Как мы знаем, отношение равномощности симметрично, так что биекцию можно представлять себе действующей в любую сторону.) Наглядно это можно себе представлять так: каждый элемент множества пронумерован — ему присвоен номер (натуральное число), и каждое натуральное число использовано ровно один раз. Вообще, когда первоклассник считает камешки на столе, говоря "один, два, три, четыре или когда завхоз составляет список мебели в номере (типа «1. Кровать железная. 2. Шкаф деревянный.. . . »), то, научно говоря, они устанавливают взаимно однозначное соответствие между предметами и натуральными числами. Для счётных множеств происходит то же самое, только процесс этот бесконечный: мы пересчитываем элементы множества, присваивая им номера и располагая их в последовательность, и «в результате» (если представить себе, что этот бесконечный процесс завершился) каждый элемент приобретает свой номер (натуральное число). Биекция f : N → A при этом сопоставляет с каждым натуральным числом предмет, пронумерованный этим числом. Сюръективность функции f означает, что каждый элемент A получит свой номер. А инъективность означает, что никакой элемент не будет пронумерован дважды. Самый простой пример счётного множества — это само множество натуральных чисел N. В качестве биекции можно взять тождественную функцию: само число и будет своим номером. Другой простой пример: множество положительных натуральных чисел. (Мы считаем нуль натуральным числом, так что это множество состоит из всех натуральных чисел, кроме нуля.) Здесь в качестве биекции можно взять функцию f (x) = x + 1 (отображающую множество натуральных чисел в множество положительных натуральных чисел). Ещё два примера у нас уже были: множество чётных натуральных чисел с биекцией x 7→ 2x и множество точных квадратов с биекцией x 7→ x2 . Чуть более сложный пример — это множество целых чисел Z. Оно тоже счетно. Чтобы это увидеть выпишем последовательно целые числа следующим образом: 0, 1, −1, 2, −2, 3, −3, . . . . Видно, что всякое целое число рано или поздно встретится в этой последовательности, и только один раз. По существу, мы только что перенумеровали множество Z. Научно говоря, мы построили биекцию: в нуле она будет равна первому элементу последовательности, в единице — второму и так далее N: Z: ↓ 1 2 ↓ ↓ 1 −1 3 4 ↓ ↓ 2 −2 5 6 ↓ ↓ 3 −3 7 8 ↓ ↓ 4 −4 9 ... ↓ 5 ... Таким образом, чтобы показать счётность множества, надо выписать его элементы в последовательность, каждый по одному разу и ничего не пропустив. 4 2.2 Свойства счётных множеств Лемма 1. Объединение двух счётных множеств счётно. Доказательство. Рассмотрим два счетных множества A и B; каждое из них можно записать в последовательность: a0 , a1 , a2 , a3 , . . . b0 , b 1 , b 2 , b 3 , . . . Теперь нетрудно перечислить и элементы множества A ∪ B, чередуя элементы из A с элементами из B: a0 , b0 , a1 , b1 , a2 , b2 , . . . . Если A и B не пересекаются, то на этом рассуждение заканчивается — но если пересекаются, то в этой последовательности общие элементы встретятся по два раза. Как это исправить? Если очередной элемент уже встречался ранее (например, если элемент aj совпадает с элементом bi , где i < j), то мы его пропускаем и второй раз не выписываем. Лемма 2. Всякое подмножество счетного множества конечно или счетно. Доказательство. Рассмотрим счётное множество A и его подмножество A0 . Выпишем элементы A в последовательность a0 , a1 , a2 , a3 , . . . . Вычеркнем из этой последовательности те элементы, которые не лежат в A0 . В результате останется последовательность элементов A0 — конечная или бесконечная. В первом случае множество будет конечным, во втором счётным. Формально говоря, для бесконечного подмножества A0 ⊂ A искомая биекция f : N → A0 ставит в соответствие числу n элемент множества A0 , который стоит n-м по счёту в последовательности (если считать только элементы A0 ). Лемма 3. Всякое бесконечное множество содержит счётное подмножество. Доказательство. Рассмотрим прозвольное бесконечное множество A. Нам надо выписать последовательность из некоторых его элементов, не обязательно всех. Будем действовать самым простым образом. Первый элемент a0 возьмем произвольно. Поскольку A бесконечно, в нем есть ещё элементы (кроме a0 ). В качестве a1 возьмем любой из них. И так далее. В общем случае, когда нам нужно выбрать очередной элемент an , мы рассматриваем подмножество {a0 , . . . , an−1 }. Оно конечно, а значит, не совпадает со всем множеством A (которое по предположению бесконечно). Значит, в A есть элементы, не лежащие в этом подмножестве — и мы можем взять любой из них в качестве an . Получили бесконечную последовательность из элементов A, и множество элементов этой последовательности образует искомое счётное подмножество множества A. Две последние леммы объясняют, в каком смысле счётные множества — это «самые маленькие» бесконечные множества. Между ними и конечными нет ничего промежуточного (лемма 2), и всякое бесконечное множество «не меньше» счётного в том смысле, что в нём есть счётное подмножество (лемма 3). Позже мы увидим, что бывают и бо́льшие (несчётные) бесконечные множества. Например, таким оказывается множество действительных чисел (или точек на прямой), но и это не предел. Пока же продолжим изучение счётных множеств. Лемма 4. Множество рациональных чисел Q счетно. Доказательство. Нам будет удобнее доказать отдельно, что множество неотрицательных рациональных чисел счётно и что множество отрицательных рациональных чисел счётно. Тогда счётность множества всех рациональных чисел сразу вытекает из леммы 1. Проведем рассуждение для неотрицательных рациональных чисел. Для отрицательных чисел рассуждение аналогично (а можно заметить, что смена знака даёт биекцию между отрицательными и положительными числами, а к положительным рациональным числам применить лемму 2). 5 Неотрицательное рациональное число задается парой чисел — числителем и знаменателем. Числитель может быть произвольным натуральным числом, а знаменатель произвольным положительным натуральным числом. Выпишем все такие числа в виде таблицы, бесконечной вниз и вправо: 0/1 1/1 2/1 3/1 . . . 0/2 1/2 2/2 3/2 . . . 0/3 1/3 2/3 3/3 . . . . 0/4 1/4 2/4 3/4 . . . .. .. .. .. .. . . . . . В строке с номером i этой таблицы стоят последовательно все числа со знаменателем i, а в столбце с номером j — все числа с числителем j. В этой таблице будут выписаны все рациональные числа, причем некоторые будут повторяться много раз (например, 0/1 = 0/2 = 0/3 = . . . и 1/2 = 2/4 = 3/6 = . . .). Числа из этой таблицы теперь уже легко выписать в последовательность. Например, можно идти по диагоналям (вниз-влево). Сначала выпишем единственное число на первой диагонали (0/1), потом два числа на второй (1/1, 0/2), потом три числа на третьей и так далее: 0/1, 1/1, 0/2, 2/1, 1/2, 0/3, 3/1, 2/2, 1/3, 0/4, . . . . Другими словами, мы сначала выписываем все числа с суммой числителя и знаменателя 1, потом — с суммой 2, потом 3 и так далее. Конечно, нужно не забыть выбрасывать из последовательности повторяющиеся члены. То есть, когда мы доходим в таблице до очередного числа и видим что равное ему уже было выписано, мы пропускаем текущее число и переходим к следующему. Получится такая последовательность рациональных чисел: 0, 1, 2, 1/2, 3, 1/3, . . . . В этом доказательстве на самом деле не имеет значения, что именно мы записываем в бесконечную вправо и вниз таблицу: верно такое общее утверждение. Теорема 1. Объединение конечного или счётного числа конечных или счётных множеств конечно или счётно. Доказательство. Пусть есть счётное количество счётных множеств A0 , A1 , A2 , . . .. Как и в прошлой лемме, расположим их элементы в виде таблицы: A0 : A1 : A2 : A3 : a30 .. . a00 a10 a20 a31 .. . a01 a11 a21 a32 .. . a02 a12 a22 a33 .. . a03 a13 a23 ... .. . ... ... ... . .. . Здесь в первой строке мы последовательно выписали элементы A0 , во второй — элементы A1 и так далее. Теперь снова соединяем эти последовательности в одну, идя по диагоналям: a00 , a01 , a10 , a02 , a11 , a20 , a03 , a12 , a21 , a30 , . . . . При этом нужно следить, чтобы члены последовательности не повторялись: когда мы рассматриваем очередной элемент таблицы, нужно проверить, не встретился ли он раньше. Если он уже был, его нужно пропустить. Мы предполагали, что все Ai счётны и что их счётное число. Если самих множеств лишь конечное число, или если какие-то из множеств конечны, то в таблице часть ячеек окажется пустой. Соответственно, мы будем их пропускать при составлении последовательности. В результате либо получится бесконечная последовательность, и тогда объединение счётно, либо получится только конечная последовательность — и тогда объединение конечно. 6 По существу ту же теорему можно сформулировать иначе: Теорема 2. Декартово произведение двух счётных множеств A × B cчётно. Доказательство. В самом деле, по определению декартово произведение есть множество всех упорядоченных пар вида ha, bi, в которых a ∈ A и b ∈ B. Разделим пары на группы, объединив пары с одинаковой первой компонентой (каждая группа имеет вид {a}×B для какого-то a ∈ A). Тогда каждая группа счётна, поскольку находится во взаимно однозначном соответствии с B (пара определяется своим вторым элементом), и групп столько же, сколько элементов в A, то есть счётное число. Например, множество пар натуральных чисел N × N счётно, поскольку его можно разбить в объединение счётного числа счётных множеств: {0} × N, {1} × N, {2} × N, . . .. А что можно сказать про N3 , множество всех упорядоченных троек натуральных чисел? Можно было бы составить аналогичную трёхмерную таблицу и перечислять все тройки по «двумерным диагональным плоскостям», то есть в порядке увеличения суммы трёх членов тройки. (В самом деле, троек с данной суммой конечное число.) Тот же приём годится и для четвёрок и вообще для множества Nk при любом натуральном k. Вместо этого можно воспользоваться индукцией по k. При k = 1 утверждение очевидно. Если мы уже доказали счётность Nk , то можно представить Nk+1 как произведение N×Nk (набор из k +1 одного числа можно, как делают программисты на лиспе, считать парой (первое число, набор из k остальных чисел), и потому Nk+1 счётно как произведение счётных множеств. Другими словами, можно разбить множество Nk+1 в счетное объединение следующих множеств: {0} × Nk , {1} × Nk , {2} × Nk , . . .. По предположению индукции каждое из этих множеств счетно, а значит счетно и их объединение. Теперь можно доказать, что множество конечных последовательностей натуральных чисел счётно. Действительно, это множество можно разбить на части: последовательности длины 1, длины 2, длины 3 и так далее. Последовательностей фиксированной длины k счётное число, как мы только что доказали, так что мы получили объединение счётного числа счётных множеств. Вместо натуральных чисел можно рассматривать элементы произвольного конечного или счётного множества A. Такое множество называют алфавитом, элементы A называют буквами, или символами алфавита A, а конечные цепочки (последовательности) букв называют словами, или строками в алфавите A. Так что можно говорить, скажем, о словах в русском алфавите (и это не только слова русского языка, но и бессмысленные цепочки русских букв). Задача 10. Докажите, что число слов в конечном или счётном алфавите счётно. Частный случай этой задачи: слова в двоичном алфавите {0, 1}, которые программисты называют битовыми строками; множество таких строк тоже счётно. Задача 11. Доказывая счётность множества битовых строк, профессор говорит: «в самом деле, запись в двоичной системе даёт биекцию между множеством всех битовых строк и множеством всех натуральных чисел». Почему он неправ? Как можно исправить его ошибку и указать искомую биекцию? 3 Несчётные множества 3.1 Интервал и отрезок равномощны В этом разделе мы перейдём к несчётным множествам. Точнее, пока что мы должны говорить о множествах, про которые не ясно, счетны они или нет. К таким множествам, например, относятся интервал (0, 1), отрезок [0, 1], полупрямая (0, ∞), прямая (−∞, ∞), а также соответствующие геометрические объекты. Мы уже видели, что интервал (0, 1) равномощен полупрямой (0, ∞). Из этого легко получить, что интервал (0, 1) равномощен прямой (−∞, ∞). Действительно, интервал (0, 1) равномощен интервалу (0, 2) (биекция f (x) = 2x), а он, в свою очередь, 7 равномощен (−1, 1) (биекция f (x) = x − 1). Теперь можно разбить интервал (−1, 1) на три части (−1, 0), {0} и (0, 1). Первую из них можно биективно отобразить на полупрямую (−∞, 0), точку 0 интервала можно отобразить в точку 0 прямой, а интервал (0, 1) можно отобразить в полупрямую (0, ∞). Соединив эти три биекции в одну, мы получаем биекцию из (−1, 1) в (−∞, ∞). Теперь, пользуясь транзитивностью отношения равномощности, мы получаем, что интервал (0, 1) равномощен числовой прямой (−∞, ∞). Это всё мы уже обсуждали — но теперь мы готовы пойти дальше и доказать, что интервал (0, 1) и полуинтервал (0, 1] тоже равномощны. Для этого мы воспользуемся известными нам сведениями про счётные множества. Выделим в интервале какое-нибудь счётное подмножество, например A = {1/2, 1/3, 1/4, 1/5, . . .}. Если мы добавим к нему точку 1, то оно останется счётным: A ∪ {1} = {1, 1/2, 1/3, 1/4, . . .}. Таким образом, существует биекция f из множества A в множество A ∪ {1}. Теперь нетрудно доопределить f до биекции всего интервала (0, 1) в полуинтервал (0, 1]. Для этого скажем, что все точки, на которых f пока не определено, то есть все точки из (0, 1) \ A, переходят в себя: f (x) = x. Можно записать это формулой: ( 1/(n − 1), если x ∈ A и x = 1/n при n ≥ 2; f (x) = x, если x ∈ / A. и изобразить на картинке: Полученная функция составлена из двух биекций и сама является биекцией из (0, 1) в (0, 1]. Задача 12. Докажите, что интервал (0, 1) равномощен полуинтервалу [0, 1). Задача 13. Докажите, что интервал (0, 1) равномощен отрезку [0, 1]. 3.2 Добавление счётного множества На самом деле геометрический характер этого рассуждения — только видимость. По существу мы доказали такой общий результат: Теорема 3. Если множество A бесконечно, а множество B конечно или счётно, то множество A ∪ B равномощно A. Доказательство. Без ограничения общности можно считать, что множества A и B не имеют общих элементов: A ∩ B = ∅. Действительно, если это не так, то можно просто не добавлять те элементы, которые уже есть в A, то есть вместо множества B рассмотреть множество B \ A. Оно тоже конечно или счётно (лемма 2), с A уже не пересекается, а объединение множеств от такой замены не изменится. Как мы уже знаем (лемма 3), в множестве A есть счетное подмножество A0 . Объединение A0 ∪ B тоже счётно (теорема 1). Значит, существует биекция f : A0 → A0 ∪ B. Остаётся продолжить её до биекции всего множества A в множество A ∪ B, положив f (x) = x для всех x ∈ A \ A0 . В сущности, мы повторили то же самое рассуждение, что и раньше, только без картинки (и для произвольного конечного или счётного множества вместо одной точки). Задача 14. Докажите, что если множество A бесконечно, а множество B конечно, то разность A \ B равномощна A. Почему в этом утверждении нельзя заменить «конечно» на «счётно»? 3.3 Числа и последовательности Теперь мы можем установить соответствие между двумя множествами, которые мы рассматривали по отдельности: 8 Теорема 4. Отрезок [0, 1] равномощен множеству бесконечных последовательностей из нулей и единиц. Отсюда следует, что и интервал, и прямая равномощны множеству бесконечных последовательностей нулей и единиц (поскольку они, как мы уже знаем, равномощны отрезку). Доказательство. Доказательство этой теоремы требует каких-то знаний о действительных числах. Будем считать, что из курса анализа известно, что каждое число x ∈ [0, 1] можно записать в виде бесконечной двоичной дроби (аналогично тому, как его можно записать в виде бесконечной десятичной дроби). Напомним, как это делается. Первый знак (бит) после запятой равен 0, если x лежит в левой половине отрезка [0, 1], и равен 1, если в правой. Чтобы определить следующий бит, нужно поделить выбранную половину снова пополам. Если x лежит в левой половине, то следующая цифра 0, а если в правой, то 1. И так далее: чтобы определить очередной знак, нужно поделить текущий отрезок пополам и посмотреть, в какую половину попадает x. Можно ли сказать, что мы тем самым построили взаимно однозначное соответствие между числами на отрезке [0, 1] и бесконечными двоичными последовательностями (дробями)? Не совсем. Проблема в том, что это соответствие не взаимно однозначно, некоторым числам соответствуют две последовательности. А именно, это происходит, когда точка попадает на границу очередного отрезка. Тогда мы можем относить её как к левой, так и к правой половине. В результате, например, последовательности 0, 1001111 . . . и 0, 101000 . . . соответствуют одному и тому же числу (какому?).2 Как же исправить положение? Мы получим взаимно однозначное соответствие, если исключим последовательности, в которых начиная с некоторого момента все цифры равны 1 (одну такую последовательность мы всё же должны оставить – это 0.111 . . .). Но таких последовательностей счётное множество, так что их добавление не меняет мощности множества по теореме 3. Естественно, не обязательно было пользоваться двоичной системой: можно было бы рассмотреть обычную десятичную систему, и показать, что отрезок [0, 1] равномощен множеству бесконечных десятичных дробей. Или троичную — и показать, что тот же самый отрезок [0, 1] равномощен множеству бесконечных последовательностей из цифр 0, 1, 2. Кстати, отсюда следует, что все эти множества последовательностей равномощны — тем самым мы получаем решение задач 8 и 9. Правда, оно использует сведения о действительных числах, и получается довольно сложно описываемое соответствие (если всё развернуть), так что всё равно остаётся задача явно указать просто описываемое соответствие между этим множествами. Задача 15. Покажите, что отрезок [0, 1] равномощен множеству бесконечных последовательностей натуральных чисел. 3.4 Отрезок и квадрат Теперь мы можем доказать следующий довольно неожиданный результат. (Изобретатель теории множеств немецкий математик XIX века Георг Кантор даже надеялся доказать обратное и тем самым подкрепить интуитивное ощущение, что «на двумерной плоскости больше точек, чем на одномерной прямой» — и был очень удивлён, когда понял, что на самом деле это не так!) Теорема 5. Отрезок [0, 1] равномощен квадрату [0, 1] × [0, 1]. 2 Тот же самый эффект хорошо известен для десятичной системы: дроби 0.19999 . . . и 0, 20000 . . . представляют одно и то же число, 1/5. 9 Доказательство. Мы уже знаем, что отрезок [0, 1] равномощен множеству бесконечных последовательностей нулей и единиц. Тогда квадрат [0, 1]×[0, 1] равномощен множеству упорядоченных пар таких последовательностей. Действительно, чтобы получить пару, соответствующую точке (x, y), надо составить пару из последовательности, соответствующей x, и последовательности, соответствующей y. Осталось установить взаимно однозначное соответствие между бесконечными последовательностями нулей и единиц и парами таких последовательностей (и воспользоваться транзитивностью). Это сделать уже не так сложно. Паре последовательностей (a0 , a1 , a2 , a3 , . . . , b0 , b1 , b2 , b3 , . . .) можно поставить в соответствие последовательность a0 , b0 , a1 , b1 , a2 , b2 , a3 , b3 , . . . . Нетрудно увидеть, что это отображение взаимно однозначное (обратное к нему выделяет из последовательности отдельно чётные и отдельно нечётные члены). Хочется сказать по-простому: каждой паре чисел (0.x1 x2 x3 . . . , 0.y1 y2 y2 . . .) мы ставим в соответствие число 0.x1 y1 x2 y2 x3 y3 . . .. И всё было бы хорошо, если бы не эта проблема с двумя представлениями: числу 0.313939393939 . . . соответствует пара (0.333 . . . , 0.1999 . . .) = (1/3, 1/5), и та же самая пара соответствует другому числу 0.323030303030 . . .. Поэтому нам понадобилось предварительно использовать тот факт, что добавление счётного множества не меняет мощности. Задача 16. Докажите, что множество точек пространства (которые можно записывать тремя координатами, то есть множество R3 ) равномощно R. Докажите, что Rk равномощно R при любом k. Задача 17. Докажите, что множество бесконечных последовательностей действительных чисел равномощно R. 4 Диагональный аргумент Кантора и сравнение мощностей 4.1 Несчётность отрезка Давайте на минутку остановимся и посмотрим, что мы уже доказали. У нас было много примеров счётных множества, а также — отдельно от этого — много примеров множества, равномощных между собой (отрезок, интервал, полуинтервал, множество последовательностей нулей и единиц, множество точек квадрата и пр.). Мы уже упоминали, что множества во втором списке несчётны, но пока что это не доказали. Давайте это сделаем. Поскольку они все равномощны, мы можем выбрать удобное нам. Теорема 6 (Кантор). Множество бесконечных последовательностей нулей и единиц несчётно. Доказательство. Предположим, что это множество счётно, то есть что последовательности нулей и единиц можно пронумеровать. Обозначим последовательность с номером i через ai , а её члены обозначим ai0 , ai1 , . . .. Удобно члены последовательностей писать слева направо, а саму последовательность последовательностей писать сверху вниз. Получится нечто вроде бесконечной таблицы: a0 a1 a2 .. . = a00 = a10 = a20 .. .. . . a01 a11 a21 .. . 10 a02 a12 a22 .. . ... ... ... .. . Теперь рассмотрим «диагональную» последовательность в этой таблице, то есть последовательность a00 , a11 , a22 , . . . и заменим в ней все биты на противоположные. Другими словами, положим bi = 1 − aii и рассмотрим последовательность b = (b0 , b1 , b2 , . . .). Последовательность b отличается от любой последовательности ai в i-й позиции, поскольку bi = 1 − aii 6= aii , так что последовательности b нет в нашей нумерации всех последовательностей — а там по предположению были все. Мы пришли к противоречию, а значит, множество всех бесконечных последовательностей нулей и единиц несчетно. Поскольку это очень важная теорема, давайте изложим по существу то же доказательство немного по-другому. Докажем, что если дано счётное множество бесконечных двоичных дробей a0 , a1 , a2 , . . ., то можно построить бесконечную дробь b, которая отлична от всех них. Нам надо удовлетворить счётное число требований: во-первых, b не должна совпасть с a0 , во-вторых, b не должна совпасть с a1 , и так далее. Заметим, что для совпадения двух дробей надо, чтобы совпадали все члены — а для несовпадения достаточно, чтобы не совпал какой-то один. Поэтому условия b 6= a0 можно добиться, взяв первый бит в b не таким, какой он в a0 . Что бы мы ни делали дальше, b уже совпасть с a0 не сможет. После этого мы гарантируем b 6= a1 , взяв второй бит b не таким, как у a1 , затем мы гарантируем b 6= a2 c помощью третьего бита и так далее. В итоге полученная последовательность b будет отличаться от всех ai . Задача 18. Можно ли провести то же самое рассуждение для конечных последовательностей нулей и единиц? В каком месте перестаёт работать доказательство? Мы уже знаем, что отрезок [0, 1] равномощен множеству бесконечных последовательностей нулей и единиц, так что отрезок тоже будет несчётным множеством. Можно доказать несчётность сразу для отрезка. Пусть дана последовательность a0 , a1 , a2 , . . . точек отрезка (действительных чисел от 0 до 1). Как построить действительное число, которого в ней нет? Построим последовательность вложенных отрезков, общая точка которых (она существует, как учит математический анализ) будет отсутствовать среди ai . Начнём с любого отрезка, не содержащего a0 . Уменьшим его так, чтобы в новый отрезок не попало и a1 (скажем, поделим его на три части, a1 в самом неудачном случае может попасть в две, а мы возьмём третью). Потом снова уменьшим, чтобы не попало и a2 . И так далее — мы постепенно отделимся (исключим возможность совпадения) от всех ai . Зная, что множество действительных чисел несчётно, а множество рациональных чисел (дробей с целыми числителями и знаменателями) счётно, мы получаем в качестве следствия, что существуют иррациональные числа (не представимые √ такими дробями). Впрочем, это знали ещё древние греки, доказавшие иррациональность 2. Но тот же метод можно использовать и для доказательства более сильного утверждения. Алгебраическим числом называется число, являющееся корнем ненулевого многочлена с целыми коэффициентами. Задача 19. Докажите, что таких многочленов счётное число. Задача 20. Докажите, что множество алгебраических чисел счётно. (Указание: из алгебры известно, что у многочлена степени n не больше n корней.) Задача 21. Докажите, что существует действительное, но не алгебраическое число. Такие числа называются трансцендентными. То, что они бывают, было доказано до Кантора. Первым это сделал французский математик Лиувилль: он показал, что бесконечная дробь 0.0100100000010000000000000000000000010 . . . в которой сначала один нуль, потом два, потом шесть (3!), потом 24 = 4! и так далее по факториалам, не будет алгебраической — основываясь на том, что она уж слишком хорошо приближается рациональными числами. Потом (гораздо более сложным образом) была доказана трансцендентность чисел e и π (второе показывает, в частности, что задача о квадратуре 11 круга не решается циркулем и линейкой). Но все эти доказательства были про конкретные числа и требовали некоторой работы — а тут пришёл Кантор и вывел это из общих соображений о счётных и несчётных множествах. Сначала это воспринималось с подозрением, но теперь эта конструкция стала стандартным средством и в анализе (теорема Бэра о том, что пересечение всюду плотных открытых множеств в полном пространстве непусто), и в computer science (диагональный метод — с его помощью, кстати, можно доказать, что в любом разумном языке программирования есть программа, печатающая свой текст), Задача 22. Докажите, что множество всех подмножеств множества натуральных чисел несчетно. Задача 23. Докажите, что множество всех функций f : N → {0, 1} несчётно. Задача 24. Докажите, что существует функция f : N → {0, 1}, для которой не существует программы на вашем любимом языке программирования, вычисляющей эту функцию. 4.2 Сравнение мощностей Вернёмся к байке, с которой мы начинали — про людей и стулья. Мы говорили тогда, что если стульев не хватило, то бессмысленно вставать и пересаживаться, их всё равно не хватит. Говоря научно, если конечное множество A равномощно некоторой части конечного множества B, не совпадающей с B, то оно не равномощно самому B. Можно сказать, что A имеет «меньшую мощность». Для бесконечных множеств это не так: множество может быть равномощно своей части. Тем не менее можно дать такое определение: множество A имеет мощность не большую, чем множество B, если A равномощно некоторому подмножеству множества B (возможно, совпадающему с B). Задача 25. Докажите, что счётное множество имеет мощность не больше, чем любое бесконечное множество. Задача 26. Докажите, что множество A имеет мощность не больше, чем множество B, в том и только том случае, когда существует инъекция f : A → B. Задача 27. Докажите, что множество A имеет мощность не больше, чем множество B, в том и только том случае, когда существует сюръекция g : B → A. Эта терминология («не больше») опасна: она подразумевает, что для такого сравнения множеств по мощности выполнены два свойства, которые мы знаем для обычного сравнения чисел — между тем мы их пока что не доказали. Вот эти свойства: • Если мощность A не больше, чем у B, и одновременно мощность B не больше, чем у A, то A и B равномощны. • Для любых двух множеств A и B мощность одного из них не больше, чем у другого. Первое свойство называется (на языке упорядоченных множеств) антисимметричностью, а второе — линейностью порядка. Оба эти свойства верны. Второе — одно из главных достижений Кантора; он доказал его, придумав то, что теперь называется «трансфинитной индукцией», это обобщение метода математической индукции на множества произвольной мощности. Сам этот метод, увы, выходит за рамки этих лекций (про него можно прочесть, например, в книге «Начала теории множеств»), так что это второе утверждение так и останется (увы) для нас недоказанным. А вот первое утверждение доказать легче. По существу мы его уже доказали, так что нужно только вспомнить. Когда мы говорили про инъекции, то доказали такое утверждение: если существует инъекция A в B, а также инъекция B в A, то из них можно составить биекцию A и B. Это то самое, что нам нужно: взаимно однозначное соответствие между A и подмножеством B — это в точности инъекция A в B. 12 Мы закончим наше знакомство с мощностями множеств ещё одним результатом Кантора. Теорему Кантора о несчётности отрезка можно интерпретировать как утверждение о том, что множество натуральных чисел по мощности меньше множества последовательностей нулей и единиц (в одну сторону биекция есть, поскольку в любом бесконечном множестве есть счётное подмножество, а в другую нет, потому что подмножество счётного множества счётно). Вместо последовательностей нулей и единиц можно рассматривать подмножества множества N: каждая битовая последовательность a0 a1 a2 . . . соответствует множеству тех i, при которых ai = 1. Таким образом, множество N имеет меньшую мощность, чем множество всех подмножеств N. Кантор заметил, что то же самое рассуждение проходит для любого множества (а не только для множества натуральных чисел). Теорема 7 (Общая формулировка теоремы Кантора). Никакое множество X не равномощно множеству своих подмножеств. Доказательство. Предположим, что множество X и множество всех его подмножеств (оно обозначается 2X ) равномощны. Пусть f — биекция из X в 2X . Рассмотрим те элементы x, которые не принадлежат соответствующим им подмножествам, то есть x ∈ / f (x). Рассмотрим теперь множество всех таких элементов: Y = {x ∈ X | x ∈ / f (x)}. До противоречия осталось совсем немного: оказывается, что этому множеству Y не может соответствовать никакой элемент множества X. Действительно, пусть Y = f (y) для некоторого y ∈ X. Тогда y∈Y ⇔y∈ / f (y) ⇔ y ∈ / Y, здесь первая равносильность верна по определению множества Y , а вторая – поскольку f (y) = Y . Мы получили противоречие, а значит такой биекции f не существует. Другими словами, мы строим множество Y , отличающееся от всех f (y) — а именно, требуем, чтобы в точке y множество Y вело себя не так же, как f (y) (ведь отличия в одной точке достаточно для различия множеств). Заметим, что легко построить инъекцию из X в 2X . Действительно, положим f (x) = {x} для всякого x ∈ X. Таким образом, можно сказать, что мощность множества X всегда меньше мощности множества 2X . Задача 28. Докажите, что для всякого n ∈ N выполняется n < 2n . Задача 29. Покажите, что не существует сюръекции X → 2X и не существует инъекции 2X → X. (Это можно вывести из теоремы Кантора и теоремы Кантора–Бернштейна, а можно доказать, приспособив доказательство теоремы Кантора.) Последняя теорема подводит нас к опасной черте, где в теории множеств начинаются парадоксы. Например, рассмотрим множество всех множеств U — его элементами являются произвольные множества. Оно выглядит как-то необозримо — мало ли какие бывают множества — и не зря: разрешив себе его рассматривать, мы сразу же придём к противоречию. Заметим, что все подмножества множества U (и вообще все подмножества любых множеств!) являются его элементами, то есть 2U ⊆ U . Но по теореме Кантора получается, что мощность 2U больше U , то есть мы приходим к противоречию. Если попытаться раскрутить это рассуждение, вспомнив доказательство теоремы Кантора, получится «парадокс Рассела»: если x — множество всех таких множеств, которые не являются своими элементами, то будет ли x своим элементом? Любой ответ приводит к противоречию: по построению y∈x⇔x∈ / x, при любом y, в том числе при y = x, так что x∈x⇔x∈ / x. Получается какая-то ерунда. 13 5 Что дальше? Теория множеств, особенно множеств большой мощности — вещь довольно абстрактная, и изучает не пойми что. Если при некотором усилии можно убедить себя, что натуральные числа встречаются «в жизни» (хотя, конечно, очень большое натуральное число каких-нибудь фотонов и во вселенной-то может не поместиться), а с ещё большей натяжкой можно считать, что и действительные числа тоже бывают, то про какое-то нибудь множество всех подмножеств множества всех подмножеств действительных чисел это уже совсем малоубедительно. Поэтому не так удивительно, что один из самых первый вопросов про множества, поставленный Кантором (есть ли множество промежуточной мощности между счётными множествами и континуумом, то есть бывает ли подмножество отрезка, которое не равномощно всему отрезку, но и не счётно), оказался неразрешимым. Сначала знаменитый логик Курт Гёдель в середине XX века доказал, что существование такого подмножества нельзя опровергнуть (пользуясь принятыми аксиомами теории множеств), а ещё через несколько десятилетий американский математик Пол Коэн доказал, что и доказать его (с помощью тех же аксиом) нельзя. Хочется спросить, «так что же на самом деле» — но вопрос этот сомнительный (примерно с тем же основанием можно было бы спрашивать, осталась ли на самом деле «век верна» пушкинская Татьяна своему нелюбимому мужу — из текста романа не следует ни того, ни другого, а никакого иного «самого дела» тут вроде как нет). Информатика, конечно, интересуется в основном конечными объектами, и даже не очень большими (для неё 21000 уже почти что бесконечность), так что теория множеств с её большими множествами вроде как тут не по делу. Тем не менее мы немного в ней поразбирались не зря — во-первых, жизнь не исчерпывается информатикой, и это просто забавно, во-вторых, тренировка в логических рассуждениях с использованием языка теории множеств в любом случае не помешает; наконец, многие идеи, возникшие в теории множества (например, диагональный аргумент) оказываются полезными и в других задачах, о чём мы уже упоминали. 14