В соответствии с определением I, для равенства двух множеств, требуется совпадение их элементов. Поэтому сначала доказывается, что для произвольного элемента а из того, что , следует, что , затем доказывается, что если , то . Таким образом, элементы множеств X и Y совпадают и, следовательно, по определению I, Х = Y.

В соответствии с определением II Х = Y, если и . Поэтому, для доказательства равенства двух множеств, требуется показать справедливость включений и .

Пример 1. Доказать справедливость соотношения

.

Предположим, что произвольный элемент , т.е. что . Это значит, что и , значит и .

Следовательно, .

Пусть теперь некоторый элемент , т.е. и . Это значит, что и , т.е. .

Следовательно, .

Таким образом, доказано, что .

Пример 2. Докажем по другому справедливость соотношения

.

Пусть имеем U = {0,1,2,3,4,5,6,7,8,9}, A = {0,1,3,7}, B = {2,3,4,6,7}.

Определим левую часть:

= {0,1,3,7} {2,3,4,6,7} = {0,1,2,3,4,6,7},

= U\( ) = {0,1,2,3,4,5,6,7,8,9}\{0,1,2,3,4,6,7} = {5,8,9}.

Определим правую часть:

= U\A = {0,1,2,3,4,5,6,7,8,9}\{0,1,3,7} = {2,4,5,6,8,9},

= U\B ={0,1,2,3,4,5,6,7,8,9}\{2,3,4,6,7} = {0,1,5,8,9},

= {2,4,5,6,8,9} {0,1,5,8,9} = {5,8,9}.

Как видим, левая часть равна правой, следовательно, соотношение справедливо.

Пример 3. Доказать справедливость соотношения

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

Используем соотношение

X\Y = .

Левая часть

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

Правая часть

A\(B C) =

Как видим, левая часть равна правой, следовательно, соотношение справедливо.

Пример 4. Доказать справедливость соотношения

.

Это свойство дистрибутивности слева объединения относительно пересечения .

• Такое доказательство может быть выполнено с помощью диаграмм Эйлера–Венна (см. пример 2, § 1.3). Здесь для этих целей используем один из приемов доказательства равенства двух множеств.

В соответствии с первым определением равенства множеств множества равны, если их элементы совпадают. Это означает, что Х = Y, если из того, что , следует , и из того, что , следует .

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

Пусть .

Из определения операции объединения следует, что элемент а принадлежит объединению множеств А и , если он принадлежит хотя бы одному из них (или, что очевидно, тому и другому). Таким образом, или , при этом возможны следующие случаи:

1.1. а принадлежит множеству А и а не принадлежит пересечению множеств :

и .

Последнее условие выполняется, если а не принадлежит В, или С, или им обоим, т.е.

1.1.1. ;

1.1.2. ;

1.1.3. ;

1.2. и , т.е. ;

1.3. и , т.е.

Рассмотрим каждый из этих случаев.

1.1. Так как , то а принадлежит объединению множества А с любым множеством, в том числе и ; следовательно, а принадлежит и их пересечению:

.

1.2. Так как , , то и , следовательно, .

1.3. Так как , то этого достаточно, чтобы и , следовательно, .

Таким образом, в любом из рассмотренных случаев из того, что , следует, что .

2. Покажем теперь справедливость второго условия определения I равенства множеств: если произвольный элемент а не принадлежит левой части соотношения , то он не принадлежит и правой части данного соотношения .

Пусть теперь: .

Элемент а не принадлежит объединению двух множеств, если он не принадлежит ни одному их них. Тогда и , т.е. возможны следующие случаи (см. п. 1.1):

2.1. ;

2.2. ;

2.3. ;

Рассмотрим каждый из этих случаев:

2.1. Так как , то , следовательно, .

2.2. Так как , то , следовательно, .

2.3. Так как , то этого достаточно, чтобы , следовательно, .

Как видим, в любом из этих случаев из того, что , следует, что .

Таким образом, множества и совпадают и по определению равенства множеств

,

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

Примечание: В примере 4 проверка условий 1.1.3 и 2.3 избыточна.

Пример 5. Доказать справедливость соотношения

.

Это свойство дистрибутивности справа пересечения относительно объединения .

Далее будем использовать символ , который в выражениях типа Р Q будет означать: "если справедливо Р, то справедливо и Q" или "из того, что Р, следует Q" и т.п., а символ в выражениях типа P Q будет означать: "тогда и только тогда, когда", "если и только если" и т.п.

• Множества Х = Y, если и .Поэтому покажем сначала, что , т.е. любой произвольный элемент а из множества, заданного левой частью соотношения, принадлежит и множеству, заданному правой частью соотношения.

Пусть . Тогда

и

( или ) и ( )

( и ) или ( и )

или

.

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

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

Пусть . Тогда

или

( и ) или ( и )

( или ) и

( и

Следовательно, .

Таким образом, , что и требовалось доказать.

Примечание: В примере 5, в силу точного совпадения второй части доказательства с первой, можно записать:

 и  и т.д.

1.7. Контрольные вопросы

2. СООТВЕТСТВИЯ

Соответствие – способ задания взаимосвязей между элементами множества. Частными случаями соответствий являются функции, отображения, преобразования, отношения.

2.1. Соответствия и их свойства

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

Таким образом, чтобы задать соответствие надо задать

• Множество A;

• Множество B;

• Множество , задающее правило соответствия, т. е. перечисляющее все пары (a, b), для которых справедливо соответствие.

Записывается это так g = (A, B, G).

Множество A называется областью отправления соответствия, множество B – областью прибытия соответствия, G – называется графиком соответствия.

С соответствием связаны еще два понятия:

область определения соответствия G – элементы множества A, участвующие в соответствии, пр₁G = {а:(a, b) G} и

область значений соответствия G – элементы множества B, участвующие в соответствии, пр₂G = {b:{а, b) G} (рис. 2.1).

Если (а, b) G, то говорят, что "b соответствует а при соответствии G ". Геометрически это обозначается стрелками (рис. 2.1).

Пример 1. Пусть имеем множества A = {1, 2}, B = {3, 5}.

Элементы этих множеств образуют такие пары

A B = {(1, 3), (1, 5), (2, 3), (2,5)}.

Из приведенных пар можно составить несколько соответствий, например, такие

G₁ = {(1, 3)}. Для этого соответствия Пр₁G₁ = {1}; Пр₂G₁ = {3}.

G₂ = {(1, 3), (1,5)}. Здесь Пр₁G₂ = {1}; Пр₂G₂ = {3, 5}.

Свойства соответствий :

• Всюду (полностью) определенное соответствие – если пр₁ G = A.

Частично определенное соответствие – в противном случае.

• Сюръективное соответствие – если пр₂ G = В.

Р
исунок 2.1

Образом элемента а в множестве В при соответствии G называется множество всех b В, соответствующих элементу а А.

Прообразом элемента b в множестве А при соответствии G называется множество всех а А, которым соответствует b В.

Образом множества называется объединение образов всех элементов а С.

Прообразом множества называется объединение прообразов всех элементов b D.

• если любой элемент множества A, участвующий в соответствии, имеет единственный образ в множестве B и наоборот, любой элемент множества B, участвующий в соответствии, имеет единственный прообраз в множестве A, то соответствие называется инъективным.

• если образом любого элемента а из области определения пр₁G является единственный элемент b из области значений пр₂G, то соответствие называется однозначным или функциональным.

• взаимно однозначное соответствие, которое всюду определено, сюръективно, функционально, и в котором прообразом любого элемента b из области значений пр₂G является единственный элемент а из области определения пр₁G, называется биекцией. Такое соответствие инъективно.

Если между множествами А и В существует взаимно однозначное соответствие, то мощности этих множеств равны, т.е. |А| = |В|. В таком случае говорят, что множества A и В равномощны.

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

Пусть дано соответствие . Тогда соответствие G^–1 называется обратным к G , если G^–1 таково, что (b, а) G^–1 тогда и только тогда, когда (а, b) G. обратное соответствие обозначается