FUNCTIONS ON DISTRIBUTIVE LATTICES WITH

THE CONGRUENCE SUBSTITUTION PROPERTY

Some Problems of Grätzer

Jonathan David Farley

Abstract. Let L be a bounded distributive lattice. For k ⩾ 1, let S_{k}(L) be the lattice of k-ary functions on L with the congruence substitution property (Boolean functions); let S(L) be the lattice of all Boolean functions.

The lattices that can arise as S_{k}(L) or S(L) for some bounded distributive lattice L are characterized in terms of their Priestley spaces of prime ideals. For bounded distributive lattices L and M, it is shown that S_{1}(L) ≅ S_{1}(M) implies S_{k}(L) ≅ S_{k}(M). If L and M are finite, then S_{k}(L) ≅ S_{k}(M) implies L ≅ M.

Some problems of Grätzer dating to 1964 are thus solved.

1. The Problem.

Let L be a bounded distributive lattice and let k ⩾ 1. A function f : L^{k} → L has the congruence substitution property if, for every congruence θ of L, and all (a_{1}, b_{1}), …, (a_{k}, b_{k}) ∈ θ, we have f(a_{1}, …, a_{k})θf(b_{1}, …, b_{k}). The set of all such functions forms a bounded distributive lattice, denoted S_{k}(L) (also called the lattice of Boolean functions in [3]). Let S(L) be the lattice of all Boolean functions of finite arity (on the variables x_{1}, x_{2}, …).

Grätzer has proposed the following problems [3]:

Problem 1 (Grätzer, 1964). Let L and M be bounded distributive lattices such that S_{1}(L) ≅ S_{1}(M).

Is S_{k}(L) necessarily isomorphic to S_{k}(M)?

1991 Mathematics Subject Classification. 06B10, 06D05, 06B05, 06B15, 06E15, 06B30, 06E30.

Key words and phrases. (bounded) distributive lattice, (partially) ordered topological space, Priestley duality, congruence substitution property, Boolean function, affine completeness, function lattice.

The author would like to thank M. Maróti for an observation leading to a useful reformulation of Corollary 6.8.

Typeset by AMS-TEX

Problem 2 (Grätzer, 1964). Characterize those lattices isomorphic to S_{k}(L) or S(L) for some bounded distributive lattice L.

(See also General Lattice Theory [4], Problem II.14.)

We solve both of these problems (Corollary 5.6, Theorem 6.7 and Theorem 6.9).

Grätzer has also proposed the following problem [3]: Given a bounded distributive lattice L, find every bounded distributive lattice M such that S_{k}(L) ≅ S_{k}(M) (or such that S(L) ≅ S(M)). (In General Lattice Theory [4], Problem II.13, he asks: To what extent do S(L) and S_{k}(L) determine the structure of L?)

We prove that, for a finite distributive lattice L, S_{k}(L) fully determines L; but there are infinitely many pairwise non-isomorphic finite distributive lattices L_{1}, L_{2}, … such that S(L) ≅ S(L_{n}) (Theorem 7.1 and Note 7.2).

Along the way, we completely classify the Boolean functions on a bounded distributive lattice L (Theorem 4.7). Our central result is that S_{1}(S_{k}(L)) is canonically isomorphic to S_{k+1}(L) (Theorem 5.5).

Our proofs rely heavily on Priestley duality for distributive latttices.

2. Historical Background.

Functions on a general algebra with the congruence substitution property are the focus of the theory of affine completeness. (See, for instance, [6].)

It is obvious that every lattice polynomial on a bounded distributive lattice has the congruence substitution property, as does every Boolean algebra polynomial on a Boolean lattice. (For instance, (x ∧ y) ∨ z′ ∈ S_{3}(L) if L is Boolean.) Grätzer proved the converse ([2], Theorem 1): Every function on a Boolean lattice with the congruence substitution property is a Boolean algebra polynomial (hence the term ”Boolean function”). He also characterized those bounded distributive lattices such that every Boolean function is a lattice polynomial ([3], Corollary 3).

The key result for our purposes is the following

Theorem [3]. Let L be a bounded distributive lattice with least element 0_{L} and greatest element 1_{L}. Let k ⩾ 1 and let 2 := {0_{L}, 1_{L}}.

For all f : L^{k} → L, let ϕ_{f} : 2^{k} → L be the restriction of f to 2^{k}.

(1) For all f, g ∈ S_{k}(L), f = g if and only if ϕ_{f} = ϕ_{g}.

(2) Let ϕ : 2^{k} → L. There exists f ∈ S_{k}(L) such that ϕ = ϕ_{f} if and only if the interval [ϕ(b⃗), ϕ(a⃗) ∨ ϕ(b⃗)] is a Boolean lattice for all a⃗, b⃗ ∈ 2^{k} such that a⃗ < b⃗.

3. Mathematical Background, Terminology, and Notation (A Primer on Priestley Duality).

The central reference is [1].

Let L be a bounded distributive lattice; let 2 := {0_{L}, 1_{L}}, where 0_{L} is the least element of L and 1_{L} is the greatest element. For a, b ∈ L, where a ⩽ b, let [a, b]_{L} be the interval { c ∈ L | a ⩽ c ⩽ b }. Let Con L be the congruence lattice of L. For θ ∈ Con L and a, b ∈ L, we write aθb if (a, b) ∈ θ.

For k ⩾ 1, a function f : L^{k} → L has the congruence substitution property if, for all θ ∈ Con L and all a_{1}, b_{1}, …, a_{k}, b_{k} ∈ L, a_{i}θb_{i} (i = 1, …, k) implies f(a_{1}, …, a_{k})θf(b_{1}, …, b_{k}). The (bounded distributive) lattice of all such functions, also called the k-ary Boolean functions, is denoted S_{k}(L).

If we view the members of S_{k}(L) as functions depending on the variables x_{1}, …, x_{k}, we can take the union

⋃_{k=1}^{∞} S_{k}(L)

to get the (bounded distributive) lattice S(L) of all (finitary) Boolean functions.

Let P be a poset. A down-set of P is a subset U ⊆ P such that, for all p ∈ P and u ∈ U, p ⩽ u implies that p ∈ U. The poset of clopen down-sets of an ordered topological space P, partially ordered by inclusion, is a bounded distributive lattice, denoted O(P). (Meet is intersection, join is union, 0_{O(P)} is ∅, and 1_{O(P)} is P.)

A Priestley space P is a compact (partially) ordered topological space such that, for p, q ∈ P, p ⩽̸ q implies that p ∉ U and q ∈ U for some U ∈ O(P). Given a bounded distributive lattice L, the poset P (L) of prime ideals forms a Priestley space, with the subbasis

{{ I ∈ P (L) | a ∈ I }, { I ∈ P (L) | a ∉ I }}.

It is well known that L is isomorphic to O(P (L)) via the map

a ↦ U_{a} := { I ∈ P (L) | a ∉ I }.

It is also well known that every Priestley space P is order-homeomorphic (i.e., order-isomorphic and homeomorphic via the same function) to P (O(P)) by the map

p ↦ I_{p} := { U ∈ O(P) | p ∉ U }.

Indeed, the category D of bounded distributive lattices with {0, 1}-preserving homomorphisms is dually equivalent to the category P of Priestley spaces with continuous order-preserving maps. [If L is a finite distributive lattice, and J (L) is its poset of join-irreducibles, then L ≅ O(J (L)). If P is a finite poset, then P ≅ J (O(P)).]

Under the dual equivalence functor, a map f : L → M in D corresponds to the map ϕ : P (M) → P (L) in P given by ϕ(J) = f^{−1}(J) for all J ∈ P (M). Similarly, a map ϕ : P → Q in P corresponds to the map f : O(Q) → O(P) in D given by f(V) = ϕ^{−1}(V) for all V ∈ O(Q). (See [8]; [1], 10.25.)

If L, M ∈ D, every prime ideal of L × M is of the form I × M or L × J where I ∈ P (L) and J ∈ P (M) ([1], Exercise 9.3). If M is a {0, 1}-sublattice of L ∈ D, then every J ∈ P (M) is of the form I ∩ M for some I ∈ P (L); moreover, the function I ↦ I ∩ M is a continuous order-preserving map from P (L) onto P (M).

It is well known (Nachbin’s Theorem, [4], Theorem II.1.22) that L ∈ D is Boolean if and only if P (L) is an antichain (that is, distinct elements are incomparable).

In the sequel, let P ∈ P and let L := O(P).

Every clopen subset of P is a Priestley space; and for U, V ∈ O(P), O(U \V) is isomorphic to [U ∩ V, U]. Every clopen subset of P ∈ P is a finite union of sets of the form U \ V, where U,V ∈ O(P).

For all Q ⊆ P, let θ_{Q} := { (U, V) ∈ L^{2} | U ∩ Q = V ∩ Q }; if Q is a singleton {p}, we write θ_{p}. It is well known that Con L = { θ_{Q} | Q ⊆ P is closed } ([1], 10.27).

Given U ⊆ P, let ↓^{∘}U := { p ∈ P | p < u for some u ∈ U }; let Max U be the set of maximal elements of the poset U; let U^{0} := P \ U and let U^{1} := U.

Let S_{k}(L) be the family of 2^{k}-tuples

{ (Uϵ⃗)_{ϵ⃗∈2^{k}} ∈ L^{2^{k}} | for all δ⃗, ϵ⃗ ∈ 2^{k}, δ⃗ < ϵ⃗ implies ↓^{∘}Uδ⃗ ⊆ Uϵ⃗ }.

(Note that S_{k}(L) is a {0, 1}-sublattice of L^{2^{k}}.)

For all p ∈ P, ϵ⃗ ∈ 2^{k}, let

I_{p,ϵ⃗} := { (Uη⃗)_{η⃗∈2^{k}} ∈ S_{k}(L) | p ∉ Uϵ⃗ }.

We know that P (S_{k}(L)) = { I_{p,ϵ⃗} | p ∈ P, ϵ⃗ ∈ 2^{k} }.

An element p ∈ P is normal if there exist U, V ∈ L such that p ∈ U, p ∉ V, and [U ∩ V, U] is a Boolean lattice; otherwise p is special. (Note that, if L is finite, every p ∈ P is normal.)

For any ordered topological space R, let P ⋉ R be the ordered topological space with underlying space P × R and partial ordering

⩽_{P ⋉R}:=⩽_{P ×R} \{ ((p, r), (p, r′)) ∈ (P × R)^{2} | p is normal and r ≠ r′ }.

We denote the i-th component of ϵ⃗ ∈ 2^{k} by ϵ_{i} (1 ⩽ i ⩽ k); ϵ⃗0 denotes the element of 2^{k+1} such that

(ϵ⃗0)_{i} = \{ \begin{matrix}ϵ_{i} & if 1 ⩽ i ⩽ k, \\ 0 & if i = k + 1. \end{matrix}

Similarly, we define ϵ⃗1 ∈ 2^{k+1}; ϵ⃗′ is the complement of ϵ⃗ in 2^{k}.

4. The Lattice of k-ary Boolean Functions.

In this section, we completely characterize the k-ary Boolean functions on a bounded distributive lattice L (Theorem 4.7). In so doing, we obtain Grätzer’s result that every f ∈ S_{k}(L) is determined by its restriction to 2^{k}, where 2 := {0_{L}, 1_{L}}; we also obtain a new description of the functions ϕ : 2^{k} → L that are restrictions of Boolean functions to 2^{k} [easily seen to be equivalent to Grätzer’s ([3], Theorem)].

In the sequel, let P be a Priestley space and let L be the bounded distributive lattice O(P).

We begin with some trivial observations.

Note 4.1. Let U ∈ O(P). Then ↓^{∘}U = U \ Max U.

Proof. Every clopen subset of P is in P, and so corresponds to the poset of prime ideals of some bounded distributive lattice. By Zorn’s Lemma, every prime ideal of in such a lattice is contained in a maximal one. □

Lemma 4.2. Let U, V, Q ⊆ P. Then U ∩ Q = V ∩ Q implies

(P \ U) ∩ Q = (P \ V) ∩ Q. □

Note 4.3. Let U, V ∈ O(P). The following are equivalent:

(1) ↓^{∘}U ⊆ V;

(2) U \ V is an antichain;

(3) [U ∩ V, U]_{L} is a Boolean lattice;

(4) [V, U ∪ V]_{L} is a Boolean lattice.

Proof. Clearly (1) is equivalent to (2), (2) is equivalent to (3), and (3) is equivalent to (4). □

Lemma 4.4. Let f ∈ S_{k}(L). Then for all U_{1}, …, U_{k} ∈ L,

f(U_{1}, …, U_{k}) = ⋃_{ϵ⃗∈2^{k}} ⋂_{i=1}^{k} f(ϵ⃗) ∩ U_{i}^{ϵ_{i}}.

Proof. Let p ∈ P; let U_{1}, …, U_{k} ∈ O(P).

For i = 1, …, k, let

ϵ_{i} = \{ \begin{matrix}1 & if p ∈ U_{i}, \\ 0 & if p ∉ U_{i} \end{matrix}

(so that p ∈ U_{i}^{ϵ_{i}} and U_{i}θ_{p}ϵ_{i}). Hence p ∈ f(U_{1}, …, U_{k}) if and only if p ∈ f(ϵ_{1}, …, ϵ_{k}).

Now assume that p ∈ ⋂_{i=1}^{k} f(ϵ⃗) ∩ U_{i}^{ϵ_{i}} for some ϵ⃗ ∈ 2^{k}. Then U_{i}θ_{p}ϵ_{i} for i = 1, …, k, so that f(U_{1}, …, U_{k})θ_{p}f(ϵ⃗) and hence p ∈ f(U_{1}, …, U_{k}). □

Lemma 4.5. Let f ∈ S_{k}(L). Then (f(ϵ⃗))_{ϵ⃗∈2^{k}} is in S_{k}(L).

Proof. Let δ⃗, ϵ⃗ ∈ 2^{k} be such that δ⃗ < ϵ⃗. Assume for a contradiction that

↓^{∘}f(δ⃗) ⊈ f(ϵ⃗). Then there exist p, q ∈ f(δ⃗) such that p < q and p ∉ f(ϵ⃗). Let U ∈ O(P) be such that p ∈ U and q ∉ U. Then Uθ_{p}1_{L} and Uθ_{q}0_{L}. For i = 1, …, k, let

U_{i} := \{ \begin{matrix}U & if δ_{i} < ϵ_{i}, \\ δ_{i} & otherwise, \end{matrix}

so that U_{i}θ_{p}ϵ_{i} and U_{i}θ_{q}δ_{i}.

Hence q ∈ f(U_{1}, …, U_{k}), so that p ∈ f(U_{1}, …, U_{k}); but

p ∉ f(U_{1}, …, U_{k}),

a contradiction. □

Lemma 4.6. Let (Uϵ⃗)_{ϵ⃗∈2^{k}} ∈ S_{k}(L). Define f : L^{k} → L as follows: for U_{1}, …, U_{k} ∈ L, let

f(U_{1}, …, U_{k}) := ⋃_{ϵ⃗∈2^{k}} ⋂_{i=1}^{k} Uϵ⃗ ∩ U_{i}^{ϵ_{i}}.

Then f ∈ S_{k}(L) and, for all ϵ⃗ ∈ 2^{k}, f(ϵ⃗) = Uϵ⃗.

Proof. First we show that f is well defined. Let U_{1}, …, U_{k} ∈ L. Clearly f(U_{1}, …, U_{k}) is a clopen subset of P. Let p, q ∈ P be such that p < q where q ∈ f(U_{1}, …, U_{k}). We must show that p ∈ f(U_{1}, …, U_{k}).

Assume not, for a contradiction. There exists δ⃗ ∈ 2^{k} such that

q ∈ ⋂_{i=1}^{k} Uδ⃗ ∩ U_{i}^{δ_{i}}.

For i = 1, …, k, let

ϵ_{i} := \{ \begin{matrix}δ_{i} & if p ∈ U_{i}^{δ_{i}}, \\ 1 & otherwise. \end{matrix}

For some j ∈ {1, …, k}, δ_{j} = 0 and ϵ_{j} = 1 (or else

p ∈ ⋂_{i=1}^{k} Uδ⃗ ∩ U_{i}^{δ_{i}},

a contradiction). Hence δ⃗ < ϵ⃗. Thus p ∈ Uϵ⃗; and since

p ∈ ⋂_{i=1}^{k} Uϵ⃗ ∩ U_{i}^{ϵ_{i}},

we have p ∈ f(U_{1}, …, U_{k}), a contradiction. Hence f : L^{k} → L is well defined. Clearly f ∈ S_{k}(L). (See Lemma 4.2.)

Finally, let ϵ⃗ ∈ 2^{k}. We will show that f(ϵ⃗) = Uϵ⃗. Certainly ϵ_{i}^{ϵ_{i}} = P for i = 1, …, k, so

⋂_{i=1}^{k} Uϵ⃗ ∩ ϵ_{i}^{ϵ_{i}} = Uϵ⃗.

Now let δ⃗ ∈ 2^{k} be distinct from ϵ⃗. Then there exists i ∈ { 1, …, k } such that δ_{i} ≠ ϵ_{i}. If δ_{i} = 0 and ϵ_{i} = 1, we have ϵ_{i}^{δ_{i}} = ∅. If δ_{i} = 1 and ϵ_{i} = 0, we have ϵ_{i}^{δ_{i}} = ∅. Hence

⋂_{i=1}^{k} Uδ⃗ ∩ ϵ_{i}^{δ_{i}} = ∅.

Thus f(ϵ⃗) = Uϵ⃗. □

The main theorem of this section provides an alternate, unified proof of both [2], Theorem 1 and [3], Theorem. (Note the similarity with [5], Theorem 2.41, which the author came across after proving the main theorem: [5], Theorem 2.41 deals with normal forms for propositional formulas.) Our result extends these theorems by explicitly describing all possible k-ary Boolean functions.

Theorem 4.7. The lattices S_{k}(L) and S_{k}(L) are isomorphic.

Define a map Φ : S_{k}(L) → S_{k}(L) as follows: for all f ∈ S_{k}(L), let

Φ(f) := (f(ϵ⃗))_{ϵ⃗∈2^{k}}.

Define a map Ψ : S_{k}(L) → S_{k}(L) as follows: for all (Uϵ⃗)_{ϵ⃗∈2^{k}} ∈ S_{k}(L), let Ψ((Uϵ⃗)_{ϵ⃗∈2^{k}}) : L^{k} → L be the function defined for all U_{1}, …, U_{k} ∈ L by

Ψ((Uϵ⃗)_{ϵ⃗∈2^{k}})(U_{1}, …, U_{k}) := ⋃_{ϵ⃗∈2^{k}} ⋂_{i=1}^{k} Uϵ⃗ ∩ U_{i}^{ϵ_{i}}.

Then Φ and Ψ are mutually-inverse order-isomorphisms.

Proof. The theorem follows from Lemmas 4.4–4.6. □

The theorem implies that the generic unary Boolean function f : L → L is given by

f(U) = (U_{0} \ U) ∪ (U_{1} ∩ U)

where U_{0}, U_{1} ∈ L are such that ↓^{∘}U_{0} ⊆ U_{1}. Example 4.8. Let P be the two-element chain {a, b} where a < b; then L = O(P) is the three-element chain {∅, a, ab} (Figure 4.1).

[figure: P; a; b; L; ∅; a; ab]

Figure 4.1. The poset P and the lattice L = O(P).

Clearly ↓^{∘}∅ =↓^{∘}a = ∅ and ↓^{∘}ab = a (Table 4.1).

\begin{matrix}U & ↓^{∘}U \\ ∅ & ∅ \\ a & ∅ \\ ab & a \end{matrix}

Table 4.1. The members of O(P) sans their maximal elements.

Hence S_{1}(L) is the lattice

{ (∅, ∅), (∅, a), (∅, ab), (a, ∅), (a, a), (a, ab), (ab, a), (ab, ab) }

(Figure 4.2).

[figure: (∅, ∅); (∅, a); (a, ∅); (∅, ab); (a, a); (a, ab); (ab, a); (ab, ab)]

Figure 4.2. The lattice S_{1}(L).

FUNCTIONS WITH THE CONGRUENCE SUBSTITUTION PROPERTY 9

The lattice S_{2}(L) has 52 elements, which we list in 2 × 2 matrix notation:

( \begin{matrix}∅ & ∅ \\ ∅ & ∅ \end{matrix} ) ( \begin{matrix}∅ & ∅ \\ ∅ & a \end{matrix} ) ( \begin{matrix}∅ & ∅ \\ ∅ & ab \end{matrix} ) ( \begin{matrix}∅ & ∅ \\ a & ∅ \end{matrix} ) ( \begin{matrix}∅ & ∅ \\ a & a \end{matrix} ) ( \begin{matrix}∅ & ∅ \\ a & ab \end{matrix} ) ( \begin{matrix}∅ & ∅ \\ ab & a \end{matrix} ) ( \begin{matrix}∅ & ∅ \\ ab & ab \end{matrix} )
( \begin{matrix}∅ & a \\ ∅ & ∅ \end{matrix} ) ( \begin{matrix}∅ & a \\ ∅ & a \end{matrix} ) ( \begin{matrix}∅ & a \\ ∅ & ab \end{matrix} ) ( \begin{matrix}∅ & a \\ a & ∅ \end{matrix} ) ( \begin{matrix}∅ & a \\ a & a \end{matrix} ) ( \begin{matrix}∅ & a \\ a & ab \end{matrix} ) ( \begin{matrix}∅ & a \\ ab & a \end{matrix} ) ( \begin{matrix}∅ & a \\ ab & ab \end{matrix} )
( \begin{matrix}∅ & ab \\ ∅ & a \end{matrix} ) ( \begin{matrix}∅ & ab \\ ∅ & ab \end{matrix} )  ( \begin{matrix}∅ & ab \\ a & a \end{matrix} ) ( \begin{matrix}∅ & ab \\ a & ab \end{matrix} ) ( \begin{matrix}∅ & ab \\ ab & a \end{matrix} ) ( \begin{matrix}∅ & ab \\ ab & ab \end{matrix} )
( \begin{matrix}a & ∅ \\ ∅ & ∅ \end{matrix} )( \begin{matrix}a & ∅ \\ ∅ & a \end{matrix} )( \begin{matrix}a & ∅ \\ ∅ & ab \end{matrix} )( \begin{matrix}a & ∅ \\ a & ∅ \end{matrix} )( \begin{matrix}a & ∅ \\ a & a \end{matrix} )( \begin{matrix}a & ∅ \\ a & ab \end{matrix} )( \begin{matrix}a & ∅ \\ ab & a \end{matrix} )( \begin{matrix}a & ∅ \\ ab & ab \end{matrix} )
( \begin{matrix}a & a \\ ∅ & ∅ \end{matrix} )( \begin{matrix}a & a \\ ∅ & a \end{matrix} )( \begin{matrix}a & a \\ ∅ & ab \end{matrix} )( \begin{matrix}a & a \\ a & ∅ \end{matrix} )( \begin{matrix}a & a \\ a & a \end{matrix} )( \begin{matrix}a & a \\ a & ab \end{matrix} )( \begin{matrix}a & a \\ ab & a \end{matrix} )( \begin{matrix}a & a \\ ab & ab \end{matrix} )
( \begin{matrix}a & ab \\ ∅ & a \end{matrix} )( \begin{matrix}a & ab \\ ∅ & ab \end{matrix} )  ( \begin{matrix}a & ab \\ a & a \end{matrix} )( \begin{matrix}a & ab \\ a & ab \end{matrix} )( \begin{matrix}a & ab \\ ab & a \end{matrix} )( \begin{matrix}a & ab \\ ab & ab \end{matrix} )
( \begin{matrix}ab & a \\ a & a \end{matrix} ) ( \begin{matrix}ab & a \\ a & ab \end{matrix} ) ( \begin{matrix}ab & a \\ ab & a \end{matrix} ) ( \begin{matrix}ab & a \\ ab & ab \end{matrix} )
( \begin{matrix}ab & ab \\ a & a \end{matrix} ) ( \begin{matrix}ab & ab \\ a & ab \end{matrix} ) ( \begin{matrix}ab & ab \\ ab & a \end{matrix} ) ( \begin{matrix}ab & ab \\ ab & ab \end{matrix} )

Example 4.9. Let P be the three-element fence {a, b, c} where b > a < c; then L = O(P) is the lattice { ∅, a, ab, ac, abc } (Figure 4.3).

[figure: P; a; b; c; L; ∅; a; ab; ac; abc]

Figure 4.3. The poset P and the lattice L = O(P).

\begin{matrix}U & ↓^{∘}U \\ ∅ & ∅ \\ a & ∅ \\ ab & a \\ ac & a \\ abc & a \end{matrix}

Table 4.2. The members of O(P) sans their maximal elements.

[figure]

Figure 4.4. The lattice S_{1}(L).

Clearly ↓^{∘}∅ =↓^{∘}a = ∅ and ↓^{∘}ab =↓^{∘}ac =↓^{∘}abc = a (Table 4.2).

Then S_{1}(L) is the lattice {∅, a} × L ∪ {ab, ac, abc} × {a, ab, ac, abc} (Figure 4.4). Example 4.10. Let Q be the four-element fence {w, x, y, z} where w < x > y < z; then M = O(Q) is the lattice { ∅, w, y, wy, yz, wxy, wyz, wxyz } (Figure 4.5).

Clearly ↓^{∘}∅ =↓^{∘}w =↓^{∘}y =↓^{∘}wy = ∅, ↓^{∘}yz =↓^{∘}wyz = y, and ↓^{∘}wxy =↓^{∘}wxyz = wy

(Table 4.3).

FUNCTIONS WITH THE CONGRUENCE SUBSTITUTION PROPERTY 11

[figure: Q; y; w; z; x; M; ∅; y; w; yz; wy; wyz; wxy; wxyz]

Figure 4.5. The poset Q and the lattice M = O(Q).

\begin{matrix}U & ↓^{∘}U \\ ∅ & ∅ \\ y & ∅ \\ yz & y \\ w & ∅ \\ wy & ∅ \\ wyz & y \\ wxy & wy \\ wxyz & wy \end{matrix}

Table 4.3. The members of O(Q) sans their maximal elements.

Thus S_{1}(M) has 52 elements:

(∅,∅) (∅,y) (∅,yz) (∅,w) (∅,wy) (∅,wyz) (∅,wxy) (∅,wxyz) (y,∅) (y,y) (y,yz) (y,w) (y,wy) (y,wyz) (y,wxy) (y,wxyz)

(yz,y) (yz,yz) (yz,wy) (yz,wyz) (yz,wxy) (yz,wxyz) (w,∅) (w,y) (w,yz) (w,w) (w,wy) (w,wyz) (w,wxy) (w,wxyz)

(wy,∅) (wy,y) (wy,yz) (wy,w) (wy,wy) (wy,wyz) (wy,wxy) (wy,wxyz)

(wyz,y) (wyz,yz) (wyz,wy) (wyz,wyz) (wyz,wxy) (wyz,wxyz)

(wxy,wy) (wxy,wyz) (wxy,wxy) (wxy,wxyz) (wxyz,wy) (wxyz,wyz) (wxyz,wxy) (wxyz,wxyz).

5. Boolean Functions on the Lattice of Boolean Functions: The Solution to Grätzer’s First Problem.

In this section, we solve Problem 1 of §1, posed by Grätzer in 1964 (Corollary 5.6): The lattice S_{k}(L) (for a bounded distributive lattice L) is determined up to isomorphism by the lattice S_{1}(L). Indeed, we prove the surprising result that S_{k+1}(L) is canonically isomorphic to S_{1}(S_{k}(L)), the lattice of unary Boolean functions on the lattice of k-ary Boolean functions of L (Theorem 5.5).

Recall that P ∈ P and L = O(P).

Lemma 5.1. Let U⃗ := (Uϵ⃗)_{ϵ⃗∈2^{k}}, V⃗ := (Vϵ⃗)_{ϵ⃗∈2^{k}} ∈ S_{k}(L) be such that

[Uδ⃗ ∩ Vϵ⃗, Uδ⃗]_{L}

is a Boolean lattice whenever δ⃗, ϵ⃗ ∈ 2^{k} and δ⃗ < ϵ⃗. Choose Wϵ⃗ ∈ [Uϵ⃗ ∩ Vϵ⃗, Uϵ⃗]_{L} for all ϵ⃗ ∈ 2^{k}.

Then (Wϵ⃗)_{ϵ⃗∈2^{k}} belongs to S_{k}(L).

Proof. Let δ⃗, ϵ⃗ ∈ 2^{k} be such that δ⃗ < ϵ⃗. Then

↓^{∘}Wδ⃗ ⊆↓^{∘}Uδ⃗ ⊆ Uϵ⃗ ∩ Vϵ⃗ ⊆ Wϵ⃗

(using Note 4.3). □

Corollary 5.2. Let U⃗ := (Uϵ⃗)_{ϵ⃗∈2^{k}}, V⃗ := (Vϵ⃗)_{ϵ⃗∈2^{k}} ∈ S_{k}(L) be such that

[Uδ⃗ ∩ Vϵ⃗, Uδ⃗]_{L}

is a Boolean lattice whenever δ⃗, ϵ⃗ ∈ 2^{k} and δ⃗ ⩽ ϵ⃗.

Then

[U⃗ ∧ V⃗ , U⃗]_{S_{k}(L)}

is a Boolean lattice.

Proof. Let

W⃗ := (Wϵ⃗)_{ϵ⃗∈2^{k}} ∈ [U⃗ ∧ V⃗ , U⃗]_{S_{k}(L)}.

Thus, for all ϵ⃗ ∈ 2^{k}, Wϵ⃗ ∈ [Uϵ⃗ ∩ Vϵ⃗, Uϵ⃗]_{L}, so there exists W ′ ; ϵ⃗ ∈ [Uϵ⃗ ∩ Vϵ⃗, Uϵ⃗]_{L}

such that Wϵ⃗ ∩ W ′ ; ϵ⃗ = Uϵ⃗ ∩ Vϵ⃗ and Wϵ⃗ ∪ W ′ ; ϵ⃗ = Uϵ⃗.

By Lemma 5.1, W⃗′ := (W ′ ; ϵ⃗)_{ϵ⃗∈2^{k}} belongs to S_{k}(L); clearly W⃗ ∧ W⃗′ = U⃗ ∧ V⃗ and W⃗ ∨ W⃗′ = U⃗. □

Lemma 5.3. Let U⃗_{0} := (Uϵ⃗0)_{ϵ⃗∈2^{k}}, U⃗_{1} := (Uϵ⃗1)_{ϵ⃗∈2^{k}} ∈ S_{k}(L) be such that (U⃗_{0}, U⃗_{1}) belongs to S_{1}(S_{k}(L)).

Then ↓^{∘}Uδ⃗0 ⊆ Uϵ⃗1 for all δ⃗, ϵ⃗ ∈ 2^{k} such that δ⃗ < ϵ⃗.

Proof. Fix δ⃗, ϵ⃗ ∈ 2^{k} such that δ⃗ < ϵ⃗. By Note 4.3,

[U⃗_{0} ∧ U⃗_{1}, U⃗_{0}]_{S_{k}(L)}

is a Boolean lattice.

For all η⃗ ∈ 2^{k}, let

Wη⃗ := \{ \begin{matrix}Uη⃗0 ∩ Uη⃗1 & if η⃗ < ϵ⃗, \\ Uη⃗0 & otherwise. \end{matrix}

Then W⃗ := (Wη⃗)_{η⃗∈2^{k}} ∈ S_{k}(L); indeed

W⃗ ∈ [U⃗_{0} ∧ U⃗_{1}, U⃗_{0}]_{S_{k}(L)}.

Let W⃗′ := (W ′ ; η⃗)_{η⃗∈2^{k}} ∈ S_{k}(L) be such that W⃗ ∧W⃗′ = U⃗_{0}∧U⃗_{1} and W⃗ ∨W⃗′ = U⃗_{0}.

Clearly W ′ ; δ⃗ = Uδ⃗0 and W ′ ; ϵ⃗ = Uϵ⃗0 ∩ Uϵ⃗1. Hence ↓^{∘}Uδ⃗0 ⊆ Uϵ⃗1. □

Lemma 5.4. Let U⃗_{0} := (Uϵ⃗0)_{ϵ⃗∈2^{k}}, U⃗_{1} := (Uϵ⃗1)_{ϵ⃗∈2^{k}} ∈ S_{k}(L) be such that (U⃗_{0}, U⃗_{1}) belongs to S_{1}(S_{k}(L)).

Then for all ϵ⃗ ∈ 2^{k}, ↓^{∘}Uϵ⃗0 ⊆ Uϵ⃗1.

Proof. Fix ϵ⃗ ∈ 2^{k}. It suffices to prove that [Uϵ⃗0 ∩Uϵ⃗1, Uϵ⃗0]_{L} is a Boolean lattice. Let W ∈ [Uϵ⃗0 ∩ Uϵ⃗1, Uϵ⃗0]_{L}.

For all η⃗ ∈ 2^{k}, let

(Wη⃗) := \{ \begin{matrix}Uη⃗0 ∩ Uη⃗1 & if η⃗ < ϵ⃗, \\ W & if η⃗ = ϵ⃗ \\ Uη⃗0 & otherwise. \end{matrix}

Then W⃗ := (Wη⃗)_{η⃗∈2^{k}} ∈ S_{k}(L), and it lies in the Boolean interval

[U⃗_{0} ∧ U⃗_{1}, U⃗_{0}]_{S_{k}(L)}.

Let W⃗′ := (W ′ ; η⃗)_{η⃗∈2^{k}} ∈ S_{k}(L) be such that W⃗ ∧W⃗′ = U⃗_{0}∧U⃗_{1} and W⃗ ∨W⃗′ = U⃗_{0}.

Clearly W ∩ W ′ ; ϵ⃗ = Uϵ⃗0 ∩ Uϵ⃗1 and W ∪ W ′ ; ϵ⃗ = Uϵ⃗0. □

Theorem 5.5. The lattices S_{k+1}(L) and S_{1}(S_{k}(L)) are isomorphic.

Define a map

Φ : S_{k+1}(L) → S_{1}(S_{k}(L))

as follows: for all (Uζ⃗)_{ζ⃗∈2^{k+1}} ∈ S_{k+1}(L), let

Φ((Uζ⃗)_{ζ⃗∈2^{k+1}}) = ((Uϵ⃗0)_{ϵ⃗∈2^{k}}, (Uϵ⃗1)_{ϵ⃗∈2^{k}}).

Define a map

Ψ : S_{1}(S_{k}(L)) → S_{k+1}(L)

as follows: for all ((Uϵ⃗0)_{ϵ⃗∈2^{k}}, (Uϵ⃗1)_{ϵ⃗∈2^{k}}) ∈ S_{1}(S_{k}(L)), let

Ψ((Uϵ⃗0)_{ϵ⃗∈2^{k}}, (Uϵ⃗1)_{ϵ⃗∈2^{k}}) = (Uζ⃗)_{ζ⃗∈2^{k+1}}.

Then Φ and Ψ are mutually-inverse order-isomorphisms.

Proof. By Corollary 5.2 and Note 4.3, Φ is well defined. By Lemmas 5.3 and 5.4, Ψ is well defined. They are clearly order-preserving and inverses to each other. □

As a corollary, we solve Grätzer’s first problem ([3]; see §1):

Corollary 5.6. Let L, M ∈ D be such that S_{1}(L) ≅ S_{1}(M).

Then S_{k}(L) ≅ S_{k}(M). □

Example 5.7. Let L be the three-element chain. In Example 4.8, we computed S_{1}(L) and S_{2}(L). In Example 4.10, we computed S_{1}(M) where M ≅ S_{1}(L). In both examples, we listed the elements of S_{2}(L) and S_{1}(S_{1}(L)). The isomorphism of Theorem 5.5 can be easily seen by turning each 2 × 2 matrix of Example 4.8 into an ordered pair by grouping the rows together and using the isomorphism S_{1}(L) ≅ M given by

(∅, ∅) ↦ ∅
(∅, a) ↦ y
(∅, ab) ↦ yz
(a, ∅) ↦ w
(a, a) ↦ wy
(a, ab) ↦ wyz
(ab, a) ↦ wxy
(ab, ab) ↦ wxyz.

6. The Priestley Dual of the Lattice of Boolean Functions: The Solution to Grätzer’s Second Problem.

In this section, we solve Problem 2 of §1, posed by Grätzer in 1964 and restated in 1978 in his influential book (Theorems 6.7 and 6.9): We completely characterize the lattices that can arise as S_{k}(L) or S(L) for a bounded distributive lattice L. We do so in terms their Priestley spaces of prime ideals.

Recall that P ∈ P and L = O(P).

Note 6.1. Let p ∈ P. The following are equivalent:

(1) p is normal;

(2) there exist U, V ∈ O(P) such that U \ V is an antichain containing p;

(3) there exist W ∈ O(P) and a clopen subset C of P such that p ∈ C ⊆ Max W.

Proof. Note 4.3 gives the equivalence of (1) and (2) and the fact that (2) implies (3). To show that (3) implies (2), let U, V ∈ O(P) be such that p ∈ U \V ⊆ C. Then U \ V is an antichain. □

Lemma 6.2. Let p, q ∈ P and let δ⃗, ϵ⃗ ∈ 2^{k}. Assume that p < q and δ⃗ ⩾ ϵ⃗. Then I_{p,δ⃗} ⊆ I_{q,ϵ⃗}.

Proof. Let (Uη⃗)_{η⃗∈2^{k}} ∈ I_{p,δ⃗}. Then p ∉ Uδ⃗. Assume for a contradiction that

q ∈ Uϵ⃗. Then p ∈↓^{∘}Uϵ⃗ and hence p ∈ Uδ⃗, a contradiction. □

Lemma 6.3. Let p ∈ P and let δ⃗, ϵ⃗ ∈ 2^{k}. Assume that p is special and that δ⃗ ⩾ ϵ⃗.

Then I_{p,δ⃗} ⊆ I_{p,ϵ⃗}.

Proof. Let (Uη⃗)_{η⃗∈2^{k}} ∈ I_{p,δ⃗}. Then p ∉ Uδ⃗ and ↓^{∘} Uϵ⃗ ⊆ Uδ⃗, so, by Note 4.3, Uϵ⃗ \ Uδ⃗ is an antichain. Hence p ∉ Uϵ⃗, by Note 6.1. □

Lemma 6.4. Let p, q ∈ P and let δ⃗, ϵ⃗ ∈ 2^{k}. Assume that I_{p,δ⃗} ⊆ I_{q,ϵ⃗}. Then p ⩽ q.

Proof. Assume for a contradiction that p ⩽̸ q. Let U ∈ O(P) be such that p ∉ U and q ∈ U. Then (U)_{η⃗∈2^{k}} ∈ I_{p,δ⃗} \ I_{q,ϵ⃗}, a contradiction. □

Lemma 6.5. Let p, q ∈ P and let δ⃗, ϵ⃗ ∈ 2^{k}. Assume that I_{p,δ⃗} ⊆ I_{q,ϵ⃗}. Then δ⃗ ⩾ ϵ⃗.

Proof. Assume for a contradiction that δ⃗ ⩾̸ ϵ⃗. For all η⃗ ∈ 2^{k}, let

Uη⃗ := \{ \begin{matrix}P & if η⃗ ⩾ ϵ⃗, \\ ∅ & otherwise. \end{matrix}

Then (Uη⃗)_{η⃗∈2^{k}} ∈ I_{p,δ⃗} \ I_{q,ϵ⃗}, a contradiction. □

Lemma 6.6. Let p ∈ P and let δ⃗, ϵ⃗ ∈ 2^{k}. Assume that I_{p,δ⃗} ⊆ I_{p,ϵ⃗} where δ⃗ ≠ ϵ⃗.

Then p is special.

Proof. By Lemma 6.5, δ⃗ > ϵ⃗.

Assume, for a contradiction, that p is normal. By Notes 4.3 and 6.1, there

exist U, V ∈ O(P) such that p ∈ U \ V and ↓^{∘}U ⊆ V. For all η⃗ ∈ 2^{k}, let

Wη⃗ := \{ \begin{matrix}V & if η⃗ ⩾ δ⃗, \\ U & if η⃗ ⩾̸ δ⃗. \end{matrix}

Then (Wη⃗)_{η⃗∈2^{k}} ∈ I_{p,δ⃗} \ I_{p,ϵ⃗}, a contradiction. □

Theorem 6.7. The Priestley space of S_{k}(L) is order-homeomorphic to the ordered space P ⋉ 2^{k}.

Define the order-homeomorphism Φ : P (S_{k}(L)) → P ⋉ 2^{k} as follows: for all p ∈ P, ϵ⃗ ∈ 2^{k}, let Φ(I_{p,ϵ⃗}) = (p, ϵ⃗′).

Proof. By Lemmas 6.4 and 6.5, Φ is well defined and order-preserving. By Lemmas 6.2 and 6.3, Φ is an order-embedding.

Obviously Φ is onto. Hence Φ is an order-isomorphism.

To prove that Φ is a homeomorphism, let

Ψ : P (L^{2^{k}}) → P (S_{k}(L))

be the function sending { (Uϵ⃗)_{ϵ⃗∈2^{k}} ∈ L^{2^{k}} | p ∉ Uϵ⃗ } to I_{p,ϵ⃗} for all p ∈ P, ϵ⃗ ∈ 2^{k}. We know that Ψ is continuous. It is also a bijection. Since Priestley spaces are compact and Hausdorff, Ψ is a homeomorphism (see, for instance, [1], Lemma 10.7A). □

After seeing Theorem 6.7 for finite lattices, M. Maróti made the following observation:

Corollary 6.8. If L is finite, then (J (S_{k}(L)), <) is isomorphic to

(J (L), <) × (2^{k}, ⩽). □

Theorem 6.9. The Priestley space of S(L) is order-homeomorphic to P ⋉2^{ℕ}.

Proof. Clearly P ⋉ 2^{ℕ} is a Priestley space. For all k ∈ ℕ, let

π_{k} : P ⋉ 2^{ℕ} → P ⋉ 2^{k}

be the obvious projection; similarly, define π_{kl} : P ⋉ 2^{l} → P ⋉ 2^{k} for all k, l ∈ ℕ such that k ⩽ l.

[figure: P; a; b; P × 2; (a, 0); (b, 0); (a, 1); (b, 1); P ⋉ 2; (a, 0); (b, 0); (a, 1); (b, 1)]

Figure 6.1. The posets P, P × 2, and P ⋉ 2.

[figure: •; •; •; •]
Figure 6.2. The lattice S_{1}(L) and the poset J (S_{1}(L)).

We verify that (P ⋉ 2^{ℕ}, (π_{k} : P ⋉ 2^{ℕ} → P ⋉ 2^{k})_{k⩾1}) is the inverse limit of the directed system

((P ⋉ 2^{k})_{k⩾1}, (π_{kl} : P ⋉ 2^{l} → P ⋉ 2^{k})_{1⩽k⩽l})

in the category of Priestley spaces. □

Example 6.10. Let P be the two-element chain {a, b} of Example 4.8 and let L = O(P) (Figure 4.1). Figure 6.1 shows P × 2 and P ⋉ 2.

Note that P ⋉2 is order-isomorphic to J (S_{1}(L)), so that O(P ⋉2) ≅ S_{1}(L) (Figures 4.2 and 6.2).

Figure 6.3 shows P, 2^{2}, P × 2^{2}, and P ⋉ 2^{2}.

[figure: P; a; b; 2^{2}; 0; α; β; 1; P × 2^{2}; (a,0); (a,α); (b,0); (a,β); (b,α); (a,1); (b,β); (b,1); P ⋉ 2^{2}; (a,0); (b,0); (a,α); (a,β); (b,α); (b,β); (a,1); (b,1)]

Figure 6.3. The posets P, 2^{2}, P × 2^{2}, and P ⋉ 2^{2}.

Example 6.11. Let P be the three-element fence {a, b, c} of Example 4.9 and let L = O(P) (Figure 4.3). Figure 6.4 shows P, P × 2, and P ⋉ 2.

[figure: P; a; b; c; P × 2; (a,0); (b,0); (c,0); (a,1); (b,1); (c,1); P × 2; (a,0); (b,0); (c,0); (a,1); (b,1); (c,1)]

Figure 6.4. The posets P, P × 2, and P ⋉ 2.

[figure: •; •; •; •; •; •]
Figure 6.5. The lattice S_{1}(L) and the poset J (S_{1}(L)).

Note that P ⋉2 is order-isomorphic to J (S_{1}(L)), so that O(P ⋉2) ≅ S_{1}(L) (Figures 4.4 and 6.5).

Indeed, J (S_{1}(L)) = { (∅, a), (∅, ab), (∅, ac), (a, ∅), (ab, ∅), (ac, ∅) }. Example 6.12. Let Q be the four-element fence {w, x, y, z} of Example 4.10 and let M = O(Q) (Figure 4.5). Figures 6.6 and 6.7 show Q, Q×2, and Q⋉2.

Let P be the two-element chain of Example 6.10. Note that Q ≅ P ⋉ 2 and that Q ⋉ 2 ≅ (P ⋉ 2) ⋉ 2 is order-isomorphic to P ⋉ 2^{2} (Figure 6.3) under the isomorphism

(w, 0) ↦ (a, α)
(x, 0) ↦ (b, α)

[figure: Q; y; w; z; x; Q × 2; (y,0); (w,0); (z,0); (x,0); (y,1); (w,1); (z,1); (x,1)]

Figure 6.6. The posets Q and Q × 2.

[figure: Q ⋉ 2; (y,0); (w,0); (z,0); (x,0); (y,1); (w,1); (z,1); (x,1)]

Figure 6.7. The poset Q ⋉ 2.

(y, 0) ↦ (a, 0)
(z, 0) ↦ (b, 0)
(w, 1) ↦ (a, 1)
(x, 1) ↦ (b, 1)
(y, 1) ↦ (a, β)
(z, 1) ↦ (b, β).

7. Recovering the Lattice from the Lattice of Boolean Functions. In this section, we address Grätzer’s remaining problem (see §1): We prove

that a finite distributive lattice L is determined by its lattice of k-ary Boolean functions (Theorem 7.1), but not by the lattice of all Boolean functions (Note 7.2).

Theorem 7.1. Let L, M be finite distributive lattices such that S_{k}(L) ≅ S_{k}(M).

Then L ≅ M.

Proof. Let P := J (L) and let Q := J (M). By Theorem 6.7 and Corollary 6.8, P ⋉ 2^{k} ≅ Q ⋉ 2^{k}, so that (P, <) × (2^{k}, ⩽) ≅ (Q, <) × (2^{k}, ⩽). By [7],Theorem 3, (P, <) ≅ (Q, <), so that P ≅ Q and hence L ≅ M. □

Note 7.2. Let L be a non-trivial finite distributive lattice. Let M be the family of finite lattices

{ S_{k}(L) | k ⩾ 1 }.

Then S(L) ≅ S(M) for any M ∈ M, but no two lattices in M are isomorphic.

Proof. The observation follows from Theorem 7.1 and the fact that, for any N ∈ D, S(N) is a limit of { S_{k}(N) | k ⩾ 1 } in the category D. □

References

1. B. A. Davey and H. A. Priestley, Introduction to Lattices and Order, Cambridge University Press, Cambridge, 1990.

2. G. Grätzer, On Boolean functions (notes on lattice theory. II), Revue de Mathématiques Pures et Appliquées 7 (1962), 693–697.

3. G. Grätzer, Boolean functions on distributive lattices, Acta Mathematica Academiae Scientiarum Hungaricae 15 (1964), 195–201.

4. George Grätzer, General Lattice Theory, Academic Press, New York, 1978.

5. Henk J. A. M. Heijmans, Morphological Image Operators, Academic Press, Boston, 1994.

6. Kalle Kaarli and Alden Pixley, Affine complete varieties, Algebra Universalis 24 (1987), 74–90.

7. L. Lovász, On the cancellation law among finite relational structures, Periodica Mathematica Hungarica 1 (1971), 145–156.

8. H. A. Priestley, Ordered topological spaces and the representation of distributive lattices, Proceedings of the London Mathematical Society 24 (1972), 507–530.

Department of Mathematics, Vanderbilt University, Nashville, Tennessee 37240, United States of America

Mathematical Sciences Research Institute, 1000 Centennial Drive, Berkeley, California 94720, United States of America

  E-mail address: farley@math.vanderbilt.edu