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.

Let us start with a few words about the "real-life" meaning of this 
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.

Does this help?  Write back if you'd like to talk about this 
some more, or if you have any other questions.

- Doctor Jacques, The Math Forum
  http://mathforum.org/dr.math/