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

Определение 1.11. Соответствие ρ между A и B называется
      • многозначным отображением или всюду определённым соответствиями, если
        MA ⊆ ρρ# (что эквивалентно Dom ρ = A );

      • частичным отображением A в B , если ρ# ρ                     ⊆MB     (что эквивалентно
        aρb1 ∧ aρb2 ⇒ b1 = b2 для a ∈ A );

      • функциональным или отображением A в B , если MA ⊆ ρρ# ∧ ρ# ρ ⊆MB (что
        эквивалентно существованию для всех a ∈ A единственного b ∈ B такого, что
        aρb );

      • дифункциональным или квазиоднозначным, если ρρ# ρ ⊆ ρ или, с учётом доказан-
        ного выше, ρρ# ρ = ρ (что эквивалентно ρ(a1 ) ∩ ρ(a2 ) 6= ∅ ⇒ ρ(a1 ) = ρ(a2 ) для
        всех a1 , a2 ∈ A или ρ# (b1 ) ∩ ρ# (b2 ) 6= ∅ ⇒ ρ# (b1 ) = ρ# (b2 ) для всех b1 , b2 ∈ B ).
        Данные соотношения указывают, что как образы, так и прообразы дифункциональ-
        ных отношений либо совпадают, либо не пересекаются. Это означает, что дифунк-
        циональные отношения задают разбиения множеств Dom ρ и Im ρ на одинаковое
        число классов, причём эти разбиения обладают тем свойством, что образы элемен-
        тов из одного класса разбиения Dom ρ лежат в одном и том же классе разбиения
        Im ρ.

1.4.2     Отображения
Наибольшее применение на практике находят функциональные соответствия. Рассмот-
рим их подробнее.
   Отображение ϕ из A в B называют также функцией из A в B .8 При этом исполь-
                                    ϕ
зуют обозначения ϕ : A → B или A → B. Тот факт, что aϕb записывают как ϕ(a) = b
        ϕ
или a 7→ b ; при теоретических выкладках удобна запись aϕ = b или даже aϕ = b.
Множество всех отображений A → B будем обозначать F un (A, B). При A = B будем
пользоваться обозначением F un (A).
   Рассмотрим специальные классы отображений множества A в множество B. Если
окажется, что ϕ(x) = b ∈ B для всех x ∈ A, то отображение ϕ называют постоянным
или константой. Единичное отношение MA , рассматриваемое как отображение A на
себя, называют тождественным. Для тождественного отображения будем употреблять
обозначение idA .
   Легко показать, что для отображений ϕ ∈ A × B и ψ ∈ B × C произведение ϕψ
также является отображением. Действительно, для ϕ и ψ справедливо

                    MA ⊆ ϕϕ# ∧ ϕ# ϕ ⊆MB          и    MB ⊆ ψψ # ∧ ψ # ψ ⊆MC .

Но тогда MA ⊆ ϕϕ# = ϕ MB ϕ# ⊆ ϕ(ψψ # )ϕ = (ϕψ)(ϕψ)# . Включение (ϕψ)# (ϕψ) ⊆MC
показывается аналогично. Таким образом, ϕψ — отображение.
   Также понятно, что произведение функций как отображений совпадает с их ком-
позицией (∗) и, в силу ассоциативности произведения соответствий, имеет место
                     def
(ϕ ¦ ψ)(x) = ψ(ϕ(x)) = (ϕ ∗ ψ)(x)9 .
Определение 1.12. Отображение ϕ : A → B называется
  8
     Таким образом, мы не различаем понятия функционального отображения и функции, хотя они не
тождественны друг другу. Пример для знакомых с теорией алгоритмов: невычислимые функции, строго
говоря, являются лишь функциональными отображениями, а не функциями.
   9
     Здесь становится очевидным удобство записи ψ(ϕ(x)) = xϕψ.

                                                 22