Отображения множеств

Пусть X и Y - два непустых множества. Закон G, согласно которому любому элементу x Î X ставится в соответствие элемент y Î Y, называется однозначным отображением X в Y, или функцией, определенной на X и принимающей значения на Y.

Используются следующие формы записи:

G: X ® Y или y = G(x), x Î X, y Î Y.

В случае однозначного отображения элемент y = G(x) называется образом элемента x.

Возможна ситуация, когда каждому x Î X отображение G ставит в соответствие некоторое подмножество G(x) Ì Y. Тогда образом элемента x будет подмножество G(x), а отображение G, будет называться многозначным отображением.Отображение является, таким образом, всюду определенным соответствием, т.е. частным случаем соответствия и определяется тройкой множеств (X, Y, G).

Интересным является случай, когда множества X и Y совпадают. При этом отображение G: X ® X представляет собой отображение множества X самого в себя и определяется парой (X, G), где G Ì X ´ X. Подробным изучением таких отображений занимается теория графов. Коснемся лишь нескольких операций над ними.

Пусть G и H – отображения множества X в X. Композицией этих отображений назовем отображение GH, которое определяется следующим образом: GH(x) = G(H(x)).

В частном случае при H = G получим отображения G2(x) = G(G(x)), G3(x) = G(G2(x)) и т.д.

Для произвольного S ³ 2: GS(x) = G(GS-1(x)).

Введем для общности рассуждений соотношение G0(x) = x. Тогда можно записать: G0(x) = G(G-1(x)) = GG-1(x) = x.

Это означает, что G-1(x) представляет собой обратное отображение. Тогда G-2(x) = G-1(G-1(x)) и т.д.

Пусть, например, X - множество людей. Для каждого человека x Î X обозначим через G(x) множество его детей. Тогда G2(x) - множество внуков x, G3(x) - множество правнуков x, G-1(x) - множество родителей x и т.д. Изображая людей точками и рисуя стрелки, идущие из x в G(x), получим родословное, или генеалогическое дерево (рис. 1.7.)

Рис. 1.7 – Генеалогическое дерево