8

Is there some existing notation for

\[f(n)\leq g(n)\] for sufficiently large n

Apart from just writing that itself? I'm thinking of something compact like the Landau notation $f\ll g$.

(Apologies if this is too specific for MathOverflow - just close it if so. I was also unsure what tags to add, so just edit it accordingly).

Rodrigo A. Pérez
  • 3,071
Thomas Bloom
  • 6,608

4 Answers4

13

In logic, this relation is called almost less than or equal, and is denoted with an asterisks on the relation symbol, like this: $f \leq^* g$.

For example, the bounding number is the size of the smallest family of functions from N to N that is not bounded with respect to this relation. Under CH, the bounding number is the continuum, but it is consistent with the failure of CH that the bounding number is another intermediate value.

Community
  • 1
Joel David Hamkins
  • 224,022
  • For example, in variations of this terminology set theorists often speak of the almost inclusion relation $A \subset^* B$, which means that A-B is finite. More generally, we have an ideal I and we use this notation to mean that A-B is in I. The structure P(omega)/Fin is extremely interesting, and uses this relation. – Joel David Hamkins Jan 06 '10 at 16:07
6

Why not just overload $\leq$ when applied to sequences? I don't think there is any opportunity for confusion, and it fits with the notation you would use when extending $\leq$ to an ultraproduct.

This is what Jim Henle does in his "non-nonstandard analysis", which uses "eventually" as a replacement for an ultrafilter.

Matt Noonan
  • 3,984
  • 4
    The ultrafilter usage would be a mathematically different concept. For example, with an ultrafilter the order is a total (linear) order, but almost-less-than is not. The almost-less-than relation in the question uses a mere filter, the Frechet filter of all co-finite sets. – Joel David Hamkins Jan 06 '10 at 16:10
  • 6
    There certainly is opportunity for confusion in overloading $\leq$. It's not uncommon to use $\leq$ to mean an entrywise comparison of sequences (or more generally pointwise comparison of functions). And since it's common (sloppy) practice to obscure the distinction between a sequence and its entries, many readers are likely to assume that's what $\leq$ means (or find it distracting nevertheless even if the meaning is clearly defined). – Mark Meckes Jan 06 '10 at 16:15
  • I still like the idea of using the same notation for a statement and the same statement extended to a product via a filter, but I also feel squeamish about almost-less-than not being a total order.. thanks for the food for thought! – Matt Noonan Jan 06 '10 at 16:19
  • 1
    @Mark: Point taken. Of course, that usage also fits with the filter usage, for the trivial filter. That said, if it needs this much justification then my suggestion is clearly not a good one. – Matt Noonan Jan 06 '10 at 16:22
5

Good notation should be self-explaining and not require the reader to remember to much. I would write either: $$ f\le g\quad\text{eventually}$$ $$ f\le g\quad\text{ near }\infty$$ If you use it more than 100 times in a paper you could use something like $$ f \preccurlyeq g.$$

Peter Michor
  • 24,985
2

I agree with Joel Hamkins's answer, but I don't entirely agree with his comment on that answer. I generally use asterisks to mean "with finitely many exceptions" or "modulo finite sets", so I'd use $f\leq^*g$ and $A\subseteq^*B$ as Joel says. But when working modulo some ideal $I$ other than the ideal of finite sets, I'd ordinarily avoid asterisks and instead write $f\leq_Ig$ and $A\subseteq_IB$.

I'd like to protest vigorously against the use of $\ll$ in this situation. To me, $f\ll g$ means that $f$ is a lot smaller than $g$ (at least eventually), whereas here you might have $f(n)=g(n)-1$ for all $n$.

Andreas Blass
  • 72,290
  • 2
    But then $\ll$ in analytic number theory and related fields has a very different meaning (referred to by OP); essentially a synonym for big-Oh. –  Dec 17 '12 at 15:54