Note that the order in which the elements of a pair are written matters. The pair
(4, 2) is in S 1 × S 2 , but (2, 4) is not.
The notation is extended in an obvious fashion to the Cartesian product of
more than two sets; generally
A set can be divided by separating it into a number of subsets. Suppose that
S 1 , S 2 , S n are subsets of a given set S and that the following holds:
1. The subsets S 1 , S 2 ,…S n are mutually disjoint;
2. S 1 ∪ S 2 ∪…∪ S n = S;
3. none of the S i is empty.
Then S 1 , S 2 ,…S n is called a partition of S.
Functions and Relations
A function is a rule that assigns to elements of one set a unique element of
another set. If f denotes a function, then the first set is called the domain of f,
and the second set is its range. We write
f : S 1 → S 2
to indicate that the domain of f is a subset of S 1 and that the range of f is a subset
of S 2 . If the domain of f is all of S 1 , we say that f is a total function on S 1 ;
otherwise f is said to be a partial function.
In many applications, the domain and range of the functions involved are in
the set of positive integers. Furthermore, we are often interested only in the
behavior of these functions as their arguments become very large. In such cases
an understanding of the growth rates may suffice and a common order of
magnitude notation can be used. Let f (n) and g (n) be functions whose domain is
a subset of the positive integers. If there exists a positive constant c such that for
all sufficiently large n