Если область прибытия соответствия совпадает с его областью отправления, то соотвествие преобразуется в отношение

 

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

Л. Толстой

Глава 6. Упорядоченные бесконечные множества

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

ЦЕЛИ

Освоив эту главу, студенты должны:

· знать основные сведения об упорядоченных бесконечных множествах;

· иметь понятия об интервале и сегменте;

· уметь определять 4 типа сечений;

· уметь строить счетные и несчетные множества;

· знать, что представляет собой проблема континуума;

· иметь понятие о парадоксах в теории множеств;

· иметь понятие о принципе трансфинитной индукции и уметь применять его на практике.

6.1. Основные сведения об упорядоченных бесконечных множествах

Простейшим примером упорядоченных бесконечных множеств (УБМ) является множество всех целых чисел, натуральных, рациональных, неотрицательных и так далее чисел. Одно и то же бесконечное множество можно упорядочить различными способами.

Пусть множество Х является УБМ, причем элементы a, b, x Î X. Если справедлива запись а ® х и х ® b (a ® x ® b), то говорят, что элемент х лежит между элементами a и b. Множество всех элементов, лежащих между a и b, называется интервалом (a, b) упорядоченного бесконечного множества Х.

Если к интервалу (а, b) добавить два его конца, т.е. элементы a и b, то получим сегмент [a, b]. Два элемента a и b множества Х называются соседними, если интервал (a, b) — пустой. Если элемент из упорядоченного бесконечного множества Х таков, что ("xÎX)(x¹a Ù aÞx),то а является первым или наименьшим элементом Х.

В противоположном случае, если ("xÎX)(x¹a Ù хÞа), то тогда а является наибольшим элементом.

Очевидно, что в каждом УБМ может быть не больше одного наименьшего и одного наибольшего элемента. Например, в множестве положительных чисел наименьшим элементом будет ноль. Соответственно в множестве неположительных чисел ноль — наибольший элемент.

Для отношения порядка в УБМ справедливо следующее выражение:

x Þ y ® f(x) Þ f(y).

Другими словами, взаимно-однозначное отображение УБМ Х на УБМ Y сохраняет порядок, т.е. х ® y влечет, что f(x) ® f(y), где xÎX, yÎY. Такое отображение часто называют соответствием подобия. Очевидно, что два подобных упорядоченных бесконечных множества эквивалентны между собой.

Введем понятие сечения. Сечением упорядоченного бесконечного множества Х называется разбиение этого множества на два непустых подмножества А и В таких, что каждый элемент одного множества низшего класса всегда предшествует каждому элементу второго множества верхнего класса.

Существует 4 типа сечений.

1. В нижнем классе А есть наибольший элемент (а), а в верхнем классе В есть наименьший элемент (b). Такое сечение называется скачком. В этом случае интервал (а, b) является пустым.

2. В нижнем классе А есть а, а в верхнем классе В нет b.

3. В нижнем классе А нет а, а в верхнем классе В есть b. Второй и третий классы называются дедекиндовыми сечениями.

4. В нижнем классе А нет а, а в верхнем классе В нет b. Такое сечение называется щелью.

Рассмотрим принцип трансфинитной индукции.

Пусть дано упорядоченное бесконечное множество Х и имеется высказывание Р = Р(х), которое зависит от этого множества. Если высказывание Р верно для первого элемента х₀ÎХ и если из того, что оно верно для всех элементов хÎХ, предшествующих данному, следует, что предположение Р верно и для элемента х’, то высказывание Р верно для любого элемента, принадлежащего множеству Х.

Когда множество Х является множеством натуральных чисел, принцип трансфинитной индукции превращается в обычный принцип полной индукции.

Приведем пример. Докажем по индукции, что равенство

выполняется при всех натуральных n.

Пусть P (n) – предикат . При n = 1 левая часть равна ½, а правая часть (1(1 + 1) / 4 также равна ½. Следовательно, выражение при P (1) – истинно.

Предположим, что равенство  справедливо для произвольного числа m. Тогда

Тогда при любом натуральном m импликация P (m) ® P (m +1) истинна. Следовательно, на основании принципа математичыеской индукции мы показали, что предикат P (n) – истина для любых натуральных n.

Приведем ряд известных положений об УБМ.

Каждое множество, содержащее бесконечное подмножество, бесконечно. Тогда очевидно, что множество всех подмножеств бесконечного множества также бесконечно.

Каждое УБМ имеет собственное подмножество, которому оно равномощно и наоборот, если множество равномощно своему подмножеству, то оно является бесконечным.

Никакое множество не является равномощным множеству всех своих подмножеств.

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

Георг Кантор предположил способ сравнения двух упорядоченных бесконечных множеств, основанный на установлении взаимно-однозначного соответствия между элементами этих множеств. Это выполняется объединением элементов одного множества в пары с элементами другого множества так, что каждый элемент входит в одну единственную пару.

Если для двух УБМ установлено взаимно-однозначное соответствие, то эти множества равнозначны, т.е. имеют одинаковое количество элементов или |A| = |B|.

В УБМ встречаются парадоксы.

Например, некоторые множества могут быть равномощными своей части. Например, можно установить взаимно-однозначное соответствие между множеством натуральных чисел N и множеством их квадратов.

N 0, 1, 2, 3, 4, 5,...

N² 0, 1, 4, 9, 16, 25,...

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

6.2. Проблема континуума

Любое множество, равномощное натуральному ряду, называется счетным. Считают, что множество действительных чисел является несчетным множеством.

Множество, равномощное множеству действительных положительных чисел, не превосходящих единицы, называется множеством мощности континуума или континуальным.

Пусть имеем множество натуральных чисел. Тогда обозначим через N его мощность. Обозначим через К мощность множества действительных положительных чисел не превосходящих единицы.

Пусть имеется произвольное бесконечное множество М. Тогда мощность |M| равна произвольному числу m. В этом случае число всех подмножеств множества М будет равно 2^m.

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

Рассмотрим множество всех действительных чисел, т.к. каждой точке прямой можно поставить в соответствие одно действительное число и наоборот. Каждое действительное число запишем в виде бесконечной дроби вида 0, a₁ a₂ a₃.... Предположим, что удалось пронумеровать все действительные числа. Для опровержения этого предположения надо найти хотя бы одно не пронумерованное действительное число.

Согласно известной эвристике способ построения заключается в использовании двух правил:

Если a=1, то ставят 2.

Если a¹1, то ставят 1.

Возьмем ноль и поставим после него запятую. Рассмотрим первую цифру, если эта цифра отлична от 1, то в соответствующий ей разряд ставим 1, иначе 2. И далее процесс продолжается аналогично до просмотра всего действительного числа. Очевидно, что построенное число не получило никакого номера, т.к. в первом десятичном знаке оно отличается от числа с номером 1, во втором — от числа с номером 2, в n-знаке — от числа с номером n и т.д.

Например, имеем несколько действительных чисел:

1) 0, 2 7 3 6 1...

2) 0, 4 1 1 2 2...

3) 0, 6 7 3 1 1...

4) 0, 7 1 1 4 4...

5) 0, 9 1 8 1 9...

Тогда число, не получившее никакого номера, может иметь такой вид 0,12111...

В упорядоченных бесконечных множествах выделяют понятия алгебраического и трансцендентного числа. А лгебраическими называются числа, которые являются корнями уравнения вида a₀xⁿ + a₁x^n-1 +... + a_kx + a_k+1 = 0, т.е. корнями уравнений с целыми коэффициентами. Числа, которые не являются корнями таких уравнений, называются трансцендентными числами. Известным трансцендентным числом является число p» 3,14159...

Оказалось, что алгебраических чисел относительно мало (т.к. это счетные множества), а трансцендентных относительно много (это несчетные множества). Луи Виль привел алгоритм построения трансцендентных чисел. Он заключается в том, что в заданном действительном числе после первой единицы ставят ноль, после второй – два нуля, после третьей шесть, после n-ой – n! нулей. Примером трансцидентного числа является число 0,101000100000001...

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

Множества точек, расположенных на отрезках, получили название множество мощности континуума (Континуум — от лат. непрерывный). Множество мощности континуума самое большое несчетное множество.

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

Рассмотрим некоторые операции над мощностями конечных и бесконечных множеств. Часто мощность множества |M| = m называют кардинальным числом и обозначают card M = m.

Пусть заданы конечные множества А и В, |A| = m, |B| = n, N — мощность множества натуральных чисел (счетного множества), К — мощность несчетного множества (континуума).

Отметим, что мощности можно складывать так же, как складывают натуральные числа.

Тогда имеем

1. m + n = n + m,

2. m + N = N,

3. N + N = N,

4. N + K = K,

5. K + K = K.

Второе выражение означает, что сумма конечного и счетного множеств является счетным множеством. Третье выражение означает, что сумма мощностей счетных множеств равна мощности счетного множества. Четвертое выражение означает, что сумма мощности счетного множества и множества мощности континуума дает множество мощности континуума. Пятое выражение означает, что сумма множеств мощности континуума дает множество мощности континуума.

Аналогичные выражения существуют при декартовом произведении мощностей

6.  m x n = n x m,

7.  N x N = N,

8.  N x K = K,

9.  K x K = K.

Седьмое выражение означает, что если множества счетные, то и множества всех пар из этих множеств счетно. Это другая формулировка утверждения, что сумма счетных множеств является счетным множеством. Равенство (9) означает, что число точек на отрезке и в квадрате одно и то же (например, пусть к – это число точек на отрезке, тогда к х к – число точек в декартовом произведении отрезка на себя, т.е. число точек в квадрате).

Очевидно, что все натуральные числа содержатся среди кардинальных чисел, но существуют кардинальные числа, не являющиеся натуральными. Приведем ряд известных теорем Кантора, доказательство которых приведено в специальной литературе, указанной в конце данной части.

Теорема 1. Для любого кардинального числа m справедливо неравенство m < 2^m.

Теорема 2. Мощность m’ подмножества множества, имеющего мощность m, удовлетворяет неравенству m’ £ m.

В теории множеств обнаружены противоречия (парадоксы), называемые антиномией. Приведем наиболее популярные из них.

Парадокс Кантора.

Пусть М – множество всех множеств, Card M = m. По теореме 1, кардинальное число множества его подмножеств 2^m удовлетворяет условию 2^m > m. С другой стороны, подмножества М являются множествами и следовательно элементами М, а их множество тогда является подмножеством множества М. Тогда по теореме 2 должно выполняться условие 2^m £ m, что приводит к противоречию.

Парадокс Рассела.

Пусть имеется множество мужчин А = {a1, a2,..., a(p), a(k), a(p+1), a(p+2),..., a(t)}, здесь а(k) – парикмахер. И задано два подмножества:

А₁ = {a1, a2,..., a(p)} – подмножество мужчин, которые бреются сами.

А₂ = {a(p+1), a(p+2),..., a(t)} – подмножество мужчин, которые не бреются сами. Парикмахеру приказано брить всех тех и только тех мужчин, которые не бреются сами.

Тогда возникает парадокс: ни в множество А₁, ни в множество А₂ нельзя внести парикмахера (элемент а(k)). Так как приказано брить только тех, кто себя не бреет, то побрить себя нельзя. Не брить себя тоже нельзя, т.к. приказано брить всех, кто себя не бреет.

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

Приведем ряд основных аксиом о бесконечных множествах.

А1. Упорядоченное бесконечное множество, не являющееся счетным, считается несчетным.

А2. Каждое несчетное множество бесконечно.

А3. Каждое бесконечное подмножество счетного множества счетно.

А4. Бесконечное подмножество счетного множества счетно.

А5. Объединение и непустое пересечение счетной совокупности счетных множеств являются счетными множествами.

А6. Множества целых (Z) и рациональных чисел (Q) являются счетными множествами.

А7. Множество действительных чисел (R) и множество комплексных чисел (C) являются несчетными множествами.

Существует стандартная система аксиом теории множеств в рамках которой излагают все общепринятые в математике способы рассуждений. Эта система позволяет строить все математические объекты на основе пустого множества. Такая система носит название системы аксиом Цермело—Френкеля (ZF). Аксиоматика ZF позволяет определять и реализовывать теоретико-множественные операции.

 

ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ

Пример 6.1. Установим взаимно-однозначное соответствие между множеством N ² и множеством A отрицательных чисел.

Решение. Необходимо построить соответствие G. Областью отправления будет N ², а областью прибытия – A. Теперь необходимо построить график Ф. При создании пар < n ², - n > и включении их в Ф будет получено искомое соответствие Г = <Ф, N ², A >, n = {1, 2, 3, …}.

 

Пример 6.2. Установить взаимно-однозначное соответствие между сегментами [ a, b ] и [ x, y ].

Решение. Выбирается произвольная точка плоскости С и через нее проводятся линии, проходящие через два сегмента (рис. 6.1). Это позволяет установить взаимно-однозначное соответствие между любыми произвольными интервалами, полусегментами вида [ a, b), [ x, y), или (a, b ], (x, y ].

Рис. 6.1. Пример установления взаимно-однозначного соответствия

Пример 6.3. Установить взаимно-однозначное соответствие между произвольными полусегментами [ a, b), и [ x, y).

Решение. Создадим произвольное взаимно-однозначное соответствие Г = < Ф, (a, b), (x, y)> между интервалами (a, b), (x, y) и добавим к графику Ф кортеж < a, x >. Тогда соответствие Г₁ = < Ф È {< a, y >}, [ a, b), [ x, y)> будет искомым.

 

Пример 6.4. Имеем множество A, состоящее из всех точек прямой линии, и множество B, состоящее из всех точек полуокружности x ² + (y – 1) ² = 1, y < 1 с центром в точке (0, 1) (рис. 6.2.). В связи с тем, что y < 1, концы полуокружности (точки (1, 1) и (-1, 1)) не принадлежат к ней.

Рис. 6.2. Пример установления взаимно-однозначного соответствия

Решение. Устанавливаем взаимно-однозначное соответствие между множествами A и B следующим образом. Каждой точке a_i прямой ставим в соответствие ту точку b_i полуокружности в которой эту окружность пересекает луч, соединяющий центр круга с точкой a_i.

 

Пример 6.5. Показать, что множество Q всех пар натуральных чисел счетно.

Примечание. Высотой кортежа < a, b > называется натуральное число a + b.

Решение. Известно, что имеется n – 1 кортежей данной высоты n (n > 1). Перечислим их:

< 1, n – 1 >, < 2, n – 2 >, …, < n – 1, 1 >

Обозначим через Q_n множество всех кортежей высоты n. Тогда видно, что Q есть сумма счетного множества конечных множеств Q_n, т.е. счетное множество.

КОНТРОЛЬНЫЕ ВОПРОСЫ

1. Что такое упорядоченное бесконечное множество?

2. Приведите способы упорядочивания бесконечных множеств.

3. Поясните понятия «интервал» и «сегмент».

4. Что такое соответствие подобия?

5. Поясните понятие сечения. Приведите примеры.

6. Поясните работу принципа трансфинитной индукции.

7. Каким образом можно сравнить два упорядоченных бесконечных множества?

8. Приведите примеры счетных и несчетных множеств.

9. В чем заключается проблема континуума?

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

11. Приведите примеры алгебраических и трансцендентных чисел.

12. Приведите операции над мощностями конечных и бесконечных множеств.

13. В чем заключается теорема Кантора о кардинальных числах?

14. Приведите примеры антиномий.

ЗАДАНИЯ ДЛЯ САМОСТОЯТЕЛЬНОЙ РАБОТЫ

1. Постройте примеры упорядоченных бесконенчых множеств.

2. Постройте взаимно-однозначное соответствие между множествами натуральных чисел и их кубами.

3. Приведите операции над мощностями бесконечных множеств. Докажите их справедливость.

4. Постройте примеры подобных упорядоченных бесконечных множеств.

5. Докажите счетность или несчетность натуральных чисел.

6. Докажите несчетность множества точек прямой.

7. Постройте основные виды сечений упорядоченных бесконечных множеств.

8. Определите мощность множества точек квадрата.

9. Определите мощность множества точек куба.

10. Докажите существование несчетных множеств с различными мощностями.

11. Доказать на основе индукции истинность предиката P (n):

, для всех n Î N.

12. Определить пересечение всех множеств A_n рациональных чисел, абсолютная величина которых меньше 1/ n, где n – натуральное число.

13. Показать, что сумма конечного или счетного числа конечных или счетных множеств есть конечное или счетное множество.

14. Показать, что всякое бесконечное множество M содержит счетное подмножество.

15. Показать, что множество всех пар натуральных чисел счетно.

16. Доказать или опровергнуть, что множество всех рациональных, т.е. целых и дробных чисел, счетно.

17. Показать, что среди действительных чисел нет наибольшего и наименьшего числа.

18. Определить, чему равна сумма счетного числа бесконечных множеств.

19. Установите взаимно-однозначное соответствие между множествами N и R.

20. Установите взаимно-однозначное соответствие между двумя произвольными объектами вида:

[ x, +¥), [ y, +¥);

(x, +¥), (y, +¥);

(-¥, x), (-¥, y).

21. Установите взаимно-однозначное соответствие между интервалом (-p, p) и R.

22. Покажите, что между множествами N и [0, 1] нельзя установить взаимно-однозначное соответствие.

23. Приведите примеры трансцедентных чисел.

24. Приведите примеры алгебраических чисел.

25. Докажите, что если A – счетное множество и S Î N ², то M^S является счетным множеством.

 

 

Между множествами натуральных чисел и точек сегмента [0, 1] нельзя установить взаимно-однозначное соответствие.