[Список тем] [Вступление к этой теме] Страницы темы: [1] [2]

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

Пример 1. Пусть Х = R. Рассмотрим бинарное отношение а, заданное правилом:
x α y x²=y².
Пример 2. Пусть Х = R. Рассмотрим бинарное отношение , заданное правилом:
x y x² <  y².
Пример 3. Пусть Х = С (С — множество комплексных чисел). Рассмотрим бинарное отношение , заданное правилом:
z₁ z₂ | z₁ | = | z₂ |.
Пример 4. Рассмотрим на С бинарное отношение , заданное правилом:
z₁z ₂ ( Re z₁ ≤ Re z₂ ) & ( Imz₁ = Imz₂ ).
Выделяют следующие основные свойства бинарных отношений: рефлексивность, транзитивность, симметричность, антисимметричность, а затем с помощью присутствия определенной комбинации этих свойств выделяют два важнейших типа бинарных отношений: отношения порядка и отношения эквивалентности.

Определение 4
Бинарное отношение α на Х называется рефлексивным, если x(xαx) ≡ 1 Т. е. бинарное отношение а, порожденное множеством Sa, называется рефлексивным, если множество Sa, порождающее а, содержит целиком диагональ декартова квадрата Х х Х — diag(X x X) = {x;x};                    x X

Определение 5
Бинарное отношение α на Х называется транзитивным, если xy z((xα y)&(yα z)→(xαz)) ≡1 (xy z((x α y)&(y α z) (x α z))).

Определение 6
Бинарное отношение α на Х называется симметричным, если xy((xαy)→ (yαx)) ≡1 (xy((x αy)(y α x))). Т. е. бинарное отношение а на Х симметрично, если множество Sa, его порождающее, расположено симметрично относительно diag(X х X).

Определение 7
Бинарное отношение α на Х называется антисимметричным, если x y ((xαy) → (x = y))&(y α x) ≡1 (xy((x α y)&(y α x)(x=y))). Т. е. бинарное отношение a на Х антисимметрично, если множество Sa, его порождающее, не содержит ни одной пары различных точек, симметричных относительно diag(X х X)  ( рис. 1).
Бинарное отношение α на Х называется несимметричным, если x y ((xαy) → ¬(y α x) Т. е. бинарное отношение a на Х несимметрично, если множество Sa, его порождающее, не содержит ни одной пары точек, симметричных относительно diag(X х X), и не содержит точек самой диагонали.

Рис.1

Пример 5. Рассмотрим таблицу:

	рефлек- сивность	симмет- ричность	транзи- тивность	антисим- метричность
α	+	+	+	-
	-	-	+	+
	+	+	+	-
	+	-	+	+
=	+	+	+	+
≤	+	-	+	+
x ≤|y|, x, yR	+	-	-	-

Здесь “+” означает, что соответствующее свойство присутствует, а “—” отсутствует, α, , , —отношения из примеров 7 - 10.

Отношение порядка

Классическим примером отношения нестрогого порядка является отношение <= на R.
Ясно что отношение (см. пример 2) является отношением порядка на С.

Определение 8a
Бинарное отношение α на Х называется отношением строгого порядка на X, если оно антирефлексивно, транзитивно и несимметрично.

Примером отношения строгого порядка является отношение < на R.
Отношение порядка α на Х называется отношением линейного порядка на Х (линейным порядком на X), если
x y((x αy) (y α x)) ≡1
В противном случае порядок называется частичным.
То есть отношение порядка на Х является линейным порядком, если любые два элемента множества Х сравнимы этим отношением.
Ясно, что отношение <= на R является отношением линейного порядка, а отношение на С — частичного порядка, так как 1 + i ¬ 2 - 2i и 2 -2i  ¬   1+i.
Пример 6. Рассмотрим произвольное множество А и на множестве 2^A - бинарное отношение . Ясно, что является отношением порядка, причем если |А| <= 1 — порядок линейный, а если |A| >= 2 — частичный.
Пара (Х,а), где а — бинарное отношение на X, называется упорядоченным множеством, если а — отношение порядка на X; линейно - упорядоченным множеством, если а — линейный порядок; частично - упорядоченным множеством, если а — частичный порядок.
Ясно, что (R, <= ) — линейно - упорядоченное множество, а (С, ) (см. пример 2) — частично - упорядоченное множество.

Доминирование

Пусть (X, а) — упорядоченное множество, определим на Х еще одно бинарное отношение d_a — доминирование.

Определение 9
Говорят, что у ( X) доминирует над х ( X) по отношению порядка α (пишут x da у), если 1) x ≠ y; 2) xα y; 3)z(xαz)&(z αy)→(x=z)(z=y) ≡ 1 Отношение доминирования антирефлексивно антисимметрично не транзитивно

Пример 7. Рассмотрим (N, <=). Ясно, что 4 доминирует над 3, 5 над 4.
Пример 8. Пусть С = {1; 2; 3}. На множестве 2^c = { Ø , {1}, {2}, {3},{1;2}, {1;3}, {2;3},С} рассмотрим отношения , d - Элементы множества 2^c изобразим точками, а пару точек x, у соединим стрелкой от х к у, если xd_cy. Тогда мы получим (рис. 2):

Рис.2

Этот рисунок ( граф) называется диаграммой Хассе, или диаграммой доминирования.

Отношение эквивалентности