In order-of-magnitude notation, the symbol = should not be interpreted as
equality and order-of-magnitude expressions cannot be treated like ordinary
expressions. Manipulations such as
are not sensible and can lead to incorrect conclusions. Still, if used properly, the
order-of-magnitude arguments can be effective, as we will see in later chapters.
Some functions can be represented by a set of pairs
where x i is an element in the domain of the function, and y i is the corresponding
value in its range. For such a set to define a function, each x i can occur at most
once as the first element of a pair. If this is not satisfied, the set is called a
relation. Relations are more general than functions: In a function each element
of the domain has exactly one associated element in the range; in a relation there
may be several such elements in the range.
One kind of relation is that of equivalence, a generalization of the concept of
equality (identity). To indicate that a pair (x, y) is in an equivalence relation, we
write
x ≡ y.
A relation denoted by ≡ is considered an equivalence if it satisfies three rules: the
reflexivity rule
the symmetry rule
and the transitivity rule
Example 1.4