[qsort]

I think the confusion is because strictly speaking $f(x) = O(g(x))$ is an abuse of notation. $O(g(n)), \Theta(g(n))$ and friends are sets. We can't say that a function equals a set, or that a function "is less" than another function, but notoriously mathematics runs on javascript, so we try to do something instead of giving a type error.

Here "is less" is interpreted as "eventually less for all values" and "plus a set" is interpreted as "plus any function of that set".

I never liked this notation for asymptotics and I always preferred the $f(x) \in O(g(x))$ style, but it's just notation in the end.

[sfpotter]

The reason it's preferred to use "=" instead of "\in" is because the way that Landau notation is generally used in practice is as a kind of ellipsis or placeholder. For example, the Taylor expansion e^x = 1 + x + O(x^2). I could just as well write e^x = 1 + x + ..., but the former conveys more meaning about what is hidden behind the ellipsis. It's an abuse of notation, but in the contexts that it's used, it's not clear what additional clarity using "\in" would bring over "=". Maybe also that big O is mainly used as a notation to facilitate doing calculations, less describing what family a function belongs to. Here are Knuth's thoughts, which I agree with: https://micromath.wordpress.com/2008/04/14/donald-knuth-calc...

[svat]

See also Terence Tao's comments at https://terrytao.wordpress.com/2022/05/10/partially-specifie... which say things even more strongly (I had collected a link to it at https://shreevatsa.wordpress.com/2014/03/13/big-o-notation-a...):

> The symbol ∈ only is a viable solution in a portion of the use cases. For instance, an assertion such as O(n)⋅O(n) = O(n²) would not be correctly describable as O(n)⋅O(n) ∈ O(n²). Perhaps O(n)⋅O(n) ⊂ O(n²) would be defensible, but now one has to devote a non-trivial amount of thought into deciding which of the connectives =, ∈, ∋, ⊂, ⊃ to use in a given context. For instance the assertion “Since sin(y) = sin(x) + O(|y−x|), we have sin(x+O(1/n)) = sin(x) + O(1/n)” would now become “Since sin(y) ∈ sin(x) + O(|y−x|), we have sin(x+O(1/n)) ⊂ \sin(x) + O(1/n)”. Using the equality sign for all of these use cases instead is more intuitive and corresponds more closely to how the verb “is” (“to be”) is actually used in mathematical English.

and

> … Nevertheless most of us still often think in mereological terms rather than set-theoretic or first-order terms […] without requiring translation to set theory or first order logic; indeed, such a translation would only serve to slow that mathematician down as he or she would usually have translate it back into mereological form in order to wield it effectively. Because of this, I think it is worth adjusting our notational conventions to more closely align with our actual thought processes… I don’t see much advantage in interpreting each instance of the O() notation in the exponential type bound f(n) = O(\exp(O(nᴼ⁽¹⁾))) or the calculation (1 + O(1/n))ᴼ⁽ⁿ⁾ = \exp(O(1/n)⋅O(n)) = \exp(O(1)) = O(1) (for n sufficiently large), in terms of ideals.

[marcosdumay]

You are talking about a completely different concept than the GP's.

That's why clear notation is important. Yours is kinda fine, but would be better with "≃".

[ndriscoll]

To me it seems similar to the + C on an antiderivative (or more generally, quotient objects). Technically, you are dealing with an equivalence class of functions, so a set. But it's usually counterproductive to think of it that way (and when you study this stuff properly, one of the first things you do is prove that you (usually) don't need to, and can instead use an arbitrary representative as a stand-in for the set), so you write F(x)+C.

[qsort]

I think the Landau notation is a bit more finicky with the details. When it's really a quotient (like modular arithmetic) I'm with you, but here $O()$ morally means "at most this" and often you have to use the "direction of the inequality" to prove complexity bounds, so I'm more comfortable with the set notation. But again, it's just notation, I could use either.

[ijustlovemath]

Huh, never thought about the potential connection between the set-containment operation and Stokes like that.

[geocar]

> We can't say that a function equals a set

Why not?

Can we not so easily speak of the set of all inputs and the set of all outputs? Why not exactly then is a function not a set of morphisms/arrows?

To me, x->x+1 and {(x,x+1)|x∈R} seem the same[1] but maybe it just seems useful to be able to make statements of the cardinality of that set: If there are a lot of rules, then that set is big, but if there are few rules (like x->x+1), that set is small. This is enough to permit some analysis.

It also preserves "plus" for sets, because a function plus a function is the sum of those rules being considered.

What is it do you think I am missing?

[1]: I understand I don't really mean big-R here because computers have limited precision for fadd/add circuits, so if you'd prefer I said something slightly differently there please imagine I did so.

[herni]

You miss the point here. Just because functions happen to be sets ZF does not mean sets of functions are functions. O(...) denotes a set of functions.

[foxes]

I feel its not that bad an abuse of notation as kinda consistent with other areas of mathematics -

A coset, quotients r + I, affine subspaces v + W, etc. Not literal sets but comparing some representative with a class label, and the `=, +` is defined not just on the actual objects but on some other structure used to make some comparison too.

[mathgradthrow]

No. Equality is defined on sets, with exactly one exception, this stupid fucking notation.

[computerfriend]

> notoriously mathematics runs on javascript

After being a software engineer for a while, coming back to mathematics really felt like this at times. Amazingly good analogy.

[charcircuit]

>but notoriously mathematics runs on javascript

Lean is much more notorious for mathematics.

[taejo]

The point GP is making, is that everyday mathematics is not done in Lean, but in a language that's more like JavaScript, where equals doesn't always mean equals, + and • mean whatever seems convenient at the time, and objects sometimes change type without notice.

[hyperpape]

Although, when I learned foundations of mathematics, every function was a set, and if you wanted them, you'd get plenty of junk theorems from that fact.

[qsort]

"Everything is an object" is for boys, "everything is the empty set composed with copies of itself via the axiom of pairing" is for men ;)

[NooneAtAll3]

when '=' is used, it no longer means "set", but "some element of that set" instead