INTERPOLATION IN ORTHOLATTICES

MARTIN GOLDSTERN

Abstract. If (L, ∨, ∧, 0, 1,^{⊥}) is a complete ortholattice, f : L^{n} → L any partial function, then there is a complete ortholattice L^{∗} containing L as a subortholattice, and an ortholattice polynomial p with coefficients in L^{∗} such that p(a_{1}, …, a_{n}) = f(a_{1}, …, a_{n}) for all a_{1}, …, a_{n} ∈ L.

Iterating this construction long enough yields a complete ortholattice in which every function can be interpolated by a polynomial on any set of small enough cardinality.

0. Introduction

In [2] and [3] we showed the following: Let L be any [bounded] lattice, then there is a lattice L̄ extending L [with the same least and greatest element] such that every monotone function from L^{n} to L is represented by a polynomial with coefficients in L̄.

It is clear that as long as we restrict ourselves to lattice polynomials we can only interpolate monotone functions. Here we consider the problem of interpolation on ortholattices, i.e., bounded lattices equipped with an “orthocomplement”. Since the orthocomplement reverses order, there is no obvious monotonicity property that all orthopolynomials in an ortholattice will share.

The main theorem of this paper shows that indeed there are no restrictions on the behavior of orthopolynomials; more precisely: If L is an ortholattice, then any function f : L^{n} → L can be represented by a polynomial with coefficients in some suitable orthoextension L̄.

By iterating the construction from the theorem we get, for every cardinal number κ, a lattice L̂ with the property that every function from L̂^{n} to L̂ can be interpolated on any set of size ≤ κ.

We also show that we can construct L̂ such that L̂ will be complete (as a partial order). Moreover, assuming that the original ortholattice L is complete, we construct L̂ such that L is a “convex” sublattice of L̂.

1. Basic definitions

1.1. Notation. Lattices are denoted by L, L′, L_{1}, etc. When we consider several lattices, we use the self-explanatory notation ∧_{L_{1}} or ∧_{1}, ≤_{2}, etc. for the operations/relation in L_{1}, L_{2}, etc. We agree that the symbol ∧ binds more tightly than ∨, i.e., a ∨ b ∧ c = a ∨ (b ∧ c).

For any lattice L we let L^{dual} be the dual lattice (with the same underlying set): x ≤^{L^{dual}} y iff x ≥^{L} y.

An ortholattice is a bounded lattice (L, ∨, ∧, 0, 1) with an additional unary operation x ↦ x^{⊥} which satisfies x ≤ y ⇒ x^{⊥} ≥ y^{⊥}, (x^{⊥})^{⊥} = x, x ∨ x^{⊥} = 1, x ∧ x^{⊥} = 0 for all x, y (and hence also the de Morgan laws (x ∨ y)^{⊥} = x^{⊥} ∧ y^{⊥}, etc.).

1.2. Abuse of Notation. If (L, ∨, ∧, 0, 1) is a bounded lattice, A ⊆ L, then we say that A is “convex” in L iff

whenever a, a′ ∈ A, x ∈ L, 0 < a ≤ x ≤ a′ < 1, then also x ∈ A i.e., if A \ {0, 1} is convex in L in the usual sense.

If L_{0} ⊆ L_{1}, we say that L_{0} is “downward closed” in L_{1} iff: For all z ∈ L_{0} \ {1}, for all x ∈ L_{1}, if x ≤ z then x ∈ L_{1}, i.e., if L_{0} \ {1} is downward closed in L_{1} in the traditional sense.

1.3. Definition. Let L_{0}, L_{1} be bounded lattices.

Date: August 14, 2000.

This research was supported by the Austrian Science Foundation (FWF), grant P13325-MAT.

This paper is available from www.arXiv.org, and also from my home page.

1. L_{0} ≤ L_{1} means that L_{0} is a {0, 1}-sublattice of L_{1} (i.e., L_{0} is a sublattice of L_{1} with the same maximal and minimal element)

2. L_{0} ⊴ L_{1} means that (a) L_{0} ≤ L_{1}

(b) For every x ∈ L_{1} the set {z ∈ L_{0} : z ≤_{L_{1}} x} has greatest element (the “projection” of x to L_{0}, written π_{L_{0}}^{L_{1}}(x) or π_{0}^{1}(x))

(c) L_{0} is downward closed in L_{1}

3. L_{0} ⊴^{dual} L_{1} is the dual notion, i.e., L_{0}^{dual} ⊴ L_{1}^{dual}.

2. Basic facts

In this section we collect a few easy facts for later reference. We also quote a theorem on interpolation of monotone functions in lattices.

2.1. Fact. Assume L_{0} ⊴ L_{1}, L_{0} ⊴^{dual} L_{2}, L_{1} ∩ L_{2} = L_{0}. Let L = L_{1} ∪ L_{2}, and let ≤_{L} be the transitive closure of (≤_{1}) ∪ (≤_{2}). Then

• x ≤_{L} y iff: x ≤_{1} y or x ≤_{2} y or there exists a z ∈ L_{0} with x ≤_{2} z ≤_{1} y.

• (L, ≤_{L}) is a lattice with

x ∧_{L} y = \{ \begin{matrix}x ∧_{1} y & if x, y ∈ L_{1} \\ x ∧_{2} y & if x, y ∈ L_{2} \\ π_{0}^{1}(x) ∧_{2} y & if x ∈ L_{1}, y ∈ L_{2} \end{matrix}

and similarly for ∨_{L}.

2.2. Fact. If L_{1} ⊴ L_{2} ⊴ L_{3}, then L_{1} ⊴ L_{3}.

2.3. Fact. L_{1} and L_{2} are complete lattices, L_{1} ≤ L_{2}, and A ⊆ L_{1}, then sup_{L_{1}} A ≥ sup_{L_{2}} A. However, if L_{1} is convex in L_{2} and sup_{L_{1}} A < 1, then sup_{L_{1}} A = sup_{L_{2}} A.

2.4. Fact. Let (I, ≤) be a linearly ordered set, and assume that (L_{i} : i ∈ I) is a family of complete lattices such that:

• for all i < j, then L_{i} is a {0, 1}-sublattice of L_{j}

• for all i < j: L_{i} is convex in L_{j}. Then L := ⋃_{i} L_{i} is a complete lattice, and L_{i} is a convex {0, 1}-sublattice of L for all i ∈ I.

Proof. It is clear that L is a lattice and that L_{i} is convex in L.

We now check that L is complete. Let A ⊆ L. We will show that sup_{L} A exists. Wlog we may assume that A ≠ ∅, 1 ∉ A, 0 ∉ A. Let a_{0} ∈ A.

We may also assume that 1 is not the least upper bound of A, so let c < 1 be some upper bound.

Fix i_{0} such that a_{0}, c ∈ L_{i_{0}}.

Let A′ := {a_{0} ∨x : x ∈ A}. Since a_{0} ∈ A, it is clear that A and A′ have the same upper bounds. Now L_{i_{0}} is convex, and a_{0} ≤ a_{0} ∨ x ≤ c for all x ∈ A, hence A′ ⊆ L_{i_{0}}.

Since L_{i_{0}} is complete, A′ has a supremum c^{∗} in L_{i_{0}}, and c^{∗} ≤ c. If d is any upper bound (in L) for A′, then also d ∧ c^{∗} is an upper bound, and d ∧ c^{∗} ∈ L_{i_{0}} by convexity, so d ∧ c^{∗} = c^{∗}. Hence c^{∗} is the supremum of A′ not only in L_{i_{0}} but also in L.

2.5. Fact. Let L = L_{1} ∪ L_{2}, where L_{1} ≤ L, L_{2} ≤ L. If L_{1} and L_{2} are both complete lattices, then also L is a complete lattice.

2.6. Theorem. Let L be a complete lattice, f : L → L a partial monotone function.

Then there is a complete lattice L̄ and a polynomial p(x) ∈ L̄[x] with p(a) = f(a) for all a ∈ dom(f). Moreover, we can choose L̄ such that

• L ⊴ L̄.

• L̄ is complete.

Proof. See [3] and [2]. (The “moreover” part is not stated there, but following the proof it is easy to see that the lattice L̄ constructed in [3] satisfies L ⊴ L̄ and will be complete.)

L_{2} = dual(L_{1}, L_{0}) L = ortho(L_{1}, L_{0}) = L_{1} ∪ L_{2} L_{0} = L_{1} ∩ L_{2} L_{1}

3. From lattices to ortholattices

We describe a construction that allows us to extend a lattice L to an ortholattice, preserving the ortholattice structure of a given sublattice of L.

3.1. Construction. Let (L_{0}, ∨, ∧, 0, 1,^{⊥}) be an ortholattice, (L_{1}, ∨, ∧, 0, 1) a bounded lattice with L_{0} ⊴ L_{1}.

We define two partial orders L_{2} = dual(L_{1}, L_{0}) ⊇ L_{0} and L = ortho(L_{1}, L_{0}) = L_{1} ∪ L_{2} as follows:

Pick a set L_{2} and a map ι satisfying the following:

• ι : L_{1} → L_{2} is a bijection.

• L_{1} ∩ L_{2} = L_{0}.

• ι(z) = z^{⊥_{0}} for all z ∈ L_{0}. (I.e., L_{2} \ L_{0} is just a disjoint copy of L_{1} \ L_{0}.) We make L_{2} into a lattice by requiring ι(x) ≤_{2} ι(y) iff y ≤_{1} x, so that ι : L_{1} → L_{2} is a dual isomorphism.

Note that ≤_{0} coincides with the restriction of ≤_{2} to L_{0}, so L_{0} ≤ L_{2}. From L_{0} ⊴ L_{1} we conclude L_{0} ⊴^{dual} L_{2}.

We let L = ortho(L_{1}, L_{0}) be the (set-theoretic) union of L_{1} ∪ L_{2}. By fact 2.1 we see that we can make L into a lattice containing L_{1} and L_{2} as sublattices.

3.2. Lemma. If L_{0} ⊴ L_{1}, (L_{0}, ∨, ∧, 0, 1,^{⊥}) is an ortholattice, then there is an ortholattice L such that L_{0} ≤ L_{1} ≤ L, and L_{0} is a subortholattice of L.

Moreover, if L_{1} is complete, then also L will be complete.

Proof. We let L_{2}, ι, and L = ortho(L_{1}, L_{0}) as above.

Let x^{⊥_{L}} = ι(x) for x ∈ L_{1} and = ι^{−1}(x) for x ∈ L_{2}.

It remains to show that the map x ↦ x^{⊥_{L}} is an orthocomplement for L. Clearly this map is well defined and an involution, and it agrees with the map x ↦ x^{⊥_{0}} on L_{0}. Also, we have z ∨_{L} z^{⊥_{L}} = z ∨_{0} z^{⊥_{0}} = 1 for all z ∈ L_{0}.

Now let x ∉ L_{0}, wlog x ∈ L_{1}. We will only check x ∨_{L} x^{⊥_{L}} = 1, leaving the dual to the reader. So let y ≥_{L} x, y ≥_{L} x^{⊥_{L}} = ι(x). Then y must be in L_{1}, and there is a z ∈ L_{0} such that ι(x) ≤_{2} z ≤_{1} y. Now ι(x) ≤_{2} z = ι(z^{⊥_{0}}) implies z^{⊥_{0}} ≤_{1} x, hence y ≥_{1} z ∨ z^{⊥_{0}} = 1.

3.3. Fact. The operation ortho(·, L_{0}) commutes with direct limits. In particular, if (I, ≤) is a linear order, (L_{i} : i ∈ I) an increasing family of lattices, L ⊴ L_{i} for all i, then

ortho(⋃_{i∈I} L_{i}, L_{0}) = ⋃_{i∈I} ortho(L_{i}, L_{0})

4. Theorems

We prove the two main theorems mentioned in the introduction. We conclude with an open question concerning the difference of unary and n-ary functions.

4.1. Theorem. If L_{0} is an ortholattice, f : L_{0} → L_{0}, then there is an ortholattice L^{∗} extending L_{0} such that f is the restriction of a polynomial function over L^{∗}.

Moreover, if L_{0} is complete then we can have L^{∗} = ortho(L_{1}, L_{0}) for some complete L_{1}, L_{0} ⊴ L_{1}.

Proof. Since every ortholattice can be embedded into a complete ortholattice (the MacNeille completion; see, e.g., [1, 4.1], [5]) we may assume that L_{0} is complete. Let f : L_{0} → L_{0}.

Let L′_{0} be horizontal sum of L_{0} and L_{0} × L_{0}, i.e., assume that L_{0} and L_{0} × L_{0} have the same least and greatest elements (but are otherwise disjoint), and make L′_{0} = L_{0} ∪ (L_{0} × L_{0}) into a lattice by taking

≤_{L′_{0}}= (≤_{L_{0}}) ∪ (≤_{L_{0}×L_{0}}).

Note that L′_{0} is a complete {0, 1}-lattice and L_{0} ⊴ L′_{0}.

Now consider the partial functions f̄, g_{1} and g_{2}, defined by

• f̄(⟨x, x^{⊥}⟩) = f(x) for all x ∈ L_{0}.

• g_{1}(x) = ⟨x, 0⟩, g_{2}(x) = ⟨0, x⟩, for all x ∈ L_{0}.

The following easy observation is the crucial step in this proof:

The elements of the set {⟨x, x′⟩ : x ∈ L_{0}} are pairwise incomparable, so the function f̄ is trivially monotone.

By theorem 2.6 we can find a lattice L_{1}, L′_{0} ⊴ L_{1} in which the functions f̄, g_{1} and g_{2} are restrictions of polynomials p, q_{1} and q_{2}, respectively. Now let L = ortho(L_{1}, L_{0}), so L is an orthoextension of L_{0}.

Now h(x) = p(q_{1}(x) ∨ q_{2}(x^{⊥})) is an orthopolynomial with coefficients in L, and clearly h(x) = p(⟨x, 0⟩ ∨ ⟨0, x^{⊥}⟩) = p(⟨x, x^{⊥}⟩) = f̄(⟨x, x^{⊥}⟩) = f(x) for all x ∈ L_{0}.

4.2. Remark. For every orthopolynomial p(x) there is a lattice polynomial p′(x, y) such that (by de Morgan’s laws) p(x) is equivalent to p′(x, x^{⊥}).

4.3. Definition. Let ℱ a family of lattices. We say that ℱ is square closed if:

For every S ∈ ℱ there is some S′ ∈ ℱ which is isomorphic to S × S. We say that L is κ-square closed if the family of sublattices of size ≤ κ is square closed.

4.4. Fact. If ℱ is square closed and closed under the formation of sublattices, then: For every S ∈ ℱ and every n > 1 there is some S′ ∈ ℱ which is isomorphic to S^{n}.

4.5. Theorem. Let L be a complete ortholattice, and let κ be any cardinal. Then:

1. There is a complete ortholattice L̄ extending L such that every function f : L → L is represented by an orthopolynomial of L̄. Moreover, L̄ can be chosen to be of the form ortho(L_{1}, L) with L ⊴ L_{1}. In particular, L will be convex in L̄. Moreover, L̄ can be chosen to be κ-square closed.

2. There is a complete ortholattice L̂ extending L such that:

For every natural number n, for every function f : L̂^{n} → L̂ and for every set A ⊆ L̂^{n} of cardinality ≤ κ there is an orthopolynomial p(x_{1}, …, x_{n}) with coefficients in L̂ that interpolates f on every point in A.

Proof. Choose a cardinal λ of cofinality > κ such that there is a transfinite enumeration (not necessarily 1-1) {f_{i} : 0 ≤ i < λ} of all functions f : L → L. Define an increasing transfinite sequence (L_{i} : i ≤ λ) of {0, 1}-lattices satisfying

1. L_{0} = L.

2. If i < j ≤ λ, then L_{i} ⊴ L_{j}

3. For every i < λ there is a lattice polynomial p_{i} with coefficients in L_{i+1} such that for all z ∈ L: f_{i}(z) = p_{i}(z, z^{⊥_{L}}).

4. For every i < λ, L_{i+1} contains an isomorphic copy of L_{i}^{2}.

5. If i is a limit stage, then L_{i} is the direct limit of (L_{j} : j < i), (i.e., L_{i} = ⋃_{j<i} L_{j}).

Finally, let L̄ = ortho(L_{λ}, L). Note that L̄ will contain an isomorphic copy of ortho(L_{i}, L) for every i. This finishes the proof of the first statement.

To prove the second claim, apply the conclusion from the first claim κ^{+} many times to get the conclusion for all unary functions, and then use fact 4.6 to take care of all n-ary functions.

4.6. Fact. Fix a cardinal number κ. We call a set A “small” if the cardinality of A is < κ. Assume that L κ-square closed, and that (a) or (b) holds:

(a) L is a lattice, and for every small A ⊆ L and for every monotone f : A → L there is a lattice polynomial p ∈ L[x] such that f(a) = p(a) for all a ∈ A

(b) L is an ortholattice, and for every small A ⊆ L and for every f : A → L there is an orthopolynomial p ∈ L[x] such that f(a) = p(a) for all a ∈ A

Then also (a’) or (b’), respectively, holds: (a’) For every n, for every small A ⊆ L^{n}, for every monotone g : A → L there is a lattice

polynomial p ∈ L[x_{1}, …, x_{n}] such that

g(a_{1}, … a_{n}) = p(a_{1}, …, a_{n}) for all (a_{1}, …, a_{n}) ∈ A.

(b’) Like (a’), but again replace “every monotone” by “every”, and “lattice polynomial” by “orthopolynomial”.

Proof. Let g : L^{n} → L, A ⊆ L small. Let S be the sub(ortho)lattice generated by A. Since L is κ-square closed, we can find a sublattice S′ ≤ L and an isomorphism ι : S^{n} → S′. For ℓ = 1, …, n let ι_{ℓ} : S → S′ be defined by

ι_{ℓ}(s) = ι(0, …, 0, s, 0, …, 0) [here, s appears in the ℓ-th coordinate]

Note that

(∗) ι(s_{1}, …, s_{n}) = ι_{1}(s_{1}) ∨ ⋯ ∨ ι_{n}(s_{1})

Define a partial function f : L → L as follows:

(∗∗) f(ι(s_{1}, …, s_{n})) = g(s_{1}, …, s_{n})

and f(t) = undefined if t ∉ S′. Note that f is monotone if g is monotone.

Now note that g, ι_{1}, …, ι_{n} are unary functions from L to L, so they are all represented by polynomials, and so by (∗) and (∗∗) also g is represented by a polynomial.

Note that the construction we used in theorem 4.1 will automatically guarantee that the resulting structure will be κ-square closed (see definition 4.3), so by fact 4.6 there will be no difference between unary and n-ary interpolation. This motivates the following questions:

4.7. Question. 1. Are there infinite ortholattices L where every function f : L → L can be interpolated by an orthopolynomial on every (say) countable set, but not every function f : L^{2} → L?

2. Are there infinite lattices L where every monotone function f : L → L can be interpolated by a lattice polynomial on every (say) countable set, but not every monotone function f : L^{2} → L?

References

[1] Günter Bruns. Free ortholattices. Can. J. Math., 28:977–985, 1976.

[2] Martin Goldstern. Interpolation of Monotone Functions in Lattices. Algebra Universalis, 36:108–121, 1996.

[3] Martin Goldstern. Interpolation of monotone functions in {0, 1}-lattices. In Contributions to General Algebra 10. Heyn Verlag, 1998.

[4] George Grätzer. General lattice theory. 2nd ed. Birkhaeuser, Basel, 1998.

[5] Gudrun Kalmbach. Orthomodular lattices, volume 18 of London Mathematical Society Monographs. Academic Press Inc., London etc., 1983.

Technische Universität Wien, Wiedner Hauptstraße 8–10/118.2, A-1040 Wien

   E-mail address: Martin.Goldstern@tuwien.ac.at
   URL: http://info.tuwien.ac.at/goldstern/