If $f$ and $g$ are increasing functions, are we guaranteed that $f=O(g)$ or $g=O(f)$? [duplicate]

Question

This question already has an answer here:

• Construct two functions $f$ and $g$ satisfying $f \ne O(g), g \ne O(f)$ 2 answers

Given two increasing functions $f$ and $g$ with values in the natural numbers, is it always the case that either $f\in O(g)$ or $g\in O(f)$.

If the statement is true, then can anyone provide a counterexample for when any of the two conditions in bold are relaxed.

If the statement is false, can someone provide a counterexample to show why

I believe that the statement is true and my attempt at the proof is by assuming without loss of generality that $f\notin O(g)$

$f\notin O(g)\implies\neg(\exists N\in\mathbb{N}$ s.t $f(n)\leq Cg(n)$, for some $C>0$ and $\forall n>N)$

$\implies\forall N\in\mathbb{N}\space,\space f(n)>Cg(n)$, for some $C>0$ and $\forall n>N$

Have I negated the expression correctly, because I can't see how I can get $g\in O(f)$ from this expression