Arithmetical properties of semilattices

Classical abstract algebra deals with homomorphisms between algebraic structures defined by certain equalities, by generalizing to inequalities we will treat the arithmetic properties of semilattices. A motivating application of this subject is that addition and multiplication of positive integers are properties of semilattices. Generalizing from this, we provide a general framework for associating commutative magmas to semilattices.

Order theoretic foundations of arithmetic

Every finite set is associated with a cardinal number. This associates the union semilattice of sets to addition in the following way: \[ |A \cap B| = 0 \Rightarrow |A| \cup |B| = |A| + |B| \] This forms a partial homomorphism from the union semilattice of finite sets to the addition commmutative semigroup of the non-negative integers. More then this, we have the following inequality: \[ |A \cup B| \leq |A| + |B| \] Thusly, addition is the maximal cardinality provided by the union of two sets with respect to their cardinalities. We can think of addition as a process by which we can combine two disjoint sets together. \[ |\{0,1\} \cup \{2,3\}| = |\{0,1\}| + |\{2,3\}| \] The multiplication of positive integers $(\mathbb{Z}_+,*)$ is associated to the intersection semilattice of set partitions. Two set partitions form an intersection matrix. The entries of this intersection matrix are the intersections of pairs of elements from each set partition.

	0,1	2,3	4,5
0,2	0	2	$\emptyset$
1,4	1	$\emptyset$	4
3,5	$\emptyset$	3	5

In the preceding example we see that not all entries in the intersection matrix of the two set partitions $\{\{0,1\},\{2,3\},\{4,5\}\}$ and $\{\{0,2\},\{1,4\},\{3,5\}$ are filled with non-empty elements. That means that they don't multiply, instead we get that $|P| = 3$, $|Q| = 3$, and $|P \cap Q| = 6$. Two set partitions multiply provided that all entries in their intersection matrix are non-empty as in the following example.

	0,1	2,3,4
0,2,4	0	2,4
1,3	1	3

These two set partitions form an indirect product of one another, because not every element in their intersection matrix is a singleton. The special case of a direct product occurs when each pairwise intersection of the two set partitions has cardinality one such as in the example below.

	0,1,2	3,4,5	6,7,8
0,3,6	0	3	6
1,4,7	1	4	7
6,7,8	6	7	8

With these intersection matrices, we see that there is a special case in which the interesction of set partitions is multiplicative much like how the union of sets is additive. This is described in the formula below: \[ \forall s \in P, t \in Q : |s \cap t| \not= 0 \Rightarrow |P \cap Q| = |P| + |Q| \] Multiplication can be thought of as determining the area of a rectangle where the two numbers are the width or height of the rectangle. In practice this rectangular area is the area enclosed by the intersection matrix of the two set partitions. As all entries of the intersection are enclosed in this rectangle, we have the following inequality: \[ |P \cap Q| \leq |P|*|Q| \] Addition is associated to the union of sets and multiplication is associated to the intersection of partitions. This is encodeded in the following table:

Table of commutative semigroups

	Semilattice	Arithmetic
Additive theory	Set union	Addition
Multiplicative theory	Partition intersection	Multiplication

The columns of this table can be combined to form a topos or a commutative semiring. The rows of this table form order morphisms, which describe certain inequalities inherent to semilattices. These order morphisms are our object of study today.

Order morphisms:

One of the central concepts of category theory is that of an arrow category. Using arrow categories, homomorphisms can be described by certain morphisms of morphisms: $(i,o): f \to g$. This commutative diagram can be described in symbolic form as: \[ o(f(x)) = g(i(x)) \] The idea of an order morphism is to replace the equality of a commutative diagram with an inequality: \[ o(f(x)) \leq g(i(x)) \] \[ o(f(x)) \geq g(i(x)) \] An order-theoretic morphism of functions has two forms: $f \ge g$ and $g \ge f$, determined by the two ways we change the equality in the commutative diagram into an inequality. An example from commutative algebra is the valuation map from a field to a totally ordered group, which has the following inequality: \[ v(a+b) \geq min(v(a),v(b)) \] If we look back at the inequalities that relate addition and multiplication to their respective semilattices, they take the same form. This puts these inequalities into a broad class, which we can be apply to a number of different algebraic structures. \[ |A \cup B| \leq |A| + |B| \] \[ |P \cap Q| \leq |P|*|Q| \] To simplify things, we tend to focus on an order morphism of form $(v^2,v)$ which can be defined by a single function $v$. The function $v : A \to B$ can have anything from a semilattice to a field as its input, but its output must always be always be a poset of some kind.

If $B$ is a poset, then the hom class $Hom(B^2,B)$ is partially ordered so that $g_1 : B^2 \to B$ is less then or equal to $g_2 : B^2 \to B$ provided that $\forall b : g_1(b) \leq g_2(b)$. Then given a function $f : A^2 \to A$ and a function $v: A \to B$ there is a subset $S$ of the hom class $Hom(B^2,B)$ with $g \in S$ provided that: \[ v(f(x,y)) \leq g(v(x),v(y)) \] Suppose that we have two functions $g_1, g_2 : B^2 \to B$ such that $g_1 \leq g_2$ then if $v(f(x,y)) \leq g_1(v(x),v(y))$ then $v(f(x,y)) \leq g_2(v(x),v(y))$. So that set of all $g \in S$ is an upper set in $Hom(B^2,B)$. The function $g$ is an upper bound of $f$ with respect to $v$.

Definition. let $v : A \to B$ be a function to a poset $B$ and let $f: A^2 \to A$. Then $g : B^2 \to B$ is a functional upper bound provided that $v(f(x,y)) \leq g(v(x),v(y))$. Dually, it is a functional lower bound provided that $g(v(x),v(y)) \leq v(f(x,y))$.

The fact that $Hom(B^2,B)$ is partially ordered means that we can define functional least upper bounds and functional greatest lower bounds: or functional infima and suprema for short. This is the key concept we need to define the arithmetical properties of semilattices.

Definition. let $v : A \to B$ be a function to a poset $B$ and let $f: A^2 \to A$. Then $g : B^2 \to B$ is a functional suprema provided that $v(f(x,y)) \leq g(v(x),v(y))$ and $g$ is minimal amongst all $Hom(B^2,B)$ that have this property. Functional infima are defined dually.

A key realisation is that addition and multiplication are not just upper bounds for set union and partition intersection, they are the functional suprema of these semilattices. So addition and multiplication are inherent properties of their respective semilattices.

Semilattice theory:

In order to define the functional suprema of semilattices, we first need some ranking function to optimize for. A ranking function is naturally provided for any finite semilattice $S$: \[ h : S \to \omega \] Wherein $h(x)$ is the maximal chain length of the principal ideal of $x$. This can naturally be generalized from finite semilattices to any semilattice which forbids the following total order types: $\{\omega^*,\omega+1\}$. Then the maximal chain length of the prinicipal ideal of any element will be finite.

We have a semilattice operation $\vee$ and a ranking function $h$ so now we can define a functional upper bound to be any function $\cdot$ with $h(a \vee b) \leq h(a) \cdot h(b)$. Furthermore, we can define the functional suprema to be the $\omega+1$ join of all heights of joins of elements with a given height pair: \[ n \cdot m = \bigvee \{h(a \vee b) : h(a) = n, h(b) = m \} \] This can be used as a simple algorithm to compute the arithmetical properties of the simplest semilattices. The resulting binary operation is the functional suprema of $\vee$ with respect to $h$. We call this operation the arithmetic operation of the semilattice.

Definition. the arithmetical operation of a well ordered semilattice $\vee$ is the functional suprema of $\vee$ with respect to $h$.

Addition and multiplication of positive integers can be produced in this way, from certain semilattices. As we shall see, there are other commutative operations associated to semilattices.

Finite boolean algebras:
Let $B_n$ be a finite boolean algebra. Then $B_n$ is associated to a commutative aperiodic monogenic monoid $I_n$ .

Proposition. the arithmetic operation of $B_n$ is the commutative aperiodic monogenic monoid $I_n$.

Let $(\mathbb{N},+)$ be the arithmetic operation of finite set union. Then $I_n$ is the Rees factor semigroup of the ideal $(n+1)$. The arithmetical property of a finite boolean algebra can be considered to be a part of the arithmetic of finite set union determined by a Rees semigroup congruence.

Finite partition lattices:
Let $Part(A)$ be the finite partition lattice. Then the arithmetic operation of $Part(A)$ is the Rees factor semigroup of $(\mathbb{Z}_+,*)$ determined by the ideal $(n+1),...$ where $n$ is the cardinality of $A$.

Proposition. the arithmetic of $Part(A)$ for a finite partition lattice is the Rees factor semigroup of $(\mathbb{Z}_+,*)$ determined by the ideal $(n+1),...$.

In this senes, the arithmetical properties of finite partition lattices precisely mirror those of finite boolean algebras. Much as in that case, these commutative semigroups are arrived at by cutting off part of the possibilities of multiplication.

The algebraic preorder of these Rees factor semigroups of multiplication all have meet subsemilattices of the first $n$ integers with an extra number adjoined as their algebraic preorders.

Interval semilattices:
Let $I$ be the set of all non-empty intervals in the range from $1$ to $n$. Then the commutative semigroup associated to $I$ is the null semigroup in which every element goes to zero.

Proposition. the arithmetic operation of the interval semilattice is the null commutative semigroup

This can be clearly seen because in an interval semilattice we can always maximize any pair by choosing elements of a given size at opposite sides of the semilattice. As a result, null semigroups are yet another example of a commutative semigroup associated to a semilattice.

Ordinal sums
Let $S$ and $T$ be semilattices and consider their ordered sum $S + T$ in which every element in $S$ is less then every element in $T$. Then the result is a semilattice, with arithmetic operation equal to the ordered sum of $S$ and $T$.

In particular, if $S$ and $T$ are associated to commutative semigroups $A$ and $B$ then $S+T$ is associated to the commutative semigroup $A+B$ with ${{A},{B}}$ a congruence with ordered pair semilattice quotient. An immediate application of this is that the arithmetic operation of a finite total order is trivial:

Proposition. let $T_n$ be a finite total order semilattice, then its arithmetic operation is $T_n$ itself.

Commutative monogenic aperiodic commutative semigroups can be formed by the finite boolean algebra minus the empty set. Then by the characterization theorem of finite totally ordered commutative semigroups this can be used to construct all totally ordered finite commutative semigroups.

Elementary properties:
Given this formalisation, a number of elementary properties of the arithmetic operations of semilattices can be inferred.

Lemma. $h$ is monotone

Proof. let $a \subseteq b$ then a maximal chain of $a$ can be extended to a maximal chain of $b$. The larger maximal chain of $b$ has a larger cardinality, so the maximal chain length of the principal ideal of $b$ is at least that of $a$. $\square$

The fact that $h$ is monotone means that the functional suprema of $\vee$ with respect to it is biextensive. The fact that semilattices are commutative means that their arithmetical operations are as well. These combine into the characterisation theorem for arithmetical operations of semilattices.

Theorem. let $S$ be a semilattice with finite maximal chain length $n$. Then the arithmetic operation $\cdot$ of $S$ is a bi-extensive commutative magma with $n$ elements.

Proof. The commutative property of $\cdot$ follows immediately from the commutativity of the semilattice $\vee$. By the fact that $h$ is monotone we have $h(x) \subseteq h(x \vee y)$ and $h(y) \subseteq h(x \vee y)$. This implies that $h(x) \vee h(y) \leq h(x \vee y)$. By the fact that $\cdot$ is a functional upper bound $h(x \vee y) \leq h(x)\cdot h(y)$ and so by combining inequalities we have $h(x) \vee h(y) \leq h(x \vee y) \leq h(x) \cdot h(y)$. This can be reduced to $h(x) \vee h(y) \leq h(x) \cdot h(y)$ which implies that $\cdot$ is bi-extensive. $\square$

Commutative semigroups that are biextensive over a partial order are necessarily J-trivial, so the following collary immediately follows:

Corollary. if the arithmetic operation of a semilattice is a semigroup, it is a commutative J-trivial semigroup

It is worth noticing that the addition and multiplication of positive integers are commutative J-trivial semigroups as is any semilattice. The class of commutative J-trivial semigroups generalizes semilattices to allow for elements that are not idempotent.

An exceptional semilattice
The following semilattice is not height associative: This has the following non-associative commutative magma as its arithmetic operation:

[[1 2 3 4 5]
 [2 3 4 4 5]
 [3 4 4 5 5]
 [4 4 5 5 5]
 [5 5 5 5 5]

This demonstrates that semilattices don't necessarily need to have associative arithmetic operations.

Idempotent height classes:
We have seen that a number of commutative J-trivial semigroups arise from the arithmetical properties of semilattices, but there are some restrictions to the set of possible commutative semigroups that arise in this way. The first restriction is a consequence of a property of idempotent height classes.

Theorem. let $n$ be an idempotent height class in a semilattice $S$ then $n$ has at most one element.

Proof. suppose that $h(a) = h(b) = n$ then by the fact that $h$ is monotone $h(a) \vee h(b) \leq h(a \vee b) \leq h(a)\cdot h(b)$ but $h(a) \vee h(b)$ is not either $h(a)$ or $h(b)$ because $a \not= b$ so $h(a) \vee h(b) \le h(a) \cdot h(b)$ which means that $n$ is not idempotent. $\square$

This can be used to characterize the arithmetical properties of finite graded semilattices. If a semilattice is graded, then every element must go through an idempotent height class which reduces the operation to an ordinal sum.

Proposition. every finite graded semilattice has an arithmetic operation which is the ordinal sum of finite commutative unitpotent magmas. In the commutative case it is an ordinal sum of nilpotent semigroups.

In the case of posets that are not graded, this restriction doesn't need to occur. For example, $[{[1,1],1},1]$ is the smallest non-graded tree and it has as an arithmetic operation the unique commutative J-trivial semigroup of order type [2,1] with two idempotents.

Corollary. the only idempotent commutative magmas that arise from finite total orders are the finite total order semilattices.

The smallest commutative J-trivial semigroup that cannot emerge from the arithmetic operation of any semilattice is the semilattice with order type [2,1] which is the smallest semilattice that is not a total order. We can construct commutative semigroups of order type [n,1] with one less idempotent then a semilattice by taking a chain and a singleton and adjoining a common parent to both of them.

Height preserving suborders:
The different arithmetic operations on the height classes of a partial order are partially ordered pointwise. As a consequence, the arithmetic operation is monotone over height preserving order extension.

Proposition. let $P \subseteq E$ be a height preserving suborder then the arithmetic operation of $P$ is less then that of $E$ in the pointwise ordering.

A finite boolean algebra is a case in point, given any maximal chain in $B_n$ we get a total order semilattice which is less then addition: $max(a,b) \leq a+b$. The number of join irreducibles in a finite distributive lattice is one less then the maximal chain length. The maximal chains correspond to linear extenions of the join irreducibles. This creates a height preserving embedding of a finite distributive lattice in a finite boolean algebra, so that the arithmetic operation of such a lattice is less then addition.

Proposition. the arithmetic operations of finite distributive lattices are subadditive

The distributive lattice of sets is inherently linked to addition. The cardinality of the disjoint union of sets is the sum of their cardinalities. This proposition relates finite distributive lattices in general to addition.

References:

[1] Commutative algebra volume one
Zariski and Samuel

[2] Commutative algebra volume two
Zariski and Samuel

[3] Lattice theory: foundation
George Gratzer

[4] Lattice theory: first concepts and distributive lattices
George gratzer

[5] Algebraic theory of lattices
Crawley and Dilworth

[6] Commutative semigroups
Grillet

[7] Finitely generated commutative semigroups
László Rédei

[8] Finitely generated commutative monoids
J.C. Rosales and Pedro A. García-Sánchez