Incidence Algebra - Examples

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
\mu(x,y)=\begin{cases} 1 & \text{if }y-x=0, \\ -1 & \text{if }y-x=1, \\ 0 & \text{if }y-x>1, \end{cases}
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
\mu(S,T)=\begin{cases} 0 & \text{if } T\setminus S \text{ is a proper multiset (has repeated elements)}\\ (-1)^{\left|T\setminus S\right|} & \text{if } T\setminus S \text{ is a set (has no repeated elements)}.\end{cases}
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:

    “There are many examples of women that have excelled in learning, and even in war, but this is no reason we should bring ‘em all up to Latin and Greek or else military discipline, instead of needle-work and housewifry.”
    —Bernard Mandeville (1670–1733)

    “Histories are more full of examples of the fidelity of dogs than of friends.”
    —Alexander Pope (1688–1744)

    “It is hardly to be believed how spiritual reflections when mixed with a little physics can hold people’s attention and give them a livelier idea of God than do the often ill-applied examples of his wrath.”
    —G.C. (Georg Christoph)