Finite Mathematics

Robert S. Wilson

3. Functions

Definition 3.1: Let A and B be two sets. A relation between elements of A and elements of B is a subset of A x B. If r is a relation between elements of A and elements of B, we will often write

a r b

instead of

Definition 3.2: Let A and B be two sets. A function from A to B is a relation between the elements of A and B such that each element of A is associated with only one element of B.

If f is a function from A to B we write

The condition that each element of A is associated with a unique element of B can be stated by saying that

if a = b, then f (a) = f (b).

This is called the well definedness property of a function.

Definition 3.3: If

A is called the domain of the function and B is called the range.

Definition 3.4: If A, B, and C are sets and

and

are functions, then the composition of f followed by g

is defined by

gf (a) = g (f (a ))

Theorem 3.1 (The Closure Property of Composition of Functions): If A, B, and C are sets and

and

are functions then the composition of f followed by g

is a function.

Definition 3.5: If

and the converse of the well definedness property is true, i. e.,

if f (a ) = f (b ) then a = b,

then the function is said to be one to one.

Definition 3.6: If

and if every element of B comes from some element of A, then we say that the function is onto.

Definition 3.7: If a function is both one to one and onto, we say that it is a one to one correspondence.

Definition 3.8: If A and B are two sets, and if there is a function

which is a one to one correspondence, then we say that A and B are equivalent.

Theorem 3.2: If A, B, and C are sets and

and

are functions where f and g are both one to one, then so is gf.

Theorem 3.3: If A, B, and C are sets and

and

are functions where f and g are both onto, then so is gf.

Theorem 3.4: If A, B, and C are sets and

and

are functions where f and g are both one to one correspondences, then so is gf.

Theorem 3.5 (The Associative Property of Composition of Functions): If A, B, C and D are sets and

and

are functions then

(hg )f = h (gf )

Definition 3.9: Let A be a set. The identity function on A denoted by

iA

is a function

defined by

iA (a ) = a

for all

Theorem 3.6: If A is a set then iA is both one to one and onto.

Definition 3.10: Let

be a one to one correspondence. Then the function

defined by

f -1 (b ) = a iff f (a ) = b

is called the inverse function of f.

Theorem 3.7: Let

be a one to one correspondence, then

is also a one to one correspondence.

Theorem 3.8: If

is a one to one correspondence, then

f -1f = iA and ff -1 = iB

4. Natural Numbers