What is f(x) ≤ g(x) + O(1)? Inequalities With Asymptotics
jamesoswald.dev
jamesoswald.dev
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.
You can do this sort of "particular solution plus kernel" analysis on any linear operator, which gives one strategy for solving linear differential equations. e.g. (aD^2+bD+cI) is a linear operator (weighted sums and compositions of linear operators are linear), so you can potentially do that analysis to solve problems like af''+bf'+cf=g. In that context you say the general solution is to add a homogeneous solution (af''+bf'+cf=0) to a particular solution (my intro differential equations class covered this but didn't have linear algebra as a prereq so naturally at the time it was just magic, like everything else presented in intro diffeq).
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.
f = g + O(h)
and then proceed to do a bunch of manipulations without getting bogged down in set theory syntax.
Also equality isnt just defined on sets, usually people start by defining it as like a formal thing satisfying a bunch of rules as a part of their logic, and going from there.
That's why clear notation is important. Yours is kinda fine, but would be better with "≃".
e^x ≃ 1 + x + O(x^2) would only assert that lim (x->0) (e^x)/(1+x) = 1.
However "e^x = 1 + x + O(x^2)" means that for some function r(x) belonging to the set O(x^2), e^x is exactly equal to 1 + x + r(x). Another way to rewrite that equation that eliminates the "abuse of notation" would be:
e^x − (1 + x) ∈ O(x^2)
> 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.
Lean is much more notorious for mathematics.
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.
We can enumerate all programs up to a given length, so up to that limit all sets of functions are functions.
f(x)=O(g(x)) still makes sense in exactly this way: if g(x) is 1, then f(x) is a function that is O(1) right? How do we know g(x) is 1? Because all programs of some length that compute f(x) have that property. Of course there are longer programs that do it, and shorter programs that don't, and other programs still, but we're talking about these ones.
f(x)<O(g(x)) then says that the f(x) must be shorter than that; it isn't a member of the set.
What do you think I am missing?
After being a software engineer for a while, coming back to mathematics really felt like this at times. Amazingly good analogy.
I have always thought that expressing it like that instead of f(x) ∈ O(g(x)) is very confusing. I understand the desire to apply arithmetic notation of summation to represent the factors, but "concluding" this notation with equality, when it's not an equality... Is grounds for confusion.
f(x) = g(x) + O(1)
f(x) - g(x) = O(1)
it's a notation for "some element of that set"
You get:
f(x) - g(x) ≤ O(1)
f(x) - g(x) = O(1)
f(x) - g(x) ≤ O(1)
I think first we should teach "f in O(g)" notation, then teach the above, then observe that a special case of the above is the "abuse of notation" f(x) = O(g(x)).
Programmers wringing their hands over the meaning of f(x)=O(g(x)) never seem to have manipulated any expression more complex than f(x)=O(g(x)).