How to prove that o(f(n)) is in O(f(n))?

Question

I tried to prove that "$o(f(n)) \in O(f(n))$".

I knew intuitively that the proposition is true, through the fact that $n^2=O(n^k), \forall k \ge 2$, but $n^2\ne o(n^k), \forall k>2$.

However, I want to prove this mathematically.

---

My proof:

$o(g(n)) = \{f(n): \forall c\gt0, \exists n_0>0 \ s.t. 0 \le f(n) \lt cg(n), \forall n \ge n_0\}$

$O(g(n)) = \{f(n): \exists c\gt0, \exists n_0>0 \ s.t. 0 \le f(n) \le cg(n), \forall n \ge n_0\}$

---

$\forall c > 0$ means "should satisfy for all $c$", while $\exists c>0$ means "should satisfy for some $c$"

$\therefore\{\forall c > 0\} \in \{\exists c>0\}$

Also, $\{f(n) \lt cg(n)\}\in\{f(n) \le cg(n)\}$

$$\therefore o(g(n)) \in O(g(n)) \Leftrightarrow o(f(n)) \in O(f(n))$$

---

I think my proof is ambiguous and defective because it is proved linguistically, not mathematically.

I hope somebody gives me any direction to prove mathematically. Thank you.

Answer 1

To complete the proof you need to show that there is at least one $c \gt 0$, so that you can go from $\forall c\gt0$ to $\exists c\gt0$; otherwise you may have a vacuous truth. Since the real numbers are an ordered field, $c=1$ is such an example. Thus

$$\forall c\gt0, \exists n_0>0 \ s.t. 0 \le f(n) \lt cg(n), \forall n \ge n_0$$ $$\implies c= 1, \exists n_0>0 \ s.t. 0 \le f(n) \lt cg(n), \forall n \ge n_0$$ $$\implies \exists c\gt0, \exists n_0>0 \ s.t. 0 \le f(n) \lt cg(n), \forall n \ge n_0$$

and thus $f(n)\in o(g(n)) \implies f(n)\in O(g(n))$ and so $o(g(n)) \subseteq O(g(n))$