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:
- (GCD-LCM product formula) For positive integers $n,m$, $$\operatorname{gcd}(n,m)\operatorname{lcm}(n,m)=nm.$$
- (Inclusion-exclusion principle) For sets $A,B$, $$\#(A\cap B)+\#(A\cup B)=\#A+\#B$$
- ("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:
-
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).$$
-
For bounded subsets $A,B$ of a complete lattice $L$, $$\sup(A\cap B)\lor\sup(A\cup B)=\sup(A)\lor\sup(B)$$
-
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.$$
-
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.
Would you be looking for the names valuation and/or modular function? Some references:
Garret Birkhoff, Lattice Theory, revised edition (1948), p. 74:
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)$.
Geissinger, Ladnor, Valuations on distributive lattices. I, II, III, Arch. Math. 24, 230-239 (1973); 24, 337-345 (1973); 24, 475-481 (1973). ZBL0268.06008.
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.)