и нумеровать по столбцам. При этом 0 получит № 1, -1 — № 2, 1 — № 3, -2 — № 4 и т. д. Иными словами, все положительные числа и нуль нумеруются нечетными числами, а все отрицательные целые числа — четными. Это похоже на то, как директор гостиницы поместил всех филателистов в гостиницу, заполненную космозоологами.
Но если в то, что множество всех целых чисел счетно, легко поверить, то в счетность множества рациональных чисел поверить труднее. Ведь рациональные числа расположены очень густо — между любыми двумя рациональными числами найдется еще бесконечно много рациональных чисел. Поэтому совершенно непонятно, как их нумеровать; кажется, что между любыми двумя числами надо перенумеровать еще бесконечно много чисел и этот процесс никогда не закончится. И действительно, занумеровать рациональные числа в порядке возрастания их величины невозможно.
Однако если отказаться от расположения рациональных чисел в порядке возрастания, то занумеровать их все же удается. Сделаем так: выпишем сначала все положительные дроби со знаменателем 1, потом все положительные дроби со знаменателем 2, потом со знаменателем 3 и т. д. У нас получится таблица следующего вида:
Ясно, что в этой таблице мы встретим любое положительное рациональное число, и притом не один раз. Например, число 3 встретится и в виде дроби 3/1, и в виде дроби 6/2, и в виде дроби 9/3.
Теперь приступим к нумерации. Для этого вспомним последний подвиг директора необыкновенной гостиницы, который расселил в ней жителей из бесконечного множества таких же гостиниц. Он тогда воспользовался нумерацией по квадратам. Точно так же поступим и мы, только с тем осложнением, что некоторые дроби будем пропускать (например, так как 1/1 получила уже № 1, то дроби 2/2, 3/3 и т. д. пропустим: они выражают то же самое число). Получится следующая нумерация положительных рациональных чисел:
Мы занумеровали, таким образом, все положительные рациональные числа. А теперь уже легко понять, как нумеруются все (то есть положительные и отрицательные) рациональные числа. Для этого надо записать их отдельно в виде двух таблиц и числа одной таблицы нумеровать четными номерами, а второй — нечетными (и еще оставить один номер для нуля).
Вообще, складывая счетное множество счетных множеств, мы снова получим счетное множество. Это доказывается тем же самым приемом нумерации по квадратам.
Алгебраические числа.
Нам удалось занумеровать все рациональные числа. Но рациональные числа получаются из натуральных чисел с помощью лишь одной операции — деления (и еще, быть может, изменения знака). А теперь мы добавим еще операцию извлечения корня и будем рассматривать все числа, которые можно получить из натуральных чисел с помощью этой операции и арифметических действий. Среди этих чисел будут такие, как и даже такие "монстры", как
Возникает вопрос: можно ли занумеровать множество всех таких чисел? Это кажется еще более трудным, чем занумеровать множество рациональных чисел. В самом деле, какому числу надо приписать меньший номер: или ? Но оказывается, что и это множество счетно, то есть его элементы можно перенумеровать.
Чтобы доказать это утверждение, отметим сначала, что каждое число рассматриваемого вида является корнем алгебраического уравнения вида
где a0≠0 и a0 , ..., an — целые числа. Например, 3/7 — корень уравнения 7x — 3 = 0, — корень уравнения x3 — 5 = 0, а — корень уравнения x6 — 6x4 + 12x2 — 11 = 0. Иногда бывает очень трудно написать уравнение, которому удовлетворяло бы число описанного выше вида, но тем не менее это всегда возможно.
Заметим, что далеко не все корни уравнений вида (1), где a0,..., an — целые числа, выражаются через натуральные числа с помощью арифметических действий и операции извлечения корня. Например, корни уравнения
x5 — 3x + 3 = 0
нельзя выразить в таком виде, оно, как говорят, не решается в радикалах. Все числа, являющиеся корнями уравнений вида (1) с целыми коэффициентами, называют алгебраическими числами. Таким образом, множество алгебраических чисел содержит в себе множество всех чисел, выражаемых через натуральные с помощью арифметических действий и извлечений корней. Поэтому если нам удастся перенумеровать все алгебраические числа, то тем более мы решим задачу, поставленную в начале этого пункта.
Но прежде чем нумеровать алгебраические числа, надо перенумеровать сами алгебраические уравнения вида (1), А тогда задача будет уже решена. Ведь каждое алгебраическое уравнение n-й степени имеет не более n корней. Поэтому после того, как все уравнения с целыми коэффициентами будут перенумерованы, мы составим таблицу, в первой строке которой будут все различные корни первого уравнения, во второй — все различные корни второго уравнения, не попавшие в первую строку, в третьей- все различные корни третьего уравнения, не попавшие в первую или вторую строку, и т. д. Таблица получится такая:
Теперь ясно, как нумеруются все числа этой таблицы (порядок нумерации указан стрелками).
Итак, займемся нумерацией множества алгебраических уравнений с целыми коэффициентами. Для этого применим идею, с помощью которой пробовал решить самую трудную задачу директор гостиницы. Напомним, что он предложил воспользоваться числами вида 2m3n. Чтобы решить нашу задачу, придется использовать все простые числа. Читатель, конечно, помнит, что любое натуральное число единственным образом представляется в виде произведения простых множителей.
Поступим следующим образом. Сначала перенумеруем все целые числа (это мы уже умеем делать). Номер целого числа a обозначим через a. Каждому уравнению вида a0xn + a1xn-1 + ... + an = 0 (где, напомним, a0,..., an — целые числа) поставим в соответствие число
(через pn+1 здесь обозначено (n-+1)-е простое число). Например, уравнению 3x2 — 2 = 0 ставим в соответствие номер 243156 = 150 000, потому что целое число -2 имеет номер 4, нуль — номер 1, а целое число 3 — номер 5. Теперь каждое уравнение получило свой номер, причем разным уравнениям соответствуют разные номера (каждый номер N единственным образом разлагается на простые множители, то есть единственным образом задает числа an, an+1,..., a0; этим же числам соответствуют определенные целые числа an, an-1, ..., a0, а тем самым и определенное уравнение a0xn+ ... + an = 0).
Неравные множества.
Мы уже выяснили, что значат слова "два множества имеют поровну элементов".
А теперь выясним, что значит "одно множество имеет больше элементов, чем второе". Для конечных множеств это тоже можно выяснить, не прибегая к счету. Вспомним пример с танцплощадкой.
Если после того, как заиграет оркестр и юноши пригласят девушек танцевать, некоторые нерасторопные юноши окажутся не у дел, то ясно, что юношей больше. Если же часть девушек будет с грустью наблюдать за своими танцующими подругами, то ясно, что больше девушек.
В этих случаях мы поступали так: устанавливали взаимно однозначное соответствие между одним множеством и частью другого множества. Если это удавалось, то отсюда следовало, что второе множество содержит больше элементов, чем первое. Пользуясь этим методом, легко установить, например, что рыб в океане меньше, чем атомов на земном шаре (хотя оба эти множества и конечны, их вряд ли возможно пересчитать). Для этого достаточно каждой рыбе поставить в соответствие один атом, входящий в состав ее тела. Тем самым будет установлено взаимно однозначное соответствие между множеством всех рыб и частью множества всех атомов на земном шаре.
К сожалению, для бесконечных множеств так просто поступить нельзя. Ведь мы уже видели, что множество может иметь столько же элементов, сколько и его часть. Поэтому только из того, что множество A имеет столько же элементов, сколько часть множества B, еще нельзя заключить, что оно имеет меньше элементов, чем все множество B.
Мы скажем, что если A можно поставить во взаимно однозначное соответствие с частью множества B, то множество B имеет не меньше элементов, чем множество A. Можно доказать, что это отношение обладает всеми свойствами неравенств:
1. каждое множество имеет не меньше элементов, чем оно само;
2. если в одном множестве не меньше элементов, чем во втором, а во втором — не меньше элементов, чем в третьем, то первое множество имеет не меньше элементов, чем третье;
3. если каждое из двух множеств имеет не меньше элементов, чем другое, то оба имеют поровну элементов (то есть между элементами этих множеств можно установить взаимно однозначное соответствие).
Первое свойство вытекает из того, что, ставя в соответствие каждому элементу множества A сам этот элемент, получаем взаимно однозначное отображение A на себя. Прозрачен и смысл второго свойства: если A можно взаимно однозначно отобразить на часть множества B, а B — на часть множества C, то существует взаимно однозначное отображение A на часть C.
А вот третье свойство при всей простоте его формулировки означает довольно сложное утверждение: если можно взаимно однозначно отобразить множество A на часть множества B, а множество B на часть множества A, то существует и взаимно однозначное отображение всего множества A на B. То, что дело обстоит таким образом, с самого начала подозревал Г. Кантор. Однако ему в течение долгого времени не удавалось найти доказательства этого утверждения. О своих затруднениях он рассказал в 1897 г. на ле