Associated Topics || Dr. Math Home || Search Dr. Math

### Equivalence Relations

```Date: 08/12/2003 at 16:23:16
From: Ryan
Subject: Equivalence relations

If I have a function that maps from R to R (where R is the reals) and
a set of functions, say O(f), for g where there exist constants c and
a in R+ (positive reals), where |g(x)| <= c|f(x)| for x > a, how would
I define a relation, say Q, on the set of functions mapping R to R by
putting (g,h) in R iff g-h is in O(f)?

The confusing part to me is understanding what a real life
interpretation would be of the problem. It's difficult for me to just
pull a relation out of thin air without actually knowing what I'm
supposed to be relating.

I tried going through to find a relation that would be reflexive,
where (x,x) in R, along with symmetric, where if (x,y) is in R that
implies (y,x) is in R, and transitive, where if (x,y) and (y,z) are
in R, then that implies (x,z) are in R. But i've failed at all my
attempts. If i can just get pointed in the right direction to obtain
the equivalence relation I will be able to begin the proof that is in
fact an equivalence relation.
```

```
Date: 08/13/2003 at 09:52:25
From: Doctor Jacques
Subject: Re: Equivalence relations

Hi Ryan,

This is called the "big-oh" notation.

notation.

We want basically to describe how fast a function grows for large
values of its argument, without worrying about possibly irrelevant
details.

This is very often used in the description of algorithms. Consider,
for example, an algorithm for solving a system of n linear equations
in n unknowns, like the standard Gauss-Jordan elimination algorithm.
It can be shown that the running time of that algorithm is O(n^3).
This means that, for sufficiently large n, the running time will be
less than c*n^3, for some constant c.

Note that the constant is left unspecified, because the exact number
of operations is rather difficult to compute, and may vary depending
on specific implementation details, and it will also sometimes depend
on the inputs. We also say that the inequality holds for "sufficiently
large" n, because, for smaller systems, it is possible that some
operations like initial setup, reading, and printing the data will
overweigh the actual computation time. The important point is that,
for large systems, if you have twice as many equations, you will not
spend more than abour eight times the effort.

Other examples can be found in number theory. For example, there is a
formula that gives the overall density of prime numbers. This formula
is not exact - the distribution of primes is quite irregular - but it
allows us to estimate the approximate number of primes less than a
given number N, and also to estimate the possible error. This error
is described using the "big oh" notation, because the exact value is
not known, and the whole point of the formula is to have an idea of
how things go for large N.

When we say "x > a ==> |g(x)| < c*|f(x)|" :

* The "x > a" part means that we only consider what happens for large
values of x.
* The "c" part means that we are interested in how fast the function
grows, not in the exact value of the function.

Note that, in the definition, you can always replace a and c by
larger values a' > a and c' > c. Indeed, if we know that:

x > a ==> |g(x)| < c*|f(x)|

then we may also write:

x > a' ==> |g(x)| < c'*|f(x)|

since x > a' implies x > a, and |g(x)| < c*|f(c)| implies
|g(x)| < c'*|f(c)| in that case. We will use this property later.

Let us now return to the problem at hand. We have a fixed function
f(x), and we consider the functions in O(f).

The _definition_ of the relation R is exactly what you have written:
for two functions g and h, we have (g,h) in R if |g-h| is in O(f) (we
usually simply say ".. is O(f)").

This means that (g,h) is in R if there exist positive numbers a and c
such that:

x > a ==> |g(x) - h(x)| < c*|f(x)|

Note that the values of a and c may (and usually will) very well
depend on the particular choice of functions g and h.

This means that the difference between g and h is "of the order of f,"
i.e. it does not grow faster than some multiple of f. In some sense,
this measures the extent of the error made when using g instead of h.

We want to show that this is indeed an equivalence relation.

The relation is reflexive
-------------------------
We must show that, for any function g, we can find a and c such that:

x > a ==> |g(x)-g(x)| < c*|f(c)|

Since the left-hand side is 0, this will be true for any a and c
(there would be a problem if f = 0, but we may exclude this case;
alternately, we may replace "<" with "<=" in the definition, since we
are only interested in approximations).

The relation is symmetric
-------------------------
This results from the fact that we use the absolute value of (g - h);
I'll let you fill in the details.

The relation is transitive
--------------------------
This is the hardest part. Assume that R contains (g, h) and (h, k).
This means that there exist positive numbers a1, a2, c1, and c2 such
that:

x > a1 ==> |g(x) - h(x)| < c1*|f(x)|
x > a2 ==> |h(x) - k(x)| < c2*|f(x)|

We must find a3 and c3 such that:

x > a3 ==> |g(x) - k(x)| < c3*|f(x)|

Now is the time to use the remark I made previously. Pick any number
a3 greater than both a1 and a2, and any number d greater than c1 and
c2.

Assume that x > a3; then we have x > a1 and x > a2. By hypothesis, we
have:

|g(x) - h(x)| < c1*|f(x)| < d*|f(x)|
|h(x) - k(x)| < c2*|f(x)| < d*|f(x)|

If we add those inequalities together, we get:

|g(x) - h(x)| + |h(x) - k(x)| < 2d*|f(x)|

We can use the "triangle inequality":

|A + B| <= |A| + |B|

which is true for all real numbers A and B. In this case, we use:

A = g(x) - h(x)
B = h(x) - k(x)
A + B = g(x) - k(x)

and this yields:

|g(x) - k(x)| <= |g(x) - h(x)| + |h(x) - k(x)| < 2d*|f(x)|

and, if we let c3 = 2d, we obtain:

|g(x) - k(x)| < c3*|f(x)|

As this is verified for all x > a3, this shows that (g,k) is in R, as
required.

some more, or if you have any other questions.

- Doctor Jacques, The Math Forum
http://mathforum.org/dr.math/
```
Associated Topics:
High School Calculators, Computers
High School Sets

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search