Определение. Пусть А и В - множества. Произведением множеств А и Вназывается множество всех упорядоченных пар (а, в), где аÎА и вÎВ. Произведение обозначается А´В.
А´В={(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] – прямоугольник на плоскости.
Определение. Бинарным отношением(или просто отношением) в А´В называется любое подмножество множества А´В.
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. Аналогично показывается обратное включение.
