If not an upper bound, is it a lower bound?

Question

I wanted some help with a bounding question. The question asks that if $f$ is not an upper bound on $g$, is it a lower bound? $f,g: \mathbb{N} \to \mathbb{N} \cup \{\infty\}$.

By definition for an upper bound, there exists a constant $c$, there exists a constant $n_0$ such that $f(n) \le c \cdot g(n)$ for all $n > n_0$.

Negating that suggests for all $c$, for all $n_0$, $f(n) > c\cdot g(n)$.

So it would seem like the statement is true, but is it?

Thanks.

Try $g(n) = n$ and $f(n) = 0$ for even $n$ and $f(n) = n!$ for odd $n$. — Louis, Jan 30 '13 at 16:14
Your don't negate the statement correct. It would be: $\exists n>n_0$ such that $f(n)>c\cdot g(n)$. — Thomas, Jan 30 '13 at 16:16

score 1 · Accepted Answer · answered Jan 30 '13 at 16:27

Let $$f(n)=\begin{cases}1&n\text{ odd}\\n&n\text{ even}\end{cases}$$ $$g(n)=\begin{cases}1&n\text{ even}\\n&n\text{ odd}\end{cases}$$ Then $f$ is neither an upper nor a lower bound for $g$ in the sense of your question. Whatever positive real $c$ (and natural $n_0$ ) you choose, $f(n)\le cg(n)$ becomes false as soon as $n>c$ (and $n_0$) is even and $f(n)\ge cg(n)$ becomes false as soon as $n>\frac1c$ (and $n_0$) is odd.

Note that the negation of $$ \exists c\exists n_0\forall n>n_0\colon f(n)\le cg(n)$$ is rather $$ \forall c\forall n_0\exists n>n_0\colon f(n)> cg(n)$$ and that is not the definition of lower bound.

If not an upper bound, is it a lower bound?

1 Answers1