Theorem 1 (Moebius Inversion).
Proof: Fix some . Assuming (1), we have
Conversely, assuming (2), we get
G.-C. Rota has described a generalization of the Möbius formalism. In it, the set , ordered by the relation between elements and , is replaced by a more general ordered set, and is replaced by a function of two variables.
becomes a monoid if we define the product of any two of its elements, say and , by
The sum makes sense because is nonzero for only finitely many values of . (Clearly this definition is akin to the definition of the product of two square matrices.)
Consider the element of defined simply by
The function , regarded as a matrix over , has an inverse matrix, say . That means
Thus for any , the equations
Now let’s sketch out how the traditional Möbius inversion is a special case of Rota’s notion. Let be the set , ordered by the relation between elements and . In this case, is essentially a function of only one variable:
Proposition 3: With the above notation, for all such that .
The proof is fairly straightforward, by induction on the number of elements of the interval .
Now let be a function from to some additive group, and write for all pairs such that .
Example: Let be a set, and let be the set of all finite subsets of , ordered by inclusion. The ordered set is left-finite, and for any such that , we have , where denotes the cardinal of the finite set .
An Additional Generalization
|Date of creation||2013-03-22 11:46:58|
|Last modified on||2013-03-22 11:46:58|
|Last modified by||mathcam (2727)|
|Defines||Mobius inversion formula|