Композиція відношення

Нехай A={a₁,a₂,a₃}, B={b₁,b₂}, R={(a₁,b₁),(a₂,b₂),(a₃,b₁)}. Застосовуючи природну нумерацію рядків та стовбців, отримуємо: M_R= ${\begin{bmatrix}1&0\\0&1\\1&0\end{bmatrix}}$, M_R⁻¹= ${\begin{bmatrix}1&0&1\\0&1&0\end{bmatrix}}$, Тобто R^-1={(b₁,a₁),(b₂,a₂),(b₁,a₃)}. Композиція відношень: визначається для відношень R:A→B та S:B→C,як відношення R о S:A→C, таке, що: a(R о S)c рівносильно, що існує b, що належить B: aRb ^ bSc. Зауважимо, що для запису композиції функції зручним та загальноприйнятим є зворотний запис, що виглядає так: ((g о f(x))=g(f(x))), однак для композиції відношень часто використовують як прямий, так і зворотній запис. Для скінченних множин А, В та С з невеликою кількістю елементів композицію відношень зручно обчислювати за допомогою стрілкових діаграм.

Властивості

• Ядро відношення R симетрично:

a (R о R⁻¹) b рівносильно існує c: (a R c) ^ (c R⁻¹ b) рівносильно існує c: (b R c) ^ (c R⁻¹ a) рівносильно b (R о R⁻¹ ) a

• (R^−1)-1 = R

• (R о S) о T = R о (S о T)

• (R о S)⁻¹ = (S ⁻¹) о (R ⁻¹)

• (R U S)⁻¹ = (R⁻¹) U (S⁻¹)

• (R U S) ⁻¹ = (R⁻¹) U (S⁻¹)

Слід зазначити, що операція композиції відношень може бути і невизначеною, якщо в множині B для заданих елементів а із A та c із C не існує відповідного елемента b. Але якщо А = В = С, то ця операція завжди визначена.

Нехай R – відношення на множині A. Ступенем відношення R на множині A є його композиція із самим собою. Позначається: R_n = R◦…(n разів)… ◦R. Відповідно, R₀ = I, R₁ = R, R₂ = R◦R і взагалі R_n = R_n-1◦R. Якщо R, R₁, R₂ – бінарні відношення, задані на множині A, то:

• (R₁∪R₂) ◦R = R₁◦R ∪ R₂◦R; R₁⊆R₂ ⇒ R₁◦R ⊆ R₂◦R.
• (R⁻¹)⁻¹ = R; R⊆R₁ ⇒ R⁻¹⊆R₁⁻¹.
• (R₁◦R₂)⁻¹ = (R₂⁻¹) ◦ (R₁⁻¹).
• (R₁∩R₂)⁻¹ = (R₁⁻¹) ∩ (R₂⁻¹).
• (R◦R₁) ◦ R₂ = R ◦ (R₁◦R₂).

Доведення. а) Якщо (a, b)∈(R₁∪R₂) ◦ R, то існує елемент c∈A такий, що (a, с)∈R₁∪R₂ і с, b)∈R. Значить, (a, с)∈R₁ або (a, с)∈R₂ і (с, b)∈R. Звідси маємо, що (a, b)∈R₁◦R або a, b)∈R₂◦R, тобто (a, b)∈R₁◦R ∪ R₂◦R. Обернене включення доводиться аналогічно.

Друга частина твердження випливає з того, що коли R₁⊆R₂, то R₁∪R₂ = R₂, звідки маємо(в силу вище доведеного), що (R₁∪R₂) ◦R = R₁◦R ∪ R₂◦R = R₂◦R, тобто R₁◦R ⊆ R₂◦R. б) (a, b)∈R⁻¹ ⇔ (b, a)∈(R⁻¹)⁻¹ ⇔ (b, a)∈R. Звідки випливає, що (R⁻¹)⁻¹ = R. Для доведення другої частини зауважимо, що (a, b)∈R ⇔ (b, a)∈R⁻¹, (a, b)∈R ⇒(a, b)∈R₁ ⇒ (b, a)∈R⁻¹ ⇒ (b, ∈R₁⁻¹, тобто R⁻¹⊆R₁⁻¹. в) (a, b)∈(R₁◦R₂)⁻¹ ⇔ (b, a)∈(R₁◦R₂) ⇒ (∃c∈A | (b, c)∈R₁ і (c, )∈R₂). Але тоді (c, b)∈R₁⁻¹ і(a, c)∈R₂⁻¹ ⇒ (a, b)∈(R₂⁻¹◦R₁⁻¹), тобто R₁◦R₂)⁻¹⊆ (R₂⁻¹) ◦ (R₁⁻¹). Обернене включення доводиться аналогічно. г) (a, b)∈(R₁∩R₂)⁻¹ ⇔(b, a)∈R₁∩R₂ ⇔ (b, a)∈R₁ і (b, a)∈R₂ ⇔ (a,b)∈R₁⁻¹ і (a, b)∈R₂⁻¹, тобто (R₁∩R₂)⁻¹ = (R₁⁻¹)∩(R₂⁻¹). д) Нехай (a, d)∈(R◦R₁) ◦ R₂, тоді існує c∈A такий, що (a, c)∈R◦R₁ і (c, d)∈R₂. Отже існує такий b, що (a, b)∈R, (b, c)∈R₁ і (c, d)∈R₂, а це означає, що (b, d)∈R₁◦R₂ і a,d)∈R◦(R₁◦R₂), тобто(R◦R₁)◦R₂ ⊆ R◦(R₁◦R₂). Обернене включення доводиться аналогічно.

Див. також

Відношення Теорія множин