Теория множеств

Если функция f : A  B является биекцией, то обратное отношение f^–1 также является функцией из B в A, причем биекцией. Обратно, если f^–1 – функция из B в A, то f является биекцией.
Доказательство:
 Для доказательства того, что  f^–1– функция из B в A, нужно убедиться, что областью определения  f^–1 является B, и что если (b,a)  f^–1 и (b,a’)  f^–1, то a = a’. Поскольку f сюръективна (т.е. отображение на), то bB  aA | f(a)=b. Значит, (b,a)  f^–1, и B является областью определения f^–1. Пусть теперь (b,a)  f^–1 и (b,a’)  f^–1, тогда (a,b) и (a’,b) принадлежат f. Поскольку f инъективна, то a=a’. Значит, f^–1– функция.
Теперь покажем, что она является биекцией, т.е. сюръективна и инъективна.
Поскольку f – функция, то aA  bB| f(a)=b, т.е. (a,b)f. Тогда (b,a) f^–1, и элемент a принадлежит области значений функции f^–1. Значит, A представляет собой область значений f^–1, и сама функция f^–1 сюръективна. Для доказательства инъективности возьмем (b,a)  f^–1 и (b’,a)  f^–1, т.е. a = f^–1(b) и a = f^–1(b’). Тогда
f(a) = b  и f(a) = b’  b’= b, т.к. f – функция.
 Для доказательства обратного утверждения нужно провести аналогичные рассуждения, заменив f^–1 на f. 
Теорема 1.4: Если функция f : A  B является биекцией, то:
а)  b B f(f^–1(b))=b, б)  a A f^–1(f(a))=a.
Доказательство: Возьмем  b  B. Поскольку f – биекция, то  aA | a= f^–1(b). Тогда f(a)=b. Но поскольку a = f^–1(b),  f(f^–1(b)) = f(a) = b 
Доказательство второго утверждения выполняется аналогично.
Теорема 1.5: Если функция f : A  A и I – тождественная функция на A, то I◦ f = f  ◦ I = f. Если для f существует обратная функция, то
f^–1◦ f = f ◦ f^–1= I.
Теорема 1.6: Пусть функции g : A  B и f : B  C. Тогда:

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, то это значит, что оно выполняется для всех целых чисел»?