Examples
- Positive integers ordered by divisibility
- The Möbius function is μ(a, b) = μ(b/a), where the second "μ" is the classical Möbius function introduced into number theory in the 19th century.
- Finite subsets of some set E, ordered by inclusion
- The Möbius function is
- whenever S and T are finite subsets of E with S ⊆ T, and Möbius inversion is called the principle of inclusion-exclusion.
- Geometrically, this is a hypercube:
- Natural numbers with their usual order
- The Möbius function is
- and Möbius inversion is called the (backwards) difference operator.
- Geometrically, this corresponds to the discrete number line.
- Recall that convolution of sequences corresponds to multiplication of formal power series.
- The Möbius function corresponds to the sequence (1, −1, 0, 0, 0, ... ) of coefficients of the formal power series 1 − z, and the zeta function in this case corresponds to the sequence of coefficients (1, 1, 1, 1, ... ) of the formal power series, which is inverse. The delta function in this incidence algebra similarly corresponds to the formal power series 1.
- Subgroups of a finite p-group G, ordered by inclusion
- The Möbius function is
- if is a normal subgroup of and
- and it is 0 otherwise. This is a theorem of Weisner (1935).
- Finite sub-multisets of some multiset E, ordered by inclusion
- The above three examples can be unified and generalized by considering a multiset E, and finite sub-multisets S and T of E. The Möbius function is
- This generalizes the positive integers ordered by divisibility by a positive integer corresponding to its multiset of prime divisors with multiplicity, e.g., 12 corresponds to the multiset
- This generalizes the natural numbers with their usual order by a natural number corresponding to a multiset of one underlying element and cardinality equal to that number, e.g., 3 corresponds to the multiset
- Partitions of a set
- Partially order the set of all partitions of a finite set by saying σ ≤ τ if σ is a finer partition than τ. Then the Möbius function is
- where n is the number of blocks in the finer partition σ, r is the number of blocks in the coarser partition τ, and ri is the number of blocks of τ that contain exactly i blocks of σ.
Read more about this topic: Incidence Algebra
Famous quotes containing the word examples:
“Histories are more full of examples of the fidelity of dogs than of friends.”
—Alexander Pope (16881744)
“In the examples that I here bring in of what I have [read], heard, done or said, I have refrained from daring to alter even the smallest and most indifferent circumstances. My conscience falsifies not an iota; for my knowledge I cannot answer.”
—Michel de Montaigne (15331592)
“It is hardly to be believed how spiritual reflections when mixed with a little physics can hold peoples attention and give them a livelier idea of God than do the often ill-applied examples of his wrath.”
—G.C. (Georg Christoph)