ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 16.12.2020
Просмотров: 2177
Скачиваний: 53
Счетные множества
65
«Я не вижу возможности никакого другого решения, как при-
знать, что бесконечно количество чисел вообще, бесконечно число
квадратов, бесконечно и число корней. Нельзя сказать, что чис-
ло квадратов меньше количества всех чисел, а последнее больше:
в конечном выводе свойства равенства, а также большей и меньшей
величины не имеют места там, где дело идет о бесконечности, и при-
менимы только к конечным количествам».
Мы видим, что Галилей, по сути дела, владел идеей взаимно
однозначного соответствия и видел, что такое соответствие можно
установить между множеством всех натуральных чисел и множе-
ством квадратов, а потому эти множества можно считать имеющими
одинаковое количество элементов. Понимал он и то, что для беско-
нечных множеств часть может быть равной целому. Но отсюда он
сделал неверный вывод, что все бесконечности одинаковы: он имел
дело лишь с бесконечными подмножествами натурального ряда, а их
можно перенумеровать.
Галилей не мог себе представить, что множество всех точек отрез-
ка перенумеровать нельзя (это у нас вскоре будет показано). Подобно
атомистам древности он полагал, что отрезок складывается из под-
дающейся пересчету бесконечной совокупности атомов.
F
Счетные множества
Все множества, которые имеют столько же элементов, сколь-
ко имеет множество натуральных чисел, называют
счетными
.
Иными словами, множество называется счетным, если оно бес-
конечно, но его элементы можно перенумеровать натуральными
номерами. Например, множество четных чисел, множество нечетных
чисел, множество простых чисел, да и вообще любая бесконечная
часть множества натуральных чисел являются счетными множе-
ствами.
Иногда для того, чтобы установить счетность того или иного
множества, надо проявить изобретательность. Возьмем, например,
множество всех целых чисел (как положительных, так и отрица-
тельных):
. . . ,
−
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
, . . .
Мы занумеровали, таким образом, все положительные рацио-
нальные числа. А теперь уже легко понять, как нумеруются все
(то есть положительные и отрицательные) рациональные числа.
Для этого надо записать их отдельно в виде двух таблиц и числа од-
ной таблицы нумеровать четными номерами, а второй — нечетными
(и еще оставить один номер для нуля).
Вообще, складывая счетное множество счетных множеств, мы
снова получим счетное множество. Это доказывается тем же самым
приемом нумерации по квадратам.
Алгебраические числа
F
Нам удалось занумеровать все рациональные числа. Но рацио-
нальные числа получаются из натуральных чисел с помощью лишь
одной операции — деления (и еще, быть может, изменения знака).
А теперь мы добавим еще операцию извлечения корня и будем рас-
сматривать все числа, которые можно получить из натуральных
чисел с помощью этой операции и арифметических действий. Среди
этих чисел будут такие, как
3
√
2 + 1
,
4
p
3
−
√
5
и даже такие «мон-
стры», как
7
v
u
u
t
15
p
147 +
√
3
−
14
p
6 +
√
2
21
q
289
−
5
p
4 +
√
2 + 1
.
Возникает вопрос: можно ли занумеровать и множество всех та-
ких чисел? Это кажется еще более трудным, чем занумеровать
множество рациональных чисел. В самом деле, какому числу надо
приписать меньший номер,
3
√
2
или
√
3
? Но оказывается, что и это
множество счетно, то есть его элементы можно перенумеровать.
Чтобы доказать это утверждение, отметим сначала, что каждое
число рассматриваемого вида является корнем алгебраического
68
Глава II. В мире чудес бесконечного
уравнения вида
a
0
x
n
+
a
1
x
n
−
1
+
. . .
+
a
n
= 0
,
(1)
где
a
0
6
= 0
и
a
0
, . . . , a
n
— целые числа. Например,
3
7
— корень уравне-
ния
7
x
−
3 = 0
,
3
√
5
— корень уравнения
x
3
−
5 = 0
, а
p
2 +
3
√
3
— ко-
рень уравнения
x
6
−
6
x
4
+ 12
x
2
−
11 = 0
. Иногда бывает очень трудно
написать уравнение, которому удовлетворяло бы число описанного
выше вида, но тем не менее это всегда возможно. Попробуйте сами
составить уравнение, которому удовлетворяло бы число
√
2 +
3
√
3
.
Заметим, что далеко не все корни уравнений вида (1), где
a
0
, . . . , a
n
— целые числа, выражаются через натуральные числа
с помощью арифметических действий и операции извлечения корня.
Например, корни уравнения
x
5
−
3
x
+ 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
|
.
Например, высота уравнения
2
x
4
−
3
x
+ 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