Equivalence RelationsDate: 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/ |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994- The Math Forum at NCTM. All rights reserved.
http://mathforum.org/dr.math/