6 ms·

Operators in mathematics are overloaded in a very similar way to operators in computer science (in languages that permit overloading). I think the author hints

Operators in mathematics are overloaded in a very similar way to operators in computer science (in languages that permit overloading). I think the author hints toward a good point: there is no use arguing over the meaning of "=" in a general sense, because the meaning is contextual. I think this whole discussion is merely indicative of inexperience on the part of computer scientists attempting to navigate mathematics.

deleted 9y ago
[deleted]
roywiggins 9y ago
CS already abuses equality all the time with big-O notation. Often you see stuff like f(n) = O(N²), when they mean that f ∈ O(N²). It's fine because everyone knows what's going on, but it's not using it in the sense of equality.
- gizmo686 9y ago
  Mathamaticians also abuse big-O in a simmilar way. For instance we might say: sin(x) = x -x^3/6 + x^5/120 + O(x^7) To indicate that the terms we did not write are in O(x^7). Also note that, in this case, we are actually looking at big-O as x->0.
  - xyzzyz 9y ago
    The statement about sine above is not something mathematicians would write. It makes little sense to use big-O notation in this context, as it doesn't say anything useful here: the O(x^7) element absolutely dominates the remaining explicit elements of lower order, so including them tells us absolutely nothing. In fact, sin(x) = O(1). However, mathematicians do indeed use similar notation in this context, that is, little-o notation. It is in fact true that sin(x) = x -x^3/6 + x^5/120 + o(x^5), x -> 0.
    - gizmo686 9y ago
      https://en.wikipedia.org/wiki/Taylor_series#First_example https://en.wikipedia.org/wiki/Taylor_series#First_example https://www.wolframalpha.com/input/?i=taylor+series+sin+x https://www.wolframalpha.com/input/?i=taylor+series+sin+x Notice that in your example, you have o(x^5) and an explicit x^5 term. In my example I have O(x^7), but no explicit x^7 term. It is true that I cannot think of a circumstance where you want to do this abuse of notation and would care if you were forced to use little-o or big-O instead of the other. In my experience, it happens to be more common to use big-O.
    - j2kun 9y ago
      I have definitely used big-O as the parent described. I think many mathematicians would write it in that way.
    - proto-n 9y ago
      Have you considered that higher orders of x are in fact smaller when x is near 0? The parent comment was right and you are wrong, around zero x^5 absolutely dominates x^7 and the big-O notation is used. See for example here [1] [1] https://en.wikipedia.org/wiki/Taylor_series#First_example https://en.wikipedia.org/wiki/Taylor_series#First_example
- danharaj 9y ago
  Sure it is, O notation denotes equivalence classes and being part of the same equivalence class is a perfectly cromulent notion of equality.
  - gizmo686 9y ago
    Big-theta gives you equivalence classes. Big-O only gives you partial ordering. For instance, we might say x = O(x^2) and x=O(x), but we would not say O(x^2)=O(x). Interestingly, in my experience, some people will actually say O(x)=O(x^2), but that seems a bit too abusive for my liking.
    - danharaj 9y ago
      Yea, my mistake :)
  - deleted 9y ago
    [deleted]
- svat 9y ago
  Sigh; it seems it's only programmers who think CS has a monopoly on big-O notation, or keep calling it abuse of notation and trying to use ∈, when it's really = that's the standard notation in mathematics (and for good reason). Before Knuth popularized Big O notation in CS and started the field of analysis of algorithms, already in 1958 N. G. de Bruijn wrote an entire book on Asymptotic Methods in Analysis (not CS): see a few of its leading pages here: https://shreevatsa.wordpress.com/2014/03/13/big-o-notation-a-couple-of-sources/ https://shreevatsa.wordpress.com/2014/03/13/big-o-notation-a... And the notation was already being used by Bachmann in 1894 and Landau by 1909 in analytic number theory, well before computers. It was perfectly commonplace to use big-O notation with the equals sign very quickly: see e.g. this paper by Hardy and Littlewood (https://projecteuclid.org/download/pdf_1/euclid.acta/1485887376 https://projecteuclid.org/download/pdf_1/euclid.acta/1485887...) from 1914, well before even Turing machines or lambda calculus were formulated, let alone actual computers or analysis of algorithms.
- js8 9y ago
  I was taught to use tilde in big-O notation. Your use of "set element" operator is not quite correct either, because of the limit that's going on there.
  - gizmo686 9y ago
    I don't think the limit is really an issue here. Most CS textbooks define big-O with the limit ->infinity part baked into the definition. So, this is more of an issue of different people using different definitions than an issue of abuse of notation.
contravariant 9y ago
While operators are 'overloaded' all the time, equality is a bit of a special case as it is part of logic rather than some algebraic operation. In model theory you don't require your models to have an equality operator, they have one simply by being logical constructs. Then again mathematicians use quotient spaces so transparently that you might as well consider: 5 = 1 (mod 4) as 'overloading the equality operator' even though the technical definition implies that those 5 and 1 are different from the 5 and 1 in the set of natural numbers, and in Z/4Z the symbols 1 and 5 refer to the same object.

deleted 9y ago

[deleted]

roywiggins 9y ago

CS already abuses equality all the time with big-O notation. Often you see stuff like f(n) = O(N²), when they mean that f ∈ O(N²). It's fine because everyone knows what's going on, but it's not using it in the sense of equality.

gizmo686 9y ago
Mathamaticians also abuse big-O in a simmilar way. For instance we might say: sin(x) = x -x^3/6 + x^5/120 + O(x^7) To indicate that the terms we did not write are in O(x^7). Also note that, in this case, we are actually looking at big-O as x->0.
- xyzzyz 9y ago
  The statement about sine above is not something mathematicians would write. It makes little sense to use big-O notation in this context, as it doesn't say anything useful here: the O(x^7) element absolutely dominates the remaining explicit elements of lower order, so including them tells us absolutely nothing. In fact, sin(x) = O(1). However, mathematicians do indeed use similar notation in this context, that is, little-o notation. It is in fact true that sin(x) = x -x^3/6 + x^5/120 + o(x^5), x -> 0.
  - gizmo686 9y ago
    https://en.wikipedia.org/wiki/Taylor_series#First_example https://en.wikipedia.org/wiki/Taylor_series#First_example https://www.wolframalpha.com/input/?i=taylor+series+sin+x https://www.wolframalpha.com/input/?i=taylor+series+sin+x Notice that in your example, you have o(x^5) and an explicit x^5 term. In my example I have O(x^7), but no explicit x^7 term. It is true that I cannot think of a circumstance where you want to do this abuse of notation and would care if you were forced to use little-o or big-O instead of the other. In my experience, it happens to be more common to use big-O.
  - j2kun 9y ago
    I have definitely used big-O as the parent described. I think many mathematicians would write it in that way.
  - proto-n 9y ago
    Have you considered that higher orders of x are in fact smaller when x is near 0? The parent comment was right and you are wrong, around zero x^5 absolutely dominates x^7 and the big-O notation is used. See for example here [1] [1] https://en.wikipedia.org/wiki/Taylor_series#First_example https://en.wikipedia.org/wiki/Taylor_series#First_example
danharaj 9y ago
Sure it is, O notation denotes equivalence classes and being part of the same equivalence class is a perfectly cromulent notion of equality.
- gizmo686 9y ago
  Big-theta gives you equivalence classes. Big-O only gives you partial ordering. For instance, we might say x = O(x^2) and x=O(x), but we would not say O(x^2)=O(x). Interestingly, in my experience, some people will actually say O(x)=O(x^2), but that seems a bit too abusive for my liking.
  - danharaj 9y ago
    Yea, my mistake :)
- deleted 9y ago
  [deleted]
svat 9y ago
Sigh; it seems it's only programmers who think CS has a monopoly on big-O notation, or keep calling it abuse of notation and trying to use ∈, when it's really = that's the standard notation in mathematics (and for good reason). Before Knuth popularized Big O notation in CS and started the field of analysis of algorithms, already in 1958 N. G. de Bruijn wrote an entire book on Asymptotic Methods in Analysis (not CS): see a few of its leading pages here: https://shreevatsa.wordpress.com/2014/03/13/big-o-notation-a-couple-of-sources/ https://shreevatsa.wordpress.com/2014/03/13/big-o-notation-a... And the notation was already being used by Bachmann in 1894 and Landau by 1909 in analytic number theory, well before computers. It was perfectly commonplace to use big-O notation with the equals sign very quickly: see e.g. this paper by Hardy and Littlewood (https://projecteuclid.org/download/pdf_1/euclid.acta/1485887376 https://projecteuclid.org/download/pdf_1/euclid.acta/1485887...) from 1914, well before even Turing machines or lambda calculus were formulated, let alone actual computers or analysis of algorithms.
js8 9y ago
I was taught to use tilde in big-O notation. Your use of "set element" operator is not quite correct either, because of the limit that's going on there.
- gizmo686 9y ago
  I don't think the limit is really an issue here. Most CS textbooks define big-O with the limit ->infinity part baked into the definition. So, this is more of an issue of different people using different definitions than an issue of abuse of notation.

contravariant 9y ago

While operators are 'overloaded' all the time, equality is a bit of a special case as it is part of logic rather than some algebraic operation. In model theory you don't require your models to have an equality operator, they have one simply by being logical constructs. Then again mathematicians use quotient spaces so transparently that you might as well consider: 5 = 1 (mod 4) as 'overloading the equality operator' even though the technical definition implies that those 5 and 1 are different from the 5 and 1 in the set of natural numbers, and in Z/4Z the symbols 1 and 5 refer to the same object.