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

33 ментов множества X , т . е . x X ∀ ∈ 1 ( ( )) y f x ≠ . Зафиксируем в мно - жестве Y элемент 2 1 y y ≠ . Определим функцию : g Y Y → следую - щим образом : y Y ∀ ∈ ( ) g y = 1 2 1 , если ; , если . y y y y y y ≠   =  (2.16) Тогда x X ∀ ∈ ( ) ( )( ) ( ( )) ( ) ( ( )) ( )( ) y y f g x g f x f x I f x f I x = = = = o o . Итак , y f g f I = o o , но , как это следует из (2.16), y g I ≠ . Условие (2.15) не выполняется . Противоречие . Следовательно , допущение о том , что f несюръективно , неверно . Теорема доказана . Функция f биективна тогда и только тогда , когда справедли - вы утверждения (2.14) и (2.15), т . е . возможны сокращения слева и справа . Теорема 2.3. Если функции : f X Y → и : g Y Z → инъек - тивны , сюръективны или биективны , то такими же соответственно являются и композиции : f g X Z → o . Доказательство . Докажем сначала , что композиция инъекций является инъекцией : ( 1 2 1 2 1 2 1 , ( ) ( ) ( ( )) x X x f f x g f x x x x ∈ ≠ → ≠ → ≠ ∀ ) 2 1 2 ( ( )) ( )( ) ( )( ) g f x f g x f g x ≠ → ≠ o o , что и требовалось доказать . Докажем теперь , что композиция сюръекций является сюръ - екцией : ( z Z ∀ ∈ ( ( ( ))) & y Y z g y y Y ∃ ∈ = ∀ ∈ ( x X y ∃ ∈ = ( ))) f x , так как f и g сюръекции . Следовательно , z Z x X ∀ ∈ ∃ ∈ ( ( ( )) z g f x = = ) ( )( ) f g x = o , что означает сюръективность композиции f g o .