Is there a contradiction between "set-theoretic" and "formal" definition of "Big-O"?
The first statement you made is not correct. $O(n)$ is the set of all functions $f(n)$ that are bounded above by some constant multiple of $n$ for sufficiently large $n$. The functions you have listed all belong to the set $\Omega(n)$ which is almost like $O(n)$ but instead of being bounded above by $k\cdot n$, this is the set of functions that are bounded below by $k\cdot n$ for sufficiently large $n$.

So, there is no contradiction. But you do need to look at your definitions a bit more carefully.