B. A Гордин

Сколько на свете дробей и как считать бесконечные множества.II

Сколько на свете дробей и как считать бесконечные множества.II

1  Последовательность отображений

Если заданы отображения f: A® B и g: B ® C, то можно построить новое отображение g°f: A ® C, последовательно перевод произвольный элемент a О A в f(a), а затем f(a) в g(f(a)). Такое отображение называется композицией или суперпозицией или произведением отображений f и g.
Например, отображение sinx2 переводит вещественную ось в отрезок [-1, 1], а отображение (sinx)2 — в отрезок [0, 1]. Оба отображения не являются взаимнооднозначными.
Задача 1. Верно ли, что отображение g°f взаимно-однозначно, если и только если и f, и g взаимно-однозначны ?
Возможен случай, когда отображение осуществляется в то же множество, т.е. f: A® A. Такое отображение будем называть преобразованием множества A. Возможно осуществить одно и то же преобразование много раз: x ® f(f(ј f(x)ј))ј). Этот процесс называется итерацией отображения f.
Задача 2. Оцените образ преобразования x ® f(f(ј f(x)ј) если f(x) = sinx или f(x) = sin2 x, а число итераций, стремится к бесконечности.
Преобразование множества чисел, которое ставит в соответствие каждому числу его целую часть x® [x], не является взаимнооднозначным. Действительно, и 1/2, и 1/3 переходят при этом преобразовании в ноль. Аналогичная отображение для дробной части: x® x - [x], также не является (докажите !) взаимно-однозначным.
Заметим, что повторное применение этих преобразований совпадает с однократным f(f(x)) є f(x). А если применить поочереди преобразования целой части и дробной части (в любом порядке), то все числа перейдут в одно единственное — ноль.
Если преобразование f является взаимно-однозначным отображением, то оно называется перестановкой множества A. Например, тождественное отображение I: x® x является перестановкой.
Задача 3. Докажите, что произведение любых перестановок есть снова перестановка.
Задача 4. Докажите, что для любой перестановки f существует левое обратное и правое обратное отображения, т.е. такие перестановки g и h, что g(f(x)) є I,  f(h(x)) є I. Обязаны ли они совпадать?
Перестановку f, при которой f(f(x))=x при всех x О A, можно интерпретировать как квадратный корень из тождественного отображения. Таким, например, является отображение целых чисел x® -x.
Возможны также отображения, при которых квадрат отображения не совпадает с тождественным, а какая-то более высокая степень — совпадает:

f(f(јf(x)ј)) є x.                                                            
(1)
Например, преобразование окружности — поворот на угол p/10 обладает этим свойством.
Задача 5. Докажите, что поворот на угол j обладает этим свойством, если и только если

j =  m p

k
,    где  mk О Z,  k 0.
Пусть множество A состоит из n элементов. Докажем, что люба перестановка в некоторой (мы оценим, какой !) степени являетс тождественным преобразованием A.
Рассмотрим произвольный элемент x1 О A и рассмотрим последовательность из n+1 элементов f(x1),  f(f(x1)),ј. Среди них есть хотя бы два одинаковых, поскольку разных — всего n. Пусть это fk1(x1) и fk2(x1), где 1 Ј k1 < k2 Ј n+1. Поскольку отображение f — взаимнооднозначно, совпадают между собой и элементы x1 и f(k2-k1)(x1). Конечно, другие элементы множества A при отображении f(k2-k1)(x1) могут меняться и утверждение еще не доказано. Но множество {x1}c состоит лишь из n-1-го элемента. Мы можем выделить в нем элемент x2, и не более чем после n итераций преобразовани f(k2-k1)(x1) он перейдет в себя. Затем возьмем третий элемент и т.д. Таким образом, не позднее чем после n ! итераций отображени f все элементы множества A перейдут в себя.
Задача 6. Сколько всего существует перестановок множества из n элементов ? (сравните с задачей 9 из Статьи I).
Для бесконечного множества свойством (1) — в некоторой степени (т.е. после нескольких итераций) быть тождественным, обладают отнюдь не все взаимно-однозначные преобразования. Например, поворот Sa окружности1 S1 на угол a·p, где a не является рациональным числом, не вернет точки окружности на свои места после любого числа итераций.
Напомним: рациональным числом называется дробь [(m)/(n)], где mn О Z,  n 0, причем, если числитель и знаменатель имеют общий делитель, то на него можно сократить — число остается то же. Поэтому будем (использу множитель —1) считать, что n > 0.
Также и сдвиг прямой Th на ненулевое число h, т.е. взаимно-однозначное преобразование прямой: x: ® x + h, после n итераций переходит в преобразование x: ® x + n h, которое, как и Sa, не имеет неподвижных (т.е. переходящих при преобразовании в себя) точек.
Мы будем обозначать n-ую итерацию преобразования f знаком fn, если исключается путаница с алгебраической степенью f.
Предыдущие утверждения можно усилить (в чем здесь усиление высказывания ?): преобразования San и Thn не имеют неподвижных точек при n > 0,  h 0,  a- иррациональное число.
В ряде случаев степень n можно интерпретировать как дискретное время, и следить за последовательностью точек xn+1 = f(xn). Эту последовательность назовём траекторией точки x0 при преобразовании f.
Как устроена траектория произвольной точки окружности x О S1 при преобразовании Sa с иррациональным a ? Она, конечно, не заполняет всю окружность S1, но плотна на ней. Это значит, что для любой точки y О S1 и для любого сколь угодно малого положительного числа e существует такой номер n = n(ey), что r(xny) < e. Здесь r(xy)- угол между точками x и y.
Задача 7. Докажите это утверждение.
Количество отображений служит дискретным аналогом времени в этом процессе последовательного отображения A в себя. Интересные и красивые траектории на двумерной плоскости A = R2 мы рассмотрим в следующей статье. При этом будут использованы т.н. комплексные числа.

2  Рациональные числа, можно ли их пересчитать

В предыдущей статье мы определили понятие равномощности множеств.
Множество A называется счетным, если оно равномощно натуральному ряду, Другими словами, можно "пересчитывать" элементы множества A и до каждого элемента дойдет очередь. Мы доказали в предыдущей статье, что множество целых чисел Z или четных чисел — счетные.
Рассмотрим целочисленную решетку на плоскости, т.е. множество пар целых чисел Z ЕZ.
Теорема Кантора. Множество Z ЕZ счетно.
Как мы уже знаем из прошлой статьи, объединение двух счетных множеств счетно. Аналогично можно доказать, что и объединение четырех счетных множеств счетно. Поэтому мы докажем, что каждый из четырех квадрантов множества Z ЕZ, например, Z+ ЕZ+ есть счетное множество. Здесь Z+ есть множество целых неотрицательных чисел.
На Рис. 1 спpава представлены два способа обхода (пересчитывания) множества Z+ ЕZ+. В этом и состоит все доказательство теоремы Кантора.

1/1
1/2
1/3
1/4
ј
2/1
2/2
2/3
2/4
ј
3/1
3/2
3/3
3/4
ј
.
.
.
.
ј
.
.
.
.
ј
.
.
.
.
ј
       
1
2
4
7
ј
3
5
8
.
ј
6
9
.
.
ј
10
.
.
.
ј
.
.
.
.
ј
.
.
.
.
ј
       
1
2
5
10
ј
4
3
6
11
ј
9
8
7
12
ј
.
.
.
.
ј
.
.
.
.
ј
.
.
.
.
ј
Рис.1.
Задача 8. Получите явные формулы для номера каждого элемента множества Z+ ЕZ+ для каждого из обходов. Придумайте другие диаграммы и формулы для обходя множества Z+ЕZ+.
Таким образом, счетное множество счетных множеств — счетно.
Задача 9. Докажите счетность множества Z+ ЕZ+ ЕZ+ — целочисленной решетки в трехмерном пространстве, для четырехмерной решетки Z+ ЕZ+ЕZ+ ЕZ+ и т.д.
Множество целых чисел вкладывается во множество рациональных чисел Q при n=1, а само Q — в целочисленную решетку на плоскости Z ЕZ. Оба эти множества счетны. Следует ли отсюда, что Q счетно ?
Конечно, мы для доказательства этого утверждения можем модифицировать доказательство теоремы Кантора, устроить бесконечную двумерную таблицу: числитель — по горизонтали, знаменатель — по вертикали, а при обходе не считать дробь, если она — сократимая.
Но можно также использовать Теорему Кантора–Бернштейна: пусть имеют место вложени

A М Aў М A"                                                       
(2)
и крайние множества равномощны: A ~ A". Тогда и среднее множество им равномощно. В предыдущем примере для доказательства счетности по этой теореме мы можем использовать вложения Z+ М Q М ( Z+ ЕZ+). Заметим, что сама теорема не подразумевает счетности A и/или A". Поэтому мы будем применять ее и для несчетных множеств — есть, оказывается, и такие.
Перейдем к доказательству теоремы. Условие A ~ A" означает, что существует взаимно-однозначное отображение f: A ® A". Обозначим A1 прообраз подмножества Aў при этом отображении, а A2 — прообраз A. Поскольку при любом отображении вложение одного множества в другое сохраняется, из (2) следуют вложения A2 М A1 М A и мы получаем следующую диаграмму отображений:

ј
A2
М
A1
М
A
М
Aў
М
A"
f ­
f ­
f ­
f ­
f ­   ,
ј
A4
М
A3
М
A2
М
A1
М
A
где подмножества A3A4ј определяются аналогично A1A2, все вертикальные стрелки — взаимно-однозначные отображения.
Отсюда следует что дополнения тоже отображаются друг в друга взаимно-однозначно:

A\A1 f
®
 
A"\Aў,   A1\A2 f
®
 
Aў\A,   A2\A3 f
®
 
A\A1ј
Теперь мы можем представить множества Aў и A, равномощность которых мы пытаемся доказать, в виде объединений трех непересекающихс множеств:

Aў = Uў И
Vў И
Wў,    где   Uў = Aў З
A З
ж
и
Ґ
З
j=1 
Aj ц
ш
,

Vў=(Aў\A) И(A1\A2) И(A1\A2)Иј,   Wў=(A\A1) И(A2\A3) И(A4\A5)Иј,   

A = U И
V И
W,   U = A З
ж
и
Ґ
З
j=1 
Aj ц
ш
,

V=(A\A1) И(A2\A3) И(A4\A5)Иј,   W=(A1\A2) И(A3\A4) И(A5\A6)Иј.
Теперь мы заметим, что следующие множества равномощны:

U ~ Uў,    V є Wў    W f
®
 
V.
Первое соотношение выполняется, так как дополнительное пересечение с Aў не уменьшает множества, поскольку U М Aў.
Доказательство этой теоремы дает нам возможность сравнивать мощности бесконечных множеств. Мы уже знаем, что бывают равномощные множества. А бывает ли так, что мощность одного больше мощности другого ? Определение естественно. Мы говорим, что мощность множества A больше мощности множества B, если 1) они не равномощны; 2) существует подмножество A1 М A, которое равномощно B. До того, как мы доказали теорему Кантора - Бернштейна, мы должны были допускать существование ситуации, когда мощность A больше мощности B, но и мощность B больше мощности A.
Задача 10. Используя теорему, докажите, что такого не может быть.

3  Для каждого множества построить более мощное

Мы не доказали, что про любые два множества можно выяснить: чь мощность больше.
Однако для всякого множества найдется множество с большей мощностью. И его можно предъявить.
Теорема Кантора. Множество 2A всех подмножеств любого непустого множества A имеет большую мощность, чем само множество A.
Предположим противное. Это означает, что существует взаимнооднозначное отображение

f: A ® 2A.
По основному постулату теории множеств про каждый элемент можно сказать, принадлежит он данному подмножеству или нет. Мы разделим все элементы множества A на две части, скажем "хорошие" и "плохие". Хорошими мы будем называть такие a О A, что a О f(a) (напомним, что f(a) есть некоторое подмножество множества A. Плохими будем называть остальные элементы множества A. Рассмотрим теперь множество B всех плохих элементов и его прообраз f-1(B) О A. Если этот прообраз есть хороший элемент, то, согласно определению, f-1(B) О B. Но ведь в B находятся только плохие элементы — противоречие. Предположим, что f-1(B) — плохой элемент. Тогда f-1(B) П B. Но все плохие элементы принадлежат B. Значит f-1(B) — хороший элемент. И здесь противоречие.
Следовательно, такого взаимнооднозначного отображения f не существует.
Кроме того существует естественное вложение множества A во множество 2A. Именно, каждому элементу поставим в соответствие подмножество, состоящее из одного этого элемента.
Это завершает доказательство теоремы.
В частном случае конечных множеств мы получаем очевидное неравенство: 2n > n при n і 1.

4  Рациональные числа и бесконечные дроби

Мы доказали выше, что множество рациональных чисел Q счетно. Здесь мы выясним, как записываются рациональные числа в виде десятичных или, например, двоичных дробей и покажем, что множество вещественных чисел может быть представлено в виде 2Z, а потому несчетно.
Рассмотрим множество всех бесконечных десятичных дробей (т.е. до запятой стоит любое конечное число значащих цифр, а после — бесконечное). Если начиная с некоторого номера до бесконечности идет только цифра 9,

a1 ј an 9999999ј,    an 9,
то назовем такую дробь плохой и отождествим ее с дробью, у которой на всех этих местах стоят нули (т.е. это — конечная десятичная дробь), а на n-ом (там ведь была не цифра 9) цифра на 1 большая. То множество, которое получилось после указанной идентификации (грубо говоря, плохие дроби выкинуты), назовем множеством вещественных чисел и будем обозначать R.
Задача 11. Докажите, что подмножество подвергнувшихся этой идентификации "плохих" дробей счетно.
Задача 12. Докажите, что мы получим то же множество вещественных чисел, если будем использовать в определении двичные дроби, а идентифицировать дроби, у которых начиная с некоторого номера идёт только цифра 1, с теми конечными дробями, у которых все эти единицы заменены нулями, а предыдущая цифра an = 0 заменена на 1.
Задача 13. Докажите, что конечная десятичная дробь, т.е. число, у которого начиная с некоторого номера идет только цифра 0, есть рациональное число.
Однако, конечная десятичная (или двоичная) дробь не есть общий вид рационального числа.
Задача 14. Докажите, что рациональное число m/n,  mn О Z,  n 0, будучи превращено в десятичную дробь, оказываетс дробью, у которой начиная с некоторого номера повторяется некоторый период. Другими словами, m/n можно представить в виде суммы конечной десятичной дроби (это пока периодичность не началась) и периодической дроби, умноженной на 10-k,  k О Z. Оцените максимально возможные длину конечной десятичной дроби и величину k в этом представлении числа m/n.
Оказывается, верно и обратное утверждение: всякая десятичная дробь такого вида есть рациональное число. Действительно, первое слагаемое есть число рациональное, множитель 10-k,  k О Z — тоже. Поэтому достаточно доказать, что рациональным числом являетс периодическая дробь вида

x = 0,a1 a2 ј al a1 a2 ј al a1 a2 ј al ј,
где {ai}i=1i=l есть цифры, причем, возможно, некоторые из них повторяются; l — длина периода этой периодической дроби.
Рассмотрим конечную десятичную дробь, а потому рациональное число y = a1 a2 ј al 0 0 ј. Число x можно представить в виде
x = y·(1 + 10-l + 10-2l + ј) =  y

1-10-l
.
Второе равенство проверяется умножением на знаменатель дроби, который отличен от нуля и является рациональным числом. Отношение двух рациональных чисел — рационально.
Все ли вещественные числа рациональны ? Гипотетически можно предположить, что в каждой дроби можно выделить, хотя и очень длинный, период. Нет, это не так. Например, вещественное число Ц2 не является рациональным. Вообще такие числа называются иррациональными.
Задача 15. Докажите, что число Ц2 можно представить в виде бесконечной десятичной дроби, последовательно уточняя все более дальние цифры соответствующей десятичной дроби.
Предположим, что существует представление в виде несократимой дроби: Ц2=m/n. Тогда числитель m делится на 2. Действительно, возведем равенство в квадрат. Левая часть делится на 2, следовательно и правая должна делиться: m=2 m1. Следовательно, 1=2 m12/n2, откуда n2 = 2 m12. Следовательно, и знаменатель n делится на 2, а ведь предполагалось, что дробь m/n — несократимая. Мы же нашли общий множитель: 2, и пришли к противоречию.
Множество двоичных дробей, меньших 1, равномощно множеству 2Z+. Действительно, запись в виде последовательности и есть отображение во множество, состоящее из 0 и 1. А множество всех таких двоичных последовательностей и заполняет отрезок [0, 1]. По теореме Кантора это множество несчетно. Из него, правда нужно исключить подмножество всех плохих дробей, но оно-то счетно.
Рис. 2 показывает, как интервал (т.е. отрезок без концевых точек) можно взаимно-одназначно отобразить на всю вещественную прямую. Таким образом, конечный интервал и вся прямая равномощны.
Задача 16. Докажите, что отрезок и интервал равномощны.
Для мощности множества всех точек прямой (отрезка, интервала) имеетс специальное название: континуум.
Вопрос о том, существует ли множество промежуточной мощности между счетными множествами и множествами мощности континуум, оказалс чрезвычайно трудным, и, хотя решение и получено, но формулировка этого ответа настолько сложна, что не может быть здесь приведена.

5  Канторовское множество. Его длина и мощность.

Канторовым называется следующее множество. Рассмотрим интервал (0, 1). Исключим из него средний отрезок [1/3, 2/3]. Из оставшихся двух интервалов исключим их середины — отрезки [1/9, 2/9] и [7/9, 8/9]. Продолжим этот процесс до бесконечности, а оставшиеся точки и составляют канторово множество. На каждом шаге суммарная длина оставшихся интервалов будет умножаться на 2/3. Поэтому для любого положительного числа e > 0 существует такой номер шага, когда суммарная длина их будет меньше этого e > 0. Следовательно, суммарная длина канторова множества равна нулю.
Рис. 3.
Кантоpово множество получается выбpасыванием тpоичных дpобей, содеpжащих двойки.
Однако, мощность этого "маленького" множества, по-прежнему, равна континууму. Действительно, все числа интервала можно записать в троичной системе. Какие дроби выброшены ? Те, у которых в этой записи есть цифра 1. Те, которые состоят только из 0 и 2 остались. Т.е. остались все последовательности из цифр 0 и 2. Но множество таких последовательностей совпадает со множеством всех двоичных дробей — какая разница, значок 1 или 2 используется вместе со значком 0 ? — Нет разницы !
Рис. 4.
Ковер Серпинского. Множество получается последовательным выбрасыванием центральных частей правильных треугольников. Площадь остатка стремитс к нулю, а множество остающихся точек континуально (докажите !)
Так что решение вопроса — маленькое или нет какое-то множество, зависит от того, какие именно свойства множества мы анализируем, длину или мощность.

References

[1]
П. С. Александров: Введение в общую теорию множеств и функций. 1948.
[2]
Н. К. Верещагин, А. Шень: Начала теории множеств. М., 1999,
МЦНМО.
[3]
Г. Е. Шилов: Математический анализ (функции одного переменного). Части 1-2. М., 1969, "Наука".

Footnotes:

1 Буква S — от английского слова sphere, а 1 — означает одномерность этой сферы. Т.е. взять небольшой кусочек, то он во многом будет похож на кусочек одномерной прямой. Аналогично символ S2 обозначает обычную двумерную сферу — поверхность глобуса — она двумерна, поскольку ее маленькие кусочки похожи на кусочки двумерной плоскости. Позднее мы разберемся и со сферами больших размерностей.