АкушерствоАнатомияАнестезиологияВакцинопрофилактикаВалеологияВетеринарияГигиенаЗаболеванияИммунологияКардиологияНеврологияНефрологияОнкологияОториноларингологияОфтальмологияПаразитологияПедиатрияПервая помощьПсихиатрияПульмонологияРеанимацияРевматологияСтоматологияТерапияТоксикологияТравматологияУрологияФармакологияФармацевтикаФизиотерапияФтизиатрияХирургияЭндокринологияЭпидемиология

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

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

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

Произведение двух множеств часто называют прямым или декартовым произведением. Заметим, что произведение 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 – множество действительных чисел. Тогда R² – множество, которое обычно изображается в виде плоскости, а элементы из R² называются точками плоскости.

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 некоторое отношение в А´В. Введем два множества:

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

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

Множество D_S называется областью определения отношения, а множество R_S – областью значений. Если D_S = A, то такое отношение называют всюду определенным, а если R_S = 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.

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

Лемма 2. Если {A_a} - некоторое разбиение множества А, то отношение 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. Аналогично показывается обратное включение.

Дата добавления: 2015-09-27 | Просмотры: 502 | Нарушение авторских прав