Бинарные отношения на множестве

Отношение А А называется отношением на A. Такие отношения называются также бинарными отношениями на множестве A. То есть отношение на A - это отношение между элементами одного и того же множества A.

Для таких отношений можно выделить несколько специальных свойств.

1. Рефлексивность

Отношение А А является рефлексивным, если
.

Простейшее рефлексивное отношение на A - это множество, состоящее из всех пар вида (a, a), где a A. Такое отношение называется единичным отношением или диагональю и обозначается как e.

2. Симметричность

Отношение А А - является симметричным, если
" a, b Î A (a r b Þ b r a).

То есть отношение А А симметрично, если для любых a и b из того что (a, b) следует, что пара (b, a) .

Поэтому отношение r несимметрично, если хотя бы для одной пары (a, b) не выполняется указанное свойство. Нетрудно видеть, условие симметричности равносильно условию:

" a, b Î A (a r b Û b r a).

3. Антисимметричность

Отношение А А - антисимметричное, если

" a, b Î A (a r b & b r a Þ a = b).

То есть отношение А А является антисимметричным, если из (a, b) и (b, a) следует, что a = b.

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

4. Транзитивность

Отношение А А - транзитивное, если

" a, b, c Î A (a r b & b r c Þ a r c).

Отношение А А является транзитивным если из (a, b) r и
(b, c) r следует, что (a, c) r. Содержательно транзитивность состоит в том, что если осуществляется последовательный многократный переход между элементами множества A, по связям отношения r, то между первым и последним элементами такого перехода также выполняется отношение r.

Упражнение. Доказать следующие свойства отношений:

1) - рефлексивное e Í r;

2) r - симметричное r = r^-1;

3) r - антисимметричное r Ç r^-1Í e;

4) r - транзитивное r r Í r.

Упражнение. Является ли транзитивным бинарное отношение, на множестве { a, b, c, d, e, f } заданное диаграммой:

a d

b e

c f

Рассмотрим несколько примеров отношений на множестве.

Пусть A - это множество всех людей.

Отношение r = " дружить ". Для этого отношения справедливость условия (a, b) r означает, что a дружит с b. Это отношение симметричное, но оно нетранзитивное и нерефлексивное.

Отношение " любить " - несимметричное и нетранзитивное, но, по-видимому, рефлексивное.

Отношение " быть родственником " - рефлексивное, симметричное и транзитивное.

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

Если А А - некоторое отношение, то рефлексивным, симметричным, транзитивным замыканиями этого отношения называются минимальные отношения на А, которые содержат r и являются соответственно рефлексивными, симметричными и транзитивными.

Date: 2015-10-18; view: 428; Нарушение авторских прав