Свойства соответствий

Соответствие Г называется функциональным, если его трафик G функционален. График G называется функциональным, если в нем нет пар с одинаковыми первыми и разными вторыми элементами. Другими словами, из элементов области отправления может выходить не более одной стрелки.

Следовательно, соответствие Г = < G, X, Y> функционально тогда, когда истинно

( x X, y₁, у₂ Y) [< х, у₁> G & < х, у₂> G y₁ = у₂].

Соответствие Г называется инъективным, если его график инъективен. График G называется инъективным, если в нем нет пар с разными первыми и одинаковыми вторыми элементами.

Отметим, что в частном случае инъективные и функциональные, графики могут совпадать.

Соответствие инъективно, когда справедливо:

( x₁, х₂ X, y Y) [< х₁, у> G & < х₂, у> G х₁ = х₂].

Соответствие Г = < G, X, Y> называется всюду определенным, если его область определения совпадает с его областью отправления.

Пример. Г = < G, X, Y> = < {< 1, 2>, < 3, 2>, < 4, 5> }; {1, 3, 4}; {2, 5}>. Здесь область отправления соответствия X = {1, 3, 4}совпадает с областью определения.

Для всюду определенного соответствия справедливо выражение:

пp₁G =Х.

Аналогично можно записать:

( x)( y)[< x, y> G].

Соответствие Г = < G, X, Y> называется сюръективным, если его область значений совпадает с его областью прибытия.

Пример. Г =< G, X, Y> = < {< l, b>, < 2, а> }; {1, 2, 3}; {а, b}>. Здесь область прибытия соответствия X ={а, b} совпадает с областью значений.

Для сюръективного соответствия справедливо выражение:

пp₂G =Y.

Аналогично можно записать:

( y)( х)[< x, y> G].

Соответствие Г = < G, X, Y> называется биективным соответствием или биекцией, или взаимооднозначным соответствием, если оно функционально, инъективно, всюду определено и сюрьективно.

Частным случаем соответствия является понятие отображения. Всюду определенное соответствие называется отображением X в Y и записывается

G: X Y.