Детская энциклопедия
Том 1. Земля. Том 4. Растения и животные. Том 7. Человек. Том 10. Зарубежные страны.
Том 2. Мир небесных тел. Числа и фигуры. Том 5. Техника и производство. Том 8. Из истории человеческого общества. Том 11. Язык. Художественная литература.
Том 3. Вещество и энергия. Том 6. Сельское хозяйство. Том 9. Наша советская Родина. Том 12. Искусство.

Но теперь возникает самый главный, основ­ной для всей теории множеств вопрос. Всегда ли можно занумеровать элементы бесконечного множества натуральными числами так, чтобы каждый элемент данного множества получил определенный номер? Другими словами, можно ли установить взаимно-однозначное соответ­ствие между произвольным бесконечным множеством и множеством всех натураль­ных чисел?

Оказывается, ответ на этот вопрос отри­цательный, и мы постараемся убедиться в этом. Но сначала несколько подготовимся. Прежде всего установим название для тех множеств, которые могут быть поставлены во взаимно-­однозначное соответствие с множеством всех натуральных чисел. Эти множества называются счетными. Это название естественно: счет­ное множество — это такое множество, которое может быть сосчитано посредством натуральных чисел. Наша задача — показать, что сущест­вуют несчетные множества, т. е. такие, которые не могут быть поставлены во взаимно-одно­значное соответствие с множеством всех нату­ральных чисел.

Множество всех рациональных чисел счетно

В поисках несчетного множества обратимся к множеству всех рациональных чисел (чита­тель, конечно, помнит, что рациональными называются все целые и все дробные числа). Посмотрим, можно ли занумеровать все рацио­нальные числа с помощью натуральных. Для простоты рассмотрим сначала все положитель­ные рациональные числа и попробуем их как-нибудь занумеровать. Сразу же сталкиваемся с трудностью: среди положительных рацио­нальных чисел заведомо нет наименьшего чис­ла, каким является единица среди натураль­ных чисел: ведь каково бы ни было положительное рациональное число r, число 1/2r также

является положительным рациональным чис­лом, и оно меньше, чем r. Предположим, мы обойдем эту трудность, начав счет с какого-нибудь рационального числа r1, которое со­гласимся считать первым. Но тогда на следую­щем этапе возникает такая трудность: какое рациональное число считать вторым, т. е. не­посредственно следующим в порядке нашего счета за числом r1? Дело в том, что, какое бы рациональное число r2>r1 мы ни взяли, имеются рациональные числа большие, чем r1,

и меньшие, чем r2, и таких бесконечное мно­жество, например числа:

r3=1/2 (r1+r2), r4=1/2(r1+r3),...

Таким образом, среди всех рациональных чисел, больших, чем выбранное нами число r1, нет наименьшего. Какое же объявить пер­вым из следующих за r1? Но возникшая труд­ность — кажущаяся. Она показывает только, что невозможно занумеровать рациональные числа с помощью натуральных чисел таким образом, чтобы при этой нумерации возраста­ющим номерам соответствовали возрастающие числа. Придется попытаться занумеровать ра­циональные числа как-нибудь иначе, не стре­мясь к тому, чтобы число r2, первое после r, в порядке нашего счета, было и первым по величине, т. е. наименьшим из всех следую­щих за r1. А тогда нужная нам нумерация находится очень легко.

В самом деле, каждое положительное ра­циональное число однозначно записывается

в виде несократимой дроби p/q (целое число n будем при этом записывать в виде дроби n/1 и также считать ее несократимой). Назовем высотой дроби — натуральное число q+р.

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

Посмотрим, сколько приходится рациональ­ных чисел на каждую данную высоту. Высоту

1 не имеет ни одно положительное рациональ­ное число (потому что, записывая рациональное

число в виде несократимой дроби p/q, видим,

что ее высота равна натуральному числу р+q, а так как pі1, qі1, то р+qі2). Высоту

2 имеет, очевидно, единственное рациональное

число 1/1=1.

Высоту 3 имеют дроби 1/2 и 2/1, т. е. рациональные числа 1/2 и 2.

Высоту 4 имеют дроби 1/3, 2/2, 3/1.

Среди них оставляем лишь несократимые

1/3 и 3/1. Итак, высоту 4 имеют рациональные

числа 1/3 и 3.

Высоту 5 имеют дроби 1/4, 2/3,3/2,4/1, среди

378