RSA Laboratories

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.

Consider the set Z of integers. We may define a function f : Z ® Z such that f(x) = x2 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.

Let N be the set of nonnegative numbers. With f : Z ® N defined as f(x) = x2 and g : N ® Z defined as g(y) = y-y2, we obtain that g °f : Z ®Z is the function h defined as

h(x) = g(x2) = x2 - x4.

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 fS : S ® B defined as fS(s) = f(s) for all s Î S.


  • The function f : Z ® Z defined as f(x) = x3 is injective, because x3 = y3 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.

Top of the page