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

Пример.

A={1, 3, 5, 18},  B={1, 3, 7, 9}. A\B={5, 18}.

 

Определение симметрической разности множеств. Симметрической разностью множеств A и B называется множество всех элементов из A, не являющихся элементами множества B в объединении с множеством всех элементов из B, не являющихся элементами множества A. A∆B=(A\B)È(B\A).

Пример.

A={1, 3, 5, 18},  B={1, 3, 7, 12}. A∆B={5, 7, 12, 18}.

 

Определение абсолютного  дополнения. Пусть A – подмножество U. Абсолютным дополнением множества A до множества U называется множество, содержащее все элементы множества U, которые не принадлежат множеству A. A'= =U\A, где U - универсальное множество. =U\A={x | xÎU L xÏA}.

Обычно все рассматриваемые  в ходе какого-либо рассуждения множества  являются подмножествами некоторого множества U, которое называют универсальным. Например, для числовых множеств универсальным является R, для точечных множеств на плоскости - множество точек всей плоскости и т.д.

 

Приоритеты операций.

Под приоритетом операции понимается порядок ее выполнения. Первой выполняется та операция, приоритет которой выше.

Приоритет операции пересечения множеств выше приоритета операции объединения.

Приоритет операции пересечения множеств выше приоритета операции вычитания.

Объединение и вычитание множеств считают равноправными операциями.

Пример. В выражении CÈА\В надо сначала выполнить вычитание (из А вычесть В), а затем полученное множество объединить с множеством С.

 

Свойства операций над  множествами.

1. "A, AÈA=A. AÇA=A (идемпотентность).

2. Пересечение и объединение множеств коммутативно (перестановочно):

"A ,B AÈB = BÈA; "A ,B AÈB = BÈA.

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

Эти свойства вытекают из определения. Действительно, пусть xÎAÇB, тогда xÎA и xÎB, следовательно, xÎBÇA. Отсюда (AÇB)Í(BÇA). Аналогично доказывается обратное утверждение (BÇA)Í(AÇB). Отсюда AÇB = BÇA.

Пусть xÎAÈB, тогда либо xÎA, либо xÎB, но тогда xÎBÈA и (AÈB) Í (BÈA). Аналогично (BÈA) Í (AÈB). Следовательно, AÈB = BÈA.

3. Пересечение и объединение множеств ассоциативно: для любых множеств A, B и C имеем (AÈB)ÈC=AÈ(BÈC); (AÇB)ÇC=AÇ(BÇC).

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

Пусть xÎ(AÇB)ÇC, отсюда xÎ(AÇB) и xÎC, или xÎA, xÎB, xÎC. Отсюда xÎ(BÇC) и xÎA, следовательно, xÎAÇ(BÇC) и верно (AÇB)ÇCÍAÇ(BÇC). Наоборот, если xÎAÇ(BÇC), следует, что xÎA, xÎC, xÎB, откуда xÎ(AÇB)ÇC и верно AÇ(BÇC)Í(AÇB)ÇC. Отсюда AÇ(BÇC) = (AÇB)ÇC. Аналогично доказывается равенство множеств AÈ(BÈC) = (AÈB)ÈC.

4. Для любых множеств A, B справедливо: если AÌB, то AÇB = A; AÈB = B.

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

Пусть xÎAÇB, то есть xÎA и xÎB, отсюда xÎA. Пусть теперь xÎA. Из условия AÌB следует, что xÎB, отсюда xÎAÇB. Следовательно, AÇB = A.

Пусть xÎA ÈB, тогда xÎA или xÎB. Но AÌB, и, следовательно, xÎB, AÈBÌB. Если xÎB, то по определению xÎAÈB и верно включение BÌAÈB. Отсюда AÈB = B.

5. Для любых множеств A, B и C справедливы равенства (свойство дистрибутивности):

a) AÇ(BÈC) = (AÇB) È (AÇC);

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

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

а) Пусть xÎAÇ(BÈC). Тогда xÎA и xÎ(BÈC) → xÎA, xÎB или xÎC → xÎAÇB или xÎAÇC → xÎ (AÇB)È(AÇC) → AÇ(BÈC) Ì (AÇB)È(AÇC). Пусть xÎ (AÇB)È(AÇC). Тогда xÎ(AÇB) или xÎ(AÇС)→(xÎA, xÎB) или (xÎA, xÎC) → xÎA и xÎB или xÎC→xÎAÇ(BÈC) и отсюда (AÇB)È(AÇC)Ì AÇ(BÈC). Окончательно имеем AÇ(BÈC) = (AÇB)È(AÇC).

б) Пусть xÎAÈ (BÇC). Тогда xÎA или xÎ (BÇC) → xÎA или (xÎB и xÎC) → (xÎA или xÎB) и (xÎA или xÎC) → xÎ (AÈB) Ç (AÈC) → AÈ (BÇC) Ì (AÈB) Ç (AÈC). Обратно, пусть xÎ (AÈB) Ç (AÈC). Тогда xÎ (AÈB) и xÎ (AÈC) → (xÎA или xÎB) и (xÎA или xÎC) → или xÎA или (xÎB и xÎC) → xÎAÈ (BÇC), то есть (AÈB) Ç (AÈC) ÌAÈ (BÇC). Следовательно, AÈ (BÇC) = (AÈB) Ç (AÈC).

6. ; (законы де Моргана).

7. Свойства универсального и пустого множества: "A справедливо

• AÈU=U;
• AÈÆ=A;
• AÇU=A;
• AÇÆ=Æ;
• ;
• ;
• A\Æ=A;

8. Свойства абсолютного дополнения: "A справедливо

• ÈA=U;
• ;
• ÇA=Æ.

9. Частные свойства разности множеств:

• Если AÇB=Æ, то А\В=А;
• Если AÍB, то А\В=Æ;
• А\В = А\(АÇВ);
• A\A =Æ;
• A\Æ =A.

 

2.3. Диаграммы Эйлера-Венна

 

Операции множеств и связанные  с ними соотношения представляются наглядно с помощью диаграмм Эйлера-Венна (названных по имени русского математика Леонарда Эйлера (1707-1783гг.) и английского  логика Джона Венна (1834-1923гг.). На этих диаграммах любые множества изображаются кругами, пересекающими друг друга, исходя из того, что внутренними точками круга изображаются элементы множества. Общей частью двух кругов, пересекающих друг друга, представляются возможные общие элементы двух множеств. Универсальное множество изображается в виде прямоугольника. Единичный элемент множества – точкой в круге.

Объединение множеств C=АÈВ (серое выделение):

Рис. 1

 

Пересечение множеств C=АÇВ (черное выделение):

Рис. 2

 

Множество В является подмножеством множества А:

Рис. 3

 

Разность A\B (серое выделение):

Рис. 4

 

Дополнение ко множеству А (черное выделение):

Рис. 5

 

Симметрическая разность множеств А∆B (серое выделение):

Рис. 6

 

2.4. Прямое произведение множеств

 

Одним из способов конструирования  новых объектов из уже имеющихся  множеств является декартово (прямое) произведение множеств.

Пусть A и B - множества. Выражение вида (a, b) , где aÎA и bÎB, называется упорядоченной парой. Элемент а называют первой координатой (компонентой) пары, элемент b - второй координатой (компонентой) пары.

Равенство вида (a, b)=(c, d) означает, что a=c и b=d. В общем случае, можно рассматривать упорядоченную n-ку (a₁, a₂, a₃, … ,a_n) из элементов a₁ÎA₁, a₂ÎA₂ … a_nÎA_n. Упорядоченные n-ки иначе называют наборами или кортежами.

Определение прямого произведения множеств. Декартовым (прямым) произведением множеств A₁, A₂,… A_n называется множество упорядоченных наборов (кортежей) вида A₁´A₂´…´A_n={( a₁, a₂,… a_n | a_iÎA_i}.

Из вышеприведенного определения  следует, что для любых a₁ ¹a₂ справедливо (a₁,a₂) ¹ (a₁,a₂).

Операция нахождения декартова  произведения множеств называется декартовым умножением множеств.

Определение степени прямого произведения. Степенью декартового произведения A₁´A₂´…´A_n называется число множеств n, входящих в это декартово произведение.

Замечание. Если все множества A_i одинаковы, то используют обозначение

Aⁿ=A´A´…´A.

Выясним, какими свойствами обладает операция нахождения декартова произведения множеств. Так как декартовы произведения (a₁, a₂) ¹ (a₂, a₁), a₁ ¹a₂ состоят из различных элементов, то декартово умножение множеств свойством коммутативности не обладает.

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

• (A U B) ´ C = ( A ´ C ) U ( B ´ C );
• (A \ B) ´ C = ( A ´C ) \ ( B ´ C ).

 

 

2.5. Отношения на множестве

 

Определение отношения степени n. Подмножество R декартового произведения множеств A₁´ A₂´…´ A_n называется отношением степени n (n-арным отношением).

Определение мощности отношения. Мощность множества кортежей, входящих в отношение R, называют мощностью отношения R.

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

Так как любое множество можно рассматривать как декартовое произведение степени 1, то любое подмножество, как и любое множество, можно считать отношением степени 1. Это не очень интересный пример, свидетельствующий лишь о том, что термины “отношение степени 1” и “подмножество” являются синонимами. Нетривиальность понятия отношения проявляется, когда степень отношения больше 1. Ключевыми здесь являются два момента:

Во-первых, все элементы отношения есть однотипные кортежи. Если же множество состоит из разнотипных числовых кортежей, то это множество не является отношением ни в R¹, ни в R², ни в Rⁿ.

Во-вторых. За исключением крайнего случая, когда отношение есть само декартово произведение A₁´A₂´…´A_n, отношение включает в себя не все возможные кортежи из декартового произведения. Это значит, что для каждого отношения имеется критерий, позволяющий определить, какие кортежи входят в отношение, а какие - нет. Этот критерий, по существу, определяет для нас смысл (семантику) отношения.

Действительно, каждому отношению  можно поставить в соответствие некоторое логическое выражение  P(x₁ ,x₂, … , x_n), зависящее от n параметров  и определяющее, будет ли кортеж (a₁, a₂, … ,a_n) принадлежать отношению R. Это логическое выражение называют предикатом отношения R. Более точно, кортеж (a₁, a₂, … ,a_n) принадлежит отношению R тогда и только тогда, когда предикат этого отношения P(a₁, a₂, … ,a_n) принимает значение “истина”. Таким образом, существует взаимно однозначное соответствие между n-арными отношениями и n-местными предикатами.

Примеры отношений.

Бинарные отношения (отношения  степени 2)

В математике большую роль играют бинарные отношения, т.е. отношения, заданные на декартовом произведении двух множеств A₁´A₂.

Определение отношения эквивалентности. Отношение R на множестве A² называется отношением эквивалентности, если оно обладает следующими свойствами:

1. (x, x)ÎR для всех xÎA (рефлексивность).
2. Если (x, y)ÎR, то (y, x)ÎR (симметричность).
3. Если (x, y)ÎR и (y, z)ÎR, то (x, z)ÎR (транзитивность).

Обычно отношение эквивалентности  обозначают знаком “=” или “ ”. Говорят, что это отношение задано на множестве А (но не на А²). Условия 1-3 в таких обозначениях выглядят более естественно:

1. x=x для всех xÎA (рефлексивность).
2. Если x=y, то y=x (симметричность).
3. Если x=y и y=z, то x=z (транзитивность).

Определение отношения порядка. Отношение R на множестве A² называется отношением порядка, если оно обладает следующими свойствами:

1. Если (x, y)ÎR и (y, x)ÎR, то x=y (антисимметричность).
2. Если (x, y)ÎR и (y, z)ÎR, то (x, z)ÎR (транзитивность).

Обычно отношение порядка обозначают знаком £. Если для двух элементов x и y выполняется x£y , то говорят, что x “предшествует” y. Как и для отношения эквивалентности, условия 1-3 в таких обозначениях выглядят более естественно:

1. x£x для всех xÎA (рефлексивность).
2. Если x £ y и y £ x, то x = y (антисимметричность).
3. Если x £ y и y £ z, то x £ z(транзитивность).

Определение функционального отношения. Отношение R на декартовом произведении двух множеств A₁´A₂ называется функциональным отношением, если оно обладает следующим свойством:

1. Если (x, y)ÎR и (x, z)ÎR, то y=z (однозначность функции).

Обычно, функциональное отношение обозначают в виде функциональной зависимости - (x, y)ÎR тогда и только тогда, когда y=f(x). Функциональные отношения (подмножества декартового произведения) называют иначе графиком функциональной зависимости.

N-арные отношения (отношения степени n).

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

 

ГЛАВА 3

ТЕОРИЯ БЕСКОНЕЧНЫХ  МНОЖЕСТВ

 

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

 

Понятие “мощность множества” введено основателем теории множеств Г. Кантором (1878), который установил, что мощность множества действительных чисел больше , и тем самым показал, что бесконечные множества могут быть расклассифицированы по их мощности.

Мощность множества в математике есть обобщение на произвольные множества понятия «число элементов». Мощность множества определяется методом абстракции как то общее, что есть у всех множеств, эквивалентных (количественно) данному; при этом два множества называемых эквивалентными, если между ними можно установить взаимно однозначное соответствие. Мощности называются часто кардинальными (т. е. количественными) числами.

 

3.2. Множество натуральных чисел