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

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

Множество А нестрого включено в множество В (обозначается АÍВ) если для любого х ÎА, следует что х ÎB. Нестрогое включение не исключает совпадения множеств.

Множество А строго включено в множество В (обозначается АÌВ) если:

1) АÍВ;

2) существует y ÎB, такой, что y ÏB.

Множество А совпадает с множеством В (А = В), если все элементы множества В являются элементами множества В и все элементы множества В являются элементами множества А, т.е.

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

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

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

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

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

1) АÍВ;

2) $ y: y Î B и y Ï A.

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

Задача 1. Доказать тождество AÇ(B \ C) = (AÇB)\(AÇC).

Решение. I способ.

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

2) Пусть теперь 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ÎA, то остается лишь случай xÏC. Поэтому имеем xÎA, xÎB и xÏC. Но тогда xÎA и xÎB \ C и, следовательно, xÎ AÇ(B \ C).

II способ.

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

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

Û Û

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

Û

Квадратная скобка означает выполнение хотя бы одного из свойств, т. е. доказательство в дальнейшем распадается на 2 случая, которые и далее объединяются квадратной скобкой.

Û

Û

Распишем также, что означает, что элемент не принадлежит множеству, построенному с помощью операций над множествами.

Û

Û

Û

Û

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

Решение.

Для любого множества отличного от A₁, в силу транзитивности отношения нестрогого включения, получим A₁ Í A_i Í A₁. А, следовательно, A₁ = A_i для любого i, и все множества совпадают.

Так тождества A Ç (B \ C) = (AÇB) \ (AÇC) = (AÇB) \ C = =(A \ C) Ç (B \ C) можно доказать с помощью цепи включений

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

Задача 3. Доказать, что 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. Следовательно, требуемое включение доказано.

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

Решение. Так как 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}.

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 – 12).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

21. Доказать равносильность включений A \ B Í C и 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 называется тождественным отображением.

Задача 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], что невозможно. Следовательно, это отображение также не является сюръективным.

Задача 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.

Контрольные вопросы и задания

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)).

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Мощность – это то общее, что есть у любых двух эквивалентных множеств. Мощность множества A обозначается m(A) или |A|. Таким образом, m(A) = m(B), если A ~ 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 эквивалентно какому-либо подмножеству множества B, то мощность A не больше мощности B (т.е. m(A)£m(B)). Если при этом множество B не эквивалентно никакому подмножеству множества A, то m(A) < m(B).

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

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

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

Задача 2. Доказать, что множество точек разрыва монотонной функции, заданной на [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] функции доказательство аналогично.

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

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

Контрольные вопросы и задания

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

⇐ Предыдущая1234Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: