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

1 способо
i-ая строка соответствует элементу хi,
j-ый столбец элементу хj,
на их пересечении ставится 1, если отношение хiАхj выполнено,
0, если нет.
Так, единица, стоящая на пересечении 4ой строки и 1го столбца, соответствует тому, что игрок х4 выиграл у игрока х1, т.е. <х4Ах1>.

На множестве М отношение
«xi – победитель yj» задано матрицей

Если aij≡0 (i, j = 1,n) , то имеем пустое
отношение, т.е. такое, которое не выполнено
ни для какой пары хiхj.
Если aij≡1, имеем полное отношение, т.е. отношение, выполненное для всех пар.
Единичная матрица Е задает диагональное отношение, отношение равенства:
<хiАхj>, если хi=хj.

2 способ
Элементы множества изобразим точками, проведем стрелку от хi к хj, если выполнено хiАхj, получим фигуру – ориентированный граф.
Точки х1, х2, х3, х4, х5 – вершины графа, направленные линии – ребра графа.

Свойства отношений:
Отношение А рефлексивно, если оно выполнено между объектом и им самим, т.е. хАх.
Отношения «быть похожим», «быть знакомым» – рефлексивны. Отношение «быть братом» – нерефлексивно.

2) Если отношение А может выполняться лишь для несовпадающих объектов, то оно антирефлексивно, т.е. из хАу следует, что х≠у.
3) Отношение А называется симметричным, если при выполнении хАу выполнено уАх.
Отношения «быть родственником», «быть похожим на» – симметричны.

4) Отношение А называется антисимметричным, если из двух отношений хАу и уАх хотя бы одно не выполнено. Так, приведенный выше пример: отношение «x – победитель y» – антисимметрично.
Теорема:
если отношение антисимметрично,
то оно антирефлексивно.

5) Отношение называется транзитивным, если при выполнении хАу и уАz выполнено хАz.
Примером является отношение «быть больше (меньше)»:
если х<у и у

Отношение эквивалентности определяется отображением множества Х на множество Y и характеризуется разбиением множества Х на классы.
Отношение эквивалентности – рефлексивно, симметрично и транзитивно

Отношение А на множестве М называется толерантностью, если оно рефлексивно и симметрично.
Пример: отношение «быть знакомым»
Отношение А на множестве Х называется отношением порядка, если оно транзитивно и антирефлексивно.
Пример: отношение x

Множество, на котором задано отношение порядка, называется упорядоченным множеством.
Биективное отображение “f” в упорядоченном множестве Х на упорядоченное множество Y называют соответствием подобия или подобным соответствием, если оно сохраняет порядок.