FUNCTIONS

9.1 The definition of a Function

1. a function f from A to B, written as f . A -> B, is a relation from A to B, such that

such that f(a) = b.

The above definition means that for every a there is a b such that a gets mapped to
b by f, and it also means that a cannot be mapped to two different b -values.

2. note that not all the relations are functions. Only the ones that satisfy the above
definition. However, every function is a relation.

3. The set A is called the domain, set B is the codomain, every element of b ∈B for
which f(a) = b is called the image of a. Note that not all the elements of B are
images of elements of A, but these that are images will form the range of f. That is
ran

4. two functions f and g are equal, written as f = g iff they have the same domain and
codomain, and

9.2 The Set of All Function from A to B

1. we define the set of all possible functions from A to B to be
2. the number of such functions is
3. if B = {0, 1}, then we denote

9.3 One-to-One and Onto Functions

1. we say that f is a one-to-one or injective function if

2. in practice, most times it is easier to use the contrapositive of the statement above.

3. we say that f is a onto or surjective function if

such that f(a) = b.

That is, every element of the codomain is the image of some element of the domain,
i.e. every element of the codomain has a pre -image.

9.4 One-to-One Correspondence, or Bijective Functions

1. we say that f is a one-to-one correspondence or bijective function if f is both one-to-
one and onto.

2. the identity function by definition, is the function whose output equals the input, i.e.
f(x) = x, in the domain. The notation we will use for the identity function is

3. a function f . A -> B is defined, if

whenever a ∈A, then f(a) ∈B (i.e. B must be sufficiently large to contain all
the images of the elements of the domain)

whenever f(a) = b and also f(a) = b0, then it must be the case that b = b', where
This is the same as saying that each element of the domain has
a single image (i.e, if there are two images b and b' of the same element a, then
the two images must equal.) This condition alone is referred to as well-defined.

4. skip Result 9.6 as we have not talked about Z_n.

9.5 Composition of Functions

1. given two functions f and g,

f . A -> B and g . A -> B, we define the sum of f and g , denoted by f + g, to
be the function (f + g)(x) . A -> B, by (f + g)(x) = f(x) + (g(x).
f . A -> B and g . A -> B, we define the di erence of f and g, denoted by f -g,
to be the function (f - g)(x) . A -> B, by (f - g)(x) = f(x) - (g(x).
g . A -> B and f . B -> C, we define the composition of g and f, denoted by
, to be the function . A -> C, by

2. note that composition of functions is not commutative, i.e. , yet the sum
is. The difference is not commutative either.

3. composition of one-to-one functions is not always one-to-one. Similarly, for onto. See
Thm 9.7.

4. composition of bijective functions is always bijective (Cor 9.8).

5. composition of functions is associative (Thm 9.9.), i.e. in composing more than two
functions, the order the composition is computer doesn't matter.

9.6 Inverse Functions
-skip this section. I will mention it brie y.

9.7 Permutations
-skip this section. I will mention it brie y.