03. Произведение множеств. Бинарные отношения. Отношение эквивалентности

Определение. Пусть А и В - множества. Произведением множеств А и В называется множество всех упорядоченных пар (а, в), где аÎА и вÎВ. Произведение обозначается А´В.

А´В={(a, b):aÎA и bÎB}.

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

Примеры. 1) Если А = {a, b}, B = {0, 1}, C = Æ, то

А´В = {(a, 0), (a, 1), (b, 0), b, 1)},

B´A = {(0, a) (0, b), (1, a), (1, b)},

A´C = C´A = Æ.

2) Пусть R – множество действительных чисел. Тогда R2 – множество, которое обычно изображается в виде плоскости, а элементы из R2 называются точками плоскости.

3) Пусть [a, b], [c, d] – отрезки прямой. Тогда [a, b]´[c, d] – прямоугольник на плоскости.

Определение. Бинарным отношением (или просто Отношением) в А´В называется любое подмножество множества А´В.

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

2) Возьмем S = {(1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (1,7), (2,2), (2,4), (2,6), (3,3), (3,6)}. Ясно, что SÍA´B, т. е. S является бинарным отношением в A´B. Это отношение может быть охарактеризовано следующей формой

S = {(x, y)ÎA´B: xÎA является делителем yÎB}.

3) Пусть А некоторое множество, а B(А) множество всех его подмножеств. Множество B(А) называется Булеаном. Пусть W отношение в B(А) ´ B(А), задаваемое формой:

W = {(B, C)ÎB(A)´B(A): BÍC}.

Тогда W является отношением включения множеств.

Если S является некоторым отношением и (x, y)ÎS, то мы будем писать xSy и говорить, что x находится в отношении S с y.

Если S является отношением в А´А, то говорят, что S является отношением в А.

Пусть S некоторое отношение в А´В. Введем два множества:

DS = {aÎA: $bÎB: (a, b)ÎS},

RS = {bÎB: $aÎA: (a, b)ÎS}.

Множество DS называется областью определения отношения, а множество RS – областью значений. Если DS = A, то такое отношение называют всюду определенным, а если RS = B – Сюръективным. Когда отношение одновременно является сюръективным и всюду определенным, то говорят, что S Отношение на А´В (соответственно на А, если В=А).

Отношение S называется Инъективным, если из (a, b)ÎS и (c, b)ÎS следует, что а = с. Если отношение S является всюду определенным, инъективным и сюрьективным, то его называют Биективным .

Иногда отношения называются соответствием между элементами множества А и В.

Пусть S некоторое отношение в А´В. Введем отношение S-1 следующим образом: (у, х) ÎS-1 Û (х, у) ÎS. Отношение S-1 Назовем обратным отношением.

Определение. Отношение S на множестве А называется Отношением эквивалентности, если оно удовлетворяет следующим условиям:

1) аSа для "аÎА (Рефлексивность);

2) если аSв, то вSа (Симметричность);

3) если аSв и вSс, то аSс (Транзитивность).

В дальнейшем отношение эквивалентности будем обозначать значком ».

Определение. Пусть задано отношение эквивалентности на А. Множество ХÍА называется Классом эквивалентности для этого отношения, если оно удовлетворяет следующим условиям:

1) для любых хÎХ и уÎХ выполняется х » у;

2) если хÎХ, уÎА и х » у, то уÎХ.

Пусть на А задано отношение эквивалентности. Введем следующее обозначение:

[x] = {yÎA: x » y}.

Нетрудно видеть из определений, что [x] является классом эквивалентности. Его называют Классом эквивалентности, порожденным элементом х.

Лемма 1. Для классов эквивалентности [x] и [y] возможны только следующие два случая:

1) [x] = [y];

2) [x]Ç[y] = Æ.

Доказательство. Предположим, что [x]Ç[y]¹Æ и аÎ[x]Ç[y]. Тогда x » a и y » a. Покажем, что в этом случае один класс эквивалентности содержится в другом, а так как они равнозначны, то будет доказано равенство этих классов.

Пусть вÎ[x]. Тогда х » в, а » х, следовательно в » а. Но а » y, значит в » y и вÎ[y], т. е. [x]Í[y].

Пусть некоторое множество А представимо в виде:

А = Èa А, где Аa ÇАb = Æ , если a ¹ b.

В этом случае говорят, что {Aa} задает Разбиение А. Из доказанной леммы вытекает, что классы эквивалентности задают разбиение на А. Оказывается, верно и обратное.

Лемма 2. Если {Aa} - некоторое разбиение множества А, то отношение S, определяемое следующим условием: аSв Û $ a: аÎАa и вÎАa, является отношением эквивалентности.

Доказательство. По существу, в доказательстве нуждается лишь третье свойство эквивалентности. Пусть аSв и вSс. Тогда из задания отношения S вытекает следующее: $ a: аÎАa и вÎАa, а также $ b: вÎАb и сÎАb. Тогда вÎАa Ç Аb и из свойств разбиения следует, что Аa = Аb или a = b, следовательно, аÎАa и сÎАa. Это доказывает, что аSс и отношение S является отношением эквивалентности.

Теорема. Пусть S - некоторое отношение эквивалентности на А. Пусть {Аa} - разбиение множества А, порожденное этим отношением (лемма 1). Пусть Т - отношение эквивалентности, порожденное разбиением {Аa} (лемма 2). Тогда S=T.

Доказательство. Для доказательства напомним, что S и T являются подмножеством А´А и их равенство понимается как равенство множеств. Пусть (а, в)ÎS, т. е. аSв. Тогда а и в из одного класса эквивалентности, т. е. $ a: аÎАa и вÎАa. Это означает, что (а, в)ÎT и SÍT. Аналогично показывается обратное включение.

Задачи.

1. Доказать, что существуют А, В и С такие, что

А) А´В ¹ В´А;

Б) А´(В´С) ¹ (А´В) ´С.

2. Доказать, что если А, В, С и D не пусты, то

А) АÍВ и СÍD Û А´СÍВ´D;

Б) А=В и С=D Û A´C = B´D.

3. Доказать, что

А)(АÇВ)´(СÇD) = (А´С)Ç(В´D);

Б)(А´В)È(C´D) Í(AÈC)´(BÈD);

В)(АÈВ)´С=(А´С)È(В´С);

Г)А´(ВÈС)=(А´В)È(А´С);

Д)(АÈВ)´(CÈD)=(A´C)È(B´C)È(A´D)È(B´D);

Е)(А-В)´С=(А´С)-(В´С);

Ж)А´(В-С)=(А´В)-(А´С);-

З)А´В=(A´D)Ç(C´B), где АÍС и BÍD.

4. Найти область определения и область значений для отношений:

А) R={(x, y): x, yÎN и x делит y};

Б) R={(x, y): x, yÎN и y делит x};

В) R={(x, y): x, yÎR и x+y ³0};

Г) R={(x, y): x, yÎR и 2x>3y}.

5. Пусть R, S, T - некоторые отношения. Проверить справедливость равенств:

А) Ro(SoT) = (RoS)oT;

Б) (R-1)-1 = R;

В) (RoS)-1 = S-1oR-1.

6. Пусть на множестве А заданы отношения R1 и R2. Доказать:

А) если отношения R1 и R2 рефлексивны, то рефлексивны отношения R1ÈR2, R1ÇR2, R1-1, R1oR2;

Б) если отношения R1 и R2 иррефлексивны (т. е. для " ХÎ А не выполняется ХRХ), то иррефлексивны R1È R2, R1ÇR2, R1-1, суперпозиция R1оR2 может быть иррефлексивной;

В) если отношения R1 и R2 симметричны, то симметричны отношения R1ÈR2, R1ÇR2, R1-1, R1oR2-1;

Г) отношение R1oR2, где R1 и R2 симметричны, симметрично тогда и только тогда, когда R1oR2 = R2oR1;

Д) если отношения R1 и R2 антисимметричны, то антисимметричны R1ÇR2, R1-1.

7. Пусть А - конечное множество, n - число его элементов. Доказать, что число подмножеств множества А, состоящих из m элементов, где 0£ m £n, равно

8. Пусть r - отношение, обладающее свойством рефлексивности и транзитивности в множестве А. Определим для а, bÎА отношение R, полагая аRb, если аrb и brа.

А) Доказать, что R есть отношение эквивалентности на А.

В) Доказать, что если аRа', bRb' и аrb, то а'rb'.

9. Во множестве Z+´Z+ положим по определению (а, b)r(с, d), если а+d=b+с. Доказать, что r является отношением эквивалентности на данном множестве.

«Понятие функции такое же основное, как и понятие множества» Хаусдорф

< Предыдущая		Следующая >