5.5 Функция

Понятие «функции» является одним из основополагающих в математике. В дан­ном случае подразумеваются прежде всего функции, отображающие одно конеч­ное множество объектов в другое конечное множество.

Пусть f — отношение из А в В, такое что

a (a,b) ϵf&(а,с) ϵfb = с.

Такое свойство отношения называется однозначностью, или функциональностью, а само отношение называется функцией из А в Ви обозначается следующим образом: f:A→В. Если f: A→В, то обычно используется префиксная форма записи:

b = f(a)=(a,b) ϵf.

Если b = f(a), то а называют аргументом, а b — значением функции.

Пусть f:A→ В, тогда

область определения функции: fА= {aϵА| bϵВ b= f(а)};

область значенийфункции: fB= {bϵ В|аϵAb = f(а)}.

Если fА = A, то функция называется тотальной, а если fА≠A — частичной. Сужением функции f:A→ В на множество М А называется функция f|M, определяемая следующим образом:

f|M = {(а, b) | (а, b) ϵf& а ϵ М}

Для тотальной функции f= f|fA.

Функция f: A1?…? Ап→ В называется функцией n аргументов, или п-местной функцией.

Пусть f:A→ В. Тогда функция f называется:

инъективной, еслиb = f(a1) & b = f(a2) a1 = a2;

сюръективной, если bϵ ВaϵА b = f(а);

биективной, если она инъективная и сюръективная.

Биективную функцию также называют взаимнооднозначной.

Следующий рисунок иллюстрирует понятия отношения, функции, инъекции, сюръекции и биекции.

Теорема. Если f:A→ В — тотальная биекция (fА = А), то отношение f -1В ?А (обратная функция) является биекцией.

Доказательство.

Поскольку f — биекция, имеем (b1= f (a)&b2 = f (a)b1 = b2) &(b= f(a1) &b = f (а2)a1 = a2) &(bϵВaϵА b = f(а)).

Покажем, что f -1 — функция.

f -1 = {(b,а) | aϵА &bϵВ&b = f(а)}.

Пустьa1 = f -1(b) &а2 = f -1(b). Тогдаb= f(a1) &b = f (а2)a1 = a2.

Покажем, что f -1— инъекция. Пусть a1 = f -1(b1)& а2 = f -1(b2). Тогда b1= f (a)&b2 = f (a)b1 = b2.

Покажем от противного, что f -1— сюръекция.

ПустьaϵАbϵВ a = f -1(b). ТогдаaϵАbϵВa≠f -1(b). Обозначимэтотэлементa0. Имеемba0≠f -1 (b) bb≠f (a0) a0fAА→ a0А.

Пусть f:A→ В ипусть А1⊂ A, В1⊂В. Тогда множество

F(А1) = {bϵ В |аϵА1b = f(а)}

называется образом множества А1, а множество

F-1(В1) = { аϵ А |bϵВ1b = f(а)}

прообразом множества В1. Заметим, что Fявляется отношением из множества 2fAв множество 2fB:

F = {(Al,B1) | А1A& В1 В & В1= F(А1)}.

Теорема. Если f:A→ В функция, тоF: 2fA→ 2fBи F-1: 2fB→ 2fA– тоже функции.

Fназывается индуцированной функцией, а F-1— переходом к прообразам.

Принцип Дирихле. Пусть f:A→ В– функция, причем Х и Y – конечные множества. Если |Х|>то по крайней мере одно значение fвстретится более одного раза. Неформально, принцип Дирихле можно например записать следующим образом:

Если Х – множество белок, аY – множество клеток, и |Х| = 12, а |Y| =11, то 12 белок нельзя посадить в 11 клеток так, чтобы в каждой клетке находилась одна белка.