Рис. 0.1. Диаграмма Веипа для включения множеств: А<В.

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

Существует несколько основных операций над множествами, с помощью которых можно строить новые множества.

Определение. Пусть А и В - множества. Объединением множеств А м В (записывается >1 и £f) называется множество, содержащее все элементы из А вместе со всеми элементами из В. Формально А[} В== {х\х А или хВ\).

Пересечением множеств А \\ В (записывается Л П ) называется множество, состоящее из всех тех элементов, которые принадлежат обоим множествам А и В. Формально А(]В = \х\хА н хеВ}.

Разностью множеств А и В (записывается А-В) называется множество тех элементов из Л, которые не принадлежат В.

Если Л - множество всех элементов, рассматриваемых в данной ситуации (иногда его называют универсальным и обозначают через U), то разность U - В часто обозначается В и называется дополнением множества В.

Заметим, что мы говорим об универсальном множестве как о множестве всех элементов, „рассматриваемых в данной ситуации". При этом мы должны быть уверены в том, что U существует. Например, если взять в качестве U „множество всех множеств*, то снова получится парадокс Рассела. Заметим также, что В не определено, если не ясно, по отношению к какому универсальному множеству рассматривается операция дополнения.

) Заметим, что существование множества Ли не гарантировано, так что возможность определения с помощью предиката вызывает сомнение. В аксиоматической теории множеств существование множества A\JB принимается за аксиому.

0.1. ОСНОВНЫЕ понятия ТЕОРИИ МНОЖЕСТВ

Вообще Л -Бл П . Диаграммы Венна для этих операций над множествами показаны на рис. 0.2.

Если АС\В = 0, то говорят, что А п В не пересекаются.

Определение. Пусть / - некоторое множество, элементы которого используются как индексы, и для каждого 11 множество Л/ уже известно. Через U Л/ обозначим множество {X \ суще-

ствует такое iI, что XAi}. Так как / может не быть конечным, то это определение обобщает определение объединения двух

A\J5 АПВ А~В

Рис. 0.2. Диаграммы Венна для операций над множествами.

множеств. Если множество / определено с помощью предиката Р(0, то иногда пишут U Л,- вместо U Л/. Например, U Л,- оз-

P(i) iel i> 2

начает AU A[j Ar,[J ... .

Определение. Пусть Л-множество. Множество всех подмножеств множества Л будем обозначать через (Л) или 2-, т. е. {А) = {В I ВА\).

Пример 0.4. Пусть Л = -1,2}. Тогда 5> (Л) = {0, {!}, {2}, {1,2}}. Другой пример: &{0) = {0\. □

Вообще, если Л - конечное множество, состоящее из т элементов, то 3 (А) состоит из 2" элементов. Пустое множество является элементом множества 5* (Л) для любого Л.

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

) Существование множества всех подмножеств для любого множества - аксиома теории множеств. Другими аксиомами теории множеств, в дополнение к этой и к ранее упомянутой аксиоме об объединении, являются следующие;

(1) Если Л -множество и Р -предикат, Toj-K Р (Л) и X Л} -множество.

(2) Если X -атом нлп множество, то л} -множество.

Ci) Если Л -множество, то {X существует У, для которого ХУ и УМ - множество.

0.1.3. Отношения

Многие распространенные математические понятия, такие, как принадлежность, включение множеств, числовое неравенство, являются отношениями. Мы дадим формальное определение понятия отношения и посмотрим, как под это определение подходят известные примеры отношений.

Определение. Пусть А и В - множества. Отношением из А в В называется любое подмножество множества Ах В. Если Л = В, то говорят, что отношение задано, или определено, на А (или просто, что это - отношение на множестве Л). Если - отно-нгеиие из Л в й и (а, b)R, то пишут aRb. Множество Л называют областью определения отношения а множество В-множеством его значений.

Пример 0.6. Пусть Л--множество целых чисел. Отношение < представляет собой множество {{а,Ь)\а Меньше Ь]. Как и следовало ожидать, для таких пар (а, Ь) мы будем писать а<Ь. □

Определение. Отношение {(&, а) \ {а, b)R} называется обратным к отношению R и часто обозначается через R~.

Понятие отношения очень общее. Часто отношение обладает рядом свойств, для которых установлены специальные названия.

Определение. Пусть Л -множество и / - отношение на Л. Отношение R называется

(1) рефлексивным, если aRa для всех а из Л,

(2) симметричным, если aRb влечет bRa для а и b из Л,

(3) транзитивным, если aRb и bRc влекут aRc для а, b }1с из Л. Элементы а, Ь \i с не обязаны быть различными.

Рефлексивное, симметричное и транзитивное отношение называется отношением эквивалентности.

Важное свойство любого отношения эквивалентностиопределенного на множестве Л, заключается в том, что оно разбивает множество Л на непересекающиеся подмножества, называемые классами эквивалентности. Для каждого элемента аА обозначим через [а] класс эквивалентности, содержащий а, т. е. множество {b\aRb).

Пример 0.7. Рассмотрим отношение сравнения по модулю Л, определенное на множестве неотрицательных целых чисел. Говорят, что а сравнимо с b по модулю N, и пишут аЬ {mod N)j если существует такое целое число k, что a - b = kN. Пусть, например, Л/" = 3. Тогда множество {О, 3, 6, ..., Зп, ...} будет одним из классов эквивалентности, поскольку Зп Зт(mod 3) для любых целых чисел тип. Этот класс обозначим через [0]; можно взять также [3], или [б], или [Зп], поскольку любой элемент класса эквивалентности является представителем этого класса.

Другие два класса эквивалентности отношения сравнения по модулю 3 таковы:

[1]{1,4,7, ...,Зя + 1, ...} [2]-{2,5.8, .,3/2 + 2, ...}

Объединение трех множеств [0], [1] и [2] совпадает с множеством всех неотрицательных целых чисел. Таким образом, это отношение эквивалентности разбивает множество всех неотрииатель-Ных целых Чисел на три непересекающихся класса эквивалентности [0], [1] и [2] (рис. 0.3). □

нетрицтелшт ц&гтх чисел

Рис. 0.3. Классы эквивалентности отношения сравнения по модулю 3.

Индексом отношения эквивалентности, определенного на множестве Л, называется число классов эквивалентности, на которые разбивается множество Л этим отношением.

Определение. Пусть а и b-объекты. Через {а, Ь) обозначим упорядоченную пару, состоящую из объектов л: и взятых в этом порядке. Упорядоченные пары [а, Ь) и [с, d) называются равными, если а -с и b = d. В противоположность этому {а, Ь} = {Ь, а\.

Упорядоченные пары можно рассматривать как множества, если определить [а, Ь) как множество {а, {а, Ь\\. Мы оставляем в качестве упражнения доказательство того, что {а, {а, Ь\} = -{c,\c,d}} тогда и только тогда, когда G=b и cd. Таким образом, это определение согласуется <: тем, что можно считать фундаментальным свойством упорядоченных пар.

Определениё. Декартовым произведением множеств А м В, обозначаемым через ЛхВ, называют множество {{а, Ь)\аА и

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

0.1.4. Замыкание отношений

Для данного отношения R часто бывает нужно найти другое отношение R, включающее R и обладающее некоторыми дополнительными свойствами, например транзитивностью. Более того, обычно хочется, чтобы R было как можно „меньше", т. е. чтобы оно было подмножеством любого другого отношения, включающего R и обладающего желаемыми свойствами. Конечно, это „наименьшее" отношение может определяться неоднозначно, если дополнительные свойства какие-нибудь странные. Однако для тех распространенных свойств, которые упоминались в предыдущем разделе, часто можно однозначно найти наименьшее надмножество данного отношения, обладающее этими свойствами. Далее мы рассмотрим некоторые частные случаи.

Определение, k-я степень отношения R на множестве А (обозначаемая R), определяется следующим образом:

(1) aRb тогда и только тогда, когда aRb\

(2) aRb для i > 1 тогда и только тогда, когда существует такое сА, что aRc и cR~b.

Это пример рекурсивного определения; таким методом определения мы будем пользоваться много раз. Чтобы уяснить себе рекурсивный аспект этого определения, допустим, что aRb. Тогда, по (2), существует такое Cj, что aRc и cRb. Снова применяя (2), видим, что существует такое с, что cRc и cR-b. Еще одно применение (2) говорит о том, что существует такое Cg, что cRc н cRb. Теперь можно применить (1) и убедиться, что cRb.

Таким образом, если aR*b то существует такая последовательность элементов б\, бз, из Л, что aRc, cRc, cRcm cRb.

Транзитивное замыкание отношения R на множестве Л обозначается через R+ и определяется так: aRb тогда и только тогда, когда aRb для некоторого il. Мы увидим, что R+ - наименьшее транзитивное отношение, включающее R.

Можно было бы иначе определить 7? + , сказав, что а/+б, если существует такая последовательность с, Cg, ..., с,, состоящая из

нуля или более элементов, принадлежащих Л, что a/Cj, Cj/Cg, ... ..., Cri iRc, CiRb. Если л -О, то полагаем aRb.

Рефлексивное и транзитивное замыкание отношения R на множестве Л обозначается через 7?* и определяется следующим образом:

(1) aR*a для всех аЛ;

(2) aRb, если aR+h]

(3) в R* нет ничего другого, кроме того, что содержится там в силу (1) или (2).

Если определить R*, сказав, что aRb тогда и только тогда, когда а = Ь, то aR*b тогда и только тогда, когда aRb для некоторого 10.

Единственное различие между и R* состоит в том, что aRa истинно для всех аА, но aRa может быть, а может и не быть истинным. /?*это наименьшее рефлексивное и транзитивное отношение, включающее R.

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

Теорема 0.2. Если R и -соответственно транзитивное и рефлексивно-транзитивное замыкание отношения R, то

(а) R+ транзитивно и если R - любое транзитивное отношение, для которого R R, то R+R;

(б) R* рефлексивно и транзитивно и если R-любое рефлексивное и транзитивное отношение, для которого RR\ то RR.

Доказательство. Докажем только (а); утверждение (б) оставим в качестве упражнения. Во-первых, чтобы показать, что R транзитивно, нужно показать, что если aRb и bR+c, то aRc. Так как aRb, существует такая последовательность элементов dj, ..., что dRd, ..d„ Rd, где =а и d,b. Так как bR+c, то можно найти такие е, ..е,„, что e-Re, ..e jRe, где e = b = dj и еггс. Отсюда, используя определение R, заключаем, что aR+c.

Теперь покажем, что R- - наименьшее транзитивное отношение, включающее R. Пусть R - любое транзитивное отношение, для которого RR\ Надо показать, что R+R. Пусть {tb)R\ т. е. aRb. Тогда существует такая последовательность Ci, ...,с„, что uCj, b = c}\ CiRci+i для l<i</z. Так как RR, получаем C;/?c,-+i для 1<1</г. Так как R транзитивно, повторное применение определения транзитивности дает

В качестве упражнения предлагаем доказать следующую теорему об отношениях эквивалентности:

Теорема 0.1. Пусть R - отношение эквивалентности на А. Тогда ля всех а и b из А либо [а\ = [Ь], либо [а\ и {Ь\ не пересекаются.

Доказательство. Упражнение. П