# A general "inclusion-exclusion principle" / Formulas like $\inf(a,b)\sup(a,b)=ab$

Let me list a few formulas which should be well-known:

1. (GCD-LCM product formula) For positive integers $$n,m$$, $$\operatorname{gcd}(n,m)\operatorname{lcm}(n,m)=nm.$$
2. (Inclusion-exclusion principle) For sets $$A,B$$, $$\#(A\cap B)+\#(A\cup B)=\#A+\#B$$
3. ("Linear inclusion-exclusion principle") For subspaces $$W_1,W_2$$ of a vector space $$V$$, $$\dim(W_1\cap W_2)+\dim(W_1+W_2)=\dim(W_1)+\dim(W_2)$$

All of these formulas have the same form: We have:

• A lattice $$L$$,
• A commutative ordered monoid $$(M,\star,\leq)$$,
• an order-preserving "size" function $$S\colon L\to M$$ such that $$S(a\land b)\star S(a\lor b)=S(a)\star S(b)\qquad\text{for all }a,b\in L.\tag{\star}$$

In the first example, $$L=\mathbb{Z}_{>0}$$ with the divisibility ordering ($$n\leq m$$ iff $$n$$ divides $$m$$); $$M=\mathbb{Z}_{>0}$$ with product and the usual order (or the divisibility ordering, doesn't matter); $$S$$ is the identity function of $$\mathbb{Z}_{>0}$$.

In the second example, $$L$$ is the power set of some universe, ordered by inclusion; $$M$$ is $$\mathbb{Z}_{>0}$$ with sum and the usual ordering; $$S$$ is the function which outputs the cardinality of a set.

In the third example, $$L$$ is the lattice of subspaces of $$V$$; $$M$$ is as in the second example; $$S$$ is the function mapping each subspace to its dimension.

Here are a few other examples of the same nature, which are more-or-less trivial but interesting nevertheless:

1. If $$B_1$$, $$B_2$$ are Boolean algebras is a Boolean Algebra and $$S\colon B_1\to B_2$$ is a homomorphism, then for all $$a,b\in B_1$$, $$S(a\land b)\lor S(a\lor b)=S(a)\lor S(b).$$

2. For bounded subsets $$A,B$$ of a complete lattice $$L$$, $$\sup(A\cap B)\lor\sup(A\cup B)=\sup(A)\lor\sup(B)$$

3. For real functions $$f,g$$ on $$[0,1]$$, $$\int_0^1\min(f,g)+\int_0^1\max(f,g)=\int_0^1f+\int_0^1g.$$

4. For subsets $$A,B$$ of a vector space $$V$$, $$\operatorname{span}(A\cap B)+\operatorname{span}(A\cup B)=\operatorname{span}(A)+\operatorname{span}(B).$$

(Examples 4, 5 and 7 are more trivial, as the commutative ordered monoid under consideration is simply a lattice with the join operation and the "size" function preserves joins)

Question: Is there a name for the kind of structure described as in $$(\star)$$? These seem to be reocurring in different areas concerning all kinds of interesting structures.

• The description of $S$ is cut off. It should say that $S$ is the function mapping each subspace to its dimension. Aug 25 at 3:32
• @GeoffreyTrang Thanks for pointing that out. Fixed. Aug 25 at 3:57
• Does it really matter that $M$ is ordered and $S$ preserves the ordering of $L$? Aug 25 at 4:03
• FWIW example 6 follows directly from its pointwise counterpart $\,\min(a,b)+\max(a,b)=a+b\,$.
– dxiv
Aug 25 at 4:13
• @MishaLavrov Not really. But since in all the examples we have that, I guess that could be necessary if one would pursue an study of this kind of structure. Aug 25 at 14:42

In general, by a valuation on a lattice $$L$$ is meant a real-valued function $$v(x)$$ defined on $$L$$ which satisfies $$v(x)+v(y) = v(x \wedge y) + v(x \vee y)$$. A valuation is called isotone if and only if $$x \ge y$$ implies $$v(x) \ge v(y)$$; positive if and only if $$x>y$$ implies $$v(x)>v(y)$$.
A function $$f$$ from a lattice $$L$$ into an abelian group is modular if $$f(a \vee b)+f(a \wedge b)=f(a)+f(b)$$ for all $$a,b \in L$$. Following Rota [19], we call any such modular function a valuation. (Birkhoff [2] reserves the term valuation for real-valued modular functions.)