7. Свойства бинарных отношений

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

Отношение R называется рефлексивным, если (х, х)R для любого хA.

Примеры рефлексивных отношений: отношения "", "" на множестве R.

2) Антирефлексивность.

Отношение R называется антирефлексивным, если (х, х)R для любого хA.

Примеры антирефлексивных отношений: отношения "<", ">" на множестве R.

Если R – антирефлексивное отношение, то xG_R(x) и хH_R(x) для любого хA .

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

Отношение R называется симметричным, если для любых x, yA из того, что (x, y)R следует (y, x)R и обратно.

Примеры симметричных отношений: отношения "=" и "".

Если отношение R симметрично, то для любого хA

а) G_R(x) = H_R(x); б) R = R^–1.

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

Отношение R называется антисимметричным, если для любых x и y из A из одновременного выполнения условий (x, y)R и (y, x)R следует, что x = y.

Отношение "" также антисимметрично: если x  y и y  x, то x=y.

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

Отношение R асимметрично, если R  R^-1= , т.е. пересечение отношения R с обратным отношением пусто.

Эквивалентное определение асимметричности: из двух отношений (x, y)R и (y, x)R одно не выполняется.

Примеры асимметричных отношений: ">", "<", "быть начальником".

Если R – асимметричное отношение, то из xRy следует y x.

Для любого отношения R вводятся понятия симметричной части отношения R^s = R R^-1 и асимметричной части отношения R^a = R \ R^s. Если отношение R симметрично, то R= R^s, если отношение R асимметрично, то R = R^a.

Примеры. Если R – "", то R^–1 – "<", R^s – "=", R^a – ">".

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

Отношение R транзитивно, если для любыx x, y, zA из того, что (x, y)R и (y, z)R следует (x, z)R.

Свойства транзитивного отношения:

а) RoR  R;

б) для любого хA из yG_R(x) следует, что G_R(y)  G_R(x).

Нетранзитивным является отношение "". Пусть x = 2, y = 3, z = 2, тогда справедливо x  y и y  z, но x = z, т.е. (x, z)R.

Отношение R₁ называется транзитивным относительно отношения R₂, если:

а) из (x, y) R₁ и (y, x) R₂ следует, что (x, z) R₁;

б) из (x, y) R₂ и (y, x) R₁ следует, что (x, z) R₁.

7) Негатранзитивность.

Отношение R называется негатранзитивным, еслиR транзитивно.

Примеры.

Отношения R₁ –">" и  R₂ –" " негатранзитивны, так как отношенияR₁ – "",R₂ – "=" транзитивны. Возможно одновременное выполнение свойств транзитивности и негатранзитивности. Например, отношение R₁ одновременно транзитивно и негатранзитивно, а R₂ , как известно, транзитивным не является.

8) Полнота.

Отношение R полно, если для любых x, yА либо (x, y)R, либо (y, x)R, либо оба отношения выполняются одновременно.

Свойства полных отношений:

а) G_R(x)  H_R(x) = А для любого хA;

б) полное отношение рефлексивно.

9) Слабая полнота.

Отношение R называется слабо полным, если для любых х  y из А или (x, y)R, или (y, x)R.

Пример слабо полного отношения. Пусть А – множество предприятий, "неблагополучных" в смысле своего бюджета. Отношение R "быть должным" является слабо полным, так как каждое из этих предприятий или кому-либо должно, или ему кто-то должен, но быть должным самому себе нельэя и (x, x)R.

10) Ацикличность.

Бинарное отношение R ациклично, если Rⁿ R^–1=  для любого nN . Иными словами, если из любой конечной цепочки отношений х₁Rx₂, x₂Rx₃,..., x_n-1Rx_n следует, что x₁х_n, то отношение R ациклично.

Задача 1. Доказать, что если отношения R₁, R₂ рефлексивны, то справедливо включение R₁R₂  R₁oR₂ .

Решение. Пусть (x, y)R₁R₂, тогда (x, y)R₁ или (x, y)R₂. В первом случае из рефлексивности R₂ следует (y, y)R₂ и, следовательно,(x, y)R₁ o R₂. Аналогично для второго случая получим (x, x)R₁ и (x, y)R₁ o R₂, что и требовалось доказать.

Задача 2. Доказать, что отношение R негатранзитивно тогда и только тогда, когда R^d транзитивно.

Решение. Пусть отношение R негатранзитивно, т.е. если (x, y)R и (y, z)R, то (x, z)R. Пусть для u, v, w выполнены условия (u, v)R^d и (v, w)R^d. Тогда, по определению двойственного отношения, (v, u)R и (w, v)R. Так как R негатранзитивно, то (w, u)R, что означает (u, w)R^d. Следовательно, R^d транзитивно.

Обратное следствие доказывается аналогично.

Задача 3. Доказать, что отношения R  (R  R^d ) = R  (R )^s полны.

Решение. Докажем равенство множеств, воспользовавшись свойствами операций над множествами и отношениями.

R(R  R^d ) = R  (R  ) = R  (R(R )^-1) = R  (R )^s.

Покажем теперь, что отношение R  (R )^s полно. Для любых x, yA возможен один из трех случаев: 1) (x, y)R; 2) (y, x)R; 3) (x, y)R и (y, x)R. В первых двух случаях принадлежность (x,y) к рассматриваемому отношению очевидна. Рассмотрим третий случай. Так как (x,y)R и (x,y) ^-1, то (x,y)(R )^s. Следовательно, рассматриваемое отношение полно.

Задача 4. Доказать, что композиция эквивалентностей R₁ и R₂ является отношением эквивалентности тогда и только тогда, когда R₁ o R₂ = R₂ o R₁.

Решение. 1) Пусть R₁, R₂ и R₁ o R₂ - отношения эквивалентности. Докажем, что R₁ o R₂ = R₂ o R₁.

Пусть (x, y)R₁ o R₂, так как R₁ o R₂ – отношение эквивалентности, то (y,x)R₁ o R₂. Последнее означает, что существует такой элемент zA, что (y, z)R₁ и (z, x)R₂. Так как R₁ и R₂ – симметричны, то (x, z)R₂ и (z, y)R₁. Следовательно, (x, y)R₂ o R₁. Обратное включение доказывается аналогично.

2) Пусть R₁ o R₂ = R₂ o R₁, покажем, что R₁ o R₂ является отношением эквивалентности.

Пусть x – произвольный элемент множества A. Так как R₁, R₂ рефлексивны, то (x, x)R₁ и (x, x)R₂, следовательно, (x,x)R₁oR₂, т.е. отношение R₁ o R₂ – рефлексивно.

Докажем его симметричность. Пусть (x, y)R₁oR₂, в силу равенства R₁ o R₂ = R₂ o R₁ получим (x, y)R₂ o R₁, т.е. существует такой zA, что (x, z)R₂, (z, y)R₁. Из симметричности R₁ и R₂ следует, что (y, z)R₁ и (z, x)R₂. Следовательно, (y, x)R₁ o R₂.

Для доказательства транзитивности достаточно показать, что (R₁ o R₂) o (R₁ o R₂)  R₁ o R₂. Действительно,

(R₁ o R₂) o (R₁ o R₂) = R₁ o (R₂ o R₁) o R₂ = R₁ o (R₁ o R₂) o R₂ =

= (R₁ o R₁) o (R₂ o R₂)  R₁ o R₂.

Задача 5. Пусть отображение   : AAA обладает свойствами:

а)  (x, y) = (y, x);

б)  (x, (y, z)) = ((x, y), z);

в)  (x, x) = x.

Доказать, что отношение R={ (x, y) | (x, y) = x } является частичным порядком.

Решение. Проверим выполнение свойств отношения частичного порядка. Так как (x, x) = x, то (x, x)R и отношение рефлексивно.

Пусть выполнены оба условия (x, y)R и (y, x)R, т.е. (x,y)=x и  (y, x) = y. Тогда x = y, так как (x, y) = (y, x) по определению функции . Следовательно, отношение антисимметрично.

Докажем его транзитивность. Пусть (x, y)R и (y, z)R, т.е. (x, y) = x и (y, z) = y. Тогда

(x, z) = ((x, y), z) = (x, (y, z)) = (x, y) = x.

Следовательно, (x,z)R, что и требовалось доказать.