Find all positive increasing sequences $f, g:\mathbb{N}\to\mathbb{R}$ such that $$f(n)\notin O(g(n))\quad\mbox{and}\quad g(n)\notin O(f(n)) $$
$f(n)\in O(g(n))\iff \exists K>0,\exists N\in\mathbb{N} : n\geq N\Longrightarrow |f(n)|\leq K|g(n)| $
according to wiki
$$f(n)\notin O(g(n))\Longrightarrow\forall M>0, \forall n\in\mathbb{N}\, f(n) > Mg(n) $$
and 2.
$$g(n)\notin O(f(n))\Longrightarrow\forall K>0, \forall n\in\mathbb{N}\, g(n) > Kf(n) $$
Combined, for every $L>0$ and for every $n\in\mathbb{N}$:
$$g(n)<Lf(n)\quad\mbox{and}\quad g(n)>Lf(n) $$
INCORRECT
We have instead:
$$f(n)\notin O(g(n))\iff \forall M>0\ \forall n\in\mathbb{N}\ \exists N\in\mathbb{N} : N > n\quad\mbox{and}\quad f(N)>Mg(N) $$
Let's try to construct something like this:
Let $f(j) = x_j, \forall j\in\mathbb{N}$, where $x_j>0, \forall j\in\mathbb{N}$ and $f$ is increasing. Define $g(j) = y_j$ the same way.
Fix $M>0$ and $n\in\mathbb{N}$. There exist $N_1, N_2\in\mathbb{N}$ :
$$N_1>n\quad\mbox{and}\quad f(N_1)>Mg(N_1) $$
coupled with
$$N_2>n\quad\mbox{and}\quad g(N_2)>Mf(N_2) $$
Possibly need to make use of monotonicity. to be continued ..
You wrote:
(1) and (2) are not correct. Recall that $f(n) \in O(g(n)$ means that $$ \exists M > 0 \; \exists N \in \mathbb{N} \; \forall n > N \;:\; f(n) \le M g(n). $$ If we correctly negate this, we get that $f(n) \notin O(g(n))$ iff $$ \forall M > 0 \; \forall N \in \mathbb{N} \; \exists n \in \mathbb{N} f(n) > M g(n). $$ which is weaker than your statement.
As for classifying all such pairs of functions, you will have to have one subsequence $n_k$ where $\frac{f(n_k)}{g(n_k)} \to \infty$ and another subsequence $m_k$ where $\frac{g(m_k)}{f(m_k)} \to \infty$.