M3-N5 theorem

Hasse diagrams of the lattices N5 (left) and M3 (right)

In mathematics, particularly in order theory, the M3–N5 theorem is a mathematical theorem that characterizes the modularity and distributivity of a lattice by examining only its finite sublattices.

The first part of the theorem, stating that a lattice is modular if and only if it contains no sublattice isomorphic to N5, was first proved by the German mathematician Richard Dedekind in 1900. The second part, stating that a lattice is distributive if and only if it contains no sublattice isomorphic to either N5 or M3, was proved by the American mathematician Garrett Birkhoff in 1934. The theorem is also sometimes referred to as the Dedekind–Birkhoff theorem.

Basic definitions

A set L equipped with two binary operations ∧ and ∨ is called a lattice if and only if both operations are associative, commutative, and idempotent, and satisfy the absorption identities a∨(a∧b)=a and a∧(a∨b)=a. For a,b∈L, one writes a≤b if and only if a∧b=a, or equivalently, a∨b=b. The operations ∧ and ∨ are called the meet and join, respectively.

A lattice L is called modular if and only if it satisfies the identity (x∨y)∧z=(x∧z)∨y whenever y≤z. Furthermore, a lattice is called distributive if and only if it satisfies the identity x∧(y∨z)=(x∧y)∨(x∧z) for all x,y,z∈L (without any comparability requirement). Every distributive lattice is necessarily modular.

Given a lattice L, a subset L′⊆L is called a sublattice if and only if it is closed under meet and join.

Two lattices L,M are called isomorphic if there exists a bijective function φ:L→M such that φ(a∧b)=φ(a)∧φ(b) and φ(a∨b)=φ(a)∨φ(b) for all a,b∈L.

The pentagon lattice is the lattice N5={0,1,a,b,c}, where 0<a<b<1 and 0<c<1, and c is incomparable with both a and b.

The diamond lattice is the lattice M3={0,1,a,b,c}, where 0<a<1, 0<b<1, and 0<c<1, and the elements a, b, and c are pairwise incomparable.

Statement of the theorem

Let (L,∧,∨,≤) be any lattice. Then:

  1. L is a modular lattice if and only if it contains no sublattice isomorphic to N5.
  2. L is a distributive lattice if and only if it contains no sublattice isomorphic to either N5 or M3.

Outline of the proof

Proof of the first statement

⟹: Suppose that L is a modular lattice, and assume for a contradiction that it contains a sublattice L′:={0′,1′,a,b,c}⊆L isomorphic to N5. By modularity,

a=0′∨a=(c∧b)∨a=(c∨a)∧b=1′∧b=b.

However, a≠b, since otherwise L′ would not be isomorphic to N5. This is a contradiction, and therefore L contains no sublattice isomorphic to N5.

⟸: We proceed by contraposition. Suppose that L is not modular. We must show that it contains a sublattice isomorphic to N5.

Since L is not modular, there exist x,y,z∈L such that y≤z and

(x∧z)∨y≠(x∨y)∧z.

Define

a:=(x∧z)∨y,b:=(x∨y)∧z,c:=x,0′:=x∧z,1′:=x∨y.

It can be shown that these five elements are pairwise distinct, that 0′<a<b<1′ and 0′<c<1′, that c is incomparable with both a and b, and that a∧c=0′ and b∨c=1′. Consequently, L′:={0′,1′,a,b,c}⊆L is a sublattice isomorphic to N5.

Proof of the second statement

To prove the second statement, we first use the following lemma: a lattice L is distributive if and only if, for all x,y,z∈L,

(x∧y)∨(x∧z)∨(y∧z)=(x∨y)∧(x∨z)∧(y∨z).

Note that the inequality

(x∧y)∨(x∧z)∨(y∧z)≤(x∨y)∧(x∨z)∧(y∨z)

always holds in any lattice.

Since the first statement establishes that L is modular if and only if it contains no sublattice isomorphic to N5, it suffices to assume that L is modular and prove that it is distributive if and only if it contains no sublattice isomorphic to M3.

⟹: Suppose that L is distributive, and assume for a contradiction that it contains a sublattice L′:={0′,1′,a,b,c}⊆L isomorphic to M3. By distributivity,

0′=0′∨0′=(a∧c)∨(b∧c)=(a∨b)∧c=1′∧c=c.

However, 0′≠c, since otherwise L′ would not be isomorphic to M3. This is a contradiction, and therefore L contains no sublattice isomorphic to M3.

⟸: We proceed by contraposition. Suppose that L is modular but not distributive. We must show that it contains a sublattice isomorphic to M3.

Since L is not distributive, there exist x,y,z∈L such that

(x∧y)∨(x∧z)∨(y∧z)<(x∨y)∧(x∨z)∧(y∨z).

Define

0′:=(x∧y)∨(x∧z)∨(y∧z),1′:=(x∨y)∧(x∨z)∧(y∨z),a:=(x∧1′)∨0′=(x∨0′)∧1′,b:=(y∧1′)∨0′=(y∨0′)∧1′,c:=(z∧1′)∨0′=(z∨0′)∧1′.

It can be shown that these five elements are pairwise distinct, that 0′<a<1′, 0′<b<1′, and 0′<c<1′, that a, b, and c are pairwise incomparable, and that

a∧b=a∧c=b∧c=0′

and

a∨b=a∨c=b∨c=1′.

Consequently, L′:={0′,1′,a,b,c}⊆L is a sublattice of L isomorphic to M3.

This completes the proof.

Example

Let V be a vector space, and denote by S(V) the set of all its linear subspaces. For any U,W∈S(V), both U∩W and U+W are linear subspaces of V and therefore belong to S(V). It follows that S(V) forms a lattice under set inclusion, with intersection and subspace sum as the meet and join operations, respectively.

One may ask whether S(V) is modular or distributive. It can be shown that, for all U,W,Z∈S(V), whenever W⊆Z,

(U+W)∩Z=(U∩Z)+W.

Thus, S(V) is modular. However, if the dimension of V is at least two, it is not distributive. For example, if V=ℝ2, define

0′:={0},1′:=ℝ2,a:={(t,0)∣t∈ℝ},b:={(0,t)∣t∈ℝ},c:={(t,t)∣t∈ℝ}.

It can be shown that L′:={0′,1′,a,b,c}⊆S(ℝ2) is a sublattice isomorphic to M3. Therefore, S(ℝ2) is not distributive.

Significance and applications

The significance of the M3–N5 theorem lies in its characterization of two fundamental classes of lattices by means of a finite number of forbidden sublattices, rather than by directly verifying the algebraic identities that define them. In particular, although the theorem applies to infinite lattices as well, any failure of modularity or distributivity implies the existence of a five-element sublattice witnessing that failure. Thus, to prove that a lattice is not modular or not distributive, it suffices to find a sublattice isomorphic to one of the corresponding forbidden lattices.

The theorem illustrates the relationship between the algebraic properties of a lattice and the order-theoretic structure of its sublattices. It is a fundamental example of the characterization of classes of mathematical structures by means of forbidden substructures.