2.2.1. Correspondences. Suppose that to each element of a set

A we assign some elements of another set B. For instance, A = N,

B = Z, and to each element x ∈N we assign all elements y ∈Z such

that y^2 = x (fig. 2.8).

Figure 2.8. Correspondence

This operation is called a correspondence.

2.2.2. Functions. A function or mapping f from a set A to a set

B, denoted f : A -> B, is a correspondence in which to each element

x of A corresponds exactly one element y = f(x) of B (fig. 2.9).

Figure 2.9. Function.

Sometimes we represent the function with a diagram like this:

For instance, the following represents the function from Z to Z

defined by f(x) = 2x + 1:

The element y = f(x) is called the image of x, and x is a preimage

of y. For instance, if f(x) = 2x + 1 then f(7) = 2 · 7 + 1 = 15. The

set A is the domain of f, and B is its codomain. If
the image

of A' by f is f(A') = {f(x) | x ∈A'}, i.e., the subset of B consisting

of all images of elements of A'. The subset f(A) of B consisting of

all images of elements of A is called the range of f. For instance, the

range of f(x) = 2x + 1 is the set of all integers of the form 2x + 1 for

some integer x, i.e., all odd numbers.

Example: Two useful functions from R to Z are the following:

1. The floor function:

= greatest integer less than or equal to x .

For instance:

2. The ceiling function:

least integer greater than or equal to x .

For instance:

Example: The modulus operator is the function mod : Z×Z^{+}
-> Z

defined:

x mod y = remainder when x is divided by y.

For instance 23 mod 7 = 2 because 23 = 3·7+2, 59 mod 9 = 5 because

59 = 6 · 9 + 5, etc.

Graph: The graph of a function f : A -> B is the subset of A × B

defined by G(f) = {(x, f(x)) | x ∈A} (fig. 2.10).

**2.2.3. Types of Functions.**

1. One-to-One or Injective: A function f : A -> B is called one-to-

one or injective if each element of B is the image of at most

one element of A (fig. 2.11):

Figure 2.10. Graph of f(x) = x^2.

For instance, f(x) = 2x from Z to Z is injective.

Figure 2.11. One-to-one function.

2. Onto or Surjective: A function f : A -> B is called onto or

surjective if every element of B is the image of some element of

A (fig. 2.12):

such that y = f(x) .

For instance, f(x) = x^2 from R to is onto.

Figure 2.12. Onto function.

3. One-To-One Correspondence or Bijective: A function f :
A ->

B is said to be a one-to-one correspondence, or bijective, or a

bijection, if it is one-to-one and onto (fig. 2.13). For instance,

f(x) = x + 3 from Z to Z is a bijection.

Figure 2.13. Bijection.

2.2.4. Identity Function. Given a set A, the function 1_{A}
: A ->

A defined by 1_{A}(x) = x for every x in A is called the identity function

for A.

2.2.5. Function Composition. Given two functions f : A ->
B

and g : B -> C, the composite function of f and g is the function

: A -> C defined by ()(x)
= g(f(x)) for every x in A:

For instance, if A = B = C = Z, f(x) = x + 1, g(x) = x^2,
then

()(x) = f(x)^2 = (x+1)^2. Also ()(x)
= g(x)+1 = x^2 +1 (the

composition of functions is not commutative in general).

Some properties of function composition are the following:

1. If f : A -> B is a function from A to B, we have that

2. Function composition is associative, i.e., given three functions

we have that

Function iteration. If f : A -> A is a function from A to
A, then

it makes sense to compose it with itself:
For instance, if

f : Z -> Z is f(x) = 2x + 1, then

Analogously we can define , and so on,

2.2.6. Inverse Function. If f : A -> B is a bijective
function, its

inverse is the function f^{−1} : B -> A such that f^{−1}(y) = x if and only

if f(x) = y.

For instance, if f : Z -> Z is defined by f(x) = x + 3,
then its

inverse is f^{−1}(x) = x − 3.

The arrow diagram of f^{−1} is the same as the arrow diagram
of f

but with all arrows reversed.

A characteristic property of the inverse function is that

and

2.2.7. Operators. A function from A × A to A is called a
binary

operator on A. For instance the addition of integers is a binary operator

+ : Z × Z -> Z. In the usual notation for functions the sum of

two integers x and y would be represented +(x, y). This is called prefix

notation. The infix notation consists of writing the symbol of the binary

operator between its arguments: x+y (this is the most common).

There is also a postfix notation consisting of writing the symbol after

the arguments: x y +.

Another example of binary operator on Z is (x, y) -> x · y.

A monary or unary operator on A is a function from A to A.
For

instance the change of sign x -> −x on Z is a unary operator on Z. An

example of unary operator on R* (non-zero real numbers) is x -> 1/x.