Упорядоченные множества и универсальная алгебра (вводный курс). Гуров С.И. - 14 стр.

1.2.2    Псевдообращение и произведение соответствий
В данном разделе вводятся новые операции для бинарных отношений (соответствий):
унарная псевдообращения и бинарная произведения.

Определение 1.6. Пусть ρ ⊆ A × B. Операция (# ) псевдообращения соответствия ρ
                                                                          def
задаёт псевдообратное к нему отношение ρ# ⊆ B × A, определяемое как bρ# a = aρb
для любых a ∈ A, b ∈ B.

   Часто употребляют также термины обратное, транспонированное, инверсное или
симметричное отношение и пользуются обозначениями ρ−1 , ρ 0 и др. Легко установить
следующие свойства псевдообращения относительно теоретико-множественных операций
и отношения включения:

                                           (ρ# )# = ρ ,
                                              ρ# = (ρ)# ,
                                          α ⊆ β ⇒ α# ⊆ β # ,
                                      (α ∪ β)# = α# ∪ β # ,
                                      (α ∩ β)# = α# ∩ β # .

Покажем, например, справедливость последнего равенства (a и b — произвольные эле-
менты из A и B соответственно):

          b(α ∩ β)# a = a(α ∩ β)b = aαb ∧ aβb = bα# a ∧ bβ # a = b(α# ∩ β # )a .

Определение 1.7. Пусть A, B и C — непустые множества и α ⊆ A × B, β ⊆ B × C.
Тогда произведение α ¦ β (или сокращённо αβ ) соответствий α и β определяется как
                                               def
                                  a(α ¦ β)c = ∃ b (aαb ∧ bβc)
                                                     B

для произвольных a ∈ A, c ∈ C.

     Можно показать, что произведение соответствий обладает свойствами

                                          α(βγ) = (αβ)γ ,
                                   (αβ)# = β # α# ,
                       α(β ∪ γ) = αβ ∪ αγ , (α ∪ β)γ = αγ ∪ βγ ,

но
                       α(β ∩ γ) 6= αβ ∩ αγ ,              (α ∩ β)γ 6= αγ ∩ βγ .
     Пусть M1 ∈ Mm×n , M2 ∈ Mn×r . Определим произведение M1 · M2 данных матриц:
                                  n
                                  _
               k M1 · M2 ki,j =         k M1 ki,k ∧ k M2 kk,j ,      i = 1, m, j = 1, r .
                                  k=1

Легко показывается, что если α ⊆ A × B и β ⊆ B × C, где A, B, C — конечные
множества, то справедливо равенство

                                   M (α ¦ β) = M (α) · M (β) .


                                                     14