Lattices#

GALACTIC core kernel

A lattice [Bir48] is a special type of partially ordered set (poset) that possesses additional structure, allowing for the combination of any two elements in a meaningful way.

Introduction#

Definition

A lattice is a mathematical structure \(\left\langle L, \leq,\lor,\land\right\rangle\) in which \(\left\langle L, \leq\right\rangle\) is a poset and every pair of elements has both a least upper bound (supremum or join) and a greatest lower bound (infimum or meet).

For any two elements \(a\) and \(b\) in \(L\), there exists an element \(a \lor b\) (also denoted as \(\sup(a, b)\)) such that:

\(a \leq a \lor b\) and \(b \leq a \lor b\),
If \(a \leq c\) and \(b \leq c\) for any \(c \in L\), then \(a \lor b \leq c\).

For any two elements \(a\) and \(b\) in \(L\), there exists an element \(a \land b\) (also denoted as \(\inf(a, b)\)) such that:

\(a \land b \leq a\) and \(a \land b \leq b\),
If \(c \leq a\) and \(c \leq b\) for any \(c \in L\), then \(c \leq a \land b\).

Operation properties

Commutativity

The operations \(\lor\) and \(\land\) are commutative:

\[ a \lor b = b \lor a \quad \text{and} \quad a \land b = b \land a \]

Associativity

The operations \(\lor\) and \(\land\) are associative:

\[ a \lor (b \lor c) = (a \lor b) \lor c \quad \text{and} \quad a \land (b \land c) = (a \land b) \land c \]

Idempotency

The operations \(\lor\) and \(\land\) are idempotent:

\[ a \lor a = a \quad \text{and} \quad a \land a = a \]

Absorption

The operations \(\lor\) and \(\land\) satisfy the absorption laws:

\[ a \lor (a \land b) = a \quad \text{and} \quad a \land (a \lor b) = a \]

Lattices properties

Finite Lattice

A lattice is finite if the set \(L\) is finite

Complete Lattice

A lattice is complete if all subsets of \(L\) have a supremum and an infimum.

A complete lattice has therefore a maximum and a minimum element and cannot be empty.

A non-empty finite lattice is a complete lattice.

Modular Lattice

A lattice is modular if it satisfies the modular law:

\[ a \leq c \implies a \lor (b \land c) = (a \lor b) \land c \]

A lattice is upper semimodular is it satisfiers the upper semimodular law:

\[ a \land b \prec a \implies b \prec a \lor b \]

A lattice is lower semimodular is it satisfiers the lower semimodular law:

\[ a \prec a \lor b \implies a \land b \prec b \]

Distributive lattice

A lattice is distributive if the operations \(\lor\) and \(\land\) distribute over each other:

\[ a \lor (b \land c) = (a \lor b) \land (a \lor c) \quad \text{and} \quad a \land (b \lor c) = (a \land b) \lor (a \land c) \]

A lattice is join-semidistributive if:

\[ a \lor b = a \lor c \implies a \lor b = a \lor (b \land c) \]

A lattice is meet-semidistributive if:

\[ a \land b = a \land c \implies a \land b = a \land (b \lor c) \]

A lattice is meet-distributive if it is join-semidistributive and lower semimodular.

A lattice is join-distributive if it is meet-semidistributive and upper semimodular.

Complemented Lattice

A lattice is complemented if it has a greatest element (\(1\)) and a least element (\(0\)), and every element \(a\) has a complement \(b\) such that:

\[ a \lor b = 1 \quad \text{and} \quad a \land b = 0 \]

Boolean Lattice

A lattice is a boolean lattice if it is distributive, complemented and complete.

Filter

A subset \(F \subseteq L\) is called a filter if it satisfies:

Non-emptiness: \(F \neq \emptyset\),
Upward directedness: For all \(a, b \in F\), \(a \wedge b \in F\),
Upper set condition: If \(x \in F\) and \(y \geq x\), then \(y \in F\).

Intuitively, a filter is closed upward and closed under finite meets.

Ideal.

A subset \(I \subseteq L\) is called an ideal if it satisfies:

Non-emptiness: \(I \neq \emptyset\),
Downward directedness: For all \(a, b \in I\), \(a \vee b \in I\),
Lower set condition: If \(x \in I\) and \(y \leq x\), then \(y \in I\).

Intuitively, an ideal is closed downward and closed under finite joins.

Semi-lattices#

A semilattice is a partial order that provides a weaker structure compared to a lattice, as it only requires the existence of either a least upper bound (join-semilattice) or a greatest lower bound (meet-semilattice) for any two elements.

Special elements#

Maximum and minimum

In lattice theory, the maximum (resp. minimum) element is the greatest (resp. lowest) element of the lattice (if they exist).

Atoms and coatoms

In lattice theory, atoms and coatoms are specific types of elements that play a crucial role in the structure of a lattice. Here’s how to define them mathematically:

In a lattice \(\left\langle L, \leq,\lor,\land\right\rangle\) with a least element (bottom) 0, an atom is an element that covers 0. In other words, an atom is a minimal non-zero element.

Mathematically, an element \(a \in L\) is an atom if:

\[ 0 \prec a \]

A lattice is called atomistic if every element is a join of atoms. This means that for every element \(b \in L\), there exists a set of atoms \(\{a_i\}\) such that \(b = \bigvee a_i\).

In a lattice \(\left\langle L, \leq,\lor,\land\right\rangle\) with a greatest element (top) 1, a coatom is an element that is covered by 1. In other words, a coatom is a maximal non-unit element.

Mathematically, an element \(c \in L\) is a coatom if:

\[ c \prec 1 \]

A lattice is called coatomistic if every element is a meet of coatoms. This means that for every element \(b \in L\), there exists a set of coatoms \(\{c_i\}\) such that \(b = \bigwedge c_i\).

Irreducibles

In a lattice \(\left\langle L, \leq,\lor,\land\right\rangle\), an element \(j \in L\) is join-irreducible if it cannot be expressed as the join (supremum) of two distinct elements that are strictly less than \(j\):

The atoms are join-irreducible.

\[ j = a \lor b \implies j = a \text{ or } j = b \quad \text{for all } a, b \in L \]

In a lattice \(\left\langle L, \leq,\lor,\land\right\rangle\), an element \(m \in L\) is meet-irreducible if it cannot be expressed as the meet (infimum) of two distinct elements that are strictly greater than \(m\):

\[ m = a \land b \implies m = a \text{ or } m = b \quad \text{for all } a, b \in L \]

The coatoms are meet-irreducible.