Дискретная математика

21 Можно доказать следующие теоремы. Теорема 1.4. Функция /имеет обратную функцию/ " тогда и только тогда, когда / биективна. Теорема 1.5. Композиция биективных функций является функцией биективной. Рис. 1,12 показывают различные отношения, все они, кроме первой, являются функциями. О G- Ю О о отношение, но н е (Ь УНКЦИЯ 01 о *о инъекция, но не сюоъекция 0 01 е Ю сюръекция, но не инъекция GT' биекция Рис. 1.12 Пусть/; A —^B - функция, a множества A И В - конечные множества, положим \А \ = п,\в \ = т. Принцип Дирихле гласит, что если п > т, то, по крайней мере, одно значение / встречается более одного раза. Иными словами, найдется пара элементов Я/ а,-, ojeA, для KoTopbix/('aij= ffaj). Принцип Дирихле легко доказать, поэтому оставляем его читателю в качестве тривиального упражнения. Рассмотрим пример. Пусть в группе более 12 студентов. Тогда, очевидно, что, по крайней мере, у двоих из них день рождения в одном и том же месяце. § 7. Отношение эквивалентности. Фактор-множество Бинарное отношение R на множестве А называется отношением эквивалентности, если R рефлексивно, симметрично и транзитивно. Отношение равенства на множестве чисел обладает указанными свойствами, поэтому является отношением эквивалентности. Отношение подобия треугольников, очевидно, является отношением эквивалентности.