- From: Russell Steven Shawn O'Connor <roconnor@uwaterloo.ca>
- Date: Wed, 12 Apr 2000 13:18:46 -0400 (EDT)
- To: www-math@w3.org

On Wed, 12 Apr 2000, David Eppstein wrote: > "Russell Steven Shawn O'Connor" <roconnor@uwaterloo.ca> writes: > > Are you saying that if an application wants to read the argueably > > meaningless statement [f(x) = 5x + 6x^2 + O(x^3)], then it has to figure > > out that it really means [f(x) - 5x - 6x^2 $isin; O(x^3)]. I suppose > > that's fair. > > In what sense is the first statement meaningless? To me, it means that > there exists a function g(x) and numbers c and x0, such that for all > x>x0, g(x)<=cx^3, and such that f(x) = 5x + 6x^2 + g(x). So, the > equality really is an equality, and the O is a convenient shorthand for > "a function I don't want to bother naming, that has certain asymptotic > growth behavior". That is also a valid definition of the meaning of (1), but note that in both your case and in my case we hand to translate the statement into something else. I rearranged stuff and used set inclusion. Your rearranged a bit less, but added two quantifiers. Either way the point is that if the statement is going to get used by a computer, it is going to have to get translated into a first-order statement. In that sense (1) is meaningless because it is not a first-order statement. That is why I was concerned, but now I get the impression that it is up to whatever UA to perform the translation from (1) into a meaningful FO statement. > I think it is incorrect to say that the two > statements are the same or that the first one "really means" the second. > For instance, I would hope that a symbolic algebra system might know > enough to simplify the first expression to f(x)=O(x^3) since the other > two terms on the rhs have lower growth rates, while the second > expression should not be simplified. why not. f(x) = O(x^3) iff f(x) - 5x - 6x^2 = O(x^3). It seems fair to simplify the second expression if interpreting it. > If you want to argue about sloppy definitions wrt O-notation, [Good example...] Okay this brings up a very good point. This is how I see the world. O(f(x)) is either a subset of functions from R to R, or perhaps in yoru quantifier case g(x) must be a function from R to R (otherwise the comparison g(x) <= c*x^3 makes no sense). If f is a function from R^2 to R, then one can't apply the normal definition. Once has to curry f, and make a new function F(d)(x) (often writeens as F<sub>d</sub>(x) ), where F is a function from R to the set of function from R to R. Since currying wrt the first variable is different from currying wrt the second variable, one can't determine how to curry without the authours help. So MathML needs a curry object. But you might feel (and so do I) that a currly function makes MathML to complex. Currying isn't really taught in K-13. But I don't see how one can actually encode spemantics without getting your hands dirty like this. -- Russell O'Connor roconnor@uwaterloo.ca <http://www.undergrad.math.uwaterloo.ca/~roconnor/> ``Paradoxically, a refusal to `put a monetary value on life' means that life is often undervalued.'' -- Artificial Intelligence: A Modern Approach

Received on Wednesday, 12 April 2000 13:18:48 UTC