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

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

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

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.,

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

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

is a function

defined by

for all

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

Definition 3.10: Let

be a one to one correspondence. Then the function

defined by

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

4. Natural Numbers