Funayama's lattice

Hasse diagram of Funayama's lattice

In mathematics, particularly in lattice theory, Funayama's lattice is a distributive lattice whose Dedekind–MacNeille completion is not a modular lattice.

The lattice was constructed by the Japanese mathematician Nenosuke Funayama in his 1944 paper, which demonstrated that the Dedekind–MacNeille completion does not necessarily preserve modularity or distributivity. In the same paper, Funayama established a necessary and sufficient condition for the Dedekind–MacNeille completion of a distributive lattice to remain distributive.

Background and motivation

In 1872, the German mathematician Richard Dedekind introduced a method for constructing the real numbers from the rational numbers using cuts. Given the set of rational numbers ℚ, a cut (A,B) is a pair of nonempty disjoint sets whose union is ℚ, such that every element of A is smaller than every element of B, and A has no greatest element. In this way, all real numbers can be constructed. This method is known as the construction by Dedekind cuts.

In 1937, the American mathematician Holbrook Mann MacNeille generalized Dedekind's construction to arbitrary partially ordered sets. MacNeille showed that, given a partially ordered set P, one can construct a complete lattice L into which P can be order-embedded, by generalizing the idea of Dedekind cuts beyond the rational numbers. Furthermore, MacNeille proved that this completion is the smallest possible completion: if M is a complete lattice into which P can be order-embedded, then L can also be order-embedded into M. This construction became known as the Dedekind–MacNeille completion.

In his paper, MacNeille proved that if P is a Boolean algebra, then its Dedekind–MacNeille completion is a complete Boolean algebra. MacNeille also raised the questions of whether the Dedekind–MacNeille completion of a modular lattice is necessarily modular, and whether the completion of a distributive lattice is necessarily distributive.

These questions remained open until 1944, when Nenosuke Funayama published a paper providing a counterexample: a distributive lattice whose Dedekind–MacNeille completion is not modular. Since every distributive lattice is modular, this example answered both of MacNeille's questions in the negative. The lattice is known as Funayama's lattice.

Notation

Given a partially ordered set (P,≤) and a subset S⊆P, define:

Sub:={y∈P∣∀x∈S,x≤y},Slb:={y∈P∣∀x∈S,y≤x}

Additionally, for every x∈P, define:

↓x:={y∈P∣y≤x},↑x:={y∈P∣x≤y}

It follows that ↑x={x}ub and ↓x={x}lb.

Finally, denote the Dedekind–MacNeille completion of P by DM⁡(P). By definition:

DM⁡(P):={A⊆P∣(Aub)lb=A}

The order on DM⁡(P) is set inclusion. For every X,Y∈DM⁡(P), the meet and join are given by:

X∧DM⁡(P)Y=X∩YX∨DM⁡(P)Y=((X∪Y)ub)lb

It can be shown that ↓x∈DM⁡(P) for every x∈P, and that (Sub)lb∈DM⁡(P) for every S⊆P.

Construction of the lattice

The ordinal sum of omega and its reverse
The ordinal sum of ω and ω∗. This is a totally ordered set whose lower part has no greatest element and whose upper part has no least element. It can be visualized as having an "infinite gap" in the middle.

First, consider the ordinal number ω={0,1,2,…}, ordered by the usual "less than or equal to" relation. Let ω∗:={0←,1←,2←,…} denote a copy of ω with the reverse order (the left-pointing arrows distinguish the elements of ω∗ from those of ω). Define l:=ω⊕ω∗, where ⊕ denotes the ordinal sum. Since both ω and ω∗ are totally ordered sets, l is also totally ordered.

The plane formed by the direct product of l with itself
The plane formed by the direct product of l with itself. This plane is not totally ordered, but it is a distributive lattice.

Next, define the plane p:=l×l (see product order). This plane is not totally ordered. However, since every totally ordered set is a distributive lattice, and the direct product of distributive lattices is distributive, p is a distributive lattice.

In the next step, an additional copy of the plane p is introduced, producing two planes. Define the resulting lattice by r:=p×{0,1}, where the copy p×{0} lies below the copy p×{1}. This lattice is also distributive, being the direct product of a distributive lattice and a totally ordered set.

For (x1,x2,x3),(y1,y2,y3)∈r, the meet and join are computed coordinatewise:

(x1,x2,x3)∧(y1,y2,y3)=(min⁡(x1,y1),min⁡(x2,y2),min⁡(x3,y3))(x1,x2,x3)∨(y1,y2,y3)=(max⁡(x1,y1),max⁡(x2,y2),max⁡(x3,y3))

Finally, define the following sets:

A:=ω×ω×{0}B:=ω∗×ω×{0}C:=ω∗×ω×{1}D:=ω∗×ω∗×{1}

Funayama's lattice with its four components distinguished by color
Funayama's lattice, with the sets used in its construction highlighted: A in blue, B in purple, C in red, and D in green.

All four sets are subsets of r. Define their union by L:=A∪B∪C∪D. This is Funayama's lattice.

Properties

Distributivity

First, it must be shown that Funayama's lattice is distributive. Since L is a subset of r, which is a distributive lattice, it is sufficient to prove that L is a sublattice. Indeed, every sublattice of a distributive lattice is distributive.

For this purpose, given x,y∈L, we must determine whether x∧y and x∨y also belong to L. This can be verified by considering the components of L containing x and y. The results are summarized in the following tables.

Components containing x∧y
x∖y A B C D
A A A A A
B A B B B
C A B C C
D A B C D
Components containing x∨y
x∖y A B C D
A A B C D
B B B C D
C C C C D
D D D D D

As the tables show, regardless of which components contain x and y, both their meet and their join belong to L. Therefore, L is a sublattice of r, and hence is distributive.

Non-modularity of the Dedekind–MacNeille completion

Embedding of N5 into the Dedekind–MacNeille completion of Funayama's lattice
Embedding of the pentagon lattice N5 into the Dedekind–MacNeille completion of Funayama's lattice: 0′ is shown in red; a in red and blue; b in red, blue, and green; c in red and purple; and 1′ in red, blue, green, purple, and orange (the entire colored region).

Consider DM⁡(L). Recall that X∈DM⁡(L) if and only if X⊆L and (Xub)lb=X. Note that the operations ⋅ub and ⋅lb are taken with respect to L, rather than r.

Define:

0′:=ω×{0}×{0}a:=l×{0}×{0}b:=a∪(ω∗×{0}×{1})c:=A=ω×ω×{0}1′:=A∪B∪C

Consider the set L′:={0′,1′,a,b,c}. First, it must be shown that L′⊆DM⁡(L).

Observe that a=↓(0←,0,0) and b=↓(0←,0,1). Therefore, a,b∈DM⁡(L) and a⊊b.

Furthermore, Aub=D and Dlb=A, implying that c=A∈DM⁡(L).

Since a∩c=b∩c=ω×{0}×{0}=0′, and DM⁡(L) is closed under intersections, it follows that 0′∈DM⁡(L).

Finally, it can be shown that

(a∪c)ub=(b∪c)ub={0←}×ω∗×{1}.

Consequently,

a∨DM⁡(L)c=b∨DM⁡(L)c=({0←}×ω∗×{1})lb=A∪B∪C=1′,

and hence 1′∈DM⁡(L).

Thus, L′⊆DM⁡(L). Moreover, the five elements satisfy 0′⊊a⊊b⊊1′, while c is incomparable with both a and b, and

a∧c=b∧c=0′,a∨c=b∨c=1′.

Therefore, L′ is a sublattice isomorphic to the pentagon lattice N5. By the M3–N5 theorem, DM⁡(L) is not modular.

Necessary and sufficient condition for preserving distributivity

In his paper, Funayama also established a necessary and sufficient condition for the Dedekind–MacNeille completion of a distributive lattice to remain distributive.

Funayama proved that DM⁡(L) is distributive if and only if, for every S∈DM⁡(L), the mapping

fS:L→DM⁡(L)×DM⁡(L)x↦(↓x∨S,↓x∧S)

is injective, where the meet and join operations are taken in DM⁡(L).

In a distributive lattice, two elements having the same meet and the same join with a third element must be equal. Funayama's result shows that, for the Dedekind–MacNeille completion of a distributive lattice to remain distributive, it is sufficient for this property to hold between elements of the original lattice and every element of the completion.

This condition fails for Funayama's lattice. Indeed, a=↓(0←,0,0) and b=↓(0←,0,1), but a∧c=b∧c=0′ and a∨c=b∨c=1′. Therefore, DM⁡(L) is not distributive.