§ 3. Свойства отношений

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

Определение. Пусть — отношение на множест­ве А. Тогда:

а) рефлексивно, если х х для любого х А;

б) симметрично, если х у влечет у х;

в) транзитивно, если х у и y z влечет х z;

г) антисимметрично, если х у и у х влекут х = у.

Терминология, введенная здесь, вероятно, является новой для читателя, однако он, по-видимому, знаком с этими понятиями. Поясним их на следующих примерах.

Пример 3.1. Пусть

= {(х, у): х, у N и х — делитель y},

= {(х, у): х, у N и х < у},

={(х, у): х, у N\{1} и х и y имеют общий делитель}.

Тогда :

а) рефлексивно, так как х/х = 1 для всех x N;

б) несимметрично, поскольку 2 — делитель 4, но 4 не является делителем 2;

в) транзитивно, так как если у/х N и z/y N, то

z/x=(y/x) (z/y) N;

г) антисимметрично, так как если х/y N и y/x N, то х = y.

Аналогично :

а) рефлексивно, так как х ≤ х для всех x N;

б) несимметрично, так как 2 ≤ 3, но 3 ≤ 2;

в) транзитивно;

г) антисимметрично, так как если х ≤ у и у ≤ х, то х = у.

Наконец, рефлексивно и симметрично, но не тран­зитивно или антисимметрично. //

Пример 3.2. Пусть P — множество всех людей, а A и S определяются следующим образом:

А = {(х, у): х, у P и х — предок у},

S = {(х, у) Р и х и у имеют одних и тех же родителей).

Очевидно, что A транзитивно, a S рефлексивно, симме­трично и транзитивно. //

Заметим, что свойства симметричности и антисимме­тричности не являются взаимоисключающими. Для лю­бого множества X отношение I_X является симметричным и антисимметричным. (Проверьте!) Мы можем также иметь отношения, которые не являются ни симметрич­ными, ни антисимметричными.

Пример 3.3. Пусть опять P есть множество всех людей. Определим отношение B такое, что хBу тогда и только тогда, когда х является братом у. В семье, состоя­щей из двух братьев p и q и сестры r, мы имеем ситуа­цию, изображенную на рис. 2.6. Отношение B не сим­метрично, так как pBr, но не rBp. Это отношение также не является антисимметричным, так как pBq и qBp, хо­тя p и q различны.

В более общей ситуации мы можем интерпретировать рассмотренные выше характеристики отношения путем построения диаграммы:

а) отношение рефлексивно тогда и только тогда, когда для каждого узла (точки) на диаграм­ме существует стрелка, которая начинается и заканчивается на этом узле;

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

в) отношение транзитивно тогда и только тогда, когда для каждой пары узлов х и у, связанных последовательностью стрелок от x к a₁, от a₁ к a₂, ..., от a_n-1_к a_n от a_n к у, существует также стрелка от х к у;

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

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

Упражнение 2.3.

1. Являются ли следующие отношения рефлексивны­ми, симметричными, транзитивными или антисимметричными:

а) отношение на {1, 2, 3, 4, 5} определяется как

{(а, b): a-b четное};

б) отношение на {1, 2, 3, 4, 5} определяется как

{(а, b): a+b четное};

в) отношение на P (множестве всех людей) определяется как

{(а, b): а и b имеют общего предка}?

2. Следующее утверждение ошибочно. Симметричное и транзитивное отношение на S является также рефлек­сивным, так как aRb и bRa влекут aRa, Внимательно изучив определения, найти ошибку. Построить отноше­ние на {1, 2, 3}, которое является симметричным и тран­зитивным, но не рефлексивным.

3. Пусть — отношение между A и B, а A. Тогда (a) определено как множество {b: a b} и является под­множеством В. Пусть на {-4, -3, -2, -1, 0, 1, 2, 3, 4} определены следующие отношения:

= {(х, у): х, у N и х — делитель y},

= {(х, у): х, у N и х < у},

={(х, у): х, у N\{1} и х и y имеют общий делитель}.

= {(a, b): a <b},

= {(a, b): b – 1 < a <b+2},

={(a, b): a² ≤ b},

Какие это множества:

а) (0); б) (0); в) (0);

г) (1); д) (-1); е) (-1)?