Элементы теории множеств

43

Каждая скобка последнего «произведения» определяет в силу алгебраичности операции « » некоторый элемент множества А.

Обозначим эти элементы b, c, d соответственно. Получим:

=(b c) d =

Всилу базы индукции в последнем «произведении» можно изменить расстановку скобок. Тогда расставляя скобки иначе и вспоминая определение элементов b, c, d, получим:

=b (c d) = (a1 a2 … ai) ((ai+1 … ak) (ak+1 … am+1)) =

Поскольку «произведение» (ai+1 … ak) (ak+1 … am+1) содержит ≤ m «множителей», то, в силу предположения индукции, оно не зависит от

расстановки скобок. Следовательно, скобки в нем можно убрать. Получим:

= (a1 a2 … ai) (ai+1 … ak ak+1 … am+1) = (a1 a2 … ai) (ai+1 … am+1).

Таким образом,

(a1 a2 … ak) (ak+1 … am+1) = (a1 a2 … ai) (ai+1 … am+1).

Шаг индукции доказан.

4. Вывод. Для бинарной ассоциативной алгебраической операции « », заданной на некотором множестве А, справедлив общий ассоциативной закон: сложные «произведения» a1 a2 … an (n ≥ 3) не зависят от порядка расстановки скобок в этих «произведениях».

Задачи для самостоятельного решения

Задание 1.Какие из следующих утверждений верны?

1){{1, 2}, 3} = {3, {2, 1}};

2)1 {{1,2}, {3,4}};

3){1,2} {{1,2}, {3,4}};

4){1,2,3,4} = {{1,2}, {3,4}};

5){3} {{1,2}, 3};

6)= { };

44

Задание 2. Какие из следующих утверждений верны для любых множеств А, В, С?

1)A B ˄ B C A C;

2)A B ˄ B C A C;

3)A∩B С ˄ A C B A∩C = ;

4)A ≠ B ˄ B ≠ C A ≠ C;

5)A В С ˄ B А С B = ;

6)A B ˄ B C A C.

Задание 3. Пусть U - множество всех десятичных цифр. А, В U.

А = {1,3,4,5,7,8,9}, B = {2,3,4,6,8}. Найти А В, А∩В, А\В, В\А, А, В , А В,

В А.

Задание 4. Пусть: А = {(x,y) 2 x < 0, y ≥ 0, x+y < 3};

B= {(x,y) 2 y – x2 > 0};

C= {(x,y) 2 y2 - x ≥ 1}.

Построить в прямоугольной декартовой системе координат: А, В, С,

А В, А∩С, А\(A\B), С (С∩В).

Задание 5. Пусть U = , A = {n n ˄ n 2}, B = {n n ˄ n 3}, C = {n n ˄ n 5}. Найти:

Задание 6. Построить диаграммы Эйлера, изображающие непустые множества А и В, для которых выполняются следующие условия:

1)А В ˄ А В ;

2)А В ˄ А В ;

3)А В В ˄ А В А;

4)А В = В ˄ А ∩ В = А ˄ А ∩ В = ˄ А В = U.

Задание 7.Используя диаграммы Эйлера доказать следующие тождества в теории множеств:

1) (X \ Y) \ Z = X \ (Y Z);

2) X (Y \ Z) = (X Y) \ (Z \ X);

45

3) X ∩ (Y \ Z) = (X∩Y) \ (X ∩ Z);

4)X \ (Y Z) = (X \ Y) ∩ (X \ Z);

5)X \ (Y ∩ Z) = (X \ Y) (X \ Z);

6)X \ (Y \ Z) = (X \ Y) (X ∩ Z);

7)(X \ Y) \ Z = X \ (Y Z);

8)X ∩ (Y \ Z) = (X ∩ Y) \ (X ∩ Z) = (X ∩ Y) \ Z;

9)(X Y) \ Z = (X \ Z) (Y \ Z);

10)X ∩ (Y Z) = (X ∩ Y) (X ∩ Z);

11)X (X Y) = Y.

Задание 8. Доказать тождества теории множеств, используя связь формул

АВ и АМ:

1) (X \ Y) \ Z = X \ (Y Z);

2) X (Y \ Z) = (X Y) \ (Z \ X);

3) X ∩ (Y \ Z) = (X∩Y) \ (X ∩ Z);

4)X \ (Y Z) = (X \ Y) ∩ (X \ Z);

5)X \ (Y ∩ Z) = (X \ Y) (X \ Z);

6)X \ (Y \ Z) = (X \ Y) (X ∩ Z);

7)(X \ Y) \ Z = X \ (Y Z);

8)X ∩ (Y \ Z) = (X ∩ Y) \ (X ∩ Z) = (X ∩ Y) \ Z;

9)(X Y) \ Z = (X \ Z) (Y \ Z);

10)X ∩ (Y Z) = (X ∩ Y) (X ∩ Z);

11)X (X Y) = Y.

Задание 9. Доказать, что:

2)А В (А ∩ С) (В ∩ С);

3)А В (А \ С) (В \ С);

4)А В В А;

5)А С ˄ В D (A B) (C D);

6)А С ˄ В D (A ∩ B) (C ∩ D);

7)А С ˄ В D (A \ B) (C \ D);

46

8)А С ˄ В D (A B) (C D);

9)А В 2A 2B;

Задание 10. Для каждой диаграммы Эйлера построить формулу алгебры множеств, задающую заштрихованную (более темную) область.

Задание 11. Упростить следующие формулы АМ:

1)В(А∩В∩С);

2)В ( А В С) D (D E);

3)(A A) B (C C) D;

4)A B C A B C ;

5)((A A) B) ((C C) D) ;

6)((A B) (A B)) ( A (A C));

47

7) ( A ( A B C)) ((A B) ( A B)).

Задание 12. Пусть А = {a, b, c} и В ={0, 1}. Найти:

1)А В;

2)А В2;

3)В А В;

4)В3.

Задание 13. Доказать, что для непустых множеств А, В, С, D имеют место следующие утверждения:

1)А В ˄ С D A C B D;

2)А= В ˄ С= D A C = B D;

Задание 14. Доказать, что для любых множеств А, В, С, D имеют место следующие утверждения:

1)(A∩ B) (C∩ D) = (A C)∩ (B D);

2)(A B) C = (A C) (B C);

3)(A B) (C D) = (A C) (B C) (A D) (B D);

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

Задание 15. Изобразить с помощью диаграмм Эйлера отношения между множествами:

1)А - квадраты;

2)B - четырехугольники;

3)C - ромбы;

4)D - параллелограммы;

5)E - прямоугольники;

6)F - трапеции.

Задание 16. Пусть R = {(0,2), (1,2), (2,2)}, S = {(0,1), (0,2), (1,1), ((2,3), (2,1),

(3,2)}. Найти:

1)R S;

2)S R;

48

Задание 17. Найти: a) область определения D(R); b) множество значений

E(R); c) R-1; d) R R; e) R-1 R; f) R R-1 для отношений:

1)R = {(x,y) 2 y = 2х - 1};

2)R = {(x,y) 2 х делит y};

3)R = {(x,y) 2 у делит х};

4)R = {(x,y) 2 х + y ≤ 0};

5)R = {(x,y) 2 2х ≥ 3y}.

Задание 18. Доказать, что для отношений R1, R2, Q, заданных на множестве А, если R1 R2, то:

1)Q R1 Q R2;

2)R1 Q R2 Q;

3)R1-1 R2-1.

Задание 19. Пусть А = {1, 2, 3}. На множестве А задано отношение

R = {(1,1), (2,2), (3,3), (1,2), (2,3)}. Является ли отношение R

рефлексивным, иррефлексивным, симметричным, антисимметричным, транзитивным?

Задание 20. Заполнить таблицу следующим образом: если отношение,

записанное в верхней строке, является рефлексивным (Р), иррефлексивным

(ИР), симметричным (С), антисимметричным (АС) или транзитивным (Т), то на пересечении соответствующих строк и столбцов ставится «+», в

противном случае – « - ».

Отношение R= {(l1,l2)}

Отношение R = {(x,y)} задано на множестве

задано на множестве

натуральных чисел

прямых плоскости

Р

ИР

49

С

АС

Т

Задание 21. Доказать, что если отношения R1 и R2 рефлексивны, то рефлексивны и отношения:

1. R1 R2;

2. R1 ∩ R2;

3. R1 -1;

4. R1 R2.

Задание 22. Доказать, что если отношения R1 и R2 иррефлексивны, то иррефлексивны и отношения:

1.R1 R2;

2.R1 ∩ R2;

3.R1 R1 -1.

Задание 23. Доказать, что если отношения R1 и R2 симметричны, то

1. R1 R2;

2. R1 ∩ R2;

отношений R1 и R2 симметрична тогда и только тогда, когда

R1 R2=R2 R1.

Задание 26. Построить бинарное отношение R со следующими свойствами:

1. R – рефлексивное, симметричное и не транзитивное;

50

2.R – рефлексивное, антисимметричное и не транзитивное;

3.R – рефлексивное, транзитивное и не симметричное;

4.R – антисимметричное, транзитивное и не рефлексивное;

5.R – симметричное, транзитивное и не рефлексивное.

Задание 27. Доказать, что любое отношение R, симметричное и антисимметричное одновременно, является транзитивным.

Задание 28. Пусть R – бинарное отношение на А и Rn R R ... R .

0

n

Доказать, что отношение S = R0n - транзитивно.

n 1

Задание 29. Доказать, что если отношение R на множестве А – симметричное и транзитивное и D(R) E(R) = A, то отношение R – отношение эквивалентности на А.

Задание 30. Доказать, что отношение R является отношением эквивалентности:

1.R определено на 2 и R = { (a, b),(c, d) | a + d = b + c};

2.R определено на 2 и R = { (a, b),(c, d) | a· d = b· c};

Задание 31. Доказать, что если отношение R является отношением эквивалентности, то R-1 также является отношением эквивалентности.

Задание 32. Доказать, что если R1 и R2 - отношения эквивалентности, то:

1.R1 ∩ R2 - отношение эквивалентности;

2.R1 R2 - отношение эквивалентности R1 R2 = R1 R2;

3.R1 R2 - отношение эквивалентности R1 R2 = R2 R1.

Задание 33. Доказать, что бинарное отношение R является отношением эквивалентности. Построить фактор-множество по этому отношению эквивалентности:

a) R – отношение подобия на множестве всевозможных треугольников;

51

b) R – отношение изоморфизма вещественных линейных пространств размерности ≤ n над полем .

Задание 34. Доказать, что множество действительных чисел бесконечно.

Задание 35. Пусть бинарное отношение R задано на множестве А={a,b,c}. R = {(a,a), (b,b), (c,c), (a,b), (b,c), (a,c)}. Доказать, что R –

отношение частичного порядка.

Задание 36. Доказать, что если R – отношение частичного порядка, то R-1

– отношение частичного порядка.

Задание 37. Доказать, что для любого множества А: 2А; - частично упорядоченное множество (ЧУМ).

Задание 38. Доказать, что если А; R1 - ЧУМ и А; R2 - ЧУМ, то А; R1∩ R2

- ЧУМ.

Задание 39. Пусть А; R1 - ЧУМ и В; R2 - ЧУМ. На множестве А В зададим отношение R следующим образом:

(a,b),(c,d) A B: [(a,b),(c,d)) R (a,c) R1 ˄ (b,d) R2].

Доказать, что А В; R - ЧУМ.

Задание 40. Построить диаграммы Хассе следующих ЧУМ:

1.В3; , В = {0, 1};

2.В4; , В = {0, 1};

3.2{a,b,c}; ;

4.{2,3,4,5,8,12,18,24,30,32,36,40}; x ≤ y x y .

Задание 41. Построить диаграммы Хассе всех попарно неизоморфных ЧУМ:

1.На множестве из трех элементов;

2.На множестве из четырех элементов.

Задание 42. Построить пример ЧУМ, в котором имеется точно один минимальный элемент и нет наименьшего элемента.

52

Задание 43. Доказать, что отношение R на множестве А является одновременно отношением эквивалентности и отношением частичного порядка тогда и только тогда, когда R = IA.

Задание 44. Пусть А = В2, В = {1, 2, 3, 4}. Введем отношение «≤1» на В:

(a,b) ≤1 (c,d) < > (a < c) ˄ [(a = c) (b ≤ d)].

Доказать, что «≤1» - отношение частичного порядка. Найти, если они существуют, минимальные, наименьшие, максимальные, наибольшие элементы в A относительно этого частичного порядка. Является ли указанный частичный порядок линейным? Построить диаграмму Хассе частично упорядоченного множества А.

Задание 45. Используя метод математической индукции доказать, что:

c) n : 1 + 3 + 5 + 7 +…+ (2n-1) = n2.

Ответы и решения.

Задание 1. Утверждение 1) верное (почему?) и неверны все остальные утверждения (почему?).

Задание 2. Верными являются утверждения 3) и 6). Неверными – остальные утверждения (приведите контрпримеры). Например, для утверждения 2): A = {a}, B = {a,b}, C = {{a,b},c}. Тогда А В, В С, но А С.

Задание 3. Имеем:

А В = {1,2,3,4,5,6,7,8,9}, А∩В = {3,4,8}, А\В = {1,5,7,9},

В\А ={2,6}, А = {0,2,6}, В = {0,1,5,7,9}, А В = {1,2,5,6,7,9} = В А.