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

Поскольку f — биекция, имеем (b₁ = f (a)& b₂ = f (a) b₁ = b₂) & (b = f(a₁) & b = f (а₂) a₁ = a ₂) & ( b ϵ В a ϵ А b = f(а)).

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

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

Пусть a₁ = f ^-1 (b) & а₂ = f ^-1 (b). Тогда b = f(a₁) & b = f (а₂ ) a₁ = a ₂.

Покажем, что f ^-1 — инъекция. Пусть a₁ = f ^-1 (b₁) & а₂ = f ^-1 (b₂). Тогда b₁ = f (a)& b₂ = f (a) b₁ = b₂.

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

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

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

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

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

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

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

F = {(A_l, B₁) | А₁ A & В₁ В & В₁= F(А₁)}.

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

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

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

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