3.1.3. Задание отношений при помощи предикатов

Если для отношения , заданного на всем квадрате Х ² либо его части, возможности всего две (х у либо х у), то такой набор пар элементов (х, у) всегда может быть интерпретирован как область истинности некоторого двухместного предиката Р(х, у), заданного на Х ², который определяется следующим образом: P(х,y) = true, если х у, иначе P(х,y) = false.

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

Пример 3. Отношение из примера 1 можно задать при помощи предиката Р(х,у) = х  y , поскольку все пары (х, у), входящие в отношение и только они, удовлетворяют данному условию.

Пример 4. Х = R². Зададим отношение при помощи предиката Р(x, у) = «x больше у». Оно будет образовано парами (x, у) из области истинности предиката Р(x, у), которая на декартовой плоскости будет полуплоскостью, лежащей ниже прямой х = у.

Замечание. 1. В ряде случаев при задании отношения с помощью предикатов необходимо дополнительно уточнять условие непринадлежности пары элементов (х, у) отношению  — (х  у), поскольку отрицание предиката может быть интерпретировано неоднозначно.

2. Будем считать, что в исходном множестве А все элементы – разные и равенство элементов может означать только тождество элемента с самим собой. В случае одинаковых элементов в А для непротиворечивого задания отношения на него необходимо накладывать дополнительные ограничения.

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

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

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

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

2. Антирефлексивность: x X (х  х). Для всех x X пары (х, х) не принадлежат отношению .

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

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

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

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

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

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

5. Асимметричность: x,у X ((х  у)  (у  х)). Для всех x,у X из принадлежности пары (х, у) отношению  следует, что (у, х) обязательно не принадлежит .

Асимметричность – частный случай антисимметричности, отличается от нее тем, что главная диагональ матрицы полностью не входит в отношение, id   (иначе для пары (х, х) получим противоречие: (х  х) (х х)). Поэтому при выполнении данной аксиомы автоматически выполняется антирефлексивность.

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

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

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

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

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

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

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

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

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

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

x\y	p	q	r
p	1	0	1
q	1	1	0
r	0	1	0

Решение.

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

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

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

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