Excuse my mathematical informality. But, this question is of great importance to me:
We know from the fundamental theorem of arithmetics that natural numbers are made up from elementary blocks we call primes, basically by means of multiplying certain unique primes we produce any number we want.
Jumping to Linear Algebra, if we take a look at a vector space spanned by a certain group of vectors we call a base, basically by means of adding certain unique base vectors we produce any vector we want.
The similarity is quite noticeable between the two examples:
- Every object has a unique elementary composition.
- The order of composing the object does not matter both addition and multiplication are commutative with respect to the fields they are defined in.
Back to the main question, I am looking for any other fields, where one could find the two properties presented in the above examples and preferably with an addition-like operation. (Something that does not cause a rapid increase in space complexity.)
The examples you give are both free objects in a certain category (left adjoints to the forgetful functor to sets). The multiplicative monoid of positive integers is the free monoid over the set of prime numbers. A vector space is the free vector space over a basis. (By the axiom of choice, every vector space is free.)
Other examples: Given a set $S$, we can form the free group over $S$, it consists of formal products of elements $s \in S$ and formal inverses $s^{-1}$. The order of the factors matters. When it does not, we obtain the free abelian group, where every element is uniquely represented as a formal sum of $s \in S$ with coefficients in $\mathbb Z$. The free module over a set (when fixing a ring) generalizes the notions of (free) vector spaces and free abelian groups.