INTERPOLATION IN {0, 1}-LATTICES

MARTIN GOLDSTERN

Abstract. The following theorem is known:

Let L be a lattice, f : L^{n} → L monotone. Then there is a lattice L^{∗} containing L as a sublattice, and a lattice 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.

We show here that if L is a bounded lattice with a least element 0 and a greatest element 1, then we can choose L^{∗} as above in which 0 and 1 are still minimal and maximal, respectively. Iterating this construction long enough yields a bounded lattice in which every monotone function can be interpolated by a polynomial on any set of small enough cardinality.

0. Introduction/Motivation

In [1] the following was shown:

0.1. Theorem. (a) Let L be a lattice, n a natural number, f : L^{n} → L a monotone partial function. Then L can be extended to a lattice L′ such that for all x_{1}, …, x_{n} in L we have f(x_{1}, …, x_{n}) = p(x_{1}, …, x_{n}) for some lattice polynomial p with coefficients in L′. Moreover, p can be chosen to be of degree 1 in each variable.

(b) Let L be a lattice, κ a cardinal. Then L can be embedded into a lattice L̄ which

is “κ-order-polynomially complete”, i.e:

For every natural number n, for every monotone partial function f : L̄^{n} → L̄ with |dom(f)| ≤ κ there is a polynomial p with coefficients in L̄, such that p(a_{1}, …, a_{n}) = f(a_{1}, …, a_{n}) for all a ∈ dom(f). (Again p can be chosen to be of degree 1 in each variable.)

The author was supported by the FWF through an Ernst Schrödinger fellowship. A more recent version of this paper may be available in the World-Wide Web at

http://info.tuwien.ac.at/goldstern/.

2 MARTIN GOLDSTERN

This theorem was motivated by the question of (non)existence of order-polynomially complete lattices. (See [2] for a survey of some recent results in this area.) To show that no infinite o.p.c. lattices exist it would be enough to show that on any infinite lattice there is always a monotone function with a property that a polynomial cannot have. The paper [1] gave a (partial) negative answer to the question: “Is there a property of polynomial functions that not all monotone functions share?”

A distinguishing characteristic of the construction of an extension lattice in [1] was that the bigger lattice L′ always had new elements bounding all old elements. However, [3] showed that an o.p.c. lattice is necessarily bounded, so one could argue that only constructions in the variety (or category) of {0, 1}-lattices (i.e., where homomorphisms by definition have to preserve 0 and 1) are relevant. Since the construction of [1] does not give a {0, 1}-extension, the question appeared whether the quoted theorem is still true for {0, 1}-lattices.

The disadvantage of having to add new bounds in the proof of part (a) becomes even more apparent in part (b): Here we just iterate the construction of part (a) a transfinite number of times, using a “bookkeeping argument” to eventually catch our own tail. Since the construction in [1] adds new lower and upper bounds are added in each step (and since there is no “last” step), the resulting lattice will not be bounded.

We show here that we can improve the construction from [1] to yield a {0, 1}- extension for part (a), and to yield a {0, 1}-lattice (hence in particular: a bounded lattice) in part (b). We remark that it is impossible to prove the same theorem for {0, 1}-lattices if we only allow polynomials of degree 1, and we show that we can choose our interpolating polynomials to be of degree 2.

0.2. Notation. 1. A bounded lattice is an algebra (L, ∨, ∧) of type (2,2) which

(a) is a lattice and (b) happens to have a least and a greatest element.

2. A {0, 1}-lattice is an algebra (L, ∨, ∧, 0, 1) of type (2,2,0,0) such that (L, ∨, ∧) is a bounded lattice, and 0 and 1 are the least and the greatest element.

INTERPOLATION IN {0, 1}-LATTICES 3

3. When it is convenient we may also write a lattice (or a {0, 1}-lattice) as (L, ≤), where ≤ is the usual partial order on L.

4. If L is a {0, 1}-lattice (or a bounded lattice), S ⊆ L a sublattice, then we say that S is a {0, 1}-sublattice of L (or that L is a {0, 1}-extension of S) iff S contains the greatest and the least element of L.

5. Operations are evaluated from lef to right. E.g., x∨a∧b∨c means [(x∨a)∧b]∨c.

6. The “degree” of a polynomial p(x_{1}, …, x_{n}) in the variable x_{k} is the number of occurrences of the variable x_{k} in p. (The degree of a polynomial function f is the smallest degree of a polynomial that induces f.)

0.3. Observation. 1. If (L, ∨, ∧, 0, 1) is a {0, 1}-lattice with at least three elements, then there is a monotone function f : L → L whose range includes {0, 1}, f not equal to the identity function.

2. If f : L → L is a polynomial function of degree 1, and f is not the identity, then the range of f cannot include {0, 1}.

Proof. (1) is clear, and for (2) notice that there must be a polynomial p representing f which is of the form p(x) = q(x) ∨ a, a > 0, or p(x) = q(x) ∧ b, b < 1.

0.4. Theorem. Let (L, ∨, ∧, 0, 1) be a {0, 1}-lattice, n a natural number, f : L^{n} → L a partial monotone function. Then there is a {0, 1}-lattice (L′, ∨, ∧, 0, 1) such that L is a {0, 1}-sublattice of L′ and a polynomial p with coefficients in L′ (of degree 2 in each variable) such that p(x_{1}, …, x_{n}) = f(x_{1}, …, x_{n}) for all x_{1}, …, x_{n} ∈ L.

0.5. Remark. We may assume that L is complete, as every {0, 1}-lattice is a {0, 1}- sublattice of a complete {0, 1}-lattice.

Hence we may also assume that the monotone function f is total.

Moreover, as in [1] it is enough to prove the theorem for the case n = 1.

0.6. Corollary. For every {0, 1}-lattice L and every cardinal κ there is a {0, 1}- extension L̄ of L such that every monotone partial function from L̄^{n} to L̄ whose domain is at most of cardinality κ is the restriction of a polynomial.

Proof. Iterate over all possible monotone partial functions with small domain, as in [1].

1. Preliminaries

1.1. More Notation. If L is a {0, 1}-lattice, A and B are nonempty subsets of L, then we say that A, B are complementary iff for all a ∈ A\{0, 1}, for all b ∈ B\{0, 1} we have a ∨ b = 1, a ∧ b = 0.

Let L be a {0, 1}-lattice. We write [a, b] for the set {x ∈ L : a ≤ x ≤ b}. We say that S ⊆ L is a proper interval iff there are 0 < a < b < 1 in L such that S = [a, b].

The letter ι, possibly with subscripts, always denotes a (partial) lattice isomorphism. We usually use a superscript and a subscript to indicate domain and range of this isomorphism, respectively. If ι_{n}^{m} is an isomorphism from S_{m} to S_{n}, then ι_{m}^{n} will always denote its inverse.

For polynomials we use the letters p, q, … However, a polynomial that interpolates an isomorphism ι_{n}^{m} is sometimes written i_{n}^{m}.

We often do not distinguish between a polynomial and the induced polynomial function, but to emphasize a point we may distinguish between an argument x of a polynomial function and a formal variable (or “indeterminate”) x by using different fonts.

The set of unary polynomials with coefficients in L is written as L[x].

1.2. Definition and Fact. If S = [a, b] ⊆ L, we let π_{S}^{L} : [0, b] → S be the function that maps x to x ∨ a. Clearly π_{S}^{L}(x) ∈ S, π_{S}^{L}(x) = inf{s ∈ S : s ≥ x}, and π_{S}^{L} is idempotent, so we are justified in calling π_{S}^{L} the “projection” from L to S.

1.3. Abuse of Notation. If L is a {0, 1}-lattice, then we call a subset A ⊆ L “downward closed” iff (A ∪ {0}) \ {1} is downward closed in the traditional sense, or equivalently, if A \ {0, 1} is downward closed in L \ {0, 1}.

Similarly we will ignore 0 and 1 when we speak of an “upward closed” subset.

INTERPOLATION IN {0, 1}-LATTICES 5

2. A special case

Our first observation proves the theorem in a special case which is trivial but important:

2.1. Observation. Let L be a lattice, T_{1} = [a_{1}, b_{1}] and T_{5} = [a_{5}, b_{5}] two proper intervals. Assume that ι_{5}^{1} : T_{1} → T_{5} is an isomorphism, and that T_{1} and T_{5} are complementary.

Then there is a {0, 1}-extension L̄ of L such that the isomorphism ι_{5}^{1} is induced by a polynomial (of degree 1) over L̄. Moreover, T_{1} and T_{5} will still be proper intervals in L̄.

Proof. Let T_{2}, T_{3}, T_{4} be isomorphic copies of T_{1}, pairwise disjoint, and also disjoint from L. The following diagram indicates how to make L ∪ T_{2} ∪ T_{3} ∪ T_{4} a lattice such that ι_{5}^{1}(x) = x ∨ inf T_{2} ∧ sup T_{3} ∨ inf T_{4} ∧ sup T_{5}. (Recall that we evaluate operations from left to right.)

T_{2}  T_{4}
ι_{2}^{1}↗  ↖^{ι_{2}^{3}}  ^{ι_{4}^{3}}↗  ↖^{ι_{4}^{5}}
T_{1}  T_{3}  T_{5}

Formally, let ι_{j+1}^{j} : T_{j} → T_{j+1} be an isomorphism from T_{j} to T_{j+1} for j = 1, 2, 3, 4 such that ι_{5}^{1} = ι_{5}^{4} ∘ ι_{4}^{3} ∘ ι_{3}^{2} ∘ ι_{2}^{1}. Let ι_{j}^{j+1} = (ι_{j+1}^{j})^{−1}. Define ≤ on L̄ as follows: x ≤ y iff at least one of the following holds:

1. x = 0 or y = 1

2. x, y ∈ L, x ≤_{L} y

3. x, y ∈ T_{j}, x ≤_{T_{j}} y for some j

4. x ∈ T_{j}, y ∈ T_{j+1}, ι_{j}(x) ≤_{T_{j+1}} y for j = 1 or j = 3

5. x ∈ T_{j+1}, y ∈ T_{j}, ι_{j}^{j+1}(x) ≤_{T_{j}} y for j = 2 or j = 4

6. x ∈ L, y ∈ T_{2}, x ≤_{L} ι_{1}^{2}(y) [or equivalently, ι_{2}^{1}(π_{T_{1}}^{L}(x)) ≤_{T_{2}} y]

7. Similarly for x ∈ L, y ∈ T_{4}. Then it is easy to see that L̄ will be a lattice extending the lattice L and also extending each T_{j}, with lattice operations satisfying furthermore the following rules:

6 MARTIN GOLDSTERN

- If x ∈ T_{j}, y ∈ T_{j+1}, then x∨y is either ι_{j+1}^{j}(x)∨_{T_{j+1}} y or x∨_{T_{j}} ι_{j}^{j+1}(y), depending on whether j is odd or even.

- Similarly, if x ∈ T_{j}, y ∈ T_{j+1}, then x∧y is either ι_{j+1}^{j}(x)∧_{T_{j+1}} y or x∧_{T_{j}} ι_{j}^{j+1}(y), depending on whether j is even or odd.

- If x ∈ T_{j}, y ∈ T_{j+2}, then x ∨ y = ι_{j+1}^{j}(x) ∨_{T_{j+1}} ι_{j+1}^{j+2}(y) if j is odd, and x ∨ y = 1 if j is even.

- If x ∈ T_{j}, y ∈ T_{j+2}, then x ∧ y = ι_{j+1}^{j}(x) ∧_{T_{j+1}} ι_{j+1}^{j+2}(y) if j is even, and x ∧ y = 0 if j is odd.

- If x ∈ T_{j}, y ∈ T_{j+3}, then x ∨ y = 1, x ∧ y = 0.

- If x ∈ L, y ∈ T_{2}, then x ∧ y = x ∧ ι_{1}^{2}(y), and x ∨ y = ι_{2}^{1}(π_{T_{1}}^{L}(x)) ∨_{T_{1}} y if π_{T_{1}}^{L}(x) is defined, x ∨ y = 1 otherwise.

- Similarly for x ∈ L, y ∈ T_{4}.

- If x ∈ L, y ∈ T_{3}, then x ∧ y = 0. For x > 0 at most one of π_{T_{1}}^{L}(x), π_{T_{5}}^{L}(x) (see 1.2), since T_{1} and T_{5} are complementary. If neither exists, then x ∨ y = 1, otherwise x∨y = ι_{2}^{1}(π_{T_{1}}^{L}(x))∨_{T_{2}} ι_{2}^{3}(y) or x∨y = ι_{4}^{5}(π_{T_{5}}^{L}(x))∨_{T_{4}} ι_{4}^{3}(y), respectively.

It is now clear that (letting a_{j} = inf T_{j}, b_{j} = sup T_{j}) we have ι_{5}^{1}(x) = x ∨ a_{2} ∧ b_{3} ∨ a_{4} ∧ b_{5}.

3. Two known constructions

The following fact is easy:

3.1. Fact. Let (L_{1}, ≤_{1}) and (L_{2}, ≤_{2}) be two {0, 1}-lattices with L_{1} ∩ L_{2} = {0, 1}. Then the “horizontal sum” of L_{1} and L_{2}, i.e.,

L := (L_{1} ∪ L_{2}, ≤_{1} ∪ ≤_{2}),

is a {0, 1}-lattice and L_{1}, L_{2} are {0, 1}-sublattices of L which are complementary.

3.2. Lemma. 1. Let L be a complete lattice, f : L → L a monotone partial function. Then there is a bounded lattice L′ ⊇ L and a polynomial p ∈ L′[x] (of degree 1) such that p(a) = f(a) for all a ∈ L. Moreover, L′ can be chosen such that L is downward (or, dually: upward) closed in L′.

INTERPOLATION IN {0, 1}-LATTICES 7

2. Let S_{3}, S_{4} be complete lattices, disjoint, and let f : S_{3} → S_{4} be monotone. There there exists a {0, 1}-lattice L′ containing S_{3} and S_{4} as proper intervals, and a polynomial r ∈ L′[x] with coeffients in L′ such that f(x) = r(x) for all x ∈ S_{3}. r can be chosen to be of degree 1 (moreover: even of the form x ∨ a ∧ b for appropriate constants a and b).

Proof. Part (1): The existence of the extension L′ was shown in [1]. The construction in [1] yields a lattice L′ such that the original lattice is upward closed in L′.

To prove part (2), let L = S_{3} ∪ S_{4} ˙∪ {⊤, ⊥}, as in 3.1, with ⊤ = sup L, ⊥ = inf L, S_{3} and S_{4} complementary in L. L is easily seen to be a complete lattice, and S_{3} and S_{4} are downward closed in L. Now apply part (1) to get an appropriate extension L′.

(The “moreover” claim follows from the construction in [1]. As we will not need it, we leave this part of the proof to the reader.)

4. Extracting a closed set

4.1. Definition. Let L be a {0, 1}-lattice, S ⊆ L a downward closed sublattice.

(a) We let S^{∗} be an isomorphic copy of (S ∪ {0}) \ {1} (disjoint from L).

(b) We let ι = ι_{S^{∗}}^{S} be a bijection between S ∪ {0, 1} and S^{∗} ∪ {1}, with ι(1) = 1. ι induces on S^{∗} ∪ {1} a lattice structure (≤_{S^{∗}}, ∨_{S^{∗}}, ∧_{S^{∗}}).

(c) Since we may consider several disjoint copies of S at the same time, we may distinguish them by additional superscripts: S^{∗1}, S^{∗2}, etc.

(d) We let L + S^{∗} be the structure (L ∪ S^{∗}, ≤^{+}), where the binary relation ≤^{+} is defined as follows: a ≤^{+} b iff one of the following holds:

1. a = 0 or b = 1

2. a ≤_{L} b and {a, b} ∩ {0, 1} = ∅

3. a ≤_{S^{∗}} b and {a, b} ∩ {0, 1} = ∅

4. ι(a) ≤_{S^{∗}} b and {a, b} ∩ {0, 1} = ∅ (Note that these 4 cases are mutually exclusive.)

S S^{∗} Figure >

Figure > illustrates this definition. The ellipse represents L, the rectangle inside the ellipse is S \ {0, 1}. The rectangle outside the ellipse is S^{∗} \ {inf S^{∗}}. Dotted lines indicate the order relation.

4.2. Main Lemma. Let L be a {0, 1}-lattice, S ⊆ L a downward closed sublattice. Then:

(a) L + S^{∗}, as defined above, is a {0, 1}-lattice. We will write the operations as ∨^{+} and ∧^{+} or more explicitly as ∨^{L+S^{∗}} and ∧^{L+S^{∗}}.

(b) L is a {0, 1}-sublattice of L + S^{∗}.

(c) S is downward closed in L + S^{∗}.

(d) S^{∗} ∪ {1} is an upward closed sublattice of L + S^{∗}

(e) ≤_{S^{∗}}, ∨_{S^{∗}}, ∧_{S^{∗}} are the restrictions of ≤^{+}, ∨^{+} and ∧^{+} to S^{∗} ∪ {1}.

(f) For x ∈ S ∪ {0, 1}, ι(x) = x ∨^{+} inf(S^{∗}). ι is a lattice isomorphism between S ∪ {0, 1} and S^{∗} ∪ {1}.

(g) Whenever A ⊆ L \ S is upward closed in L, then A is upward closed in L + S^{∗}.

(h) If S \ {1} has a greatest element s, then for all x ∈ S^{∗}: ι^{−1}(x) = x ∧^{+} s.

Proof. The (easy) proof that ≤^{+} is indeed a partial order is left to the reader. It is also easy to see that 0 and 1 will be the the least and the greatest element of L+S^{∗}.

We will have proved most of the theorem once we have checked that the following table correctly computes inf_{≤^{+}}{a, b} and sup_{≤^{+}}{a, b}, depending on where a and

INTERPOLATION IN {0, 1}-LATTICES 9

b are. Here, ∨_{L} and ∧_{L} are the lattice operations of L, and ∨_{S^{∗}} and ∧_{S^{∗}} are the lattice operations of S′ (induced by the isomorphism ι). In this table we assume that {a, b} ∩ {0, 1} = ∅

inf_{≤^{+}}{a, b} sup_{≤^{+}}{a, b}
(A) a ∈ L, b ∈ L a ∧_{L} b a ∨_{L} b
(B) a ∈ S, b ∈ S^{∗} a ∧_{L} ι^{−1}(b) ι(a) ∨_{S^{∗}} b
(C) a ∈ L \ S, b ∈ S^{∗} a ∧_{L} ι^{−1}(b)  1
(D) a ∈ S^{∗}, b ∈ S^{∗} a ∧_{S^{∗}} b  a ∨_{S^{∗}} b

The proof is boring but straightforward. We first deal with greatest lower bounds, i.e., the inf column. Fix a, b both different from 0 and 1, and assume y ≤^{+} a, b. We have to show “y ≤^{+} a ∧_{L} b”, “y ≤^{+} a ∧_{L} ι^{−1}(b)”, or “y ≤^{+} a ∧_{S^{∗}} b”, respectively.

This is trivial if y = 0, so we may assume y ≠ 0 whenever that is convenient. We distinguish 4 cases:

(A): a, b ∈ L. So y ∈ L, y ≤_{L} a, b, y ≤_{L} a ∧_{L} b, y ≤^{+} a ∧_{L} b. (B,C): a ∈ L, b ∈ S^{∗}. Again y ∈ L and y ≤_{L} a. Also ι(y) ≤_{S^{∗}} b, so y ≤_{L} ι^{−1}(b),

y ≤_{L} a ∧_{L} ι^{−1}(b), y ≤^{+} a ∧_{L} ι^{−1}(b). (D1): a, b ∈ S^{∗}, y ∈ S^{∗}. So y ≤_{S^{∗}} a, b, y ≤_{S^{∗}} a ∧_{S^{∗}} b, y ≤^{+} a ∧_{S^{∗}} b. (D2): a, b ∈ S^{∗}, y ∈ L. So ι(y) ≤_{S^{∗}} a, b, ι(y) ≤_{S^{∗}} a ∧_{S^{∗}} b, y ≤^{+} a ∧_{S^{∗}} b. We now turn to the “sup” column. Again fix a, b both different from 1, and

assume z ≥^{+} a, b. If z = 1 then we are again immediately done, so assume z ≠ 1. We distinguish 5 cases:

(A1): a, b ∈ L, z ∈ L. So z ≥_{L} a, b, z ≥_{L} a ∨_{L} b, z ≥^{+} a ∨_{L} b. (A2): a, b ∈ L, z ∈ S^{∗}. So z ≥_{S}^{∗} ι(a), ι(b), z ≥_{S^{∗}} ι(a) ∨_{S^{∗}} ι(b) = ι(a ∨_{L} b),

z ≥^{+} a ∨_{L} b. (B): a ∈ S, b ∈ S^{∗}. So z ∈ S^{∗}, z ≥_{S^{∗}} b, z ≥_{S^{∗}} ι(a), z ≥^{+} ι(a) ∨_{S^{∗}} b. (C): a ∈ L \ S, b ∈ S^{∗}. z ≥^{+} a implies z ∈ L since S is downward closed in L,

but z ≥^{+} b implies z ∈ S^{∗} ∪ {1}, so z = 1. (D): a, b ∈ S^{∗}. So z ∈ S^{∗}. z ≥_{S^{∗}} a, b, z ≥_{S^{∗}} a ∨_{S^{∗}} b, z ≥^{+} a ∨_{S^{∗}} b.

10 MARTIN GOLDSTERN

Thus we have shown that the table above is correct. This proves in particular part (a) of our theorem.

Part (b) follows from line (A) in our table.

Part (c) follows immediately from the definition of ≤^{+}.

Part (d): The definition of ≤^{+} implies that S^{∗} ∪ {1} is upward closed, and line (D) of our table shows that S^{∗} ∪ {1} is a sublattice.

Part (e) follows from the definition and from line (D).

Part (f): ι(x) = x ∨^{+} inf(S^{∗}) follows from line (B), and ι is a lattice isomorphism by the definition of ≤_{S^{∗}}.

Part (g) follows from the definition of ≤^{+}.

Part (h): If s = sup(S \ {1}), then for all x ∈ S^{∗} we have ι^{−1}(x) ∈ S \ {1}, so ι^{−1}(x) = s ∧_{L} ι^{−1}(x) = s ∧^{+} ι^{−1}(x).

This concludes the proof of 4.2.

4.3. Conclusion (The Y-shaped extension). Let L be a {0, 1}-lattice, S a downward closed sublattice. Then there exists a {0, 1}-extension L^{Y} of L containing two isomorphic copies S^{∗1}, S^{∗2} of S ∪ {0} \ {1} such that for ℓ = 1, 2:

1. S^{∗ℓ} is upward closed, and has a least element a_{ℓ} = inf S^{∗ℓ}.

2. The map ι_{ℓ} : S∪{0, 1} → S^{∗ℓ}∪{1}, defined by ι_{ℓ}(x) = x∨a_{ℓ} is an isomorphism.

3. x = ι_{1}(x) ∧ ι_{2}(x) for all x ∈ S. (See figure Y.)

Proof. We use the construction from the main lemma twice: First we extend L to a lattice L′ = L + S^{∗1}, then we extend this intermediate lattice again to L^{Y} := (L+S^{∗1})+S^{∗2}. This is possible, as S is still a downward closed sublattice of L+S^{∗1} by 4.2(c).

a_{ℓ} = inf S^{∗ℓ} exists by the main lemma. All that remains to prove is that x = ι_{1}(x) ∧ ι_{2}(x) for all x ∈ S:

So let x ∈ S and let y := ι_{1}(x) ∧ ι_{2}(x). Clearly y ≥ x, so in particular: If x = 1, then y = 1.

S  S^{∗1} S^{∗2}  a_{1} a_{2} Figure Y

Now assume x < 1. Since ι_{1}(x) ∈ S^{∗1} ⊆ L′ \ S and ι_{2}(x) ∈ S^{∗2}, we get ι_{1}(x) ∧ ι_{2}(x) = ι_{1}(x) ∧ ι_{2}^{−1}(ι_{2}(x)) by rule 4.2(C), so y = (x ∨ a_{1}) ∧ x = x.

4.4. Conclusion (The M-shaped extension). Let L be a {0, 1}-lattice, S_{0} a downward closed {0, 1}-sublattice. Then there exist

- a {0, 1}-extension L^{M} of L

- two sublattices S_{1} ⊆ L^{M}, S_{2} ⊆ L^{M} which are both downward closed proper intervals, and are isomorphic to S_{0}—say, via isomorphisms ι_{1}^{0} : S_{0} → S_{1}, ι_{2}^{0} : S_{0} → S_{2}

- polynomials i_{1}^{0}(x) and i_{2}^{0}(x) of degree 1 whose restrictions to the set S_{0} are the functions ι_{1}^{0}, ι_{2}^{0}, respectively

- polynomials p_{1}(x), p_{2}(x) of degree 1 in L^{M}[x] satisfying

(∗) a = p_{1}(ι_{1}^{0}(a)) ∧ p_{2}(ι_{2}^{0}(a))

for all a ∈ S_{0}. Again S_{0} will still be downward closed in L^{M}.

Note that this includes the case S_{0} = L.

Proof. We will use the extension L^{Y} = L ∪ S^{∗1} ∪ S^{∗2} from 4.3, and apply the dual of the main lemma twice.

S S^{∗2} a_{2}  S^{∗1} a_{1}  S_{1}b_{1} c_{1} Figure N

First we note that S^{∗1} is upward closed in L^{Y}, so we can define an extension

L′ := L^{Y} + (S^{∗1})_{∗}.

Let S_{1} = (S^{∗1})_{∗}. (See figure N.)

Let a_{1} = inf S^{∗1} (so a_{1} > 0). So also S_{1} will have a least element b_{1} := inf S_{1}. By the (dualized version) of the main lemma 4.2, S_{1} ∪ {0} is isomorphic to S^{∗1} ∪ {0, 1}, so S_{1} will have a greatest element c_{1} = sup S_{1}. Clearly S_{1} will be downward closed. The map x ↦ x∧c_{1} is an isomorphism from S^{∗1} ∪{1} to S_{1} with inverse y ↦ y ∨a_{1}, by 4.2(f) and 4.2(h).

Now S^{∗2} is still upward closed in L′, so we can again apply the dual of the main lemma and let

L^{M} = L′ + (S^{∗2})_{∗}.

Let S_{2} = (S^{∗2})_{∗}, c_{2} := inf S_{2}. Again the maps x ↦ x ∧ c_{2} and its inverse y ↦ y ∨ a_{2} are isomorphisms between S^{∗2} ∪ {1} and S_{2}. (See figure M.)

By 4.3(3), we have for all x ∈ S: x = (x ∨ a_{1}) ∧ (x ∨ a_{2}). Let i_{ℓ}^{0}(x) = x ∨ a_{ℓ} ∧ c_{ℓ} and p_{ℓ}(x) = x ∨ a_{ℓ} for ℓ = 1, 2. Then i_{ℓ}^{0}(x) = ι_{ℓ}^{0}(x)

and x = p_{1}(ι_{1}^{0}(x)) ∧ p_{2}(ι_{2}^{0}(x)) for all x ∈ L, as required.

S  S^{∗1} S^{∗2}  a_{1} a_{2} S_{2} b^{2}c_{2}  S_{1} b^{1} c_{1} Figure M

5. Proof of the theorem:

Start with a complete lattice L and a monotone function f : L → L. Let S_{0} = L and construct L^{M} as in 4.4: L^{M} = L ∪ S^{∗1} ∪ S^{∗2} ∪ S_{1} ∪ S_{2}. Let ι_{1}^{0}, ι_{2}^{0}, i_{1}^{0}, i_{2}^{0} be as in 4.4.

Let S_{3}, S_{4} be isomorphic copies of the lattice L with isomorphism ι_{3}^{0} : S_{0} → S_{3}, ι_{4}^{0} : S_{0} → S_{4}.

The function f_{4}^{3} : S_{3} → S_{4}, defined by f_{4}^{3} = ι_{4}^{0} ∘ f ∘ ι_{0}^{3} is a monotone function from S_{3} to S_{4}, so we can find a {0, 1}-lattice L̄ containing S_{3} and S_{4} as proper intervals ≤ L̄ such that for some a, b ∈ L̄, for all y ∈ S_{3}, f_{4}^{3}(y) = r(y) for some polynomial r(x) ∈ L̄[x]. Hence:

∀x ∈ L : ι_{4}^{0}(f(x)) = ι_{4}^{0}(f(ι_{0}^{3}( ι_{3}^{0}(x) ))) = r(ι_{3}^{0}(x))

We may assume that L̄ ∩ L^{M} = {0, 1}. So we can find a lattice L′ = L^{M} ∪ L̄ as in 3.1. Since S_{1}, S_{2}, S_{3}, S_{4} are all proper intervals ≤ L′, and since S_{1} and S_{2} are both complementary from both S_{3} and S_{4}, we can apply 2.1 to extend the {0, 1}-lattice L′ to a {0, 1}-lattice L′′ in which the isomorphisms

ι_{3}^{1} : S_{1} → S_{3}

ι_{1}^{4} : S_{4} → S_{1}
ι_{2}^{4} : S_{4} → S_{2}

are all realized by polynomials (of degree 1), which we call i_{3}^{1}, i_{1}^{4}, i_{2}^{4}, respectively.

S  S^{∗1} S^{∗2} S_{2}  S_{1}  S_{3}  S_{4} L^{M}  L̄ i_{3}^{1} i_{1}^{4} i_{2}^{4}  f_{4}^{3} p_{2}  p_{1} Figure {·· \atop ⌣}

Now for all x ∈ L we have by 4.4(∗):

f(x) = p_{1}(ι_{1}^{0}(f(x))) ∧ p_{2}(ι_{2}^{0}(f(x)))

so it is enough to show that the function x ↦ ι_{ℓ}^{0}(f(x)) can be interpolated by a polynomial on S_{0} for ℓ = 1, 2. But by construction we have for ℓ = 1, 2

ι_{ℓ}^{0}(f(x)) = ι_{ℓ}^{4}( ι_{4}^{0}(f(x)) ) = ι_{ℓ}^{4}( r(ι_{3}^{0}(x)) ) = i_{ℓ}^{4} ∘ r ∘ i_{3}^{1} ∘ i_{1}^{0}(x)

hence f is realized by a polynomial of degree 2. (See figure {·· \atop ⌣}.)

References

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

[2] Hans Kaiser. Interpolation and order polynomially complete lattices. In G. Pilz, editor, Contributions to General Algebra 9, Wien, 1995. Hölder-Pichler-Tempsky.

[3] Hans Kaiser and Norbert Sauer. On order polynomially complete lattices. Algebra Universalis, 30:171–176, 1993.

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

   E-mail address: Martin.Goldstern@tuwien.ac.at