Мощность множества

Одной из задач теории множеств является определение числа элементов множества и исследование вопроса о сравнении друг с другом двух множеств по количеству элементов.

Для конечных множеств самой разной природы эта задача легко решается непосредственным подсчетом. Для бесконечных – с помощью взаимно однозначного (биективного) отображения. Рассмотрим примеры построения такого отображения.

Задача 1. В качестве множества А рассмотрим интервал на числовой прямой, пусть А=(–1, 1), а в качестве множества В –множество действительных чисел R. Это множества одинаковой мощности, т.к отображение f(x) = tg(px/2), хÎА позволяет установить между ними искомое взаимно-однозначное соответствие.

Задача 2. Пусть А = [–1,1], В = (–1,1). Строим отображение f : A ® B по следующему правилу: выделим в А последовательность –1, 1, 1/2, 1/3, 1/4, . . . , 1/n и положим f(–1)=1/2, f(1)=1/3, f(1/2)=1/4, f(1/3)=1/5, т.е. f(1/n) = 1/(n+2), а все точки, не входящие в эту последовательность отобразим сами в себя, т.е. f(x) = х. Следовательно, открытый и замкнутый интервалы эквивалентны.

Мощность – это то общее, что есть у любых двух эквивалентных множеств. Мощность множества A обозначается m(A) или |A|. Таким образом, m(A) = m(B), если A ~ B.

Если множество A эквивалентно какому-либо подмножеству множества B, то мощность A не больше мощности B (т.е. m(A)£m(B)). Если при этом множество B не эквивалентно никакому подмножеству множества A, то m(A) < m(B).

Наименьшим среди бесконечных множеств является множество натуральных чисел N.

ОПРЕДЕЛЕНИЕ. Назовем счетным всякое множество, эквивалентное множеству N. Другими словами, счетным называется всякое множество, элементы которого можно перенумеровать или составить из них бесконечную последовательность.

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

1. Множество целых чисел Z={0, ±1, ±2, . . .}. Построим из его элементов последовательность: a₁ = 0; a₂= – 1; a₃ = 1; a₄ = –2; a₅ = 2;... Формулу для вычисления ее общего члена можно записать в виде

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

Задача 3. Установить взаимно однозначное соответствие между множеством всех последовательностей натуральных чисел и множеством всех строго возрастающих последовательностей натуральных чисел.

Решение. Рассмотрим произвольную последовательность натуральных чисел

n₁, n₂, . . . , n_k, . . .

Поставим ей в соответствие возрастающую последовательность

m₁< m₂< . . . < m_k< . . . ,

где m₁=n₁, m₂=m₁+n₂, . . . , m_k=m_k-1+n_k, . . . Легко видеть, что это соответствие - взаимно однозначное.

Задача 4. Доказать, что если A \ B ~ B \ A, то A ~ B.

Решение. Для произвольных множеств A и B справедливо равенство A =(A\B)È(AÇB), где (A\B)Ç(AÇB)=Æ. Аналогично B= =(B\A)È(AÇB), где (B\A) Ç (AÇB)=Æ. Так как оба множества A и B являются объединением непересекающихся множеств, A\B~B\A по условию и (AÇB)~(AÇB), то A~B.

Задача 5. Доказать, что если расстояние между любыми двумя точками множества E на прямой больше единицы, то множество E конечно или счетно.

Решение. Разобьем прямую на счетное множество отрезков точками 0, ±1, ±2, ±3, . . . Каждый отрезок содержит не более одной точки данного множества, следовательно, между точками множества E и некоторым подмножеством построенного множества отрезков существует взаимно однозначное соответствие. Значит, множество E не более чем счетно.

Задача6. Доказать, что множество точек разрыва монотонной функции, заданной на [a, b], не более, чем счетно.

Решение. Каждая точка разрыва монотонной функции f(x) является точкой разрыва первого рода. Действительно, так как функция f(x) монотонна и ограничена на отрезке, то она имеет конечные пределы при x®x±0, где x – произвольная точка разрыва функции f(x).

Назовем скачком функции в точке x разность f(x+0) –f(x–0) этих пределов. Пусть функция f(x) возрастает. Легко проверить, что множество точек разрыва, в которых скачок больше a (где a – произвольное положительное число), конечно, а число этих точек не больше, чем (f(b) – f(a)) /a.

Обозначим через E_k множество точек разрыва со скачком, большим, чем 1/ k. Множество E всех точек разрыва равно объединению всех E_k: E = E₁ È E₂ È E₃ È . . . È E_k È . . .

Так как все E_k конечны, то E не более чем счетно.

Для монотонно убывающей на [a, b] функции доказательство аналогично.

Задача 7. Доказать, что множество всех непрерывных функций на отрезке [a, b] имеет мощность континуума.

Решение. Рассмотрим множество Q всех рациональных точек отрезка [a,b], занумерованных произвольным образом, т.е. Q= ={r₁, r₂,...}. Поставим в соответствие каждой непрерывной на [a,b] функции f последовательность действительных чисел f(r₁), f(r₂),... Так как непрерывная функция на [a,b] полностью определяется своими значениями в точках множества Q, то тем самым устанавливается взаимно однозначное соответствие между множеством всех непрерывных функций на [a,b] и частью множества всех последовательностей действительных чисел. Значит, в силу результатов задач 11-13 п. 4, мощность множества всех непрерывных функций на [a,b] не больше мощности континуума. С другой стороны, она не может быть меньше мощности континуума, так как все функции, постоянные на [a,b], уже образуют множество мощности континуума. Для завершения доказательcтва остается применить теорему Кантора-Бернштейна (см. п.4).

КОНТРОЛЬНЫЕ ВОПРОСЫ И ЗАДАНИЯ

1. Найти взаимно однозначное отображение отрезка [0, 1] на отрезок [a, b].

2. Отобразить взаимно однозначно луч [0, +¥) на всю числовую прямую.

3. Построить взаимно однозначное отображение окружности единичного радиуса на отрезок [0, 1].

4. Установить взаимно однозначное соответствие между открытым единичным кругом E={(x, y) | x² +y² < 1} и множеством точек плоскости, являющемся дополнением к замкнутому единичному кругу (замкнутый круг – K={(x, y) | x² +y² £ 1}.

5. Установить взаимно однозначное соответствие между открытым единичным кругом и замкнутым единичным кругом.

6. Установить взаимно однозначное соответствие между окружностью и прямой.

7. Установить взаимно однозначное соответствие между сферой с одной выколотой точкой и плоскостью.

8. Установить взаимно однозначное соответствие между сферой и плоскостью.

9. Установить взаимно однозначное соответствие между множеством всех многочленов с рациональными коэффициентами и множеством всех натуральных чисел.

10. Установить взаимно однозначное соответствие между множеством всех конечных подмножеств натурального ряда чисел и множеством натуральных чисел.

11. Установить взаимно однозначное соответствие между множеством всех последовательностей действительных чисел и множеством всех последовательностей натуральных чисел.

12. Установить взаимно однозначное соответствие между

множеством всех строго возрастающих последовательностей натуральных чисел и множеством всех бесконечных двоичных дробей, которые соответствуют числам интервала (0, 1].

13. Верно ли утверждение: "Если A ~ C, B ~ D, причем A É B, C É D, то A \ B ~ C \ D"?

14. Пусть A É C, B É D, C È D ~ C. Доказать, что A È D~A.

15. Верно ли утверждение: "Если A ~ B, C É A, C É B, то C \ A ~ C \ B"?

16. Верно ли утверждение: "Если A ~ B, A É C, B É C, то A \ C ~ B \ C"?

17. Какова мощность множества всех рациональных функций с целыми коэффициентами в числителе и знаменателе?

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

19. Какова мощность множества всех многочленов, коэф-фициентами которых служат корни многочленов с целыми коэф-

фициентами (алгебраические числа).

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

21. Пусть E – какое-либо несчетное множество положительных чисел. Доказать, что найдется такое число t > 0, что множество E Ç(–t, +¥) несчетно.

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

23. Определить мощности следующих множеств:

а) множество всех треугольников на плоскости, координаты вершин которых выражаются рациональными числами;

б) множество корней многочленов с целыми коэффициентами;

в) множество вещественных чисел от 0 до 1, в десятичном представлении которых 7 стоит на 3-м месте (т.е. числа вида 0.ab7cd...).

24. На числовой прямой задано неограниченное счетное множество Е. Доказать, что всегда существует вещественное число z, что сдвинув множество Е на z вправо, получим новое множество Е₁, которое будет иметь пустое пересечение с Е.

25. Какова мощность множества всех функций, определенных на отрезке [a, b] и разрывных хотя бы в одной точке этого отрезка?

26. Какова мощность множества всех строго возрастающих непрерывных функций, заданных на отрезке [a, b]?

27. Какова мощность множества всех монотонных функций на отрезке [a, b]?

28. Показать, что множество всех перестановок натурального ряда N имеет мощность континуума.

29. Какова мощность множества всех строго возрастающих последовательностей натуральных чисел?

30. Какова мощность множества всех последовательностей натуральных чисел?