Глава 3.

Декартовым произведением двух множеств называется новое множество, состоящее из всех тех и только тех пар, т.е. кортежей длины 2, первая компонента которых принадлежит первому множеству, а вторая — второму.

Степенью S множества M называется декартово произведение S - одинаковых множеств, равных М.

Проекцией кортежа  на i-тую ось называется i-тая компонента кортежа .

Проекция множества М — это множество проекций кортежей из М.

График — это множество пар, т.е. множество, каждый элемент которого является парой или кортежем длины 2.

Инверсией кортежа  = <c, d> называется кортеж  = <d, c>.

Композицией двух кортежей  = <x, z> и  = <z, y> называется кортеж  = <x, y>.

Инверсией графика называют множество инверсий его пар (элементов).

График называется симметричным, если он наряду с любой своей парой содержит ее инверсию.

Диагональю множества X (|X| = n) называется график, содержащий пары вида <x₁, x₁>, <x₂, x₂>, …, <x_n, x_n>.

Композицией двух графиков P и Q называется график R тогда и только тогда, когда z такое, что <x, z>P & <z, y>Q.

График называется функциональным, если в нем нет пар с одинаковыми первыми и разными вторыми компонентами.

График называется инъективным, если в нем нет пар с различными первыми и одинаковыми вторыми компонентами.

Глава 4.

Отношение — это связь между любыми объектами в природе. Отношение — это пара множеств, причем упорядоченная, первая компонента которой является подмножеством квадрата второй компоненты.

Запись  = <Ф, М> называется отношением, , т.е. Ф  М  М, где  — отношение; Ф — график отношения; М — область задания отношения, представляющая из себя неупорядоченное множество.

Отношение называется бинарным, если Ф  М².

Отношение называется k-арным, если Ф  М^k.

Отношение  = <Ф, М> называется полным отношением, если для любых элементов x, y, принадлежащих множеству М, истинно высказывание, что элементы x, y находятся в отношении .

Отношение  = <Ф, М> называется пустым, если график Ф является пустым множеством.

Отношение  = <Ф, М> называется отношением равенства, если Ф = М.

Отношение  = <Ф, М> называется отношением неравенства, если Ф = М² \ М.

Инверсия отношения определяется через инверсию элементов его графика на заданном множестве.

Отношение  называется отношением рефлексивности, если для любого элемента х  М истинно высказывание х  х.

Отношение  = <Ф, М> называется отношением антирефлексивности, если (хМ)(х  х), т.е. М  Ф = .

Отношение  = <Ф, М> называют отношением симметричности, если (х,уМ)(х  у  у  х).

Отношение  = <Ф, М> называется транзитивным, если (х,у,zM)( х  у & у  z  x  z).

Отношение  называется отношением эквивалентности, если оно рефлексивно, симметрично и транзитивно.

Система W множеств называется разбиением одного множества М, если она удовлетворяет следующим условиям: подмножество обязательно должно включаться как в систему, так и в отдельное множество; подмножества разбиений не должны быть пустыми; подмножества должны быть разными и обязательно находиться в различных разбиениях; все подмножества разбиения в совокупности должны представлять множество М.

Отношение  на множестве М и разбиение этого множества сопряжены, если х,уМ х  у истина, тогда, когда х и у принадлежат одному и тому же блоку разбиения.

Отношение  = <Ф, М> называется связным, если выполняется условие М² \ М  Ф  Ф^-1.

Отношение  называется отношением нестрогого порядка, если оно транзитивно, рефлексивно и антисимметрично.

Отношение  называется отношением совершенно нестрогого порядка, если оно связно и является отношением нестрогого порядка.

Отношение  называется отношением совершенно строгого порядка, если оно связно и является отношением строгого порядка.

Отношение  называется отношением доминирования (х доминирует у) если х >> у, т.е. х в чем-то превосходит у.

Отношение  называется отношением квазипорядка, если оно транзитивно и рефлексивно.

Отношение  называется отношением толерантности, если оно рефлексивно и симметрично.