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

Date: 2015-10-07; view: 397.

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

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

2.Отображения. Разбиения на классы. 3

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

Под множеством М понимается совокупность некоторых объектов, которые будут называться элементами множества М. Тот факт, что x является элементом множества М, будем обозначать через xÎM, в противном случае xÏM.

Элементы множества могут сами являться множествами. Множество можно задать перечислением принадлежащих ему элементов (то есть писать M={x₁, x₂,…, x_n}) или указанием свойств, которым элементы множества должны удовлетворять, то есть, если имеется свойство P, которым могут обладать элементы некоторого множества A, то будем обозначать {xÎA | x обладает свойством P} или {x | P(x)}, если из контекста ясно, о каком множестве А идет речь.

Множество N или w - множество натуральных чисел, Z – множество целых чисел, Q – множество рациональных чисел, R – множество вещественных чисел, C – множество комплексных чисел.

Множество А называется подмножеством множества В (обозначается АÍВ), если все элементы множества А принадлежат В:

A BÛ"x (xÎAÞ xÎB).

Если АÍВ, то будем также говорить, что множество А содержится в В, или имеется включение множества А в В. Множества А и В называются равными или совпадающими (обозначается А=В), если они состоят из одних и тех же элементов, то есть, если АÍВ и ВÍА. Таким образом, чтобы доказать равенство множеств, требуется установить два включения.

Пример 1: Справедливы следующие включения: NÍZ, ZÍQ, QÍR, RÍC.

Пример 2: Покажем, что множества М₁={x | sin x=1} и M₂={x | x=p/2+2kp, kÎZ} совпадают.

Если xÎM₁, то x можно представить в виде x=p/2+2kp и поэтому xÎM₂. Таким образом, M₁ÍM₂. Если же xÎM₂, то есть x=p/2+2kp, то sin x=1, то есть M₂ÍM₁. Следовательно, M₁=M₂.

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

Так, включения из примера 1 являются строгими.

Заметим, что XÍZ; если XÍY и YÍZ, то XÍZ; если XÍY и YÍX, то X=Y.

Не следует смешивать отношение принадлежности Î и отношение включения Í. Хотя 0Î{0} и {0}Î{{0}}, неверно, что 0Î{{0}}, поскольку единственным элементом множества {{0}} является {0}.

Совокупность всех подмножеств множества А называется его булеаном или множеством-степенью и обозначается через Р(А) или 2^А. Таким образом, Р(А)={B | BÍA}.

Мы будем предполагать, что существует множество, не содержащее ни одного элемента, которое называется пустым и обозначается через Æ. Ясно, что ÆÍА для любого множества А.

Пример 3. Если А={1; 2; 3}, то Р(А)={Æ, {1}, {2}, {3}, {1, 2}, {1, 3}, {2, 3}, A}.

Множество, содержащее все элементы, находящиеся в рассмотрении, называется универсальным или универсумом и обозначается через U. Рассмотрим операции на булеане P(U). Если А, ВÎР(U), то пересечение А В и объединение А В множеств А и В определяются равенствами А В={ x | xÎA и xÎB}, А В={x | xÎA или xÎB}. Пересечение множеств А и В называется также их произведением и обозначается А×B, а объединение – суммой: А+В. Множество А\В=А-В={x | xÎA и x B} называется разностью множеств А и В, множество А В=(А\В) (В\А) – кольцевой суммой или симметрической разностью множеств А и В, множество =U\А – дополнением множества А в U (см. рис., на котором изображены так называемые диаграммы Эйлера-Венна, наглядно поясняющие соотношения между множествами).

Пример 4. Докажем, что А\В=А .

Сначала установим, что А\ВÍА . Пусть x – произвольный элемент А\В. Тогда по определению разности множеств имеем xÎA и xÏB, отсюда xÎA и xÎ , значит, xÎA . Теперь покажем, что A ÍA\B. Если xÎA , то xÎA и xÎ , поэтому xÎA и xÏB, значит, xÎA\B. На основании включений A\BÍA и A ÍA\B делаем вывод, что A\B=A .

Аналогично примеру 4 устанавливаются следующие основные свойства операций пересечения, объединения и дополнения:

1. Ассоциативность операций и :

А (В С)=(А В) С, А (В С)=(А В) С.

2. Коммутативность операций и :

А В=В А, А В=В А.

3. Законы идемпотентности:

А А=А, А А=А.

4. Законы дистрибутивности:

А (В С)=(А В) (А С), А (В С)=(А В) (А С).

5. Законы поглощения:

А (А В)=А, А (А В)=А.

6. Законы де Моргана:

= , = .

7. Законы нуля и единицы:положим 0ÛÆ, 1ÛU, тогда

А 0=А, А 0=0, А 1=А, А 1=А, А =1, А =0.

8. Законы двойного отрицания:

=А.

Пересечение и объединение могут быть определены для любого множества множеств A_i, где индексы i пробегают множество I. Пересечение {A_i | iÎI} и объединение {A_i | iÎI} задаются равенствами:

{A_i | iÎI} = {x | xÎA_i для всех iÎI},

{A_i | iÎI} = {x | xÎA_i для некоторого iÎI}.

Вместо {A_i | iÎI} и {A_i | iÎI} часто пишут соответственно A_i и A_i, а иногда просто A_i, A_i, если из контекста ясно, какое множество I имеется в виду. Если

I={1, 2,…, n}, то используются записи A₁ A₂ A_n и A₁ A₂ A_n, а также A_i и A_i.

Множество {A_i | iÎI} непустых подмножеств множества А называется покрытием множества А, если А= A_i. Покрытие называется разбиением, если A_i A_j=Æ при i¹j. Другими словами, множество {A_i | iÎI} непустых подмножеств множества А является его разбиением, если каждый элемент xÎА принадлежит в точности одному из подмножеств A_i, каждое из которых не является пустым.

Упорядоченную последовательность из n элементов x₁, x₂,…, x_n будем обозначать через (x₁, x₂,…, x_n) или áx₁, x₂,…, x_nñ. Здесь круглые или угловые скобки используются для того, чтобы указать на порядок, в котором записаны элементы. Будем называть такую последовательность упорядоченным набором длины n, кортежем длины n или просто n-кой. Элемент x_i называется i-ой координатой кортежа áx₁, x₂,…, x_nñ.

Декартовым (прямым) произведением множеств A₁, A₂,…, A_n называется множество

{(x₁, x₂,…, x_n) | x₁ÎA₁, x₂ÎA₂,…, x_nÎA_n}, обозначаемое через или .

Если A₁=A₂=…=A_n=A, то множество называется n-й декартовой степенью множества А и обозначается Аⁿ. Положим по определению A⁰ = {Æ}.

Пример 5. Пусть А={1, 2}, B={3, 4}. Тогда ={(1, 3), (1, 4), (2, 3), (2, 4)},

={(3, 1), (3, 2), (4, 1), (4, 2)}, ={(1, 1), (1, 2), (2, 1), (2, 2)}.