nLab modular lattice

Contents

This is about a notion in order theory/logic. For an unrelated notion of a similar name in group theory/quadratic form-theory see at modular integral lattice.


Contents

Idea

A modular lattice is a lattice where “opposite sides” of a “diamond” formed by four points xyx \wedge y, xx, yy, xyx \vee y are “congruent”.

Definition

A modular lattice is a lattice which satisfies a modular law, which we introduce after a few preliminaries.

In any lattice LL, given two elements x,yLx, y \in L with xyx \leq y, let [x,y][x, y] denote the interval {z:xzy}\{z \colon x \leq z \leq y\}. Then, given any two elements a,bLa, b \in L, there is an adjoint pair

a():[ab,b][a,ab]:()ba \vee (-) \colon [a \wedge b, b] \leftrightarrows [a, a \vee b] \colon (-) \wedge b

where a()a \vee (-) is left adjoint to ()b(-) \wedge b. Indeed, for any w[ab,b]w \in [a \wedge b, b], we have a unit

w(aw)b,w \leq (a \vee w) \wedge b,

whereas for any z[a,ab]z \in [a, a \vee b], we have dually a counit

a(zb)z.a \vee (z \wedge b) \leq z.
Definition

A lattice LL is modular if for any a,bLa, b \in L, the adjoint pair

a()()b:[a,ab][ab,b]a \vee (-) \dashv (-) \wedge b \colon [a, a \vee b] \to [a \wedge b, b]

is an adjoint equivalence.

This is perhaps the most memorable definition for a category theorist: it is a precise expression of the slogan given in the Idea section.

It is immediate that the concept of modular lattice is self-dual, i.e., if LL is modular, then so is L opL^{op}.

Alternative formulations

In the lattice-theoretic literature, modularity is usually formulated somewhat differently. Here are three alternative conditions on a lattice, all equivalent to that of Definition 1.

  1. The modular law is the universal Horn sentence

    ab(az)b=a(zb).a \leq b \vdash (a \vee z) \wedge b = a \vee (z \wedge b).
  2. The modular identity is the universal equation

    (az)(ab)=a(z(ab))(a \vee z) \wedge (a \vee b) = a \vee (z \wedge (a \vee b))
  3. Freyd’s modular law” (for lack of better term; see allegory) is the universal inequality

    (az)ba(z(ab)).(a \vee z) \wedge b \leq a \vee (z \wedge (a \vee b)).

Proofs of equivalence

Derivation of modular identity

To see that the modular identity follows from Definition 1, observe that for any zLz \in L we have

a(az)(ab)aba \leq (a \vee z) \wedge (a \vee b) \leq a \vee b

Let w=(az)(ab)w = (a \vee z) \wedge (a \vee b). Under ()b:[a,ab][ab,b](-) \wedge b \colon [a, a \vee b] \to [a \wedge b, b], this element ww is sent to

(az)(ab)b=(az)b.(a \vee z) \wedge (a \vee b) \wedge b = (a \vee z) \wedge b.

Under Definition 1, this last element is sent back to ww by a()a \vee (-). Therefore we have

(az)(ab)=w=a((az)b)(a \vee z) \wedge (a \vee b) = w = a \vee ((a \vee z) \wedge b)

and since this is true for all a,b,za, b, z, we can interchange zz and bb and rearrange by commutativity to get

(az)(ab)=a(z(ab))(a \vee z) \wedge (a \wedge b) = a \vee (z \wedge (a \vee b))

which is the modular identity.

Modular law \Leftrightarrow modular identity

To get the modular law from the modular identity, just use the fact that the hypothesis aba \leq b is equivalent to ab=ba \vee b = b, and use this to substitute bb for aba \vee b in the modular identity. Conversely, from the tautology aaba \leq a \vee b, we can instantiate the modular law to derive the modular identity.

Freyd’s modular law \Leftrightarrow modular identity

From the tautology (az)b(az)(ab)(a \vee z) \wedge b \leq (a \vee z) \wedge (a \vee b), it is clear that Freyd’s modular law follows from the modular identity. Conversely, by substituting aba \vee b for bb in Freyd’s modular law, we derive the special case

(az)(ab)a(z(ab))(a \vee z) \wedge (a \vee b) \leq a \vee (z \wedge (a \vee b))

whereas the opposite inequality

a(z(ab))(az)(ab)a \vee (z \wedge (a \vee b)) \leq (a \vee z) \wedge (a \vee b)

holds in any lattice, so the modular identity follows from Freyd’s modular law.

Modular identity \Rightarrow definition 1

Finally, we derive the adjoint equivalence of Definition 1 from the modular identity. One half of the adjoint equivalence states that if azaba \leq z \leq a \vee b, then z=a(zb)z = a \vee (z \wedge b); if this holds, then the other half follows because it is the dual statement. If azaba \leq z \leq a \vee b, then

z=(ab)z=(ab)(az)z = (a \vee b) \wedge z = (a \vee b) \wedge (a \vee z)

just by the laws of a lattice. By the modular identity (again switching bb and zz), the right side equals a(b(az))a \vee (b \wedge (a \vee z)). But since az=za \vee z = z, this equals a(bz)=a(zb)a \vee (b \wedge z) = a \vee (z \wedge b), as was to be shown.

Examples

  • Every distributive lattice, e.g., a Heyting algebra, is modular. Indeed, if aba \leq b in a distributive lattice, we have

    (az)b=(ab)(zb)=a(zb)(a \vee z) \wedge b = (a \wedge b) \vee (z \wedge b) = a \vee (z \wedge b)

    which proves the modular law.

  • For any Mal'cev variety or Mal’cev algebraic theory, the lattice of internal equivalence relations of an algebra is a modular lattice. The equivalence classes often arise as cosets of kernels; for example, for a vector space VV, equivalence relations correspond to subspaces of VV, and form a modular lattice. Other examples include the lattice of normal subgroups of a group, the lattice of two-sided ideals of a ring, etc.

  • In fact, any lattice of commuting equivalence relations on a set is a modular lattice (being a suballegory of the allegory of sets, one in which composition provides the join).

  • Every abstract projective plane gives rise to a modular lattice LL whose underlying set is the disjoint union

    {0}{1}{points}{lines}\{0\} \cup \{1\} \cup \{points\} \cup \{lines\}

    where 00 is taken as bottom, 11 as top, the points are atoms, and the lines are coatoms, ordered by the incidence relation. The projective plane need not be Desarguesian.

  • Young–Fibonacci lattice

Characterization

The smallest non-modular lattice has 5 elements and is called the pentagon, denoted N 5N_5. It can be described as the lattice {,a,b,c,}\{\bot, a, b, c, \top\} where bcb \leq c and aa is incomparable with bb and cc.

Theorem

(Dedekind) A lattice LL is modular if and only if there is no injective function f:N 5Lf \colon N_5 \to L that preserves meets and joins.

(Notice we are leaving out the condition of preservation of the top and bottom elements.) The direction \Rightarrow is easy enough: LL being modular is incompatible with an injective f:N 5Lf: N_5 \to L preserving meets and joins, since we contradict the modular law in LL by applying ff to (ba)c=c=c(b \vee a) \wedge c = \top \wedge c = c and b(ac)=b=bb \vee (a \wedge c) = b \vee \bot = b.

This is reminiscent of forbidden minor characterizations of certain classes of graphs; see graph minor. There is a similar “forbidden sublattice” characterization of distributive lattices – see this comment by Tom Leinster at the nn-Category Café.

Free modular lattices

Free modular lattices tend to be complicated. Dedekind showed that the free modular lattice on 3 elements has 28 elements; its Hasse diagram can be seen in these lecture notes by J.B. Nation (chapter 9, page 100).

N.B.: this notion of lattice is meant with respect to the signature (,)(\wedge, \vee); if we include top and bottom constants in the signature, then the free modular lattice on three elements has 30 elements. A compelling illustration (in gif form) which exhibits triality of this lattice is given in this nn-Category Café post, as part of a larger discussion which explores the connection with linear representations of the quiver D 4D_4 (the Coxeter diagram of SO(8)SO(8)).

For n4n \geq 4, the free modular lattice generated by nn elements is infinite and in fact has an undecidable word problem (Freese, Herrmann).

See also

References

  • Richard Dedekind, “Über die von drei Moduln erzeugte Dualgruppe gemeinsamen Teiler”, Math. Annalen 53 (1900), 371–403, reprinted in Gesammelte mathematische Werke, Vol. 2, pp. 236–271, Chelsea, New York, 1968.
  • C. Herrmann, “On the word problem for the modular lattice with four free generators”, Mathematische Annalen 265 (1983), 513-527. (Springerlink)

  • J.B. Nation, Revised Notes on Lattice Theory. Available here: (web)

  • Tom Leinster, Comment on Solèr’s Theorem, December 4, 2010. (link)

Last revised on February 20, 2019 at 15:50:35. See the history of this page for a list of all contributions to it.