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

31 Если функции f и g отображают X в ( на ) X , то имеют смысл обе композиции f g o и g f o . Некоммутативность композиции иллюстрируется следую - щим примером . Пример 2.3. Пусть 1 2 3 , , } { X x x x = . Функции : f X X → и : g X X → заданы таблицей . x ( ) f x ( ) g x 1 x 2 x 1 x 2 x 1 x 3 x 3 x 3 x 2 x Тогда композиции f g o и g f o определяются таблицей : x f g o g f o 1 x 3 x 2 x 2 x 1 x 3 x 3 x 2 x 1 x Видно , что f g g f ≠ o o . Теорема 2.1. Функция : f X Y → является инъекцией тогда и только тогда , когда для любых двух функций : g Z X → и : h Z X → из равенства g f h f = o o следует , что g h = . Необходимость . Пусть функция : f X Y → инъективна . До - кажем , что , g h ∀ ( ) g f h f g h = → = o o , т . е . возможно сокращение справа . Итак , пусть g f h f = o o . Если z Z ∈ , то ( )( ) ( ( )) ( )( ) ( ( )) g f z f g z h f z f h z = = = o o . Из полученного равенства ( ( )) ( ( )) f g z f h z = в силу того , что f инъективна , следует ( ) ( ) g z h z = . А так как z Z ∈ произвольно , то g h = .