A.1 Functions
A function f from a set A to a set B assigns to each element a in A a unique element b in B. For each element a Î A, the corresponding element in B assigned to a by f is denoted f(a); we say that a is mapped to f(a). The notation f :A ® B means that f is a function from A to B.
Example
Consider the set Z of integers. We may define a function f : Z ® Z such that f(x) = x^{2} for each x Î Z. For example, f(5) = 25.
Let f : A ® B and g : B ® C be functions. The composition g °f of g and f is the function h : A® C defined as h(a) = g(f(a)) for each a Î A. Note, however, that ``f °g'' does not make sense unless A = C.
Example
Let N be the set of nonnegative numbers. With f : Z ® N defined as f(x) = x^{2} and g : N ® Z defined as g(y) = y-y^{2}, we obtain that g °f : Z ®Z is the function h defined as
h(x) = g(x^{2}) = x^{2} - x^{4}.
A function f : A ® B is one-to-one or injective if f(a) = f(a¢) implies that a = a¢, that is, no two elements in A are mapped to the same element in B. The function f is onto or surjective if, for each b Î B, there exists an element a Î A such that f(a) = b. Finally, f is bijective if f is one-to-one and onto. Given a bijective function f : A ® B, the inverse f^{-1} of f is the unique function g : B ® A with the property that g °f(a) = a for all a Î A. A bijective function f : A ® A is a permutation of the set A.
For any subset S of A, f(S) is the set of elements b such that f(a) = b for some a Î S. Note that f being surjective means that f(A) = B. The restriction of f to a subset S of A is the function f_{S} : S ® B defined as f_{S}(s) = f(s) for all s Î S.
Examples.
- The function f : Z ® Z defined as f(x) = x^{3} is injective, because x^{3} = y^{3} implies that x = y. However, f is not surjective; for example, there is no x such that f(x) = 2.
- Let |x| be the absolute value of x Î Z (for example, |-5| = |5| = 5). The function g : Z ®N defined as g(x) = |x| is surjective but not injective. Namely, for all x, the elements x and -x are mapped to the same element |x|. However, the restriction of g to N is injective and surjective, hence bijective.
- If A and B are finite sets of the same size, then a function f : A ® B is injective if and only if f is surjective.