Incidence Algebras and Möbius Inversion

Expanding the left bracketing and distributing the factor $h(v,y)$ through the inner sum gives $((f*g)*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*(g*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)*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)*h=f*h+g*h$.

The same calculation with the sum in the right factor gives $f*(g+h)=f*g+f*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*g)*h=f*(g*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*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*\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*g)(x,x)=1_R$ and $(h*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 $|[x,y]|=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*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*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 $|[x,y]|$, define $g$ and $h$ on every comparable pair and give $f*g=\delta$ and $h*f=\delta$.

Associativity and the identity law in [L4] now give $h=h*\delta=h*(f*g)=(h*f)*g=\delta*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*g=\delta$ at $(x,x)$ gives $f(x,x)g(x,x)=1_R$, and evaluating $g*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*\zeta=\delta$ at $x<y$ gives $\sum_{x\le z\le y}\mu_P(x,z)=0$.

Evaluating $\zeta*\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)\left(\sum_{u\le x\le y}\mu_P(x,y)\right)=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)\left(\sum_{u\le x\le y}\mu_P(u,x)\right)=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)\left(\sum_{x\le y\le z}\mu_P(x,y)\right)=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)\left(\sum_{x\le y\le z}\mu_P(y,z)\right)=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',q')]=[p,p']_P\times[q,q']_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',q')):=\mu_P(p,p')\mu_Q(q,q')$. On the diagonal, $\nu((p,q),(p,q))=1\cdot1=1$.

For a nontrivial product interval, finite Fubini gives $\sum_{(p,q)\le(u,v)\le(p',q')}\nu((p,q),(u,v))=\left(\sum_{p\le_Pu\le_Pp'}\mu_P(p,u)\right)\left(\sum_{q\le_Qv\le_Qq'}\mu_Q(q,v)\right)$.

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)^{|B\setminus A|}$ in $\mathbb Z$. On the diagonal, $B\setminus A=\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\notin E$; their contributions satisfy $(-1)^{|E|}+(-1)^{|E|+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)^{|E|}=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 $|E|$ 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|\{x\in X:T(x)=K\}|$, and let $g(J):=\iota|A_J|$. 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=\varnothing$: $h(\varnothing)=\sum_{K\supseteq\varnothing}\mu(\varnothing,K)g(K)$.

By [F1], $h(\varnothing)=\iota|X\setminus\bigcup_iA_i|$, and by [L2], $\mu(\varnothing,K)=(-1)^{|K|}$. Substitution in step 2.1 gives $\iota|X\setminus\bigcup_iA_i|=\sum_{K\subseteq I}(-1)^{|K|}\,\iota|A_K|$.

The identity in step 3.1 matches [L3] term for term, including the empty-subset term $\iota|A_\varnothing|=\iota|X|$; 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$.