Расин, Алгебра

Пусть f – отображение из N6m в N6n, причем m > n. Тогда отображение f не является инъективным.

Лемма 2. Пусть X – непустое множество, и для некоторого натурального n существует инъективное отображение f из N6n в X. Если никакое отображение из N6n+1 в X не является инъективным, то f – биективное отображение.

Д о к а з а т е л ь с т в о. Предположим, что заключение леммы не верно. Это значит, что данное инъективное отображение f не является сюръективным. Тогда существует элемент x X, не принадлежащий множеству значений отображения f . Определим отображение g из N6n+1 в X:

Легко видеть, что g инъективное отображение из N6n+1 в X. Существование такого отображения противоречит условию леммы.

Лемма 3. Предположим, что для некоторого n N существуют инъективные отображения

f1 : N6n −→ X и f2 : N6n+1 −→ X.

Тогда найдется такое инъективное отображение

h : N6n+1 −→ X,

что h(k) = f1(k) при любом k 6 n.

Д о к а з а т е л ь с т в о. Рассмотрим множества значений E(f1), E(f2) отображений f1 и f2 соответственно. Проверим, что включение

невозможно. Рассуждая “от противного”, допустим, что это включение выполнено. Поскольку f1 – инъективное отображение, из предложения 5.4 следует существование биективного отображения g из E(f1) на N6n. Из включения (4) вытекает, что определена

90

композиция g◦f2, отображающая N6n+1 в N6n. В силу п. (a) предложения 5.3 получаем, что отображение g◦f2 инъективно. Однако лемма 1 утверждает, что инъективного отображения из N6n+1 в N6n не существует.

Итак, включение (4) не выполняется. Отсюда следует, что найдется такой элемент x X, что x 6E(f1). Определим отображе-

Ясно, что h – инъективное отображение из N6n+1 в X и h(k) = = f1(k) для любого k 6 n.

Лемма 4. Пусть для любого n N существует инъективное отображение из N6n в множество X. Тогда существует инъективное отображение из N в X.

До к а з а т е л ь с т в о. Проверим сначала, что для каждого n

N можно определить инъективное отображение

для любого k 6 n. Существование такой последовательности отображений можно доказать методом математической индукции.

Если n = 1, то достаточно выбрать произвольный элемент xX и положить f1(1) = x.

Пусть n > 1, и отображение fn определено. Поскольку существует инъективное отображение из N6n+1 в X, применение леммы 3 показывает, что найдется инъективное отображение h из N6n+1 в X, обладающее свойством: h(k) = fn(k) при любом k 6 n. Ясно, что fn+1 = h.

Из доказанного свойства такой последовательности отображений легко получается следующее свойство: если m < n, то fm(m) = = fn(m).

Построим теперь отображение f : N −→ X, положив f (n) = = fn(n) для любого n N. Легко убедиться в том, что f инъективно. В самом деле, пусть m, n – различные натуральные числа.

91

Без ограничения общности можно считать, что m < n. Имеем f (n) = fn(n), f (m) = fm(m) = fn(m). Так как fn – инъективное отображение, имеем fn(n) 6= fn(m), откуда f (n) 6= f (m). Стало быть, f инъективно.

Пусть X – произвольное непустое множество. Тогда выполнено

вточности одно из двух утверждений:

1)для любого натурального n существует инъективное отображение из N6n в X;

2)существует наибольшее натуральное число n, для которого множество N6n инъективно отображается в X.

Поэтому из лемм 2, 4 вытекает

Теорема 5.1. Пусть X – непустое множество. Тогда выполняется одна из двух возможностей:

(a)существует инъективное отображение f из N в X.

(b)существует биективное отображение f из N6n на X при некотором n N;

Если реализуется возможность (a), то множество X называется бесконечным; если же имеет место возможность (b), то X называется конечным. В том случае, когда X – конечное множество, определено число |X|, называемое числом элементов множества X; а именно, если |X| = n, то существует биекция из N6n на X. Заметим, что если X – конечное множество и |X| = n, то существует биективное отображение g : X −→ N6n.

Поскольку N6n N при любом n, из определений конечного и бесконечного множеств вытекает

Предложение 5.13. Если X конечное, а Y – бесконечное множество, то существует инъективное отображение g : X −→ Y.

Давая определения конечных и бесконечных множеств, мы использовали в качестве “эталонных” множество N и его подмножества N6n, n N. Оказывается, конечные и бесконечные множества можно охарактеризовать без использования множества N и его подмножеств.

92

Теорема 5.2. Множество X бесконечно тогда и только тогда, когда существует биективное отображение f множества X на его собственное подмножество Y .

Д о к а з а т е л ь с т в о. Пусть X бесконечно. Тогда существует инъективное отображение g из N в X. Множество значений отображения g можно представить в виде

E(g) = {g(i) | i N}.

Рассмотрим множество

Y0 = {g(2i) | i N}.

Ясно, что Y0 – собственное подмножество E(g). Поэтому множество Y = (X \ E(g)) Y0 является собственным подмножеством множества X. Определим отображение f из X в Y :

Проверим, что f – биективное отображение. Пусть x1, x2 X и x1 6= x2. Если x1, x2 X \ E(g), то

f (x1) = x1 6= x2 = f (x2).

Если x1, x2 E(g), то x1 = g(i1), x2 = g(i2). Из неравенства x1 6= x2, очевидно, вытекает неравенство i1 6= i2. Поэтому

f (x1) = g(2i1) 6= g(2i2) = f (x2).

Если же x1 X \ E(g), x2 E(g), то f (x1) = x1 X \ E(g), f (x2) E(g). Неравенство f (x1) 6= f (x2) следует из того, что множества X \ E(g) и E(g) не имеют общих элементов. Итак, доказано, что при любых x1, x2 X из x1 6= x2 следует f (x1) 6= 6= f (x2). Стало быть, f – инъективное отображение.

Осталось проверить, что f сюръективно. Пусть y Y . Возможны два случая: 1) y X \ E(g), 2) y Y0. В первом случае, положив x = y, получим y = f (x). Если же имеет место второй случай, то y = g(2i) для некоторого i N. Тогда y = f (x), где

93

x = g(i). Мы проверили, что любой элемент из Y является образом некоторого элемента из X; следовательно, f сюръективно.

Проверим обратное утверждение. Пусть Y – собственное подмножество из X, и отображение f : X −→ Y биективно. Возьмем произвольный элемент x0 X \ Y . Ясно, что x0 не содержится в множестве значений отображения f , т. е. для любого x X выполнено неравенство f (x) 6= x0. Для произвольного натурального n рассмотрим элемент xn = f n(x0). Проверим, что xk 6= xm, если k, m N и k 6= m. Предположим, что это утверждение не выполняется, т. е. xk = xm для некоторых различных k и m. Пусть для определенности k < m и s = m − k. Учитывая определение элементов xk, xm, имеем

f k(x0) = f m(x0) = f k+s(x0) = f k(f s(x0)).

Из инъективности отображения f вытекает инъективность отображения f k. Поэтому из равенства f k(x0) = f k(f s(x0)) следует

равенство

x0 = f s(x0).

Последнее равенство показывает, в частности, что x0 лежит в образе отображения f . Это противоречит выбору элемента x0.

Определим отображение

g : N −→ X

при помощи правила g(n) = xn. Доказанное выше утверждение означает, что отображение g инъективно. Стало быть, X – бесконечное множество.

Теорема 5.3. Множество X конечно тогда и только тогда, когда любое инъективное преобразование f множества X является биективным.

Эта теорема непосредственно вытекает из теорем 5.2 и 5.1. В самом деле, теорему 5.1 можно переформулировать следующим образом: множество конечно тогда и только тогда, когда оно не является бесконечным. Это означает, что утверждение “X – бесконечное множество” является отрицанием утверждения “X – конечное множество”. Нетрудно понять, что для утверждения “существует инъективное отображение множества X на собственное

94

подмножество” отрицанием служит утверждение “любое инъективное преобразование f множества X является биективным”.

Понятие бесконечного множества впервые встретилось в разделе 3.7 при обсуждении теоремы Евклида о множестве всех простых чисел. Там же было высказано предположение, что для произвольного множества натуральных чисел свойства “быть бесконечным” и “быть неограниченным сверху” равносильны. Теперь мы в состоянии доказать, что это действительно так.

Предложение 5.14. Если множество натуральных чисел бесконечно, то оно неограничено сверху.

Д о к а з а т е л ь с т в о. Пусть M – бесконечное подмножество из N. Будем рассуждать “от противного”. Предположим, что M ограничено сверху. Это значит, что найдется такое натуральное число n, что M N6n. Поскольку M бесконечно, существует инъективное отображение f : N −→ M . Ясно, что f является инъективным отображением из N в N6n. Так как N6n+1 N, существование такого отображения f противоречит лемме 1.

Предложение 5.15. Если множество натуральных чисел неограничено сверху, то оно бесконечно.

Пусть M не является ограниченным сверху. Построим отображение f из N в M следующим образом. Из теоремы 2.1 следует, что M имеет наименьший элемент m1. Положим

f (1) = m1.

Предположим теперь, что для некоторого натурального n элементы f (1), f (2), . . . , f (n) уже определены. Рассмотрим множество

Mn = M \ {f (1), f (2), . . . , f (n)}.

Поскольку M неограничено сверху, множество Mn непусто. Поэтому оно имеет наименьший элемент mn+1. По определению полагаем

f (n + 1) = mn+1.

При помощи метода математической индукции легко придти к выводу, что описанная процедура определит отображение f на всем

95

множестве N, причем такое f , очевидным образом, инъективно. Стало быть, построено инъективное отображение из N в M . Поэтому M – бесконечное множество.

Из предложений 5.14 и 5.15 очевидным образом вытекает следующее утверждение.

Предложение 5.16. Множество натуральных чисел ограничено сверху тогда и только тогда, когда оно конечно.

Отображение f , построенное при доказательстве предложения 5.15, является, на самом деле биекцией. Проверим справедливость этого утверждения. В самом деле, пусть E(f ) M , т. е. E(f )

– собственное подмножество из M . Тогда M \ E(f ) – непустое множество натуральных чисел, и потому это множество содержит наименьший элемент m. Рассмотрим множество E(f ) ∩ N<m. Это множество непусто, поскольку ему принадлежит, например, f (1), являющееся наименьшим элементом множества M . Кроме того, это множество ограничено сверху; следовательно, в силу предложения 5.16 оно конечно. Поэтому существует такое k, что

E(f ) ∩ N<m = {f (1), f (2), . . . , f (k)}.

Из определения числа m вытекает, что m – наименьший элемент множества M \ {f (1), f (2), . . . , f (k)}, и потому m = f (k + 1), т. е.

mE(f ). Последнее включение противоречит выбору числа m. Эти рассуждения показывают, что справедливо

Предложение 5.17. Если множество M натуральных чисел бесконечно, то существует биективное отображение f из N на M .

5.6. Счетные множества

О п р е д е л е н и е. Множество X называется счетным, если существует биективное отображение f : N −→ X.

В том случае, когда множество X счетно, существует биективное отображение g из X на N; в качестве g можно взять, например, отображение, обратное к f . Нетрудно видеть, что счетность множества X означает возможность занумеровать элементы этого

96

множества, т. е. включить все элементы этого множества в бесконечную последовательность без повторяющихся членов.

Заметим также, что если X, Y – счетные множества, то существует биективное отображение из X на Y . В самом деле, существуют биективные отображения

f : X −→ N, g : N −→ Y.

Ясно, что композиция g◦f – биективное отображение из X на Y . В этом разделе мы изучим свойства счетных множеств. Снача-

ла приведем несколько примеров счетных множеств. 1. Множество E четных натуральных чисел счетно.

В самом деле, рассмотрим отображение f : N −→ E, определенное правилом f (n) = 2n. Ясно, что f – биективное отображение.

2. Множество O нечетных натуральных чисел счетно.

Для проверки этого утверждения достаточно рассмотреть отображение g : N −→ O, заданное правилом g(n) = 2n − 1.

3. Множество Z всех целых чисел счетно.

Рассмотрим отображение h : N −→ Z, заданное следующим

образом:

h(n) =

n/2, если n = 2k,

(1 − n)/2, если n = 2k − 1.

Читатель без труда проверит, что h – биективное отображение.

Предложение 5.18. Всякое бесконечное X множество содержит счетное подмножество.

Д о к а з а т е л ь с т в о. Поскольку X бесконечно, существует инъективное отображение

f : N −→ X.

Пусть Y = E(f ). Тогда Y счетно и Y X.

Предложение 5.19. Всякое бесконечное подмножество счетного множества само счетно.

97

Д о к а з а т е л ь с т в о. Пусть Y – бесконечное подмножество счетного множества X. Как мы знаем, существует биективное отображение

g : X −→ N.

Обозначим множество g(Y ) через M и рассмотрим отображение

h : Y −→ M,

определенное правилом h(i) = g(i) для любого i Y . Ясно, h – является биективным отображением, и потому из бесконечности множества Y следует бесконечность множества M . Следовательно, M – бесконечное подмножество из N. Применение предложения 5.17 показывает, что M – счетное множество. Поскольку h−1 является биективным отображением M на Y , получаем, что Y – также счетное множество.

Из предложения 5.19 вытекает следующее утверждение.

Предложение 5.20. Пусть X бесконечное, а Y – счетное множество. Если существует инъективное отображение f : X −→ Y , то X – счетное множество.

Д о к а з а т е л ь с т в о. Пусть Z = f (X). Тогда Z – бесконечное подмножество счетного множества Y , и потому Z счетно. Легко понять, что существует биективное отображение из Z на X. Следовательно, X – счетное множество.

Предложение 5.20 в дальнейшем часто будет использоваться для доказательства счетности множеств.

Предложение 5.21. Объединение двух счетных множеств счетно.

Д о к а з а т е л ь с т в о. Пусть A1, A2 – счетные множества. Справедливо равенство

A1 A2 = A1 (A2 \ A1).

Заметим, что множество A2 \A1 является подмножеством счетного множества A2, и потому либо конечно, либо счетно. Поскольку

98

множество E четных натуральных чисел и множество O нечетных натуральных чисел являются счетными, существуют инъективные отображения

f1 : A1 −→ E, f2 : A2 \ A1 −→ O.

Определим отображение

f : A1 A2 −→ N

Легко проверяется, что f – инъективное отображение. Так как множество A1 A2, очевидно, является бесконечным, из предложения 5.20 следует, что это множество счетно.

Теорема 5.4. Множество N × N является счетным.

Д о к а з а т е л ь с т в о. Построим инъективное отображение из N × N в N. Для этого воспользуемся тем, что множество P всех простых чисел является счетным. Пусть P = {pi | i N}. Рассмотрим произвольную упорядоченную пару (m, n) N × N и

положим

f (m, n) = pnm.

Легко проверяется, что из равенства f (i, j) = f (m, n) следует равенство (i, j) = (m, n). В самом деле, пусть pji = pnm. Из теоремы о каноническом разложении натуральных чисел вытекает, что i = m и j = n, т. е. (i, j) = (m, n). Таким образом, отображение f из N × N в N инъективно. Поскольку N × N бесконечно, оно является счетным.

Из теоремы 5.4 вытекает

Теорема 5.5. Пусть X, Y – счетные множества. Тогда множество X × Y является счетным.

Д о к а з а т е л ь с т в о. Обозначим через f , g биективные отображения из X и Y на N. Поставим в соответствие каждому элементу (x, y) X × Y элемент (f (x), g(y)) N × N. Ясно, что указанное правило определяет биективное отображение из X × Y на N × N.

99