Классификация антисимметричных отношений

Классификация рефлексивных отношений

Отношение R называется рефлексивным, если для всех х пара (х, х) входит в R (все петли ∈ в граф).

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

Граф антирефлексивного отношения не содержит ни одной петли. Граф рефлексивного отношения содержит все петли.

Отношение R называется симметричным, если всегда, когда пара (х, y) входит в R, то и пара (y, x) входит в R (инверсия R совпадает с R). (С)

Отношение R называется антисимметричным, если в него входит не более одной из каждых двух пар (х, y) или (y, x). (АнтиС)

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

Отношение называется полносвязным (П), если для всех х,у в него входит хотя бы одна из двух пар: (х,у) или (у,х).

Отношение называется слабо полносвязным (СП)(слабосвязным), если для всех неравных х,у в него входит хотя бы одна из двух пар: (х,у) или (у,х).

Отношение R называется транзитивным, если всегда, когда две пары (х, у) и (у,z) входят в R, то и пара (х,z) тоже входит в R.

Отношение R называется ацикличным, если из наличия какого-либо пути между вершинами соответствующего графа следует отсутствие обратной дуги (обратного пути) между этими вершинами (в графе отсутствуют любые циклы).

В ацикличном отношении не должно быть никаких циклов (в т.ч. – ни петель, ни колец).

Отношение R называется негатранзитивным, если отсутствие дуг от х к у и от у к z приводит к отсутствию дуги от х к z.

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

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

Отношение толерантности (безразличия) определяется наличием свойств рефлексивности и симметричности.

Строгим порядком (строгим предпочтением, сильным порядком, строгим линейным порядком) называется антирефлексивное, транзитивное, слабосвязное бинарное отношение (12).

Строгий порядок является частным случаем слабого порядка (строгого частичного предпочтения) с дополни-тельным условием слабосвязности.

Пример: Отношение "строго меньше" на множестве целых чисел.