1. Если g и f – сюръекции, то их композиция – сюръекция;

2. Если g и f – инъекции, то их композиция – инъекция;

3. Если g и f –биекции, то их композиция – биекция;

3. Некоторые специальные функции

1) Перестановка множества A была определена ранее.

2) Тождественная функция была определена ранее.

3) Пусть задано некоторое множество M  U. Характеристической функцией этого множества является функция χ, равная 1 на элементах множества M:

4) Бинарной операцией на множестве A называется функция b : A A  A. Образ пары (x,y) при отображении b записывается как b(x,y) или как xby.

Поскольку область значений бинарной операции на A по определению есть подмножество A, то множество A обладает свойством замкнутости относительно бинарной операции.

5) Конечной последовательностью называется функция из N₀ ={0, 1, 2, 3, …, n} в некоторое множество A. f : N₀  A Бесконечной последовательностью называется функция из {0, 1, 2, 3, …} в некоторое множество A. Элементом последовательности является упорядоченная пара (n,a), в которой a = f(n). Обычно эта пара обозначается через a_n, а последовательность f : N₀  A – через {a_n }.

Иногда нумерацию членов последовательности начинают с 1, т.е. иногда последовательностью называют функцию, определенную на множестве N.

26. Широко известными видами последовательностей являются арифметическая и геометрическая прогрессии.

6) Еще одна известная специальная функция, которая далее потребуется при комбинаторных вычислениях – факториал. На примере этой функции уместно вспомнить о принципе математической индукции.

Принцип математической индукции состоит в следующем.

Если некоторое свойство P выполняется на элементе 0, и для любого nN из выполнимости P на элементе n следует его выполнимость на элементе n+1, то свойство P выполняется на любом элементе nN.

Формальная запись: P ( (P(0),nN P(n)P(n+1))  nN P(n) ).

Принцип математической индукции позволяет доказывать утверждения, проверять свойства и давать индукционные определения. Итак, для доказательства свойства P согласно принципу мат. индукции выполняются следующие шаги:

1. База (базис) индукции. Проверяется выполнение P(0).

2. Индукционный переход. Предполагается, что выполнено P(n). Показывается, что тогда выполнено и P(n+1): P(n)P(n+1).

Иногда удается установить выполнение свойства P(k) только начиная с некоторого k>0 и P(n)  P(n+1) n  k.

Индукционное определение понятия P(n) дается следующим образом:

1. Задается значение P(0);

2. Задается правило получения P(n+1) по числу n и значению P(n).

27. Индукционное определение факториала f = n! будет выглядеть следующим образом: f(0)=1; f(n+1)=f(n)(n+1).

1. Контрольные вопросы

1. Пусть задана функция RAB. Какое из утверждений неверно: « a   могут соответствовать два различных элемента из множества B», « b B может соответствовать двум различным элементам из множества A»?

2. Какая функция называется инъективной? Сюръективной? Биективной?

3. Всегда ли справедливо, что обратная функция обладает тем же свойством?

4. Какое множество называется счетным?

5. Что такое характеристическая функция?

6. Как определяется бинарная операция?

7. В чем заключается принцип математической индукции?

8. Справедливо ли утверждение: «Если свойство выполняется для некоторого n, то это значит, что оно выполняется для всех целых чисел»?

24