2
$\begingroup$

I am having a hard time trying to solve the following problem. I am very novice to the topic of growth functions at the moment. I could use a little help with this problem.

Let $\preceq$ be the relation on growth functions defined by $f \preceq g$ if there is a constant $\lambda \ge 1$ such that $f(x) \le \lambda g(\lambda x + \lambda) + \lambda$ for all $x \in [0, \infty)$. Show that $\preceq$ is symmetric and transitive and that the relation $f \sim g$ - is defined to mean both $f \preceq g$ and $g \preceq f$.

  • 0
    Okay, so I wasn't going crazy. I was getting a weird answer for the symmetric part.Thanks for your help. I will keep working on it.2012-05-28

1 Answers 1

3

The relation $\preceq$ isn’t symmetric.

Let $f(x)=1$ and $g(x)=x$ for all $x\in[0,\to)$. Then with $\lambda=1$ we have

$1=f(x)\le x+2=g(x+1)+1$ for all $x\in[0,\to)$, so $f\preceq g$. Now suppose that $g\preceq f$; then there is some $\lambda\ge 1$ be such that $x+1=g(x)\le\lambda f(\lambda x+\lambda)+\lambda=2\lambda$ for all $x\in[0,\to)$, which is clearly impossible. Thus, $f\preceq g\not\preceq f$, and $\preceq$ is not symmetric.

To show that $\preceq$ is transitive, you must show that if $f,g$, and $h$ are functions such that $f\preceq g$ and $g\preceq h$, then $f\preceq h$. Your hypothesis gives you constants $\lambda,\mu\ge 1$ such that $f(x)\le\lambda g\big(\lambda x+\lambda\big)+\lambda\tag{1}$ and $g(x)\le\mu h\big(\mu x+\mu\big)+\mu\tag{2}$ for all $x\in[0,\to)$, and you want to show that there is a constant $\nu\ge 1$ such that $f(x)\le\nu h\big(\nu x+\nu\big)+\nu$ for all $x\in[0,\to)$. If you combine $(1)$ and $(2)$ in the most obvious way, you get

$\begin{align*} f(x)&\le\lambda\Big(\mu h\big(\mu(\lambda x+\lambda)+\mu\big)+\mu\Big)+\lambda\\ &=\lambda\mu h\big(\lambda\mu x+\lambda\mu+\mu\big)+\lambda\mu+\lambda\;. \end{align*}$

What happens now if you take $\nu=\lambda\mu+\lambda+\mu\,$?