Аксиомы на отношениях

Тип отношений может быть установлен путем проверки справедливости некоторых их элементарных свойств, которые также называют аксиомами. Рассмотрим их общие формулировки, а также структурные свойства отношений, вытекающие из выполнения данных аксиом.

1. Рефлексивность: "x Î X (х r х). Запись означает, что для всех элементов x Î X пары (х, х) принадлежат отношению r.

При выполнении рефлексивности id_A Ír , в отношение входят все пары из одинаковых элементов (х, х), которые в его матрице располагаются на главной диагонали.

2. Антирефлексивность: "xÎ X (х Ør х). Для всех xÎ X пары (х, х) не принадлежат отношению r.

В случае антирефлексивности ни одна из пар id_A не входит в отношение. Если не выполняется ни рефлексивность ни антирефлексивность, то это свидетельствует о том, что часть диагонали принадлежит отношению, а часть – нет (либо на ней отношение вообще не определено).

3. Симметричность: "x, у Î X (х r у ® у r х). Для всех x, уÎ X из принадлежности пары (х, у) отношению rследует принадлежность отношению rсимметричной ей пары (у, х).

Матрица такого отношения симметрична по вхождению пар в него относительно главной диагонали.

4. Антисимметричность: "x, уÎ X ( (х r у)и (уr х) ® х=у). Для всех x,уÎ X из одновременной принадлежности пар (х, у)и (у, х) отношению rследует, что х и у — один и тот же элемент. При выполнении антисимметричности:

1) для всех различающихся элементов х и у на симметричных относительно главной диагонали матрицы элементах (х, у), (у, х), вхождение в отношение должно быть противоположным (например, (х r у) и (уØr х)) либо отрицательным, при котором (хØr у)и (у Ør х);

2) пары из одинаковых элементов (х, х) — на главной диагонали матрицы ― могут как входить, так и не входить в отношение.

5. Асимметричность: "x,уÎ X ((х r у)® (у Ør х)). Для всех x,уÎ X из принадлежности пары (х, у)отношению rследует, что (у, х) обязательно не принадлежит r.

Асимметричность – частный случай антисимметричности, отличается от нее тем, что главная диагональ матрицы полностью не входит в отношение, id Ë r (иначе для пары (х, х)Îr получим противоречие: (х r х)® (хØr х)). Поэтому при выполнении данной аксиомы автоматически выполняется антирефлексивность.

6. Транзитивность: " x, у, zÎ X ((х r у)и (уr z)® (х r z)). Для всех x,у,zÎX из принадлежности пар (х, у)и (у, z) отношению rвытекает принадлежность ему и пары (х, z).

Транзитивность означает для всех возможных наборов элементов x,у,z следующее: если пары (х, у)и (у, z)входят в отношение, то пара (х, z), стоящая в матрице отношения на пересечении строки, соответствующей х, и столбца, соответствующего z, также должна входить в отношение. Нарушение данного свойства хотя бы для одной тройки x,у,z (при котором обязательно должны выполняться три условия:(х r у), (у r z)и(х Ør z)) означает отсутствие транзитивности.

В аксиоме транзитивности все три элемента в дальнейшем будем считать различными, иначе аксиома превращается в тривиальные равенства, например, при х = у: (у r z)® (у r z). Отсюда следует, что для отношений на множествах с числом элементов меньше 3, аксиома транзитивности всегда выполняется.

Пример 1. Проверить справедливость аксиом 1) —6) для отношения, заданного в примерах 1 — 3.

Решение. Проверку проще всего производить по матрице отношения, приведенной в примере 2.

1. Главная диагональ матрицы (пары (0, 0) и (1, 1)) целиком входит в отношение, следовательно, оно рефлексивно и не является антирефлексивным.

2. На двух парах, симметричных относительно главной диагонали ((0, 1) и (1, 0)), вхождение противоположное: 0r 1, и 1Ør 0. Других пар недиагональных элементов нет. Поскольку главная диагональ входит в отношение, оно является антисимметричным, но не асимметричным.

3. Как показано выше, при двух элементах в множестве транзитивность выполняется всегда.

Ответ: заданное отношение рефлексивно, антисимметрично и транзитивно.

Пример 2. Проверить справедливость аксиом 1)—6) для отношения, заданного на множестве Х ={p,q,r}, следующей матрицей:

Решение.

1. Диагональные элементы (p, p), (q, q)входят в отношение, (r, r) — нет, следовательно, для отношения не выполняется ни аксиома рефлексивности, ни аксиома антирефлексивности.

2. На всех парах, симметричных относительно главной диагонали, вхождение противоположное. Поскольку на главной диагонали есть пары, входящие в отношение, оно является антисимметричным, но не асимметричным.

3. Проверим транзитивность. Пары (q, p), (p, r)входят в отношение, пара (q, r) — не входит. Следовательно, транзитивность не выполняется.

Ответ: для заданного отношения справедлива только аксиома антисимметричности.