Виленкин Рассказы о множествах. Рассказы о множествах 3е издание
 Скачать 9.06 Mb.
|
|
на прямой или в квадрате? На первый взгляд кажется, что ответить на эти вопросы совсем просто. Ведь множество натуральных чисел является частью множе- ства рациональных чисел, а отрезок — частью прямой. Не ясно ли, что поэтому натуральных чисел меньше, чем рациональных, а то- чек на отрезке меньше, чем точек на всей прямой? Оказывается, не ясно. Ведь ниоткуда не следует, что при переходе к бесконечным множествам сохранятся законы, выведенные из рассмотрения конеч- ных множеств, например, закон о том, что «часть меньше целого». А самое главное, попытка сравнения бесконечных множеств по тому признаку, что одно является частью другого, заранее обре- чена на неудачу. Например, где больше точек, в квадрате или на всей бесконечной прямой? Ведь ни квадрат нельзя вложить в прямую линию, ни прямую линию нельзя, не ломая ее, поместить в квадрат. Разумеется, можно разломать прямую линию на отрезки, длина которых равна стороне квадрата, и после этого каждый отрезок поместить в квадрат так, чтобы они не пересекались друг с другом. Но вдруг и квадрат можно как-то разбить на части, а потом эти части положить на прямую, чтобы они не задевали друг друга? А сколько есть бесконечных множеств, не являющихся частями друг друга! Множество квадратов на плоскости и множество кругов на той же плоскости не имеют ни одного общего элемента. Как же сравнить их? Как узнать, чего больше во вселенной — атомов азота или кислорода? Итак, задача поставлена. В первую очередь мы выясним, в ка- ком случае надо говорить, что одно множество содержит столько же элементов, сколько и второе. Иными словами, выясним, в каких случаях два бесконечных множества имеют «поровну» элементов. На танцплощадке Для конечных множеств задача сравнения решается просто. Что- бы узнать, одинаково ли число элементов в двух множествах, доста- точно пересчитать их. Если получатся одинаковые числа, то, значит, На каждый прилив — по отливу 61 в обоих множествах поровну элементов. Но для бесконечных мно- жеств такой способ не годится, ибо, начав пересчитывать элементы бесконечного множества, мы рискуем посвятить этому делу всю свою жизнь и все же не закончить начатого предприятия. Но и для конечных множеств метод пересчета не всегда удо- бен. Пойдем, например, на танцплощадку. Как узнать, поровну ли здесь юношей и девушек? Конечно, можно попросить юношей отой- ти в одну сторону, а девушек в другую, и заняться подсчетом как тех, так и других. Но, во-первых, мы получим при этом избыточную информацию, нас не интересует, сколько здесь юношей и девушек, а интересует лишь, поровну ли их. Во-вторых, не для того собралась молодежь на танцплощадке, чтобы стоять и ждать конца пересчета, а для того, чтобы потанцевать. Ну что же. Удовлетворим их желание и попросим оркестр сыг- рать какой-нибудь танец, который все умеют танцевать. Тогда юно- ши пригласят девушек к танцу и... наша задача будет решена. Ведь если окажется, что все юноши и все девушки танцуют, то есть если вся молодежь разбилась на танцующие пары, то ясно, что на пло- щадке ровно столько же юношей, сколько и девушек. Совершенно тем же способом можно узнать, что число зрителей в театре равно числу театральных кресел. Если во время спектакля все места заняты, причем никто из зрителей не стоит в проходах и на каждом месте сидит один зритель, то можно быть уверенным, что зрителей ровно столько же, сколько и театральных кресел. Когда в дождливую погоду по улице пробегают люди, то число людей такое же, как и число их зонтов; у каждого человека — один и только один зонт, и никто не рискнул выбежать на улицу без зонта. На каждый прилив — по отливу Мы познакомились с тем, как узнать, что два конечных множе- ства имеют поровну элементов, не прибегая к пересчету этих мно- жеств. Этот способ можно применить и для бесконечных множеств. Только здесь уж не удастся прибегнуть к помощи оркестра, а при- дется самим располагать элементы двух сравниваемых множеств в «танцующие пары». Итак, пусть у нас даны два множества A и B. Говорят, что между ними установлено взаимно однозначное соответствие, если элемен- ты этих множеств объединены в пары (a; b) так, что: 62 Глава II. В мире чудес бесконечного 1) элемент a принадлежит множеству A, а элемент b — множе- ству B; 2) каждый элемент обоих множеств попал в одну и только од- ну пару. Например, если множество A состоит из юношей на танцплощад- ке, а множество B — из девушек на той же площадке, то пары (a; b) образуются из танцующих друг с другом юноши и девушки. Если множество A состоит из зрителей, а множество B — из театральных кресел, то пара (a; b) образуется из зрителя и кресла, на котором он сидит. Наконец, если A — множество людей на улице, а B — множе- ство их зонтов, то пара (a; b) образуется из человека и его зонта. Разумеется, не всякое соответствие между множествами является взаимно однозначным. Если множество A состоит из всех деревьев на Земле, а множество B — из растущих на них плодов, то между этими множествами можно установить соответствие: каждому плоду сопоставить дерево, на котором он растет. Но это соответствие не бу- дет взаимно однозначным: на некоторых деревьях растет помногу плодов, а другие сейчас не плодоносят. Поэтому одни элементы a (деревья) будут участвовать во многих парах, а другие элементы a не войдут ни в одну пару. Существование взаимно однозначного соответствия для конеч- ных множеств равносильно тому, что у них поровну элементов. Важ- нейшим поворотным пунктом в теории множества был момент, когда Кантор решил применить идею взаимно однозначного соответствия для сравнения бесконечных множеств. Иными словами, по Кантору два (быть может и бесконечных) множества A и B имеют поровну элементов, если между этими мно- жествами можно установить взаимно однозначное соответствие. Обычно математики не говорят, что «множества A и B имеют поровну элементов», а говорят, что «A и B имеют одинаковую мощ- ность» или «множества A и B эквивалентны» и обозначают как A ∼ B. Таким образом, для бесконечных множеств слово «мощность» значит то же самое, что для конечных множеств «число элементов». Еще до Кантора к понятию взаимно однозначного соответствия пришел чешский ученый Б. Больцано. Но он отступил перед труд- ностями, к которым вело это понятие. Как мы вскоре увидим, после принятия принципа сравнения бесконечных множеств с помощью взаимно однозначного соответствия пришлось расстаться со многи- ми догмами. Равна ли часть целому? 63 Равна ли часть целому? Основной догмой, которую пришлось отбросить, было положе- ние, установленное на самой заре развития математики: «часть меньше целого». Это положение безусловно верно для конечных множеств, но для бесконечных множеств оно уже теряет силу. Вспомните, как расселил директор необыкновенной гостиницы космозоологов по четным номерам. При этом расселении жилец из номера n переезжал в номер 2n. Иными словами, расселение шло по следующей схеме: 1 2 3 . . . n . . . ↓ ↓ ↓ ↓ 2 4 6 . . . 2n . . . Но эта схема устанавливает взаимно однозначное соответствие меж- ду множеством натуральных чисел 1, 2, 3, . . . , n, . . . и его частью — множеством четных чисел 2, 4, 6, . . . , 2n, . . . А мы договорились считать, что множества, между которыми можно установить взаимно однозначное соответствие, содержат по- ровну элементов. Значит, множество натуральных чисел содержит столько же элементов, сколько и его часть — множество четных чисел. Точно так же можно установить взаимно однозначное соот- ветствие между множеством натуральных чисел и множеством чисел вида 10, 100, 1000, 10 000, . . . Для этого надо сопоставить каждому натуральному числу n чис- ло 10 n : n → 10 n Этим желаемое взаимно однозначное соответствие и устанавливает- ся. Точно так же устанавливается взаимно однозначное соответствие между множеством натуральных чисел и множеством всех квадра- тов натуральных чисел: n → n 2 64 Глава II. В мире чудес бесконечного или множеством всех кубов натуральных чисел: n → n 3 и т. д. Вообще, между множеством всех натуральных чисел и любой его бесконечной частью всегда можно установить взаимно однозначное соответствие. Для этого достаточно перенумеровать по порядку чис- ла из этой части. Впрочем, не зря говорят, что ничто не ново под Луной, а но- вое — это только хорошо забытое старое. Еще в начале XVII века Га- лилей размышлял о противоречиях бесконечного и обнаружил воз- можность взаимно однозначного соответствия между множеством натуральных чисел и множеством их квадратов. В его книге «Беседы и математические доказательства, относящиеся к механике по мест- ному движению» (1638 год) приведен диалог, в котором Сальвиати, выражающий мысли самого Галилея, говорит: «Сказанное нами относится к числу затруднений, происходящих вследствие того, что, рассуждая нашим ограниченным разумом о бесконечном, мы приписываем последнему свойства, известные нам по вещам конечным и ограниченным. Между тем это непра- вильно, так как такие свойства, как б´ ольшая и меньшая величина и равенство, неприменимы к бесконечному, относительно которого нельзя сказать, что одна бесконечность больше или меньше другой или равна ей». В подтверждение своей мысли Сальвиати отмечает, что, с од- ной стороны, «квадратов столько же, сколько существует корней, так как каждый квадрат имеет свой корень, и каждый корень — свой квадрат; ни один квадрат не может иметь более одного корня, и ни один корень — более одного квадрата... 1 При этом число корней равно количеству всех чисел вообще, потому что нет ни одного числа, которое не могло бы быть корнем какого-нибудь квадрата; установив это, приходится сказать, что число квадратов равно общему коли- честву всех чисел...». С другой стороны, Сальвиати отмечает, что «количество всех чисел вместе — квадратов и неквадратов — больше, нежели одних только квадратов», причем «числа квадратов непре- рывно и в весьма большой пропорции убывают по мере того, как мы переходим к большим числам». В качестве единственного выхода из обнаруженного противоречия Сальвиати предлагает следующее: 1 Здесь имеются в виду только натуральные числа. Счетные множества 65 «Я не вижу возможности никакого другого решения, как при- знать, что бесконечно количество чисел вообще, бесконечно число квадратов, бесконечно и число корней. Нельзя сказать, что чис- ло квадратов меньше количества всех чисел, а последнее больше: в конечном выводе свойства равенства, а также большей и меньшей величины не имеют места там, где дело идет о бесконечности, и при- менимы только к конечным количествам». Мы видим, что Галилей, по сути дела, владел идеей взаимно однозначного соответствия и видел, что такое соответствие можно установить между множеством всех натуральных чисел и множе- ством квадратов, а потому эти множества можно считать имеющими одинаковое количество элементов. Понимал он и то, что для беско- нечных множеств часть может быть равной целому. Но отсюда он сделал неверный вывод, что все бесконечности одинаковы: он имел дело лишь с бесконечными подмножествами натурального ряда, а их можно перенумеровать. Галилей не мог себе представить, что множество всех точек отрез- ка перенумеровать нельзя (это у нас вскоре будет показано). Подобно атомистам древности он полагал, что отрезок складывается из под- дающейся пересчету бесконечной совокупности атомов. Счетные множества Все множества, которые имеют столько же элементов, сколь- ко имеет множество натуральных чисел, называют счетными. Иными словами, множество называется счетным, если оно бес- конечно, но его элементы можно перенумеровать натуральными номерами. Например, множество четных чисел, множество нечетных чисел, множество простых чисел, да и вообще любая бесконечная часть множества натуральных чисел являются счетными множе- ствами. Иногда для того, чтобы установить счетность того или иного множества, надо проявить изобретательность. Возьмем, например, множество всех целых чисел (как положительных, так и отрица- тельных): . . . , −n, . . . , −3, −2, −1, 0, 1, 2, 3, . . . , n, . . . Если мы попробуем нумеровать его по порядку, начиная с какого- нибудь места, то никогда эту нумерацию не закончим. Поэтому все числа до выбранного места останутся незанумерованными. Чтобы 66 Глава II. В мире чудес бесконечного не пропустить при нумерации ни одного числа, надо записать это множество в виде двух строк: 0, 1, 2, 3, 4, 5, 6, −1, −2, −3, −4, −5, −6, −7, и нумеровать по столбцам. При этом 0 получит № 1, −1 — № 2, 1 — № 3, −2 — № 4 и т. д. Иными словами, все положительные числа и нуль нумеруются нечетными числами, а все отрицательные целые числа — четными. Это похоже на то, как директор гостиницы поме- стил всех филателистов в гостиницу, заполненную космозоологами. Но если в то, что множество всех целых чисел счетно, легко поверить, то в счетность множества рациональных чисел поверить труднее. Ведь рациональные числа расположены очень густо — меж- ду любыми двумя рациональными числами найдется еще бесконечно много рациональных чисел. Поэтому совершенно непонятно, как их нумеровать; кажется, что между любыми двумя числами надо пе- ренумеровать еще бесконечно много чисел, и этот процесс никогда не закончится. И действительно, занумеровать рациональные числа в порядке возрастания их величины невозможно. Однако если отка- заться от расположения рациональных чисел в порядке возрастания, то занумеровать их все же удается. Сделаем так: выпишем сначала все положительные дроби со знаменателем 1, потом все положитель- ные дроби со знаменателем 2, потом со знаменателем 3 и т. д. У нас получится таблица следующего вида: 1 1 , 2 1 , 3 1 , 4 1 , . . . 1 2 , 2 2 , 3 2 , 4 2 , . . . 1 3 , 2 3 , 3 3 , 4 3 , . . . 1 4 , 2 4 , 3 4 , 4 4 , . . . Ясно, что в этой таблице мы встретим любое положительное рациональное число, и притом не один раз. Например, число 3 встре- тится и в виде дроби 3 1 , и в виде дроби 6 2 , и в виде дроби 9 3 Теперь приступим к нумерации. Для этого вспомним последний подвиг директора необыкновенной гостиницы, который расселил Алгебраические числа 67 в ней жителей из бесконечного множества таких же гостиниц. Он тогда воспользовался нумерацией по квадратам. Точно так же по- ступим и мы, только с тем осложнением, что некоторые дроби будем пропускать (например, так как 1 1 получила уже № 1, то дроби 2 2 , 3 3 и т. д. пропустим: они выражают то же самое число). Получится следующая нумерация положительных рациональных чисел: 1, 2, 1 2 , 3, 3 2 , 2 3 , 1 3 , 4, 4 3 , 3 4 , 1 4 , . . . Мы занумеровали, таким образом, все положительные рацио- нальные числа. А теперь уже легко понять, как нумеруются все (то есть положительные и отрицательные) рациональные числа. Для этого надо записать их отдельно в виде двух таблиц и числа од- ной таблицы нумеровать четными номерами, а второй — нечетными (и еще оставить один номер для нуля). Вообще, складывая счетное множество счетных множеств, мы снова получим счетное множество. Это доказывается тем же самым приемом нумерации по квадратам. Алгебраические числа Нам удалось занумеровать все рациональные числа. Но рацио- нальные числа получаются из натуральных чисел с помощью лишь одной операции — деления (и еще, быть может, изменения знака). А теперь мы добавим еще операцию извлечения корня и будем рас- сматривать все числа, которые можно получить из натуральных чисел с помощью этой операции и арифметических действий. Среди этих чисел будут такие, как 3 √ 2 + 1, 4 3 − √ 5 и даже такие «мон- стры», как 7 15 147 + √ 3 − 14 6 + √ 2 21 289 − 5 4 + √ 2 + 1 Возникает вопрос: можно ли занумеровать и множество всех та- ких чисел? Это кажется еще более трудным, чем занумеровать множество рациональных чисел. В самом деле, какому числу надо приписать меньший номер, 3 √ 2 или √ 3? Но оказывается, что и это множество счетно, то есть его элементы можно перенумеровать. Чтобы доказать это утверждение, отметим сначала, что каждое число рассматриваемого вида является корнем алгебраического 68 Глава II. В мире чудес бесконечного уравнения вида a 0 x n + a 1 x n−1 + . . . + a n = 0, (1) где a 0 = 0 и a 0 , . . . , a n — целые числа. Например, 3 7 — корень уравне- ния 7x − 3 = 0, 3 √ 5 — корень уравнения x 3 − 5 = 0, а 2 + 3 √ 3 — ко- рень уравнения x 6 − 6x 4 + 12x 2 − 11 = 0. Иногда бывает очень трудно написать уравнение, которому удовлетворяло бы число описанного выше вида, но тем не менее это всегда возможно. Попробуйте сами составить уравнение, которому удовлетворяло бы число √ 2 + 3 √ 3. Заметим, что далеко не все корни уравнений вида (1), где a 0 , . . . , a n — целые числа, выражаются через натуральные числа с помощью арифметических действий и операции извлечения корня. Например, корни уравнения x 5 − 3x + 3 = 0 нельзя выразить в таком виде, оно, как говорят, не решается в радикалах. Все числа, явля- ющиеся корнями уравнений вида (1) с целыми коэффициентами, называют алгебраическими числами. Таким образом, множество алгебраических чисел содержит в себе множество всех чисел, выра- жаемых через натуральные с помощью арифметических действий и извлечений корней. Поэтому, если нам удастся перенумеровать все алгебраические числа, то тем более мы решим задачу, поставленную в начале этого пункта. Но прежде чем нумеровать алгебраические числа, надо перену- меровать сами алгебраические уравнения вида (1). А тогда задача будет уже решена. Ведь каждое алгебраическое уравнение n-й степе- ни имеет не более n корней. Поэтому после того, как все уравнения с целыми коэффициентами будут перенумерованы, мы составим таб- лицу, в первой строке которой будут все различные корни первого уравнения, во второй — все различные корни второго уравнения, не попавшие в первую строку, в третьей — все различные корни тре- тьего уравнения, не попавшие в первую или вторую строку, и т. д. Таблица получится такая: a 1 → a 2 → . . . → a k → → b 1 → b 2 → . . . → b i → → c 1 → c 2 → . . . → c m → Здесь же показано, как можно перенумеровать все числа этой таб- лицы (стрелки показывают порядок нумерации). Алгебраические числа 69 Итак, займемся нумерацией множества алгебраических уравне- ний с целыми коэффициентами. Это можно сделать двумя способа- ми. Первый способ состоит в том, что каждому уравнению a 0 x n + a 1 x n−1 + . . . + a n = 0 ставится в соответствие его «высота», а именно число h = n + |a 0 | + |a 1 | + . . . + |a n |. Например, высота уравнения 2x 4 − 3x + 5 = 0 равна 4 + 2 + 3 + 5 = 14. Ясно, что число уравнений заданной высоты конечно. Например, высоту 2 имеют два уравнения: x = 0 и −x = 0, а высоту 3 име- ют шесть уравнений: x 2 = 0, −x 2 = 0, x + 1 = 0, x − 1 = 0, −x + 1 = 0 и −x − 1 = 0. А теперь будем нумеровать уравнения так: сначала перенумеруем все уравнения высоты 2 (уравнений высоты 1 нет во- обще), потом все уравнения высоты 3, затем все уравнения высоты 4 и т. д. Начало этой нумерации имеет следующий вид: 1 2 3 4 5 x = 0 −x = 0 x 2 = 0 −x 2 = 0 x + 1 = 0 6 7 8 9 10 x − 1 = 0 −x + 1 = 0 −x − 1 = 0 x 3 = 0 −x 3 = 0 В результате все уравнения окажутся занумерованнми, а тогда, как уже говорилось, нетрудно занумеровать и все алгебраические числа. Описанный способ нумерации уравнений имеет тот недоста- ток, что трудно сказать, какой именно номер получит данное урав- нение (хотя, конечно, эта задача и разрешима). Другой способ нуме- рации основан на той же идее, с помощью которой пробовал решить свою самую трудную задачу директор гостиницы. Напомним, что он предложил воспользоваться числами вида 2 n 3 m . Чтобы решить нашу задачу, придется использовать все простые числа. Читатель, конечно, помнит, что любое натуральное число единственным обра- зом разлагается на простые множители. Поступим следующим образом. Сначала перенумеруем все целые числа, как это было сделано на с. 66. Номер целого числа a обозначим через a. Каждому уравнению вида a 0 x n + . . . + a n = 0 70 Глава II. В мире чудес бесконечного (где, напомним, a 0 , . . . , a n — целые числа) поставим в соответствие число 2 a n 3 a n−1 . . . p a 0 n+1 (через p n+1 здесь обозначено (n + 1)-е простое число). Например, уравнению 3x 2 − 2 = 0 ставим в соответствие номер 2 4 3 1 5 5 = 150 000 (потому что целое число −2 имеет номер 4, нуль — номер 1, а целое число 3 — номер 5). Теперь каждое уравнение получило свой номер, причем разным уравнениям соответствуют разные номера (каждый номер N единственным образом разлагается на простые множители, то есть единственным образом задает числа a n , a n−1 , . . . , a 0 ; этим же числам соответствуют определенные целые числа a n , a n−1 , . . . , a 0 , а тем самым и определенное уравнение a 0 x n + . . . + a n = 0). Восьмерки на плоскости Методы, с помощью которых мы перенумеровали все алгебра- ические числа, применимы и в других случаях. Общая ситуация здесь такова. Пусть дано счетное множество счетных множеств A 1 , . . . , A n , . . . Составим всевозможные конечные «наборы» из эле- ментов этих множеств, причем в каждый набор входит не более одного элемента из каждого множества A k . Иными словами, каж- дый набор имеет вид (a m , . . . , a t ), где a m ∈ A m , . . . , a t ∈ A t (число элементов в наборе может быть разным в разных наборах, важно лишь, чтобы каждый набор состоял из конечного числа элементов). Тогда множество всех таких наборов счетно. Для доказательства этого утверждения достаточно поставить в соответствие каждому набору (a m , . . . , a t ) число N = p a m m . . . p a t t , где p m есть m-е по порядку простое число и т. д., a m — номер эле- мента a m в множестве A m и т. д. (при наших обозначениях значок m у элемента a m показывает, какому из множеств принадлежит этот элемент, а не номер этого элемента в множестве A m ). Те же рассуж- дения, что и в случае алгебраических уравнений, показывают, что при этом разным наборам будут соответствовать разные числа N , т. е. что все наборы окажутся занумерованными. А при желании можно сделать и иначе: поставить каждому набору (a m , . . . , a t ) в со- ответствие его «высоту» h = n + a m + . . . + a t и нумеровать сначала наборы высоты 2, потом наборы высоты 3 и т. д. Восьмерки на плоскости 71 Из доказанного утверждения вытекает, что если элементы неко- торого множества можно задать наборами вида (a 1 , . . . , a n ), где эле- менты a 1 принадлежат счетному множеству A 1 , элементы a 2 — счет- ному множеству A 2 и т. д., то само множество A или счетно, или конечно. В частности, счетно множество всех точек плоскости, обе координаты которых рациональны: такие точки задаются набором из двух рациональных чисел (r 1 ; r 2 ), а множество рациональных чи- сел счетно. Приведем более сложный пример доказательства счетности неко- торого множества. Пусть на плоскости изображены буквы T, причем никакие две буквы не имеют общих точек (размеры букв могут быть произвольными — рис. 24). Покажем, что это множество букв или счетно, или конечно. Для этого выберем на плоскости систему координат и поставим в соответствие каждой букве T треугольник, имеющий вершины с рациональными координатами и такой, что одна сторона тре- угольника пересекает «ножку» буквы T, а две другие — «боковые ветви» этой буквы (рис. 25). Геометрически очевидно, что если две буквы T соответствуют одному и тому же треугольнику, то они должны пересекаться — см. рис. 26 (впрочем, как это часто бывает в математике, строгое доказательство этого факта совсем не так просто). Поскольку по условию наши буквы попарно не имеют об- щих точек, то разным буквам соответствуют разные треугольники. Рис. 24 Рис. 25 Рис. 26 Поэтому нам осталось показать, что множество выбранных тре- угольников счетно или конечно. А для этого заметим, что каждый треугольник задается своими тремя вершинами A, B, C, а каждая вершина — своими координатами. Так как мы условились выбирать лишь вершины, обе координаты которых рациональны, то каждый 72 Глава II. В мире чудес бесконечного треугольник задается шестью рациональными числами — коорди- натами его вершин. А множество шестерок рациональных чисел счетно. Поэтому множество треугольников с «рациональными» вер- шинами счетно, а тогда множество треугольников, которые мы построили для наших букв, или счетно, или конечно. Значит, или счетно, или конечно и множество самих букв. Рис. 27 Точно так же доказывается, что если на плоскости нарисованы не пересекающиеся друг с другом восьмерки (рис. 27), то их множе- ство или счетно, или конечно. Неравные множества Мы уже выяснили, что значат слова «два множества имеют по- ровну элементов». А теперь выясним, что значит «одно множество имеет больше элементов, чем второе». Для конечных множеств это тоже можно выяснить, не прибегая к счету. Вспомним наш пример с танцплощадкой. Если после того, как заиграет оркестр и юноши пригласят девушек танцевать, некоторые нерасторопные юноши окажутся не у дел, то ясно, что юношей боль- ше. Если же часть девушек будет с грустью наблюдать за своими танцующими подругами, то ясно, что больше девушек. В этих случаях мы поступали так: устанавливали взаимно одно- значное соответствие между одним множеством и частью другого множества. Если это удавалось, то отсюда следовало, что второе множество содержит больше элементов, чем первое. Пользуясь этим методом, легко установить, например, что рыб в океане меньше, чем атомов на земном шаре (хотя оба эти множества и конечны, Неравные множества 73 Для него нет партнерши их вряд ли возможно пересчитать). Для этого достаточно каждой рыбе поставить в соответствие один атом, входящий в состав ее те- ла. Тем самым будет установлено взаимно однозначное соответствие между множеством всех рыб и частью множества всех атомов на зем- ном шаре. К сожалению, для бесконечных множеств так просто поступить нельзя. Ведь мы уже видели, что множество может иметь столько же элементов, сколько и его часть. Поэтому только из того факта, что множество A имеет столько же элементов, сколько и часть множе- ства B, еще нельзя заключить, что оно имеет меньше элементов, чем все множество B. Мы будем скромнее в выражениях и скажем, что если мно- жество A можно поставить во взаимно однозначное соответствие с частью множества B, то множество B имеет не меньше элементов, чем множество A. Можно доказать, что это соотношение обладает всеми хорошими свойствами неравенств: 1) Каждое множество A имеет не меньше элементов, чем само это множество. 2) Если множество A имеет не меньше элементов, чем B, а B — не меньше элементов, чем C, то A имеет не меньше элементов, чем C. 3) Если множество A имеет не меньше элементов, чем B, а B — не меньше элементов, чем A, то они имеют поровну элементов (то есть между элементами этих множеств можно установить вза- имно однозначное соответствие). 74 Глава II. В мире чудес бесконечного Из каждой рыбы по атому Может случиться, что множество B имеет не меньше элементов, чем множество A, но эти множества не эквивалентны. Иными сло- вами, может случиться, что есть взаимно однозначное соответствие между множеством A и частью B 1 множества B, но не существует взаимно однозначного соответствия между A и всем множеством B. Вот в этом случае мы и будем говорить, что B имеет больше эле- ментов, чем A. Счетное множество — самое маленькое из бесконечных Мы уже говорили, что любая бесконечная часть множества на- туральных чисел счетна. Это означает, что не может существовать бесконечное множество, мощность которого была бы меньше мощно- сти счетного множества. Докажем теперь, что в каждом бесконечном множестве есть счетное подмножество. Отсюда будет следовать, что Несчетные множества 75 мощность счетного множества не больше мощности любого беско- нечного множества, то есть что эта мощность — самая маленькая из бесконечных. Чтобы выбрать счетное подмножество из бесконечного множе- ства A, поступим так. Выберем один элемент x 1 — это можно сде- лать, так как множество A бесконечно и, во всяком случае, не пусто. Ясно, что после удаления элемента x 1 множество A не исчерпыва- ется, и мы сможем выбрать из него второй элемент x 2 . После этого выберем третий элемент x 3 и т. д. В результате мы извлечем из мно- жества A счетное подмножество занумерованных элементов X = {x 1 , x 2 , . . . , x n , . . . }. Немного усовершенствовав это доказательство, можно добиться, чтобы после удаления счетного подмножества осталось бесконеч- ное множество. Для этого надо после извлечения подмножества X вернуть обратно все элементы с четными номерами. В результате получится, что мы извлекли счетное подмножество Y = {x 1 , x 3 , x 5 , . . . }, а оставшееся множество еще содержит бесконечное множество эле- ментов: {x 2 , x 4 , x 6 , . . . , x 2n , . . . } (и, быть может, еще много других элементов). Нетрудно доказать следующие теоремы. Мощность бесконечного множества не изменяется от прибав- ления к нему счетного множества. Мощность несчетного множества не меняется от удаления из него счетного множества. Эти теоремы еще раз подтверждают, что счетные множества — самые малые из бесконечных множеств. Несчетные множества Все построенные до сих пор множества оказались счетными. Это наводит на мысль, а не являются ли вообще все бесконечные множе- ства счетными? Если бы это оказалось так, то жизнь математиков была бы легкой: все бесконечные множества имели бы поровну эле- ментов и не понадобился бы никакой анализ бесконечности. Но выяс- нилось, что дело обстоит куда сложнее, несчетные множества суще- ствуют, и притом с разными мощностями. Одно несчетное множество всем хорошо знакомо — это множество всех точек на прямой линии. 76 Глава II. В мире чудес бесконечного Но прежде чем говорить об этом множестве, мы расскажем о другом, тесно связанном с ним множестве A вариантов заполнения необык- новенной гостиницы. Заметим, что доказать несчетность какого-то множества вообще нелегко. Ведь доказать, что какое-то множество счетно, это значит просто придумать правило, по которому нумеруются его элементы. А доказать несчетность какого-то множества, это значит доказать, что такого правила нет и быть не может. Иными словами, какое бы правило мы ни придумали, всегда найдется незанумерованный эле- мент множества. Чтобы доказывать несчетность множеств, Кантор придумал очень остроумный способ, получивший название диаго- нального процесса (фактически мы с ним уже сталкивались на с. 13). Метод доказательства Кантора станет ясен из следующего рассказа Йона Тихого. Несостоявшаяся перепись До сих пор я рассказывал об удачах директора необыкновенной гостиницы: о том, как ему удалось вселить в заполненную гостиницу еще бесконечно много постояльцев, а потом даже жителей из беско- нечного множества столь же необычных гостиниц. Но был случай, когда и этого мага и чародея постигла неудача. Из треста космических гостиниц пришел приказ составить за- ранее все возможные варианты заполнения номеров. Эти варианты потребовали представить в виде таблицы, каждая строка которой изображала бы один из вариантов. При этом заполненные номера должны были изображаться единицами, а пустые нулями. Напри- мер вариант 101010101010. . . означал, что все нечетные номера заняты, а все четные пустые, ва- риант 11111111111. . . означал заполнение всей гостиницы, а вариант 000000000000. . . означал полный финансовый крах — все номера пустовали. Директор был перегружен работой и поэтому придумал простой выход из положения. Каждой дежурной по этажу было поручено со- ставить столько вариантов заполнения, сколько номеров было в ее |