1

Suppose we define a relation on functions $\mathbb{R}_{\geq 0}\rightarrow\mathbb{R}_{\geq 0}$ as follows: $f<<g$ if $f^n = o(g)$ for all $n$. Suppose we further mod out by the equivalence relation $f\cong g$ if $f<<g$ and $g<<f$. I'd like to know what the order type of the resulting order $<<$ on equivalence classes is. In particular, are there infinite descending sequences?

user270861
  • 13

1 Answers1

0

I believe there are. In particular, I think iterating $log$ will produce such a sequence. That is $$f_{n+1}= \log \circ f_n$$ and $f_0$ is the identity. You should try to prove this. (As I might not be right...)

I'm also pretty sure this is only a partial order, as oscillation can lead to incompatibilities.

Zach Stone
  • 5,701
  • I assume by f=o(g) you mean f(x)=o(g(x)) a x goes to $+\infty$. However if f is equivalent to g , then with n=2 we have f=o(g) and g=o(f) which implies f(x)=g(x)=0 for all sufficiently large x. – DanielWainfleet Sep 15 '15 at 05:02
  • Well, the setting both $f$ and $g$ to the constant function $1$ also works, so you skipped some steps in your argument. But this example is somehow trivial because its bounded. If we want to talk only about monotonically increasing functions, then the quotient shouldn't do anything interesting, as you suspect. The heart of the original question remains interesting, although I agree it is complicated by discussion of the quotient. – Zach Stone Sep 15 '15 at 05:15
  • My understanding of f(x)=o(g(x)) as x goes to infinity is that for any k>o the set of x for which |f(x)|>k|g(x)| has an upper bound. And $1\ne o(1)$, Are you sure you do not mean "O" not "o"? – DanielWainfleet Sep 15 '15 at 19:28
  • Yup, I misread that. I was thinking about big O. Amusingly, the log example still works, I think. – Zach Stone Sep 16 '15 at 02:07