Дискретная математика. Множества. Отображения. Отношения

72 ( ) { } 1 1 1 Пр : ( ) : ,..., , , ,..., k A k i i k k n R a A a A i k a a a a a R − + = ∈ ∃ ∈ ≠ ∈ . (6.1) Пусть R A B ∈ × – произвольное соответствие множеств A и B . Если R = ∅ , то соответствие R называется пустым , а если R A B = × , то соответствие R называется универсальным . Проекция R на ось A называется областью определения со - ответствия и обозначается Dom R или R D , а проекция R на ось B – множеством значений или образов соответствия R . Обозначается множество образов символом Jm R . { } { } Dom : (( , ) ) ; Jm : (( , ) ) . R a A b B a b R R b B a A a b R = ∈ ∃ ∈ ∈ = ∈ ∃ ∈ ∈ (6.2) Если Dom , R A = то соответствие называется всюду опреде - ленным . В случае , когда Jm R B = соответствие R называется сюръ - ективным . В случае , когда множества A и B конечные , возможны гра - фовые и матричные представления соответствий ( см . гл . 2 и 8). Пусть 1 1 { , ..., }, { , ...., } m n A a a B b b = = и R A B ⊂ × . Тогда матрица отношения R есть m n × - матрица [ ] ( ) ij m n R r × = с элементами 1, ( , ) ; , 0, ( , ) . i j ij i j a b R i j r a b R ∈  ∀ =  ∉  (6.3) Матрицы отношений подробно рассмотрены в гл . 8. При графовом представлении соответствия R элементы мно - жеств A и B изображаются точками плоскости и две точки i a и j b соединяются дугой , идущей от точки i a к точке j b , если ( , ) i j a b R ∈ ( т . е . i j a Rb ). Примеры диаграмм ( графов ) отображений и отноше - ний приведены в гл . 2.