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

32 Достаточность . Теперь дано , что , g h ∀ ( ) g f h f g h = → = o o . (2.14) Докажем , что отображение f является инъекцией . От против - ного , допустим , что f не является инъекцией . Тогда найдутся 1 2 , x x X ∈ такие , что 1 2 x x ≠ , но 1 2 ( ) ( ) f x f x = . Подберем функции : g X X → и : h X X → следующим образом : x X ∀ ∈ 1 ( ) , g x x = 2 ( ) h x x = . Тогда x X ∀ ∈ 1 2 ( )( ) ( ( )) ( ) ( ) ( ( )) ( )( ) g f x f g x f x f x f h x h f x = = = = = o o . Таким образом , для подобранных функций g и h равенство g f h f = o o выполняется , но g h ≠ , что противоречит условию (2.14). Следовательно , предположение о том , что f не является инъекцией , неверно , что и доказывает достаточность условия (2.14). Теорема доказана . Теорема 2.2. Отображение : f X Y → сюръективно тогда и толь - ко тогда , когда для любых двух функций : g Y Z → и : h Y Z → из равенства f g f h = o o следует , что g h = . Необходимость . Пусть f – сюръекция X на Y . Докажем , что , g h ∀ ( ) f g f h g h = → = o o , (2.15) т . е . возможно сокращение слева . Пусть y Y ∈ – произвольный эле - мент множества Y . Так как отображение f сюръективно , то x X ∃ ∈ ( ( )) y f x = . Тогда ( ) ( ( )) ( )( ) ( )( ) g y g f x f g x f h x = = = = o o ( ( )) ( ) h f x h y = = , т . е . в силу произвольности y Y ∈ функции g и h равны , что и требовалось . Достаточность . Достаточность условия (2.15) для того , чтобы отображение : f X Y → было сюръекцией так же , как в тео - реме 2.1, докажем от противного . Пусть : f X Y → несюръективно . Тогда 1 Y y ∈ ∃ такой , что 1 y не является образом ни одного из эле -