1.3. Определяющие свойства дискретных функций
Дискретными называют функции f:XY, где множества X и Y конечные или счетные. Рассмотрим функции с конечными множествами X и Y.
Весовыми характеристиками функции f:XY назовём порядки полных прообразов элементов yY относительно функции f, обозначим их wy(f). Отсюда
.
Функцию f(x) называют равновероятной (равновесной, сбалансированной), если весовые характеристики wy(f) одинаковы для всех yY.
Функция f:XY называется:
а) сюръективной (или сюръекцией, или отображением на), если для любого yY выполнено: f{-1}(y);
б) инъективной (инъекцией), если f(x)f(x) при xx;
в) биективной (или взаимно однозначной, или биекцией), если она одновременно сюръективна и инъективна.
Если множества X и Y конечные, то при сюръекции XY, при инъекции XY и при биекции X=Y.
Некоторые множества функций можно рассматривать как алгебраические структуры. Пусть f:XY, :YZ, тогда функцию :XZ, определенную равенством (x)=(f(x)) для любого xX, называют композицией функций ,f (записывается =f) или произведением функций f, (записывается =f=f). Композиция (произведение) отображений в общем случае некоммутативна, то есть f f.
Следующее утверждение показывает, что те или иные множества функций, заданных на определенном семействе множеств, могут образовать группу или полугруппу, в том числе, частичную полугруппу.
Утверждение 1.3. а) Операция умножения, определённая на множестве отображений, обладает свойством ассоциативности.
б) Если функции f и биективны (инъективны, сюръективны), то биективна (инъективна, сюръективна) функция f.
t а) Достаточно для любой тройки функций f:XY, :YZ, :ZW доказать равенство: ()f=(f).
По определению произведения отображений для любого xX выполнено:
((f))(x)= (f)((x))=f(((x)))=f((x))=(()f)(x).
б) Если функции f и сюръективны, то для любого zZ имеется yY такой, что (y)=z, и xX такой, что f(x)=y. Значит, f(x)=z, т.е. функция f сюръективна.
Если функции f и инъективны и xx, то f(x)f(x) и (f(x))(f(x)). Значит, f(x)f(x), то есть f инъективна. u
Обратные утверждения в общем случае неверны. Вместе с тем, если функция f сюръективна, то сюръективна, если f инъективна, то f инъективна.
Функцию е:XX называют тождественной или единичной, если е(x)=x для любого xX. Функции f:XY и :YX называют взаимно обратными, если функции f и f - тождественные, при этом -1=f, f-1=. Функция, для которой существует обратная функция, называется обратимой.
Утверждение 1.4. Всякое обратимое отображение имеет единственное обратное отображение.
t Пусть отображение f имеет различные обратные отображения и . В соответствии с ассоциативностью произведения функций верны равенства:
=e=(f)=(f)=e=.
Следовательно, отображения и равны. u
Теорема 1.1. Отображение f:XY имеет обратное f биективно.
Следствие. Если функции f:XY и :YZ обратимы, то обратимо и их произведение f, причем
(f)-1=-1f-1.
t В соответствии с ассоциативностью произведения функций
(f)(-1f-1)=f(-1)f-1=fef-1=ff-1=e. u