The incidence algebra of a partial order was introduced in 1964 by Gian-Carlo Rota to investigate combinatorial facts.
Formal definition
Let be a partially ordered set (i.e., a set with a partial order ). The incidence algebra is defined as follows:
![{\ mathcal {I}} _ {M}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ce0edf1949f64615b237f257d275a9d0ba908203)
![{\ mathcal {I}} _ {M}: = \ {f: M \ times M \ rightarrow \ mathbb {R} \, | \, x \ nleq y \ Rightarrow f (x, y) = 0 \}](https://wikimedia.org/api/rest_v1/media/math/render/svg/20af638f1ddd83bf429566f8c2603f5ea02c0fc7)
The addition in is defined point by point, while the multiplication is given by a convolution :
![{\ mathcal {I}} _ {M}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ce0edf1949f64615b237f257d275a9d0ba908203)
![(f * g) (a, b) = \ sum _ {{a \ leq x \ leq b}} f (a, x) g (x, b).](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3343cea1efade7fc40ea8be29ba425c2c3dfb05)
Since the underlying partially ordered set is locally finite, this sum is finite.
properties
The algebraic structure is an associative algebra over the field of real numbers . It has one element , namely
![\ delta (a, b): = \ begin {cases} 1 \ quad & \ mbox {if} a = b, \\ 0 & \ mbox {otherwise.} \ end {cases}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a37bfd3d503f9092fed20f9dedd315156c9870ac)
Rota also defines the zeta function of the partial order,
![\ zeta (a, b): = {\ begin {cases} 1 \ quad & {\ mbox {if}} a \ leq b, \\ 0 & {\ mbox {otherwise,}} \ end {cases}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/76a3386d8aa26f924b21339c52df4378cadebea9)
as well as the incidence function by
The zeta function is invertible, its inverse is inductively defined as follows:
![{\ mathcal {I}} _ {M}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ce0edf1949f64615b237f257d275a9d0ba908203)
![\ mu](https://wikimedia.org/api/rest_v1/media/math/render/svg/9fd47b2a39f7a7856952afec1f1db72c67af6161)
![{\ displaystyle {\ begin {alignedat} {2} \ mu (a, a) & = 1, && a \ in M, \\\ mu (a, b) & = - \ sum _ {a \ leq x <b } \ mu (a, x), & \ qquad & a <b. \ end {alignedat}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/108473e5890a0cbe2d2de4286b07a7aae3c411ef)
These functions satisfy the equation .
![\ zeta * \ mu = \ delta](https://wikimedia.org/api/rest_v1/media/math/render/svg/caaf2cec2c14748797cf52450549f68588be97ca)
If one takes the set of natural numbers and the partial order resulting from the divisibility relation, the following relationship exists between this function and the classic Möbius function :
![M.](https://wikimedia.org/api/rest_v1/media/math/render/svg/f82cade9898ced02fdd08712e5f0c0151758a0dd)
![\ mu _ {0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/fe2fd9b8decb38a3cd158e7b6c0c6e2d987fefcc)
![\ mu _ {0} \ left ({\ frac {m} {n}} \ right) = \ mu (n, m), \ quad n, m \ in {\ mathbb {N}}, n \ mid m .](https://wikimedia.org/api/rest_v1/media/math/render/svg/5546a1d4582b7cab06ce265e5c497495561b9e9c)
Apparently for this reason Rota calls this function the Möbius function of the partial order.
![\ mu](https://wikimedia.org/api/rest_v1/media/math/render/svg/9fd47b2a39f7a7856952afec1f1db72c67af6161)
Generalized Möbius inverse formula
The equation leads to the following generalization of Möbius' inverse formula : Let be a locally finite partial order, a real-valued (or complex-valued) function and an element with for . Accepted,
![\ zeta * \ mu = \ delta](https://wikimedia.org/api/rest_v1/media/math/render/svg/caaf2cec2c14748797cf52450549f68588be97ca)
![(M, \ leq)](https://wikimedia.org/api/rest_v1/media/math/render/svg/cf40aedf9d6403c5cfdbb5710ae07a2865757f56)
![f](https://wikimedia.org/api/rest_v1/media/math/render/svg/132e57acb643253e7810ee9702d9581f159a1c61)
![M.](https://wikimedia.org/api/rest_v1/media/math/render/svg/f82cade9898ced02fdd08712e5f0c0151758a0dd)
![p \ in M](https://wikimedia.org/api/rest_v1/media/math/render/svg/35ad2c18a15749505c928763cd4fdb56f4982816)
![f (x) = 0](https://wikimedia.org/api/rest_v1/media/math/render/svg/cf85883d74b75fe35ca8d3f2b44802df078e4fa1)
![x <p](https://wikimedia.org/api/rest_v1/media/math/render/svg/aa1bd94804b46ebc27c1bf2470175ea5d431098f)
![g (x): = \ sum _ {{y \ leq x}} f (y),](https://wikimedia.org/api/rest_v1/media/math/render/svg/d319bce613f7c9d584206735a582118dd5dada07)
then applies
![f (x) = \ sum _ {{y \ leq x}} g (y) \ mu (y, x).](https://wikimedia.org/api/rest_v1/media/math/render/svg/7c6ea38faadcf86fb1b81aa3b2a076e743a6e1ac)
Further properties of the μ-function
In the cited work Rota proves a few more properties of its μ-function:
duality
If the partial order is too dual (it is created by reversing the order relation), then applies
![M ^ {*}: = (M, \ geq)](https://wikimedia.org/api/rest_v1/media/math/render/svg/6a1fdd6bfda9cb7f7e61a3df3e8f286dd44c248b)
![(M, \ leq)](https://wikimedia.org/api/rest_v1/media/math/render/svg/cf40aedf9d6403c5cfdbb5710ae07a2865757f56)
![\ mu ^ {*} (x, y) = \ mu (y, x) \ quad {\ mathrm {f {\ ddot u} r \ all}} \ quad x, y \ in M.](https://wikimedia.org/api/rest_v1/media/math/render/svg/de4bc2ec914e4b2f7f5392172aed29905f0489de)
Segmentation
If one regards an interval as a separate partial order, its μ-function is equal to the restriction of the μ-function of to this interval.
![[a, b] \ subset M](https://wikimedia.org/api/rest_v1/media/math/render/svg/7f08560ffa24a9346793ff83ed9952445bf32f73)
![M.](https://wikimedia.org/api/rest_v1/media/math/render/svg/f82cade9898ced02fdd08712e5f0c0151758a0dd)
Direct product
If and are two partial orders, their direct product is the set with the partial order
![(M, \ leq _ {M})](https://wikimedia.org/api/rest_v1/media/math/render/svg/9c5afef629ab6c2d4e6b6ebef07b663fe1503aeb)
![(N, \ leq _ {N})](https://wikimedia.org/api/rest_v1/media/math/render/svg/47852d15ac6a23160fae2efd170e80086129abc4)
![M \ times N](https://wikimedia.org/api/rest_v1/media/math/render/svg/77b09b633429cadcb3f0ddeadc6dcbe7bd65fb13)
![(x, y) \ leq _ {{M \ times N}} (u, v): \ Leftrightarrow x \ leq _ {M} y {\ text {and}} u \ leq _ {N} v \ quad { \ mathrm {f {\ ddot u} r \; all}} \ quad x, u \ in M, y, v \ in N.](https://wikimedia.org/api/rest_v1/media/math/render/svg/8248a288b7182e1b086521bb09440eb91811c5ff)
The μ-function of the direct product results from the individual μ-functions as follows:
![\ mu ((x, y), (u, v)) = \ mu (x, u) \ mu (y, v) \ quad {\ mathrm {f {\ ddot u} r \; all}} \ quad x, u \ in M, y, v \ in N](https://wikimedia.org/api/rest_v1/media/math/render/svg/e77a47a2f0cb807e217942907c48f16e015a346a)
Relationship to the principle of inclusion and exclusion
The power set of a finite set is, with the subset relation as a relation, a partial order. Whose μ-function is
![P (M)](https://wikimedia.org/api/rest_v1/media/math/render/svg/afa81e21b1d085edd94f267faa1546609999affd)
![M.](https://wikimedia.org/api/rest_v1/media/math/render/svg/f82cade9898ced02fdd08712e5f0c0151758a0dd)
-
,
where denotes the number of elements of . Otherwise is .
![| z |](https://wikimedia.org/api/rest_v1/media/math/render/svg/28fd4d7dcabf618d707c21bd08306c7b3aa8b68e)
![z](https://wikimedia.org/api/rest_v1/media/math/render/svg/bf368e72c009decd9b6686ee84a375632e11de98)
![{\ displaystyle \ mu (x, y) = 0}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ac5bf04aba583ea5fc7d2b207f39047287487488)
From this sentence emerges the principle of inclusion and exclusion .
literature
- Gian-Carlo Rota: On the Foundations of Combinatorial Theory I: Theory of Möbius Functions . In: Journal of Probability Theory and Related Areas . Vol. 2, 1964, pp. 340-368 , doi : 10.1007 / BF00531932 .