Lattices: origins

Lattices are somehow a young mathematical object. Even though they were whispering to Boole or Peirce, it was Dedekind who probably put the finger on the lattice structure first. The XXth century had just begun. From then on until the present, several mathematicians such as Birkhoff, Ore, Von Neumann, Grätzer, Dilworth and so forth contributed to build lattice theory.

They arise in various fields, which was (and still is) a motivating reason for their study. We first think of mathematical domains such as algebra, probability, order theory and logic for instance. However, lattice theory also appears in a kind of new science (and absolutely unknown as of today): computer science.
Indeed, one may find lattices in relational databases, data mining through Formal Concept Analysis (FCA, being lattice-based), model-based reasoning, or knowledge space theory for example.

Figure 1: One of this diagram does not depict a lattice.

Figure 2: illustrating irreducible and forbidden sets.

What are they ?

Lattices have numerous definitions depending on the domain we consider. We will stick to their order theoretic one, and a set theoretic characterization. Beforehand, we shall recall few notions of ordered sets. We fix $(Q, \leq)$ as a partially ordered set, or poset . They can be graphically represented as in the Figure 1 by their Hasse diagram. The ideal of $x \in Q$, denoted by $\downarrow x$ is the set of elements $y \in Q$ below $x$ in $(Q, \leq)$. The filter $\uparrow x$ is defined dually. Let $x_1, x_2 \in Q$. When $\downarrow x_1 \cap \downarrow x_2$ admits a unique maximal element, denoted by $x_1 \land x_2$, we call it the meet of $x_1$ and $x_2$. Intuitively, the meet is the largest element on which $x_1$ and $x_2$ meet below . The join $x_1 \lor x_2$ is defined dually by the unique minimal element, if it exists, in $\uparrow x_1 \cap \uparrow x_2$. It is the least element on which $x_1$ and $x_2$ join above .

A lattice is a poset $(Q, \leq)$ in which pair $(x_1, x_2)$ has both a meet and a join.

Tiny example: let us consider the set family $\{\emptyset, \{1\}, \{2\}, \{1, 3\}, \{1, 2, 3\}\}$ ordered by inclusion as in Figure 1. The filter of $\{1\}$ contains $\{1\}, \{1, 3\}, \{1, 2, 3\}$. Its ideal in turn gathers $\{1\}$ and the empty set. Focus now on $\{1\}$ and $\{2\}$. There meet is $\emptyset$ while their join is $\{1, 2, 3\}$. Considering each pair, one may figure out that this set family ordered by inclusion is indeed a lattice.

In fact, every lattice can be regarded as a set family $\mathcal{F}$ over some set $Q$ ordered by inclusion provided it satisfies two conditions:

  • it is closed by intersection , that is if $F_1, F_2 \in \mathcal{F}$, then $F_1 \cap F_2 \in F$ ($\cap$ coincides with $\land$ in the poset).
  • $Q \in \mathcal{F}$.
Such $(\mathcal{F}, \subseteq)$ is also called a closure system .

How to hide them ?

As we said, a lattice $(\mathcal{F}, \subseteq)$ is a set family on $Q$. Therefore it takes a huge amount of space to be stored. Hence, we will look for ways to describe it compactly. Here are two ideas:

  • either we describe the sets not in the lattice, that is those sets being somehow "forbidden",
  • or we describe the sets present in the lattice.

For the first idea, we use a bunch of so-called implications . They are pairs $A \rightarrow B$ of subsets of $Q$ saying "We cannot have $A$ without $B$" . In other words, the set $A$ is then forbidden in the lattice since $A$ requires $B$.

As for the second case, we use the set $\mathcal{M} \subseteq \mathcal{F}$ of meet-irreducible elements . It is the minimal subfamily of $\mathcal{F}$ from which we can reconstruct $\mathcal{F}$ by taking successive intersections. Intuitively, if a set $A$ is obtained via the intersection of a subset of $\mathcal{M}$ then it is "allowed" in $\mathcal{F}$. An element of $\mathcal{F}$ is a meet-irreducible if it has only one successor in the diagram.

An illustration: let us consider the set family $\{\emptyset, 1, 2, 3, 13, 23, 123 \}$ (we use concatenation $12$ as a shortcut for $\{1, 2\}$) ordered by inclusion as in Figure 2. Meet-irreducible are $1, 13, 2, 23$ and we can get $3$ with $13 \cap 23$ and $\emptyset$ via $1 \cap 2$. Usually, we consider that $123$ is obtained via $\cap \emptyset$. On the other hand, the set $12$ is not in the lattice: the implication $12 \rightarrow 3$ prevents $12$ to appear without $3$.

Thanks to these representations, we can draw parallel with other fields of computer science.

Field Implications Meet-irreducible
Databases Functional dependencies Armstrong relations
Horn logic Horn clauses Characteristic models
FCA Attribute implications Reduced context
Learning Spaces Queries Base

You talked about "Learning Space" ...

Yes. Let us provide a glimpse into learning spaces. They are set families used on educational purposes. Let us assume we are given a course that some students must master. It is divided in several concepts (items) to learn. For instance, finding the roots of a second order polynom could be an item of some mathematical course in high school. The set of concept a student has already mastered is his/her knowledge state . We put some learning constraint on the items. First, one must be able to learn items one by one. Second, learning an item at some point does not prevent to learn another one later. In other words if a concept is available for learning at some point, it remains accessible until all concepts are mastered. A set family of items together with these requirements depicts what we call a learning space . It can be used to assess knowledge of a student (i.e. find his/her state), describe what is to be learnt next.

Now that the not so formal ideas are exposed we move to the mathematical definition. A set family $(\mathcal{K}, \subseteq)$ ordered by inclusion over a set (of items!) $Q$ is a learning space if gor all $K, F \in \mathcal{K}$:

  • there exists $q \in Q$, $q \notin K$, such that $K \cup q \in \mathcal{K}$,
  • if $K \subset L$ and $K \cup q \in \mathcal{K}$ for some $q \in Q$ and $q \notin K, L$, then $L \cup q \in \mathcal{K}$.

The first point corresponds to "learn items one by one" while the second describes "learning now does not prevent from learning later" . Note that we usually assume that $\emptyset \in \mathcal{K}$.

Ok, what's the point with lattices ?

Let $(\mathcal{K}, \subseteq)$ be a learning space. In fact, thanks to the learning constraints, it turns out that $\mathcal{K}$ is closed under union and therefore is coclosure system (the complement of a closure system) and hence a lattice too. However to fall back on previous definitions, put $\mathcal{F} = \{\overline{K} \mid K \in \mathcal{K}\}$. Then, $\mathcal{F}$ is a closure system.

Figure 3: On the left a learning space, and its dual closure system on the right.

The closure system associated to a learning space appears to be a famous combinatorial structure: a convex geometry.

Non-exhaustive references
  • Introduction to lattices and order (2nd Edition)
    B.A. Davey, H.A. Priestley
    Cambridge University Press, 2002.
  • Learning Spaces: Interdisciplinary Applied Mathematics.
    J.-P. Doignon , J.-C. Falmagne.
    Springer, 2011.
  • The joy of implications aka pure Horn formulas: Mainly a survey
    M. Wild.
    Theoretical Computer Science, 2017.
Last updated: April 2021.