17
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ The description of $S$ is cut off. It should say that $S$ is the function mapping each subspace to its dimension. $\endgroup$ Aug 25 at 3:32
  • $\begingroup$ @GeoffreyTrang Thanks for pointing that out. Fixed. $\endgroup$ Aug 25 at 3:57
  • $\begingroup$ Does it really matter that $M$ is ordered and $S$ preserves the ordering of $L$? $\endgroup$ Aug 25 at 4:03
  • 2
    $\begingroup$ FWIW example 6 follows directly from its pointwise counterpart $\,\min(a,b)+\max(a,b)=a+b\,$. $\endgroup$
    – dxiv
    Aug 25 at 4:13
  • $\begingroup$ @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. $\endgroup$ Aug 25 at 14:42
8
$\begingroup$

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.)

$\endgroup$
1
  • $\begingroup$ That is precisely what I wanted. On to the reference rabbit hole... $\endgroup$ Aug 26 at 15:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.