Subsumption lattice
# Subsumption lattice

A subsumption lattice is a mathematical structure used in the theoretical background of automated theorem proving and other symbolic computation applications.

## Definition

A term $t_1$ is said to subsume a term $t_2$ if a substitution σ exists such that σ applied to $t_1$ yields $t_2.$ In this case, $t_1$ is also called more general than $t_2,$ and $t_2$ is called more specific than $t_1,$ or an instance of $t_1.$

The set of all (first-order) terms over a given signature can be made a lattice over the partial ordering relation "... is more specific than ..." as follows:

* consider two terms equal if they differ only in their variable naming,
* add an artificial minimal element Ω (the overspecified term), which is considered to be more specific than any other term.

This lattice is called the subsumption lattice. Two terms are said to be unifiable if their meet differs from Ω.

## Properties

The join and the meet operation in this lattice are called anti-unification and unification, respectively. A variable x and the artificial element Ω are the top and the bottom element of the lattice, respectively. Each ground term, i.e. each term without variables, is an atom of the lattice. The lattice has infinite descending chains, e.g. x, g(x), g(g(x)), g(g(g(x))), ..., but no infinite ascending ones.

If f is a binary function symbol, g is a unary function symbol, and x and y denote variables, then the terms f(x,y), f(g(x),y), f(g(x),g(y)), f(x,x), and f(g(x),g(x)) form the minimal non-modular lattice $N_5$ (see Pic. 1); its appearance prevents the subsumption lattice from being modular and hence also from being distributive.

The set of terms unifiable with a given term need not be closed with respect to meet; Pic. 2 shows a counter-example.

Denoting by Gnd(t) the set of all ground instances of a term t, the following properties hold:

* t equals the join of all members of Gnd(t), modulo renaming,
* $t_1$ is an instance of $t_2$ if and only if $Gnd(t_1)$ ⊆ $Gnd(t_2),$
* terms with the same set of ground instances are equal modulo renaming,
* if t is the meet of $t_1$ and $t_2,$ then Gnd(t) = $Gnd(t_1)$ ∩ $Gnd(t_2),$
* if t is the join of $t_1$ and $t_2,$ then Gnd(t) ⊇ $Gnd(t_1)$ ∪ $Gnd(t_2).$

## 'Sublattice' of linear terms

* Pic. 5: Distributive sublattice of linear terms
* Pic. 4: $M_3$ built from linear terms
* Pic. 3: $N_5$ built from linear terms

The set of linear terms, that is of terms without multiple occurrences of a variable, is a sub-poset of the subsumption lattice, and is itself a lattice. This lattice, too, includes $N_5$ and the minimal non-distributive lattice $M_3$ as sublattices (see Pic. 3 and Pic. 4) and is hence not modular, let alone distributive.

The meet operation yields always the same result in the lattice of all terms as in the lattice of linear terms. The join operation in the all terms lattice yields always an instance of the join in the linear terms lattice; for example, the (ground) terms f(a,a) and f(b,b) have the join f(x,x) and f(x,y) in the all terms lattice and in the linear terms lattice, respectively. As the join operations do not in general agree, the linear terms lattice is not properly speaking a sublattice of the all terms lattice.

Join and meet of two proper linear terms, i.e. their anti-unification and unification, corresponds to intersection and union of their path sets, respectively. Therefore, every sublattice of the lattice of linear terms that does not contain Ω is isomorphic to a set lattice, and hence distributive (see Pic. 5).

## Origin

Apparently, the subsumption lattice was first investigated by Gordon D. Plotkin, in 1970.

