Arithmetic rules for big O notation, little o notation and so on...
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.
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