Множества. Операции над множествами

ГОУВПО

“Воронежская государственная технологическая академия”

 

Кафедра информационных технологий,

Моделирования и управления

 

ДИСКРЕТНАЯ МАТЕМАТИКА

Методические указания к практическим занятиям

по дисциплине "Математика",

раздел "Дискретная математика"

 

Для специалистов и бакалавров,

Обучающихся по направлениям

230400 – "Информационные системы и технологии ",

230700 – "Прикладная информацика"

Дневной и сокращенной формы обучения

 

Метод математической индукции

Метод математической индукции – универсальный способ доказательства утверждений, зависящих от натурального аргумента n. Он основан на следующем принципе математической индукции: утверждение справедливо для любого натурального n, если: 1⁰ оно справедливо для n = 1;

2⁰ из того, что оно верно для всех n £ k (k ³ 1) следует его справедливость для n = k + 1.

Задача 1. Найти сумму .

Решение. Имеем: ; ; ; . Есть подозрение, что . Докажем эту формулу.

1⁰. При n = 1 – формула верна.

2⁰. Предположим, что для произвольного k ³1 для всех n£ k . В частности, для n = k . Найдем . Имеем . По предположению это равно

= = = ,

что и требовалось доказать.

Задача 2. “Докажем”, что все натуральные числа равны между собой. Предположим, что k = k + 1. Прибавим по 1 к обеим частям этого равенства. Получим k + 1 = k + 2, что и требовалось доказать. Ошибка этого “доказательства” состоит в отсутствии проверки утверждения при n = 1.

Задача 3. Доказать неравенство 2ⁿ > 2n + 1 при n ³ 3.

Решение.

1⁰. 2³ > 7.

2⁰. 2^{k + 1} = 2×2^k > 2(2k + 1) = 4k + 2 = (2k + 3) + (2k – 1) > 2k + 3.

Задача 4. Доказать, что для любого n ³ 0 число 11^{n + 2} + 12^{2n + 1} делится на 133.

Решение.

1⁰. 11² + 12¹ = 133 – верно при n = 0.

2⁰. 11^{k +3} + 12^{2(k + 1) +1} = 11×11^{k + 2} + 144×12^{2k + 1} = (144–133) ´ ´11^{k + 2} + 144×12^{2k + 1} = 144 × (11^{k + 2} + 12^{2k + 1}) – – 133×11^{k + 2}.

В полученной разности уменьшаемое делится на 133 по предположению, а вычитаемое содержит множетель 133. Следо-вательно, все выражение делится на 133.

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

1. Доказать формулу S_n = 1² + 2² + 3² + … + n² =

= n(n +1)(2n +1) /6.

2. Обозначим H_n = 1 + 1/2 + 1/3 +…+ 1/n – гармонические числа. Доказать, что Н_n неограниченно сверху, т.е. что Н_n ® +¥ ().

3. Доказать, что любую сумму денег более 7 копеек можно уплатить монетами достоинством 3 и 5 копеек.

4. Найти формулы для вычисления:

а)

б)

Доказать формулы и утверждения (5 – 13).

5.

6. .

7. При любом х ¹ 1, .

8. Сумма кубов трех последовательных натуральных чисел n³ + (n + 1)³ + (n + 2)³ делится на 9.

9. Выражение делится без остатка на 9.

10. Число диагоналей выпуклого n-угольника k = n(n –2) /2.

11. Последовательность а_n = (n корней) возрастает.

12. cos a×cos 2a×… ×cos 2ⁿa = .

13.

14. .

15. .

16.

17.

18.

Множества. Операции над множествами

Множеством называется совокупность некоторых предметов, объединенных общим признаком. Элементы множества – это те предметы, из которых состоит множество.

Если какой-то элемент а принадлежит множеству А, то это обозначается аÎА, а если b не принадлежит А, то – bÏА. Например, пусть А – множество четных натуральных чисел, тогда 6ÎА, а 3ÏА.

Пусть имеется два множества А и В, причем все элементы множества А принадлежат множеству В, т.е. если хÎА, то хÎB. В этом случае говорят, что множество А включено в множество В. Обозначается: АÍВ (Í – символ нестрогого включения, т.е. возможно совпадение множеств). Множество А совпадает с множеством В (А = В), если все элементы множества В являются элементами множества В и все элементы множества В являются элементами множества А. Это можно записать в виде

(АÍВ и ВÍА) Û (А = В).

Большинство утверждений теории множеств связано с равенством двух множеств и включением одного множества в другое. Поэтому надо детально разобраться в методах доказательства этих фактов.

1. Доказательство включения АÍВ. Для этого нужно доказать, что любой элемент x, принадлежащий множеству А одновременно является элементом множества В, т.е.

(" x Î А) Þ (x Î В).

2. Доказательство равенства А = В. Оно сводится к доказательству двух включений А Í В и В Í А.

Определим следующие операции над множествами.

1. Объединение. Пусть А и В – произвольные множества. Их объединением называется множество С = А È В, которое состоит из всех элементов, принадлежащих хотя бы одному из множеств А или В.

2. Пересечение. Пересечением множеств А и В называется множество С, состоящее из элементов, одновременно принадлежащих А и В. Обозначается так: C = A Ç B.

3. Разность. Разность множеств А и В – это множество С (С = А \ В), состоящее из элементов множества А, не принадлежащих множеству В. Если В Í А, то разность С = А \ В называется дополнением В до А.

Считается, что все множества включены в некоторое множество U, которое называют универсальным множеством. В этом случае дополнение какого-либо множества А до U обозначается С (А) или .

4. Симметричная разность. По определению симметричная разность двух множеств А и В – это множество

С = А D В = (А \ В) È (В \ А).

Задача 1. Доказать, что для любых множеств A₁, A₂,..., A_n если справедливы включения A₁ Í A₂ Í... Í A_n Í A₁, то A₁ = A₂ =... =A_n.

Решение.

Задача 2. Доказать тождество

(AÇB) \ C = (A \ C)Ç(B \ C) = AÇ(B \ C) = (AÇB)\(AÇC).

Решение.

1) Пусть xÎ(AÇB)\C, тогда xÎAÇB и xÏC. Так как x принадлежит пересечению, то он принадлежит каждому из множеств. Следовательно, xÎA и xÏC, что означает xÎA\C. Аналогично из xÎB и xÏC следует, что xÎB\C. Так как x принадлежит обоим множествам, то xÎ(A\C)Ç(B\C). Следовательно, (AÇB)\CÍ (A\C)Ç(B\C).

2) Покажем теперь, что (A\C) Ç (B\C) AÇ (B\C). Так как xÎ(A\C)Ç(B\C), то xÎA\C и xÎB\C, а, следовательно, xÎA, xÎB и xÏC. Поэтому xÎB\C и xÎA, что и означает требуемое.

3) Пусть xÎAÇ(B\C), тогда xÎA, xÎB и xÏC. Следовательно, xÎAÇB и xÏAÇC. Но тогда по определению разности xÎ(AÇB)\(AÇC).

4) Пусть теперь xÎ(AÇB)\(AÇC), покажем, что xÎ(AÇB)\C. Из условия следует, что xÎAÇB и xÏAÇC. Первое свойство означает, что xÎA и xÎB, второе - xÏA или xÏC. Так как при xÏA получим противоречие, то остается лишь случай xÏC. Поэтому имеем xÎA, xÎB и xÏC. Но тогда xÎAÇB и xÏC и, следовательно, xÎ (AÇB)\C.

Таким образом, доказана цепь включений

(AÇB)\C Í (A\C)Ç(B\C) Í AÇ(B\C) Í (AÇB)\(AÇC) Í Í(AÇB)\C.

Для завершения доказательства остается воспользоваться результатами задачи 1.

Задача 3. Доказать тождество

A Ç (B D C) = (A Ç B) D (A Ç C).

Решение. Воспользовавшись свойством дистрибутивности и результатами задачи 2, получим

AÇ(BDD) = AÇ((B\D)È(D\B)) = (AÇ(B\D))È(AÇ(D\B)) =

= ((AÇB)\(AÇD))È((AÇD)\(AÇB)) = (AÇB) D (AÇD).

Задача 4. Доказать, что A Í (B Ç C) Û A Í B и A Í C;

Решение. Докажем, что из AÍ(BÇC) следует AÍB и AÍC. Для этого необходимо показать, что если выполнено включение посылки, т.е. AÍBÇC, то выполняются и оба включения следствия.

Пусть xÎA, тогда по условию xÎBÇC, а, следовательно, xÎB и xÎC. Поэтому справедливы включения AÍB и AÍC.

Докажем обратное следствие. Пусть выполнены оба включения AÍB и AÍC. То есть из xÎA вытекает, что xÎB и xÎC. Но это означает, что xÎBÇC. Следовательно, требуемое включение доказано.

Задача 5. Решить систему уравнений .

Решение. Так как A\X=B, то BÍA, XÇB=Æ, A\BÍX и AÍXÈB. Выполнение первых двух свойств очевидно.

Докажем справедливость третьего включения. Пусть xÎA\B, тогда xÎA и xÏB. Покажем, что xÎX. Предположим противное, т.е. xÏX, тогда из B=A\X получим xÎB, что противоречит условию. Следовательно, xÎX.

Так как BÍA, то A=(A\B)ÈB. Из этого равенства и условия A\BÍX следует, что AÍXÈB.

Аналогично из X\B=A следует, что CÍX, AÇC=Æ, XÍAÈC и X\CÍA. Так как A\BÍX и CÍX, то (A\B)ÈCÍX. Кроме того, из XÍAÈC, BÍA и XÇB=Æ следует, что XÍ(A\B)ÈC. Поэтому X=(A\B)ÈC, где BÍA и AÇC=Æ.

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

1. Доказать, что нестрогое включение обладает свойством рефлексивности: A Í A.

2. Показать, что {{1,2}, {2,3}} ¹ {1, 2, 3}.

3. Доказать, что для любых множеств A₁, A₂,..., A_n если справедливы включения A₁ Í A₂ Í... Í A_n Í A₁, то A₁ = A₂ =... =A_n.

4. Доказать, что А D В = (А È В) \ (А Ç В).

5. Доказать, что множество корней многочлена y(x) = = f(x)×j(x) есть объединение множеств корней многочленов f(x) и j(x).

6. Доказать, что пересечение множеств действительных корней многочленов f(x) и j(x) совпадает с множеством действительных корней многочлена y(x) = f ² (x) + j² (x).

Доказать тождества (7 – 17).

5. (AÇB) È (CÇD) = (AÈC) Ç (BÈC) Ç (AÈD) Ç (BÈD).

6. (A \ B) È (B \ C) È (C \ A) È (A Ç B Ç C) = A È B È C.

7. A \ (BÈC) = (A \ B)Ç(A \ C) = (A \ B) \ C = (A \ C) \ (B \C).

8. A \ (B Ç C) = (A \ B) È (A \ C).

9.(AÇB) \ C = (A \ C)Ç(B \ C) = AÇ(B \ C) = (AÇB)\(AÇC).

10. (AÈB) \ C = (A \ C) È (B \ C).

11. A \ (B \ C) = (A \ B) È (A Ç C).

12. A Ç (B D C) = (A Ç B) D (A Ç C).

13. A D (B D C) = (A D B) D C.

14. A D B = B D A. 16. A È B = A D B D (A Ç B).

15. A D (A D B) = B. 17. A \ B = A D (A Ç B).

Доказать включения (18 –24).

18. [ (B \ C) \ (B \ A) ] Í A \ C.

19. A \ C Í [(A \ B) È (B \ C)].

20. [(A Ç C) È (B Ç D)] Í [(A È B) Ç (C È D)].

21. [(A₁ È A₂ È... È A_n) D (B₁ È B₂ È... È B_n)] Í

Í [(A₁ D B₁) È (A₂ D B₂) È... È (A_n D B_n)].

22. [(A₁ Ç A₂ Ç... Ç A_n) D (B₁ Ç B₂ Ç... Ç B_n)] Í

Í [(A₁ D B₁) È (A₂ D B₂) È... È (A_n D B_n)].

23. [(A₁ \ A₂) D (B₁ \ B₂)] Í [(A₁ D B₁) È (A₂ D B₂)].

24. A D B Í [(A D C) È (B D C)].

25. Вытекает ли из A \ B = C, что A = B È C?

26. Вытекает ли из A = B È C, что A \ B = C?

27. Верны ли равенства:

а) A È (B \ C) = (A È B) \ C; б) (A \ B) È C = (A È C) \ B?

Если нет, то в какую сторону имеет место включение?

28. Доказать равносильность включений A \ B Í C и A Í

Í (B È C).

29. Доказать включение

[() \ ()] Í .

Показать на примере, что в общем случае здесь нет равенства.

30. Доказать включения:

а) A D B Í [(A D C) È (B D C)];

б) [(A È B) D F] Í [(A D F) È (B D F)];

в) [(A È B) D (C È D)] Í [(A D C) È (B D D)].

Показать на примере, что в общем случае здесь нет равенства.

31. Доказать, что:

а) A Í B Þ (A Ç C) Í (B Ç C);

б) A Í B Þ (A È C) Í (B È C);

в) A Í B Þ (A \ C) Í (B \ C);

г) A Í B Þ (C \ B) Í (C \ A);

д) B Í A Þ (A \ B) È B = A;

е) (A Ç B) È C = A Ç (B È C) Û C Í A;

ж) A Í (B Ç C) Û A Í B и A Í C;

з) (A È B) Í C Û A Í C и B Í C;

и) (A Ç B) Í C Û A Í C (B) È C;

к) A Í (B È C) Û (A Ç C(B)) Í C;

Доказать тождества (32–36).

32. C (A \ B) = C (A) È B.

33. A \ B = A Ç C (B).

34. (A Ç B) È (A Ç C (B)) È (C (A) Ç B) = A È B.

35. (A Ç B) È (A Ç C (B)) = (A È B) Ç (A È C (B)) = A.

36. C [ C (C (X) È Y) È (X È C (Y))] = Y \ X.

37. Упростить выражение C [ C (X È Y) Ç (C (X) È C (Y))].

38. Доказать, что:

а) A D B = Æ Û A = B;

б) A Ç B = Æ Þ A È B = A D B;

в) A D B = C Û B D C = A Û C D A = B.

39. Определить операции È, Ç, \ через:

а) D, Ç; б) D, È; в) \, D.

40. Пусть A, B и C – данные множества. Решить системы уравнений:

а) г)

б) д)

в) е)

Отображения

ОПРЕДЕЛЕНИЕ. Пусть X и Y – два произвольных множества. Говорят, что на X определено отображение f, принимающее значения из Y (f: X® Y), если каждому элементу x из X ставится в соответствие единственный элемент y = f(x) из Y.

Множество элементов xÎX, для которых определено отображение f, называется областью определения f и обозначается d_f.

Если имеется какой-либо элемент хÎX, то соответствующий ему элемент yÎY будем называть образом x. Пусть A – некоторое подмножество множества X (AÍX), образ множества A определяется как множество образов элементов множества A и обозначается f(A), т.е. f(A) = {f(x) | xÎA}. Образ области определения называется областью значений отображения f и обозначается r_f (т.е. r_f = f(d_f) = f(X)).

Если задать yÎY, то множество соответствующих ему x, т.е. таких, что y = f(x), будем называть прообразом y и обозначать f ^-1(y), f ^-1(y) = {xÎX | y = f(x)}. В общем случае обратное отображение f ^-1 неоднозначно. Пусть B – некоторое подмножество множества Y (BÍY), прообраз множества B определяется как множество прообразов элементов множества B и обозначается f ^-1(B), т.е. f ^-1(B) = { xÎA | f(x)=y, y Î B}.

Отображение i: X ® X такое, что i(x) = x для любого xÎX называется тождественным отображением.

Пусть f: X ® Y и g: Y ® Z. Отображение h: X ® Z, такое, что каждому элементу xÎX ставится в соответствие единственный элемент h(x) = g(f(x)), называется композицией (или суперпозицией) отображений f и g и обозначается g о f.

Отображение f: X ® Y называется сюръекцией X на Y, если множество образов всех элементов из X совпадают с множеством Y. Это обозначается как f(X) = Y. Другое эквивалентное определение сюръекции – это отображение, при котором каждый элемент из Y имеет прообраз в множестве X.

Если для любых x₁, x₂ÎX таких, что x₁ ¹ x₂, получается, что f(x₁) ¹ f(x₂), т.е. разным элементам соответствуют различные образы, то это отображение f называется инъекцией.

Отображение f, которое является одновременно сюръекцией и инъекцией, называется биекцией, или взаимно однозначным отображением.

Если между А и В установлено биективное отображение, то говорят, что множества А и В эквивалентны. Эквивалентность множеств обозначается A ~ B.

Легко видеть, что эквивалентность множеств обладает свойством транзитивности, т.е. если A ~ B и B ~ C, то A ~ C. Признаки эквивалентности множеств дают следующие

ТЕОРЕМЫ Кантора-Бернштейна.

1. Если A Í B Í C, причем A ~ C, то A ~ B.

2. Если A эквивалентно подмножеству множества B, а B эквивалентно подмножеству множества A, то A ~ B.

Задача 1. Доказать, что f(A) Í B Û A Í f ^-1(B).

Решение.

1) Пусть f(A)ÍB и xÎA. Тогда f(x)Îf(A), а в силу f(A)ÍB справедливо f(x)ÎB, что означает xÎf ^-1(B). Следовательно, AÍ Íf ^-1(B).

2) Докажем, что f(A)ÍB при условии AÍf ^-1(B). Пусть yÎf(A), это значит, что y=f(x), где xÎA. Из включения AÍf ^-1(B) следует, что xÎf ^-1(B). Тогда y=f(x)Îf(f ^-1(B)) = B. Что и требовалось доказать.

Задача 2. Можно ли построить сюръективное отображение вида

множества целых чисел на множество рациональных чисел, где коэффициенты a₀, a₁,..., a_т, b₀, b₁,..., b_ь - целые числа?

Решение.

Такое отображение построить нельзя. Любая функция f(x), представимая в виде частного от деления двух многочленов, имеет конечный или бесконечный предел при x®¥. Если f(x) = q < ¥, то существует такое N, что для всех k, таких, что |k|>N, выполнены неравенства q-1< f(x)< q+1. Если отображение f является сюръекцией, то конечное множество целых чисел k: |k| £ N отображается на бесконечное множество рациональных чисел r, лежащих в множестве (- ¥,q-1]È[q+1,+¥), что невозможно. Следовательно, не для каждого рационального r существует прообраз в множестве целых чисел.

Если f(x) = ¥, то рассуждения аналогичны (в этом случае конечное множество целых чисел k, таких, что |k| £ N, отображалось бы на множество рациональных чисел отрезка [-A, A], что невозможно. Следовательно, это отображение также не является сюръективным.

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

1. Доказать теоремы 2, 3 для бесконечного числа множеств.

2. Доказать, что для любого отображения f выполняется включение f(A Ç B) Í f(A) Ç f(B), а равенство будет только

тогда, когда f является биекцией.

3. Пусть A – произвольное множество из области определения отображения f. Верно ли равенство f ^-1(f(A)) = A?

4. Пусть B – произвольное множество из области значений отображения f. Верно ли равенство f(f ^-1(B)) = B?

Доказать тождества 5, 6.

5. f ^-1(A \ B) = f ^-1(A) \ f ^-1(B).

6. f(A) Ç B = f(A Ç f ^-1(B)).

7. Верно ли равенство f(A \ B) = f(A) \ f(B)? Если нет, то в какую сторону имеет место включение? При каких условиях выполняется тождество?

8. Доказать, что для любой функции f:

а) A Í B Þ f ^-1(A) Í f ^-1(B);

б) A Í B Þ f(A) Í f(B);

в) f(A) = Æ Û A Ç d_а = Æ;

г) f ^-1(A) = Æ Û A Ç r_а = Æ.

9. Пусть j: A ® B – взаимно однозначное соответствие. Доказать, что:

а) j ^-1 – взаимно однозначное соответствие между B и A;

б) j ^-1 o j = i; в) j o j ^-1 = i.

10. Доказать, что объединение (пересечение) двух отображений f₁ и f₂ из A в B является отображением из A в B тогда и только тогда, когда f₁ = f₂.

11. Доказать, что:

а) f(A) Ç B = Æ Û A Ç f ^-1(B) = Æ;

б) f(A) Í B Û A Í f ^-1(B).

12. Пусть f: X ® Y, g: Y ® Z, h = g o f и B Í Z. Тогда h ^-1(B) = f ^-1(g ^-1(B)).

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

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

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

Задача 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. Какова мощность множества всех последовательностей натуральных чисел?