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
    I tried starting with the elementary concept of showing that something was symmetric, but it came out strange, and the last part of the question is confusing me.2012-05-28
  • 0
    What is your definition of *growth function*?2012-05-28
  • 0
    Any non- decreasing function $f : [o, \infty) \rightarrow [o, \infty)$ is a growth function.2012-05-28
  • 0
    Then $\preceq$ **isn’t** symmetric; I’ll post an answer in a minute.2012-05-28
  • 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\,$?