## 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

i_{A}
is a function

defined by

i_{A} (a ) = a
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

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 ^{-1}f = i_{A} and ff ^{-1} =
i_{B}
4. Natural Numbers