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

   Пусть α и β — две эквивалентности на множестве A. Отношение включения β ⊆ α
для них означает, что любой смежный класс по β лежит в некотором смежном классе по
α. Иными словами, разбиение множества A на смежные классы по β есть подразбие-
ние его разбиения на смежные классы по α. Говорят также, что разбиение по β есть из-
мельчение разбиения по α. Для таких эквивалентностей определим на фактор-множестве
A/β дробную эквивалентность α/β по правилу
                                         def
                         [x]β (α/β) [y]β = xαy           (x, y ∈ A) .

Таким образом, два смежных класса по β эквивалентны по α/β, если они находятся в
одном смежном классе по α.

1.4     Соответствия и отображения
1.4.1   Основные типы соответствий
Рассмотрим соответствие ρ ⊆ A × B между непустыми множествами A и B. Ясно, что
MA ρ = ρ = ρ MB . Кроме того, всегда справедливо включение ρ ⊆ ρρ# ρ. Действительно,
aρb = aρb ∧ bρ# a ∧ aρb ⇒ a(ρρ# ρ)b.
   Для соответствия ρ первая проекция называется областью определения, а вторая —
областью значений отношения ρ, которые обозначаются Dom ρ и Im ρ соответственно.
Для a ∈ A множество ρ(a) = { b ∈ B | aρb } называется S     образом элемента a при
соответствии ρ. Если X ⊆ A, то множество ρ(X) =         x∈X ρ (x) называется образом
множества X при соответствии ρ. Если b ∈ B то множество ρ# (b) = { a ∈ A | aρb }
называется прообразом элемента b при соответствии ρ.
   В связи с введёнными понятиями рассмотрим ещё одно свойство произведения соот-
ветствий.

Теорема 1.15. Пусть α ⊆ A × B и β ⊆ B × C. Тогда

                   P r1 (αβ) = α# (P r1 β) ,        P r2 (αβ) = β(P r2 α) .

Доказательство. Заметим, что через проекции соответствия могут быть записаны об-
раз и прообраз соответствующих множеств:

                         P r1 β = β # (C)      и    P r2 α = α(A) .

Пользуясь свойствами соответствий и их псевдообращений получим

           P r1 (αβ) = (αβ)# (C) = (β # α# )(C) = α# (β # (C)) = α# (P r1 β) ;
                      P r2 (αβ) = (αβ)(A) = β(α(A)) = β(P r2 α) .



   Если ρ — соответствие между множествами A и B и A0 ⊆ A, то соответствие

                      ρ |A0 = ρ ∩ (A0 × B) = { (a, b) ∈ ρ | a ∈ A0 }

называется ограничением или сужением соответствия ρ на подмножество A0 . Понятие
сужения очевидным образом распространяется на произвольные отношения.
    Выделим основные типы соответствий между A и B, обладающие особыми свойства-
ми.

                                               21