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

   Заметим, что h ρt , ¦ i есть моногенная полугруппа hρi, порождённая отношением ρ.
   Транзитивное замыкание данного отношения легко строится. Введём обозначение
      S∞
ρ+ =     ρn . По определению произведения отношений, справедливость aρ+ b означа-
       n=1
ет существование таких элементов x0 = a, x1 , . . . , xn = b соответствующего множества,
что x0 ρx1 ∧ . . . ∧ xn−1 ρxn . Ясно, что ρ+ транзитивно, и если ρ уже транзитивно, то
ρ+ = ρ.

Утверждение 1.2. Для произвольного однородного отношения ρ справедливо ρ t = ρ+ .

Доказательство. С одной стороны, ρ ⊆ ρ+ и ρ+ транзитивно. С другой, из ρ ⊆ ρ t
следует ρ+ ⊆ (ρt )+ = ρ t и, по определению транзитивного замыкания, ρ+ = ρ t .

Следствия.    1. Для произвольного               однородного        отношения         ρ   справедливо
    ρ = { ρ ∪ ρ# ∪ M }t .
     e

     Действительно, обозначим σ = { ρ ∪ ρ# ∪ M }. Отношение ρ e должно, кроме ρ,
     содержать M и ρ# , поэтому σ ⊆ ρ e . В силу транзитивности ρ e имеем σ t ⊆ ρ e ,
     откуда σ t = ρ e по определению эквивалентного замыкания.

  2. Эквивалентное замыкание совокупности эквивалентностей совпадает с объедине-
     нием всевозможных произведений этих эквивалентностей.
     Действительно, с одной стороны, данное объединение содержит все эквивалентно-
     сти из рассматриваемой совокупности, а с другой — содержится во всех из них (см.
     теорему 1.14.)
     В частности, для двух эквивалентностей α и β их эквивалентное замыкание совпа-
     дает с объединением всевозможных произведений вида αβ, βα, αβα, βαβ . . .. От-
     сюда следует, что если α и β перестановочны, то { α, β }e = αβ = α ∪ β (см.
     следствие из теоремы 1.14).

   Рефлексивным замыканием ρ∗ однородного на множестве A отношения ρ называют
                                                                       S
                                                                       ∞
отношение MA ∪ρ+ . Обычно по определению полагают ρ0 = MA и тогда ρ∗ =   . Ясно,
                                                                                            n=0
что ρe = ρ∗ .
Пример 9.  1. Если α — отношение на множестве натуральных чисел, определяемое
                  def
    правилом mαn = m + 1 = n, то αt = <.

  2. Пусть на множестве A = { 1, 2, 3, 4, 5, 6, 7, 8 } заданы эквивалентности α и β со
     смежными классами соответственно

                {1, 2}, {3, 4}, {5, 6, 7}, {8}     и       {1, 4}, {2, 3}, {5, 6}, {7}, {8} .

     Тогда эквивалентность (α ∪ β)e порождает смежные классы {1, 2, 3, 4}, {5, 6, 7}
     и {8}.

  3. Если на множестве A = { a, b, c, d, e, f } заданы эквивалентности α и β со смеж-
     ными классами соответственно

                      {a, b}, {c}, {d}, {e, f }        и    {a}, {b, c}, {d, e}, {f } ,

     тогда ни αβ, ни βα не есть эквивалентность, а эквивалентное замыкание { α, β }e ,
     совпадающее с { αβ ∪ βα }, порождает смежные классы {a, b, c} и {d, e, f }.


                                                  20