Arithmetic rules for big O notation, little o notation and so on... There are many asymptotic notations like the big O notation: big Omega notation, little o notation, ... Thus there are many arithmetic rules for them. For example Donald Knuth states in Concrete Mathemtics (p. 436) the following rules (without a proof):


*

*$f(n)=O(f(n))$

*$c O(f(n)) = O(f(n))$, if $c$ is constant

*$O(O(f(n))) = O(f(n))$

*...


My Question: Can you recommend a reference where all arithmetic rules of the asymptotic notations are stated and proved? It would be great if also the connections between the asymptotic notations are formulated and shown, e.g. $O(o(f(n))=o(f(n))$.
My research results so far:


*

*The question What are the rules for equals signs with big-O and little-o? investigates the interpretation rules for the asymptotic notations.

*The Wikipedia article "Big O notation" states some rules but without a proof.

*(As already mentioned) there are some rules in Concrete Mathematics page 436 without proof.

*The article "Some Rules for Big-Oh Notation" lists some rules (without a proof).


Reason for my question: I write my thesis which heavily bases on asymptotic notations. I want to prove all the arithmetic rules I used which are a lot... (I also use other notations like the big Delta notation). A list of already proved arithmetic rules - which I can cite - would be great here ;-)
Update: I had an idea to minimize the number of needed arithmetic rules via generalizing the concept of asymptotic notations. I describe this idea in the MO thread Generalization of asymptotic notations like big O or little o notation.
 A: I had an idea how to shorten the list of arithmetic rules. Thanks to a comment by  Douglas Zare the list of necessary arithmetic rules became even shorter.
The idea: Note, that $O(\cdot)$ is fully described by knowing $O(1)$ because $$(\epsilon_n)_{n\in\mathbb N} \in O(a_n) \iff \left(\left|\frac{\epsilon_n}{a_n}\right|\right)_{n\in \mathbb N} \in O(1)$$ This circumstance can be condensed in the relation $a_ n O(1) = O(a_n)$. The above equivalence and characteristic equation $a_n A(1) = A(a_n)$ hold for other asymptotic notations too, i.e for all $A\in\{o,\omega, \Theta, S\}$ (whereby $(\epsilon_n)_{n\in\mathbb N} \in S(a_n)$ shall be the notation for $\epsilon_n \sim a_n$) [1].
Because asymptotic notations $A(\cdot)$ are fully defined by knowing $A(1)$ the list of necessary arithmetic rules gets shorter. For $A,B,C\in\{o,\omega, \Theta, S\}$ we find:


*

*$(1)_{n\in\mathbb N} \in A(1) \implies (a_n)_{n\in\mathbb N} \in A(a_n)$

*$A(1) \subseteq B(1) \implies A(a_n) \subseteq B(a_n)$

*$A(1)\cdot B(1) \subseteq C(1) \implies A(a_n)\cdot B(b_n) \subseteq C(a_n\cdot b_n)$

*$A(1)\cdot B(1) \subseteq C(1) \implies A(B(a_n)) \subseteq C(a_n)$

*$A(1)+ B(1) \subseteq C(1) \implies A(a_n) + B(a_n) \subseteq C(a_n)$


These rules are easy to prove when the property $a_n A(1) = A(a_n)$ is used. For example under the premise $A(1)+ B(1) \subseteq C(1)$ we get
$$A(a_n) + B(a_n) = a_n (A(1)+B(1)) \subseteq a_n C(1) = C(a_n)$$
The arithmetic rules for sets of the form $A(1)$ are often easy to show. For example $O(1)\cdot o(1) \subseteq o(1)$ is the well known proposition
$$\limsup_{n\to\infty} a_n < \infty \land \lim_{n\to\infty} b_n = 0 \implies \lim_{n\to\infty} a_n b_n = 0$$
Thus from rule 4 follow $O(a_n) \cdot o(b_n) \subseteq o(a_n \cdot b_n)$ and from rule 3 follows $O(o(a_n)) \subseteq o(a_n)$.
Conclusion: Many arithmetic rules follow directly for the arithmetic rules for sets of the form $A(1)$ via the relation $a_n A(1) = A(a_n)$. The rules for the sets $A(1)$ are often well known propositions of real analysis for sequences. See also https://math.stackexchange.com/questions/1521135/what-are-the-characteristic-properties-of-asymptotic-notations
A: 
A beautiful presentation can be found in N.G. De Bruijn classic: Asymptotic Methods in Analysis. You will find arithmetic rules of the Bachmann-Landau symbols in the section Introduction.
Another classic is Asymptotics and Special Functions by F.W.J. Olver. The first chapter Introduction to Asymptotic Analysis also provides a thorough introduction of $\sim, \mathcal{o}$ and $\mathcal{O}$ notation.

For a historical discussion I recommend the paper Big Omicron and Big Omega and Big Theta by D.E. Knuth.
A: Taking, for example, non negative case, following definition let us prove most of well known equalities as set equalities :
$O(g) =  \left\lbrace f:\exists C > 0, \exists N \in \mathbb{N}, \forall n (n >  N \& n \in \mathbb{N}) (f(n) \leqslant C \cdot g(n)) \right\rbrace $
$o(f)=\{g: \exists \epsilon, lim_{n \to \infty}\epsilon=0,  \exists N, n>N, g=\epsilon \cdot f   \}$
Firstly let me notice, that equality type $f=O(g)$ is quite different from type $O(f)=O(g)$. First means "$\in$", while under second we understand "$\subset \land \supset$".
a) Formal proof example:
$O(f) + O(g) = O(f+g) $

*

*"$\subset$".

let's take $ \varphi \in O(f) + O(g)$ then we have  $ \exists f_{1} \in O(f)$ and $  \exists g_{1} \in O(g)$ such, that $ \varphi = f_{1} + g_{1} $ and
$ \exists C_{1} > 0, \exists N_{1} \in \mathbb{N}, n >  N_{1}, \  f_{1}(n) \leqslant C_{1} \cdot f(n) $.
$ \exists C_{2} > 0, \exists N_{2} \in \mathbb{N}, \forall n >  N_{2},\ g_{1}(n) \leqslant C_{2} \cdot g(n) $.
So $ \varphi = f_{1} + g_{1} \leqslant C_{1} \cdot f + C_{2} \cdot g  \leqslant 2C \cdot (f + g)$, where $ max(C_{1}, C_{2}) = C $ and it holds when $ n>N = max(N_{1}, N_{2}) $. So $ O(f) + O(g) \subset O(f+g)$.


*"$\supset$".

Now let's take $ \varphi \in O(f+g) $. Then $ \exists C > 0, \exists N \in \mathbb{N}, n >  N $ such, that $ \varphi \leqslant C \cdot (f+g) = C \cdot f+ C \cdot g $. So we can write  $ \varphi - C \cdot f \leqslant C \cdot g $. Now let's take representation  $ \varphi = C \cdot f + \left( \varphi - C \cdot f\right)  $ and notice, that first member of sum is in $ O(f) $  and second in $ O(g) $. So  $ O(f+g) \subset O(f) + O(g) $.
b)$O(o(f))=o(f)$

*

*"$\subset$".

Firstly we take $f>0$ and then extend proof. let's take $\varphi \in O(o(f)) \Rightarrow \exists \psi \in o(f), \varphi \leqslant C \cdot \psi \Rightarrow \exists \epsilon, lim_{n \to \infty}\epsilon=0, \space \psi =\epsilon \cdot f \text{ and } \varphi \leqslant C \cdot \epsilon \cdot f$. Now we can set, that $lim_{n \to \infty}\frac{\phi}{f}=0$, so if we consider $\phi=\frac{\phi}{f} \cdot f$, then we obtain $\phi \in o(f)$. And at last lets for case $f \geqslant 0$ consider $N_1 \cap N_2 = \emptyset, N_1 \cup N_2 = \mathbb{N}$ and $0 \in f(N_1)$.
Write, please, which equality proof you would like to see.
A: The only result needed
to prove your first statement
is that
$\infty > 1 > 0$.
The only result needed
to prove the other statements
is that,
if
$\infty > a > 0$
and
$\infty > b > 0$,
then
$\infty > ab > 0$.
