Incidence Algebras and Möbius Inversion

Expanding the left bracketing and distributing the factor $h(v,y)$ through the inner sum gives $((f\ast g)\ast h)(x,y)={\sum }_{x\le v\le y}{\sum }_{x\le u\le v}f(x,u)g(u,v)h(v,y)$.

Put $D:=\{(u,v)\in [x,y{]}^2:u\le v\}$. Expanding the right bracketing gives $(f\ast (g\ast h))(x,y)={\sum }_{x\le u\le y}{\sum }_{u\le v\le y}f(x,u)g(u,v)h(v,y)$.

For every $x\le y$, $((f+g)\ast h)(x,y)={\sum }_{x\le z\le y}(f(x,z)+g(x,z))h(z,y)={\sum }_{x\le z\le y}f(x,z)h(z,y)+{\sum }_{x\le z\le y}g(x,z)h(z,y)$ by distributivity in $R$ and additivity of a finite sum; hence $(f+g)\ast h=f\ast h+g\ast h$.

The same calculation with the sum in the right factor gives $f\ast (g+h)=f\ast g+f\ast h$.

Extend the displayed summand by $0_R$ from $D$ to $[x,y{]}^2$. Splitting each finite inner sum into the admissible indices and the zero terms identifies steps 1.1 and 1.2 with its two iterated sums over $[x,y{]}^2$. Finite Fubini makes those iterated sums equal.

Since steps 2.1 and 1.2 agree for every comparable $(x,y)$, $(f\ast g)\ast h=f\ast (g\ast h)$.

Steps 3.1, 1.3 and 1.4 prove associativity and both distributive laws.

Since $I(P,R)$ is the set of functions from the comparable pairs of $P$ to $R$, [L1] makes it an abelian group under pointwise addition.

Associativity of convolution and both distributive laws are [L2].

For $x\le y$, $(\delta \ast f)(x,y)={\sum }_{x\le z\le y}\delta (x,z)f(z,y)=f(x,y)$ because only the term $z=x$ is nonzero.

Likewise $(f\ast \delta )(x,y)={\sum }_{x\le z\le y}f(x,z)\delta (z,y)=f(x,y)$ because only the term $z=y$ is nonzero.

Thus convolution is associative, distributes over the pointwise abelian-group operation, and has the two-sided identity $\delta$; these are exactly the ring axioms.

On a diagonal interval the equations $(f\ast g)(x,x)=1_R$ and $(h\ast f)(x,x)=1_R$ force $g(x,x)=h(x,x)=f(x,x{)}^{-1}$ by [L3].

Fix a natural $n$ and assume that $g$ and $h$ have been uniquely defined on every interval of cardinality less than $n$, with the required convolution equations there.

Let $x<y$ with $\mathrm{\mid }[x,y]\mathrm{\mid }=n$. Every $g(z,y)$ occurring in ${\sum }_{x<z\le y}f(x,z)g(z,y)$ belongs to the proper subinterval $[z,y]$, and every $h(x,z)$ in ${\sum }_{x\le z<y}h(x,z)f(z,y)$ belongs to the proper subinterval $[x,z]$; their cardinalities are less than $n$ by [F1] and [L2].

The displayed formulas in the Statement therefore assign unique values to $g(x,y)$ and $h(x,y)$, since the sums are finite and both diagonal inverses are unique.

Isolating the term $z=x$ in convolution gives $(f\ast g)(x,y)=f(x,x)g(x,y)+{\sum }_{x<z\le y}f(x,z)g(z,y)=0_R$ by the defining formula for $g(x,y)$.

Isolating the term $z=y$ gives $(h\ast f)(x,y)={\sum }_{x\le z<y}h(x,z)f(z,y)+h(x,y)f(y,y)=0_R$ by the defining formula for $h(x,y)$.

Steps 1.1 through 4.2, with strong induction on $\mathrm{\mid }[x,y]\mathrm{\mid }$, define $g$ and $h$ on every comparable pair and give $f\ast g=\delta$ and $h\ast f=\delta$.

Associativity and the identity law in [L4] now give $h=h\ast \delta =h\ast (f\ast g)=(h\ast f)\ast g=\delta \ast g=g$.

Hence the two recursive one-sided inverses coincide and their common value is a two-sided convolution inverse of $f$.

Suppose $f$ has a convolution inverse $g$. Evaluating $f\ast g=\delta$ at $(x,x)$ gives $f(x,x)g(x,x)=1_R$, and evaluating $g\ast f=\delta$ gives $g(x,x)f(x,x)=1_R$. Thus $f(x,x)$ is a unit for every $x$.

Conversely, if every $f(x,x)$ is a unit, [L1] constructs a two-sided convolution inverse of $f$.

Steps 1.1 and 1.2 prove both directions of the criterion.

Evaluating either inverse equation at $(x,x)$ gives ${\mu }_P(x,x)=1$.

Evaluating ${\mu }_P\ast \zeta =\delta$ at $x<y$ gives ${\sum }_{x\le z\le y}{\mu }_P(x,z)=0$.

Evaluating $\zeta \ast {\mu }_P=\delta$ at $x<y$ gives ${\sum }_{x\le z\le y}{\mu }_P(z,y)=0$.

Isolating the term $z=y$ in step 1.2 and the term $z=x$ in step 1.3 yields the two displayed recursive formulas.

Each right-hand side uses only proper subintervals, so induction on the finite cardinality of $[x,y]$ shows that either recurrence and the diagonal clause determine at most one function.

Steps 1.1 through 3.1 prove both sums, both recurrences and uniqueness.

Assume $P$ is lower-finite and $g(y)={\sum }_{u\le y}f(u)$ for every $y\in P$. Fix $y\in P$. Every index set below is contained in the finite principal ideal of $y$ by [F1]. Substitution and finite Fubini give ${\sum }_{x\le y}{\mu }_P(x,y)g(x)={\sum }_{u\le x\le y}{\mu }_P(x,y)f(u)={\sum }_{u\le y}f(u)({\sum }_{u\le x\le y}{\mu }_P(x,y))=f(y)$ by [L1].

Conversely, assume $f(x)={\sum }_{u\le x}{\mu }_P(u,x)g(u)$ for every $x\in P$, and fix $y\in P$. Then ${\sum }_{x\le y}f(x)={\sum }_{u\le x\le y}{\mu }_P(u,x)g(u)={\sum }_{u\le y}g(u)({\sum }_{u\le x\le y}{\mu }_P(u,x))=g(y)$ by [L1].

Now assume $P$ is upper-finite and $g(x)={\sum }_{y\ge x}f(y)$ for every $x\in P$. Fix $x\in P$. Every index set lies in the finite principal filter of $x$. Substitution and finite Fubini give ${\sum }_{y\ge x}{\mu }_P(x,y)g(y)={\sum }_{x\le y\le z}{\mu }_P(x,y)f(z)={\sum }_{z\ge x}f(z)({\sum }_{x\le y\le z}{\mu }_P(x,y))=f(x)$ by [L1].

Conversely, assume $f(y)={\sum }_{z\ge y}{\mu }_P(y,z)g(z)$ for every $y\in P$, and fix $x\in P$. Then ${\sum }_{y\ge x}f(y)={\sum }_{x\le y\le z}{\mu }_P(y,z)g(z)={\sum }_{z\ge x}g(z)({\sum }_{x\le y\le z}{\mu }_P(y,z))=g(x)$ by [L1].

Steps 1.1 and 1.2 prove the lower-finite equivalence, while steps 1.3 and 1.4 separately prove its upper-finite order dual.

For each $y\in P$, the principal ideal $P_{\le y}$ is a subset of $P$, hence finite by [L1]; thus $P$ is lower-finite.

For each $x\in P$, the principal filter $P_{\ge x}$ is a subset of $P$, hence finite by [L1]; thus $P$ is upper-finite.

Applying the two separate parts of [L2] proves both inversion formulas on $P$.

The product relation is reflexive because both coordinate orders are reflexive; it is antisymmetric because two opposite product inequalities give equality in each coordinate; and it is transitive because coordinatewise inequalities compose. Hence it is a partial order.

Its intervals are exactly Cartesian products: $[(p,q),(p^{\mathrm{\prime }},q^{\mathrm{\prime }})]=[p,p^{\mathrm{\prime }}{]}_P\times [q,q^{\mathrm{\prime }}{]}_Q$. Both factors are finite by local finiteness, so the interval is finite by [L1]; thus $P\times Q$ is locally finite.

Define $\nu ((p,q),(p^{\mathrm{\prime }},q^{\mathrm{\prime }})):={\mu }_P(p,p^{\mathrm{\prime }}){\mu }_Q(q,q^{\mathrm{\prime }})$. On the diagonal, $\nu ((p,q),(p,q))=1\cdot 1=1$.

For a nontrivial product interval, finite Fubini gives ${\sum }_{(p,q)\le (u,v)\le (p^{\mathrm{\prime }},q^{\mathrm{\prime }})}\nu ((p,q),(u,v))=({\sum }_{p{\le }_{P}u{\le }_P{p}^{\mathrm{\prime }}}{\mu }_P(p,u))({\sum }_{q{\le }_{Q}v{\le }_Q{q}^{\mathrm{\prime }}}{\mu }_Q(q,v))$.

Each factor in step 2.1 is $1$ when its endpoints agree and $0$ otherwise. Since the product interval is nontrivial, at least one coordinate pair has distinct endpoints, so the product is $0$.

Thus $\nu$ has the diagonal and recurrence properties of the Möbius function on $P\times Q$, and uniqueness in [L3] gives $\nu ={\mu }_{P\times Q}$.

Define $\nu (A,B):=(-1{)}^{\mathrm{\mid }B\setminus A\mathrm{\mid }}$ in $\mathbb{Z}$. On the diagonal, $B\setminus A=\mathrm{\varnothing }$, so $\nu (A,A)=(-1{)}^0=1$.

Suppose $A<B$ and choose $b\in B\setminus A$. The subsets $E\subseteq B\setminus A$ split into disjoint pairs $E$ and $E\cup \{b\}$ with $b\mathrm{\notin }E$; their contributions satisfy $(-1{)}^{\mathrm{\mid }E\mathrm{\mid }}+(-1{)}^{\mathrm{\mid }E\mathrm{\mid }+1}=0$ in $\mathbb{Z}$. Finite splitting and reindexing therefore give ${\sum }_{A\subseteq C\subseteq B}\nu (A,C)={\sum }_{E\subseteq B\setminus A}(-1{)}^{\mathrm{\mid }E\mathrm{\mid }}=0$.

Thus $\nu$ satisfies the diagonal and vanishing-sum recurrence, so uniqueness gives $\nu ={\mu }_{B(X)}$.

Equivalently, grouping the sum in step 1.2 by $\mathrm{\mid }E\mathrm{\mid }$ gives the alternating binomial sum in [L3]. Identifying the interval with a finite product of two-element chains gives the same formula by [L4], since the defining recurrence and its uniqueness in [L2] transport through a poset isomorphism.

Step 2.1 is the asserted formula, with step 2.2 recording its binomial and product-poset readings.

For $K\subseteq I$, let $h(K):=\iota \mathrm{\mid }\{x\in X:T(x)=K\}\mathrm{\mid }$, and let $g(J):=\iota \mathrm{\mid }{A}_J\mathrm{\mid }$. The trace classes partition $A_J$, and [F1] gives $g(J)={\sum }_{K\supseteq J}h(K)$ in $\mathbb{R}$.

Apply the upper-finite form of [L1] at $J=\mathrm{\varnothing }$: $h(\mathrm{\varnothing })={\sum }_{K\supseteq \mathrm{\varnothing }}\mu (\mathrm{\varnothing },K)g(K)$.

By [F1], $h(\mathrm{\varnothing })=\iota \mathrm{\mid }X\setminus {\bigcup }_i{A}_i\mathrm{\mid }$, and by [L2], $\mu (\mathrm{\varnothing },K)=(-1{)}^{\mathrm{\mid }K\mathrm{\mid }}$. Substitution in step 2.1 gives $\iota \mathrm{\mid }X\setminus {\bigcup }_i{A}_i\mathrm{\mid }={\sum }_{K\subseteq I}(-1{)}^{\mathrm{\mid }K\mathrm{\mid }}\iota \mathrm{\mid }{A}_K\mathrm{\mid }$.

The identity in step 3.1 matches [L3] term for term, including the empty-subset term $\iota \mathrm{\mid }{A}_{\mathrm{\varnothing }}\mathrm{\mid }=\iota \mathrm{\mid }X\mathrm{\mid }$; hence complementary inclusion-exclusion is Boolean-lattice Möbius inversion.

The diagonal value is $1$ by [L1].

If $y$ covers $x$, then the recurrence has only the term $z=x$, so $\mu (x,y)=-\mu (x,x)=-1$.

Fix an interval cardinality and assume the formula holds on every strictly smaller interval.

Suppose there is an element strictly between $x$ and $y$. The finite nonempty chain $(x,y]$ has a least element $c$: starting with any element, successively retain the smaller one while traversing a finite enumeration. Then $c$ covers $x$ and $c<y$.

For every $z$ with $c<z<y$, the interval $[x,z]$ is a proper subset of $[x,y]$ and contains the intermediate element $c$, so the inductive hypothesis and [L3] give $\mu (x,z)=0$.

The recurrence now gives $\mu (x,y)=-{\sum }_{x\le z<y}\mu (x,z)=-(\mu (x,x)+\mu (x,c))=-(1-1)=0$.

The diagonal and cover cases are steps 1.1 and 1.2; step 3.1 proves the longer-interval case from all smaller intervals, so strong induction completes the formula.