Разбиение множества на классы.

Подмножества.

Пусть задано множество А. Множество В, состоящее из элементов множества А, называется подмножеством А.

Например. А={a, w, b, c} и В={w, a,b}, тогда В А или А В (В включается в А или А включается в В).

Множество А является собственным подмножеством.

Множество, не содержащее ни одного элемента, называется

пустым Ø.

Пустое множество является подмножеством любого множества.

Равенство множеств.

Два множества называются равными, если они состоят из одних и тех же элементов.

А={3, 2, а}. В={а, 3, а, 3, 2, а}. Имеем А=В.

Теорема. Множество А ровняется множеству В, если А является подмножеством В, а В является подмножеством А.

Доказательство:

1) Пусть х А и А В. По определению подмножества х В. Так как х- произвольный элемент А, то все элементы множества А множеству В.

2) Пусть х В и В А. По определению подмножества х А. Так как х- произвольный элемент В, то все элементы множества В множеству А.

3) Так как все элементы множества А множеству В, а все элементы множества В множеству А, то по определению равенства множеств А=В.

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

Все множества рассматриваются как подмножества некоторого универсального множества U .

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

Количество элементов, входящих во множество, называется его мощностью.

Для бесконечных множеств говорить о количестве элементов не имеет смысла, но говорить о мощности множества можно.

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

Пример:

Имеется множество натуральных чисел и имеется множество четных чисел. Равномощны ли они?

Ответ: Да. 1 2 3 4 5…

↓ ↓ ↓ ↓ ↓

2 4 6 8 10…

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

Алгебра множеств. Операции над множествами.

Условимся U изображать в виде прямоугольника

а множество А- (круги Эйлера-Венна).

Рис.1. Множества А и U.

1).Объединение множеств. А U B.

Объединением множеств А и В называется множество, состоящее из элементов, входящих или в А, или в В.

Рис.2. Объединение множеств.

2).Пересечение. А∩В.

Пересечением двух множеств называется множество, состоящее из элементов, входящих и в А, и в В.

Рис.3.Пересечение множеств.

3).Разность. А\B.

Разностью множеств А и В называется множество, состоящее из элементов, входящих в А, но не входящих в В.

Рис.4.Разность множеств.

4) Дополнение. Ā.

Дополнением множества А называется множество, состоящее из элементов не входящих в А.

Рис.5.Дополнение множества А.

5.Симметрическая разность A ∆ B.

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

Рис.4.Симметрическая разность множеств.

Включение множеств

Определение. Множество А, все элементы которого принадлежат множеству В, называется подмножеством множества В.

Обозначение. Нестрогое включение обозначается , означает, что А - несобственное подмножество множества В, возможно совпадающее с В. Строгое включение обозначается , и означает, что А - подмножество множества В, не совпадающее с B. читается "А включено в В".

Отличия и заключается в том, что отношение допускает и тождественность (А=В), т.е. любое множество можно рассматривать как подмножество самого себя , в то время как символ строгого включения ставится тогда, когда мы хотим подчеркнуть, что , то есть во множестве В содержатся не только элементы множества А. Выполнение соотношений и возможно только при А=В. И обратно, А=В, если и . Эти соотношения являются признаком равенства множеств через отношение включения. Заметим, что иногда в литературе символом ⊂ обозначают "нестрогое" включение, допускающее и равенство множеств. В этом случае символ ⊆ не используется, а строгое включение записывают двумя соотношениями , .

Свойства операций.

1) Коммутативность.

АUB=BUA. A∩B=B∩A.

2) Ассоциативность.

АU(BUC)=(AUB)UC. A∩ (B∩C) = (A∩B) ∩C.

3) Дистрибутивность.

А∩(BUC)=(A∩B)U(A∩C). AU (B∩C) = (AUB) ∩ (AUC).

4) Законы Де-Моргана.

= ∩ = U

5) AUA=A A∩A=A

6) AUØ=A A∩Ø= Ø

7) A U=U A∩U=A

8) A A Ø

10) A\B=

Доказательства.:

Аналитическое доказательство равенств множеств заключается в том, что доказывается, что левая часть равенства является подмножеством правой, и наоборот. И на основании теоремы о равенстве множеств следует, что равенства справедливы.

Введем обозначения для второго закона дистрибутивности:

D1=AU (B∩C)

D2= (AUB) ∩ (AUC)

1. Пусть х D1. Докажем, что х D2.

Так как х D1, то х объединению, то есть х А или х В∩C.

a) Пусть х А, тогда по определению объединения х AUB и поэтому же определению х AUC. Тогда по определению пересечения х (AUB)∩(AUC). То есть х D2.

b) Пусть х B∩C. Тогда по определению пересечения х B и х C.По определению объединения х AUB и х ВUС По определению пересечения х (AUB)∩(AUC), то есть х D2.

Так как х - произвольный элемент множества D1, то все элементы множества D1 являются элементами множества D2, то есть D1-подмножество D2.

2. Пусть у D2. Докажем, что у D1.

Так как у D2, то у AUBи у AUC по определению пересечения.

a) Пусть у А, тогда по определению объединения у AU(B∩C)=D1.

b) Если у не принадлежит А, то у В и у С (так как у AUB и у AUC соответственно). По определению пересечения у B∩C. По определению объединения у AU(B∩C)=D1.

Так как у - произвольный элемент множества D2, то все элементы множества D2 являются элементами множества D1, то есть D2-под множество D1, а так как D1 является подмножеством D2, то D1=D2.Что и требовалось доказать.

Рис.6. второй закон дистрибутивности.

Разбиение множества на классы.

Пусть задано некоторое множество, например множество треугольников. В этом множестве выделим свойство (например, быть прямоугольным). Тогда множество разбивается на два класса: прямоугольные и непрямоугольные.