CONTRIBUTIONS TO GENERAL ALGEBRA 12

Proceedings of the Vienna Conference, June 3–6, 1999

Verlag Johannes Heyn, Klagenfurt 2000

LATTICES, INTERPOLATION, AND SET THEORY

MARTIN GOLDSTERN

Abstract. We review a few results concerning interpolation of monotone functions on infinite lattices, emphasizing the role of set-theoretic considerations. We also discuss a few open problems.

1. Introduction

In this article I will present a few ideas concerning the relationship between lattice polynomials and monotone functions on lattices. It turns out that (for infinite lattices) there are purely algebraic questions which (apparently) cannot be solved with purely algebraic methods; ideas from logic — in particular, from set theory — have to be used. Most prominent among these logical concepts is the notion of distinct infinite cardinalities, but also the more subtle notion of “cofinality” plays a role.

Most of the results here are not new; specifically, sections 2 and 4 just highlight ideas from papers that are already published. The reason for including those known results here is that they serve well to show the interconnections between algebraic and set theoretic ideas. The observations in sections 5, 6, and 7 are based on these older results, but are themselves new.

I will often not give complete proofs but treat only a characteristic case, in the hope that the information presented here is enough for the reader to complete the proof. For example, I will sometimes prove (or even state) a theorem which is true for n-ary functions only for unary functions. The general case is often just an easy generalization (but sometimes needs an additional idea). In any case, complete proofs are available elsewhere in the literature.

To avoid some case distinctions, we will only consider bounded lattices; in addition to the operations ∨ and ∧, all lattices that we consider in this paper come with constants 0 and 1. So “lattice” will mean “bounded lattice”, all homomorphisms have to respect 0 and 1, all sublattices contain 0 and 1, etc.

This paper is available on my homepage, and also from arXiv.org.

I am grateful to the Austrian Science Foundation (FWF) for supporting my research through grant P13325-MAT.

2. Order-polynomial completeness

The problem that got me interested in the subject was the following: It is clear that every lattice polynomial^{1} represents a monotone function. For which lattices is the converse true?

Let us call a lattice L k-o.p.c. (k-order polynomially complete) if every monotone function f : L^{k} → L is represented by a polynomial, and call L o.p.c. if L is k-o.p.c. for every k.

The finite o.p.c. lattices were characterized by Wille (see section 3). In this section we will show the main ideas of the proof of the following theorem:

1. Theorem. There are no infinite o.p.c. lattices.

Although the problem itself is now solved, I feel that our understanding is not at all complete. As evidence for this lack of understanding, see problems 8 and 9.

Cardinalities. If there are “more” monotone functions than polynomials, then clearly not all monotone functions are polynomials. In the finite case this does not help much, since there are only finitely many monotone functions for every fixed arity, while there are always infinitely many 3-ary polynomials. [Of

course, for lattices with extra properties, such as distributive lattices, we can get a normal form for polynomials, which means that the set of polynomials looks rather “small” to us.]

In infinite lattices the situation is reversed: The set P of polynomials on a lattice L has the same cardinality^{2} as L itself, whereas the set L^{L} of all functions from L into L has always strictly larger cardinality.

1Recall that the set L[x_{1}, …, x_{n}] of n-ary lattice polynomials [“with coefficients from L”] is the free product of L and the free lattice with n generators, or in other words: take the set of well-formed expression using the indeterminates x_{1}, …, x_{n}, elements of the lattice L and the operation symbols ∨ and ∧, and divide by the obvious equivalence relation: “equal in all extensions of L”. The n-ary function induced by a lattice polynomial is called “polynomial function” (or “algebraic function” by some authors).

2Recall the following elementary facts about cardinals:

• We write A ≈ B or |A| = |B| iff there is a bijection between A and B. We write |A|

for the “cardinality” of A, which can informally be defined as the equivalence class of A with respect to ≈.

• We write A ≤ B or |A| ≤ |B| iff there is a 1-1 map from A into B. Equivalently (for

nonempty A): |A| ≤ |B| iff B can be mapped onto A.

• The notation |A| ≤ |B| is justified by the following theorem: If |A| ≤ |B| and |B| ≤

|A|, then |A| = |B|.

• |A| = |A^{n}| = | ⋃_{k} A^{k}| for all infinite A.

• We say that a set A is countable and write |A| = ℵ_{0} iff there is a bijective map from

ℕ onto A. A is “at most countable” [|A| ≤ ℵ_{0}] iff A is countable or finite.

However, not all functions are monotone, and there are even trivial examples of lattices L with only “few” monotone functions, i.e., satisfying

{f : f is monotone from L to L} ≈ L

for example the linear order ℝ (the real numbers).

Here is the main idea that can be used for many lattices L to show that L is not o.p.c.:

(a) find a “nice” substructure A of the same cardinality as L

(b) find a subset L′ ⊆ L such that

• for all “nice” structures A of cardinality κ there are > κ many monotone maps from A to L′

• the set L′, with the order inherited from L, is a complete lattice [not

necessarily a sublattice of L]

(c) conclude that there are > κ many monotone maps from L to L.

Part (c) is easy: every monotone f : A → L′ can be extended to f̄: L → L′ via

f̄(x) = sup_{L′}{f(z) : z ∈ A, z ≤ x}.

From (anti)chains to monotone functions. It is well-known (see, e.g., [7] or [5]) that if A ⊆ L is an antichain^{3} then there are^{4} 2^{|A|} > |A| many pairwise incomparable^{5} functions from A to {0, 1}, and since {0, 1} is a complete lattice it is trivial to extend all those functions to monotone functions defined on all of L. If A ⊆ L is well-ordered^{6}, there are 2^{|A|} many monotone functions from A to A, and again they can all be extended to total monotone functions from L into the complete lattice A ∪ {0, 1}.

Thus, a first approximation to the program (a)(b)(c) outlined above is: For a given lattice L, find a “large” antichain or well-ordered chain in L (where “large” means: of the same cardinality as L itself).

Unfortunately, this is not always possible but at least for countable lattices the following observation helps: Ramsey’s Theorem^{7} implies that every infinite partial order contains either a chain isomorphic or anti-isomorphic to the natural numbers, or an infinite antichain.

3A ⊆ L is called an antichain if no two distinct elements of A are comparable.

4If |A| = κ, we write 2^{κ} for the cardinality of 𝒫(A). Thus, a set B is of cardinality 2^{ℵ_{0}} iff B can be mapped bijectively onto 𝒫(ℕ) or ℝ.

5If f, g : L^{n} → L are functions, we say f ≤ g iff f(a_{1}, …, a_{n}) ≤ g(a_{1}, …, a_{n}) holds for all (a_{1}, …, a_{n}) ∈ L^{n}. The relation ≤ is then a partial order of functions. The polynomials are (via the functions they induce) quasiordered.

6Recall that a linearly ordered set (A, ≤) is called “well-ordered” iff every nonempty subset of A has a least element.

7We will use the following version of the infinitary Ramsey theorem: Whenever the edges of the complete graph on countably many vertices are colored with 3 colors, then there is an infinite complete subgraph, all of whose edges have the same color.

Proof: We may assume that the partial order P is countable: P = {p_{1}, p_{2}, … }, where all p_{i} are distinct. Color the edges of the complete graph on {1, 2, … } with 3 colors: The edge {i, j} is colored according to whether the map i ↦ p_{i}, j ↦ p_{j} is an isomorphism, anti-isomorphism, or neither. Any infinite complete subgraph whose edges are colored with only one color will be the desired chain or antichain.

Hence any infinite partial order, in particular any infinite lattice, admits ≥ 2^{ℵ_{0}} many monotone functions, so an o.p.c. lattice has to have size ≥ 2^{ℵ_{0}}.

The above method yielding many incomparable functions from an antichain is set-theoretical. The next idea, converting a set of incomparable functions into an antichain, is mainly algebraic. Here it is important that we are interested in fully o.p.c.(and not only 1-o.p.c.) lattices:

From monotone functions to antichains.

2. Lemma. Let L be a lattice on which there are κ many pairwise incomparable k-ary polynomials, where^{8} cf(κ) > ℵ_{0}.

Then there is some n′ such that L^{n′} contains an antichain of size κ.

Proof. (This idea, and in fact the whole proof, is due to [7].)

Assume that the polynomials (p_{i}(x̄) : i ∈ I) are pairwise incomparable, where |I| = κ, and x̄ abbreviates (x_{1}, …, x_{k}). For each i there is a natural number n_{i} such that p_{i}(x̄) can be written as t_{i}(x̄, c̄_{i}), where t_{i} is a (k + n_{i})- ary term, and c̄_{i} ∈ L^{n_{i}} (the entries of the vector c̄_{i} are the “coefficients” of the polynomial p_{i}). Since there only countably many terms, our assumption cf(κ) > ℵ_{0} implies we can thin out the set I to a set I′ of the same cardinality such that all the (n_{i}, t_{i}) (for i ∈ I′) are equal, say = (n′, t′). Now it is easy to check that the “coefficients” (c̄_{i} : i ∈ I′) form an antichain in L^{n′}.

3. Corollary. If L^{n_{1}} has an antichain or well-ordered chain of size κ, and L is n_{1}-o.p.c., then there are 2^{κ} many pairwise incomparable polynomial functions p : L^{n_{1}} → L. So there is some n_{2} such that L^{n_{2}} has an antichain of size 2^{κ}.

Repeating this argument we can find some n_{3} such that L^{n_{3}} has an antichain of size 2^{2^{κ}}, etc.

So let L be infinite and o.p.c. To simplify some calculations, we will assume GCH, the generalized continuum hypothesis, for the rest of this chapter. However, all of what will be said will — with some obvious modifications — remain true even without this additional assumption.

8cf(κ) > ℵ_{0} [read: κ has uncountable cofinality] means: κ is the cardinality of an infinite set A with the following property:

Whenever A = ⋃_{n=1}^{∞} A_{n}, then for some n, |A| = |A_{n}|.

For example, it is true (but not quite trivial, unless we assume the continuum hypothesis)

that the set ℝ of real numbers satisfies cf(|ℝ|) > ℵ_{0}.

The negation of this property is denoted cf(κ) = ℵ_{0}: κ = |A| for some infinite set A which can be written as a countable union of sets of strictly smaller cardinality.

We know that L contains a chain or antichain of size ℵ_{0}, so also one of size 2^{ℵ_{0}} (since we assume GCH we can write this as ℵ_{1}). Iterating corollary 3 we get

|L| ≥ ℵ_{1}, |L| ≥ ℵ_{2}, |L| ≥ ℵ_{3}, …

and finally |L| ≥ ℵ_{ω}.

It turns out that the proof splits into three very different cases, depending on κ, the cardinality of L:

a: For some μ < κ, 2^{μ} ≥ κ.

b: Case (a) does not hold, and cf(κ) = ℵ_{0}.

c: Case (a) does not hold, and cf(κ) > ℵ_{0}.

Case (a) is treated similarly to the cases κ = ℵ_{1}, κ = ℵ_{2}, etc. If case (a) does not hold, i.e., if we have

∀μ < κ : 2^{μ} < κ

then we call κ a “strong limit cardinal”.

We will in this paper repeat the argument from [5] for case (b). (Case (c) was considered in [6].) It turns out that the case |L| = ℵ_{ω} is typical for (b), so to again simplify the notation we will assume this equality.

Thus L can be written as L = L_{0} ∪ L_{1} ∪ ⋯, where |L_{n}| = ℵ_{n}, L_{n+1} ≈ 𝒫(L_{n}).

Can we prove that every lattice L of size ℵ_{ω} contains either an antichain or a chain (well-ordered or dually well-ordered) of cardinality ℵ_{ω}? Unfortunately this is not true. The best we can do is to show that for each n, L must contain a (well-ordered or co-well-ordered) chain or antichain A_{n} of cardinality ℵ_{n}, but it is quite possible that the union A := A_{0} ∪ A_{1} ∪ A_{2} ∪ ⋯ is neither a chain nor an antichain, as the following examples show:

4. Example. For each n let A_{n} be a well-ordered (or co-well-ordered) set of cardinality ℵ_{n}, and assume that the union

L = {0} ∪ {1} ∪ A_{0} ∪ A_{1} ∪ ⋯

is a disjoint union. Define a partial order on L by requiring 0 and 1 to be the least and greatest elements respectively, and by also requiring

∀n ≠ k ∀a ∈ A_{n} ∀b ∈ A_{k} : a and b are incomparable.

Thus, L consists of countably many chains (of increasing sizes), arranged side-by-side. We leave it to the reader to check that L is indeed a lattice, in fact a complete lattice.

L contains chains of cardinality ℵ_{n} for each n, but no chain of length ℵ_{ω}, and every antichain in L is at most countable.

5. Example. For each n let A_{2n+1} be an antichain of cardinality ℵ_{n}, and let A_{2n} = {a_{n}}. Again, assume that the union

L = {0} ∪ {1} ∪ A_{0} ∪ A_{1} ∪ ⋯

is a disjoint union. Define a partial order on L by requiring 0 and 1 to be the least and greatest elements respectively, and by also requiring

∀n < k ∀a ∈ A_{n} ∀b ∈ A_{k} : a < b.

Thus, L consists of countably many antichains, each one on top of the previous one. Again it is easy to check that L is a complete lattice. [If a, b ∈ A_{2n+1} are distinct, then a ∧ b = a_{2n}.]

This time L contains antichains of cardinality ℵ_{n} for each n, but no antichain of length ℵ_{ω}, and every chain in L is at most countable.

6. Example. For each n let A_{n} be a well-ordered set of size ℵ_{n}. Again, assume that the union

L = {0} ∪ {1} ∪ A_{0} ∪ A_{1} ∪ ⋯

is a disjoint union. Define a partial order on L by requiring 0 and 1 to be the least and greatest elements respectively, and by also requiring

∀n < k ∀a ∈ A_{n} ∀b ∈ A_{k} : a > b.

Thus, elements of A_{0} are above all elements of A_{1}, etc. L itself is a chain of cardinality ℵ_{ω}, but L is not well-ordered. Moreover, any well-ordered subset of L has cardinality < ℵ_{ω}, and any co-well-ordered subset of L is countable. There are no antichains of size > 1 in L.

In the first two examples we have a lattice L of cardinality ℵ_{ω}, all of whose chains and antichains are of size < ℵ_{ω}.

Still, it is easy to see that the lattices in all three examples admit 2^{ℵ_{ω}} many monotone unary functions. E.g., in example 5, any map f : L → L satisfying f[A_{n}] ⊆ A_{n} for all n, f(0) = 0, f(1) = 1 will be monotone, and there are 2^{ℵ_{0}} × 2^{ℵ_{1}} × ⋯ = 2^{ℵ_{ω}} many such maps.

Hence, the following theorem suffices to prove that a lattice L of cardinality ℵ_{ω} cannot be o.p.c.:

7. Theorem (GCH). If L is a partial order of cardinality ℵ_{ω}, then L either contains a sufficiently large antichain or (well-ordered or co-well-ordered) chain, or a partial order P which is isomorphic or antiisomorphic to one of those constructed in examples 4, 5 and 6.

This theorem can be easily deduced from the “canonization” theorem of Erdős, Hajnal and Rado, see [1, 28.1].

The first “open” question is rather ill-defined:

8. Problem. Find a purely algebraic proof that every o.p.c. lattice must be finite.

Why do we need such a proof? First, there may be algebraists who are uncomfortable with the notions “cardinality” and “cofinality” which were used in the proof above. Secondly, and more to the point, a new proof of theorem 1 may also shed light on the following problem, which is still open:

9. Problem. Can there be an infinite 1-o.p.c. lattice? If yes, what about 2o.p.c.? etc.

10. Speculation. In [6] it is shown that theorem 1 cannot be proved without some weak version of AC, the axiom of choice; this seems to indicate that some set-theoretic sophistication is necessary for any proof of theorem 1. However, on closer scrutiny it turns out that the only version of AC that was shown to be necessary for such a proof is a statement that is strictly weaker than

“every infinite set contains a countable subset” which for most non-logicians is not even recognizable as a version of AC, so a “purely algebraic” proof might still be possible.

3. Finite o.p.c. lattices

For the investigation of finite lattices, set theory plays of course no role. We give the following characterization only to contrast it below with the situation for infinite lattices.

Let us call a function L → L “regressive” if ∀x ∈ L : f(x) ≤ x.

11. Definition. We say that a lattice satisfies Wille’s property if the only regressive join-homomorphisms are the identity map and the constant 0.

12. Theorem. A finite lattice is o.p.c. iff it is simple (in the algebraic sense) and satisfies Wille’s property.

This theorem is proved in [8].

It is of course crucial for the proof of this theorem that the lattice under consideration be finite, since the length of the constructed polynomial will typically increase with the size of the lattice.

The following easy example shows that the characterization theorem cannot work for infinite sets (of any cardinality).

13. Example. Let A be any infinite set disjoint from {0, 1}. Define a lattice M_{A} = A∪{0, 1} by requiring A to be an antichain and 0 ≤ a ≤ 1 for all a ∈ A.

Then M_{A} is simple and satisfies Wille’s property, but is of course not o.p.c..

4. Interpolation

There are several natural ways to generalize the question “which monotone functions are represented by polynomials” from finite to infinite lattices. The first approach, the property o.p.c., was discussed in section 2. A second approach is the following:

14. Definition. We say that a lattice L has the IP (interpolation property) iff for every monotone function f : L^{n} → L and every finite A ⊆ L^{n} there is a lattice polynomial p such that

∀(a_{1}, …, a_{n}) ∈ A : f(a_{1}, …, a_{n}) = p(a_{1}, …, a_{n}).

In other words, if we equip L with the discrete topology, and L^{(L^{n})}, the set of all functions from L^{n} to L, with the product topology (= Tychonoff topology = topology of pointwise convergence), then the IP says:

For all n, the set of monotone functions in L^{(L^{n})} is the closure of the set of all polynomial functions.

Clearly, a finite lattice has the IP iff it is o.p.c., but this is not true for infinitary lattices. For example, the lattice given in example 13 has the IP, but is of course not o.p.c.

While there are no infinite o.p.c. lattices, the following can be shown:

15. Theorem. For every lattice L there is an infinite lattice L̄ with the IP, where L is a sublattice of L̄.

Elementary cardinal arithmetic shows that L̄ can be chosen to be of the same cardinality as the cardinality of L, as long as L is infinite. (If L is finite,

then it is known that L can be extended to a finite o.p.c. lattice.)

This theorem can be proved with a combination of set-theoretic and algebraic ideas. The algebraic content of the theorem is represented by the following lemma (which is really a weak version of the theorem itself).

16. Lemma. If L is a lattice, f : L → L a monotone partial function, then there is a lattice L′ extending L, such that f is the restriction of a polynomial function with coefficients in L′. Moreover, if L is complete, then L′ can be chosen to be again a complete lattice, which is moreover an “end extension” of L, i.e.,

∀b ∈ L′ ∀a ∈ L \ {1} : (b ≤ a ⇒ b ∈ L).

(This lemma is proved in [2] and [3].)

It turns out that this lemma is sufficient to construct lattices with stronger interpolation properties. For example:

17. Definition. We say that a lattice L has the σ-IP (countable interpolation property) iff

For every monotone function L^{n} → L and every at most countable A ⊆ L^{n} there is a lattice polynomial such that

∀(a_{1}, …, a_{n}) ∈ A : f(a_{1}, …, a_{n}) = p(a_{1}, …, a_{n}).

(There is a natural generalization of the σ-IP to κ-IP for any cardinal κ. The theorems below can easily be generalized to these situations. For the sake of simplicity we will not pursue this idea here.)

18. Theorem. For every lattice L there is an infinite lattice L̄ with the σ-IP, where L is a sublattice of L̄.

We will sketch a proof of this theorem, for simplicity only for the case where the original lattice L is of size ≤ ℵ_{1}.

The simple (or even, by today’s standards, trivial) set-theoretic idea behind this theorem is the idea of transfinite iteration:

If at first you don’t succeed — try, try again. This idea goes back to Cantor. The point here is, of course that “again” can

mean here much more than “many” or even “infinitely many” times. When we are done with infinitely many repetitions, we start over!

As an index set for this iteration we will use the well-ordered set^{9} (ω_{1}, <). Rather than giving the set-theoretic definition of ω_{1} we will list some of its order-theoretic properties. The linear order (ω_{1}, <) can be characterized (up to isomorphism) by (1)–(4):

1. (ω_{1}, <) is a linear order.

2. (ω_{1}, <) is a well-order (i.e., every nonempty subset has a first element).

3. ω_{1} is uncountable.

4. For every a ∈ ω_{1} the set of predecessors, {i ∈ ω_{1} : i < a} is at most countable. (I.e., “every bounded set is countable”.)

5. Moreover: whenever A ⊆ ω_{1} is countable, there there is an a ∈ ω_{1} such

that A ⊆ {i ∈ ω_{1} : i < a}. (I.e., “every countable set is bounded.”) We will write ℵ_{1} for |ω_{1}|. We will write 0 for the smallest element of ω_{1}, and for i ∈ ω_{1} we will write i + 1 for the “successor” of i, i.e.,

i + 1 = min{j ∈ ω_{1} : i < j}.

It suffices to construct a sequence (L_{i} : i ∈ ω_{1}) starting with the original lattice L = L_{0} such that: (A) i < j implies: L_{i} ⊆ L_{j} (as a sublattice). (B) Each L_{i} is countable. (C) For every i ∈ ω_{1}, all natural numbers k, and for all monotone partial

functions with countable domain f : L_{i}^{k} → L_{i} there is a polynomial p ∈ L_{i+1}[x_{1}, …, x_{k}] such that for all ā = (a_{1}, …, a_{k}) in the domain of f: f(ā) = p(ā).

We first explain why such a construction satisfying (A)+(B)+(C) is possible. A rigorous argument would have to appeal to the fundamental theorem of Definition by Transfinite Recursion; the following informal argument captures the essence of the proof:

Assume that this construction is not possible. Since ω_{1} is well-ordered this means that there is a first index j where the construction breaks down. If j has no predecessor, then L_{j} := ⋃_{i<j} L_{i} satisfies all requirements, so we may assume that j has a predecessor, j = i + 1.

Given L_{i}, we now have to find L_{i+1} such that every countable partial monotone function from L_{i} to L_{i} is represented by a polynomial with coefficients in L_{i+1}. Elementary cardinal arithmetic shows that there are only ℵ_{1}^{ℵ_{0}} = ℵ_{1} many such partial functions, so it is enough to apply lemma 16 repeatedly (ℵ_{1} many times) to construct L_{i+1}.

9Some authors prefer to write Ω instead of ω_{1}.

We now explain why the properties (A)+(B)+(C) are sufficient:

L := ⋃_{i∈ω_{1}} L_{i} is a lattice, and (see property (5) in the description of ω_{1}) for every countable partial function f : L → L we can find an i ∈ ω_{1} such that both domain and range of f are subsets of L_{i}. Hence f is represented as a polynomial.

5. Complete lattices

Recall that a lattice is called “complete” if every subset has a greatest lower and least upper bound. We say that a lattice is σ-complete if every countable subset has a greatest lower and least upper bound. The lattice we constructed in theorem 18 is easily seen to be σ-complete. An important point in the construction of L̄ was the fact that every monotone partial function into a complete lattice can be extended to a total monotone function, so completeness (or σ-completeness, since the lattices we considered were countable) played an important role in the proof of lemma 16. But how essential is completeness for theorem 18 itself? Theorem 21 below shows that there is really no connection: σ-o.p.c. is consistent with a strong negation of σ-completeness.

19. Definition. Let L be a lattice, A, B ⊆ L. We write

A < B

to abbreviate the property

∀a ∈ A ∀b ∈ B : a < b.

If B is a singleton: B = {b} then we may write A < b instead of A < {b}, similarly if A is a singleton.

20. Definition. We call a bounded lattice σ-saturated if:

Whenever A, B ⊆ L are countable sets satisfying A < B, A upward directed^{10}, B downward directed, then there is an element c ∈ L such that A < c < B.

[This is a weak variant of the usual model-theoretic notion of saturation.] In particular, in a σ-saturated lattice no countable increasing sequence has

a least upper bound. Thus, in all interesting cases (namely, in those lattices in which there are infinite chains) σ-saturation is a strong negation of σcompleteness: In a σ-saturated lattice, no countable set has a least upper bound, except for trivial reasons.

21. Theorem. Let L be a bounded lattice. Then there is a σ-saturated σo.p.c.lattice L̄ which is an extension of L.

10i.e., ∀a, a′ ∈ A ∃a^{∗} ∈ A : a ≤ a^{∗}, a′ ≤ a^{∗}

Consequently, σ-o.p.c. does not imply σ-completeness.

Using the method of transfinite iteration, it can be seen that theorem 21 follows from lemma 16 together with the following lemma (which is a standard result in model theory, an easy consequence of the compactness theorem):

22. Lemma. Let L be a lattice, A, B ⊆ L, A < B, A upward directed, B downward directed.

Then there is a lattice L^{∗} extending L and an element c ∈ L^{∗} such that (in L^{∗}) we have A < c < B.

Note that even if we have B = {b}, b = sup A in L, b will lose this property in L^{∗}. Iterating this construction it is possible to obtain a σ-saturated lattice L̄.

Interleaving this iteration with the construction from lemma 16 will guarantee that L̄ will have the σ-IP.

6. σ-polynomials

In section 2 we have seen that there are no infinite lattices where all monotone functions are represented by polynomials. In section 4 we have seen that relaxing “represented” to “σ-interpolated” we get many lattices with this property, i.e., although there are no infinite lattices which are o.p.c., there are many lattices with the σ-IP.

In this section we will consider another variation of this theme. We are now again interested in representation (rather than interpolation), but instead of polynomial functions we will consider a wider class of functions, by allowing the infinitary operations sup and inf. We will take a “conservative” approach and only consider inf and sup over countable sets.

23. Definition. Let L be a lattice, k ∈ {1, 2, … }. By

L[[x_{1}, …, x_{k}]]

(the formal “σ-polynomials” over L) we denote the smallest set S of formal expressions (in the formal variables x_{1}, …, x_{k}) satisfying the following:

• The formal expressions x_{1}, …, x_{k} are in S, and all elements of L are in S.

• Whenever I is a finite or countably infinite set, and whenever (e_{i} : i ∈ I) is a family of expressions e_{i} ∈ S, then also the formal expressions

sup(e_{i} : i ∈ I) inf(e_{i} : i ∈ I)

are in S. If I = {0, 1} then we may write e_{0} ∨ e_{1} and e_{0} ∧ e_{1} instead of sup(e_{i} : i ∈ {0, 1}) = sup(e_{0}, e_{1}) and inf(e_{i} : i ∈ {0, 1}) = inf(e_{0}, e_{1}), respectively.

[Several variants of this definition are possible — we could divide the set of formal expressions defined above by the set of all equations that hold in all lattice extensions of L, or by the set of equations that hold in all σ-complete lattice extensions of L, etc.]

Correspondingly, we let the set of k-ary “σ-polynomial functions” be the smallest set of (partial) functions from L^{k} to L containing all the projections and closed under the pointwise sup and inf over at most countable sets.

There is a natural map (called “pointwise evaluation”) from the set of (formal) σ-polynomials onto the set of σ-polynomial functions.

Clearly, all σ-polynomial functions are monotone. In general a σ-polynomial function will not be total.

24. Theorem. For any lattice L there is a lattice L̄ such that L is a sublattice of L̄, and L̄ satisfies the following properties:

1. For every k, every monotone function from L^{k} to L is a σ-polynomial function, i.e., induced by a σ-polynomial.

2. All σ-polynomial functions on L̄ are total. Thus, the monotone functions are exactly the σ-polynomial functions.

3. Moreover, L̄ is complete, that is: every subset of L has a greatest lower and a least upper bound.

Proof. By lemma 16 we can find a sequence L = L_{0} ≤ L_{1} ≤ ⋯ of complete lattices such that:

For all k, every monotone f : L_{n}^{k} → L_{n} is represented by a polynomial with coefficients in L_{n+1}. Moreover, L_{n+1} is an end extension of L_{n}.

Let L = ⋃_{n} L_{n}. It is easy to see that L is complete. [If A ⊆ L, let a_{n} :=

inf_{L_{n}}(A ∩ L_{n}). Since the sequence (a_{n} : n ∈ ℕ) is weakly decreasing, and since L_{n+1} is an end extension of L_{n}, there must be some n_{0} such that ∀n a_{n} ∈ L_{n_{0}}. Now let a^{∗} := inf_{L_{no}} (a_{n} : n ∈ ℕ), then clearly a^{∗} = inf A. ]

Let f : L^{k} → L. For simplicity assume k = 1. For each n define f_{n} : L_{n} → L_{n} by

f_{n}(x) := sup_{L_{n}}{y ∈ L_{n} : y ≤_{L} f(x)}.

f_{n} is total (since L_{n} is complete), and clearly monotone. Let p_{n} ∈ L_{n+1}[x] be a polynomial such that p_{n}(a) = f_{n}(a) for all a ∈ L_{n}. Note: if a, f(a) ∈ L_{n}, then p_{n}(a) = f(a).

Now define a σ-polynomial p(x) by

p(x) = sup_{k≥0} inf_{n≥k} p_{n}(x)

or slightly less formally:

p(x) = (p_{0}(x)∧p_{1}(x)∧p_{2}(x)∧⋯) ∨ (p_{1}(x)∧p_{2}(x)∧⋯) ∨ (p_{2}(x)∧⋯) ∨ ⋯

It is easy to check that for all a ∈ L the sequence (p_{1}(a), p_{2}(a), p_{3}(a), …) is eventually constant with value f(a), and this implies p(a) = f(a).

Note that the lattices L_{n} in this construction might have bigger and bigger cardinalities. Of course there are also many smaller lattices in which every monotone function is a σ-polynomial, e.g., every countable lattice with the IP. This suggests the following question:

25. Problem. Describe all lattices in which every monotone function is a σpolynomial function. In particular, what are the cardinalities of such lattices?

7. Ortholattices

This section contains a preview of results (without proofs) that will be published elsewhere (see [4]). Again we give a theorem whose proof combines algebraic ideas with the simple set-theoretic idea of transfinite iteration.

An ortholattice is a bounded lattice with an additional unary operation ⊥ of “orthocomplement” which is antimonotone satisfying the following laws: x^{⊥⊥} = x, x ∨ x^{⊥} = 1, x ∧ x^{⊥} = 0. (This implies de Morgan’s laws. Informally, an ortholattice is a Boolean algebra without distributivity.)

Orthopolynomials and orthopolynomial functions are defined naturally: in addition to the operations ∨ and ∧ we also allow ^{⊥}. Hence orthopolynomials are in general not monotone. Is there any law that orthopolynomial functions have to satisfy? The theorem and its corollary below say that orthopolynomials can have arbitrary behavior.

We say that an ortholattice O has the σ-IP if every (not necessarily monotone) function f : O^{n} → O is interpolated by an orthopolynomial on any finite or countable set, and we say that an ortholattice O is σ-polynomially complete if every function f : O^{n} → O is represented by a σ-orthopolynomial.

26. Theorem. For any ortholattice (O, ∨, ∧, 0, 1, ⊥) and any f : O → O there is an ortholattice Ō such that O is an (ortho)sublattice of Ō, and there is an orthopolynomial p(x) with coefficients in Ō such that f(a) = p(a) for all a ∈ O.

27. Corollary. Every ortholattice O can be orthoembedded into an ortholattice Ō with the σ-IP.

Sketch. We only give a sketch of the main ideas of the proof. The details will appear elsewhere.

Start with a lattice O = O_{0}. Let

O_{1} := O_{0} + (O_{0} × O_{0})

i.e., O_{1} is the “horizontal sum” of the disjoint ortholattices O_{0} and O_{0} × O_{0}, where we of course identify the two top elements of the two lattices, and also the two bottom elements.

The functions g_{1}, g_{2} : O → O × O, defined by

\begin{aligned}g_{1}(x) & = & (x, 0) \\ g_{2}(x) & = & (1, x) \end{aligned}

are clearly monotone. Let A := {(x, x^{⊥}) : x ∈ O}. This set is an antichain in O_{1}, so the functions h : A → O_{0} ⊆ O_{1}, defined by

h(x, x^{⊥}) = f(x)

is trivially a (partial) monotone function from O_{1} to O_{1}.

Note that

f(x) = h(x, x^{⊥}) = h( g_{1}(x) ∨ g_{2}(x)^{⊥} )

so f can be written as a composition of monotone functions and the orthocomplement function.

By lemma 16, there is a lattice extension L_{2} of the lattice O_{1} such that h, g_{1}, g_{2} can be represented by lattice polynomials with coefficients in L_{2}.

A bit of work is now needed to find an ortholattice O_{3} which is both a lattice extension of L_{2} and an orthoextension of the original ortholattice O. Once this ortholattice is found, the function f can be represented as an orthopolynomial with coefficients in O_{3}.

References

[1] P. Erdős, A. Hajnal, A. Maté, and R. Rado. Combinatorial set theory: Partition Relations for Cardinals, volume 106 of Studies in Logic and the Foundation of Math. North Holland Publ. Co, Amsterdam, 1984.

[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] Martin Goldstern. Interpolation in ortholattices. arXiv:math.RA/0002237

[5] Martin Goldstern and Saharon Shelah. Order-polynomially complete lattices must be LARGE. Algebra Universalis, 39:197–209, 1998. arXiv:math.LO/9707203

[6] Martin Goldstern and Saharon Shelah. There are no order-polynomially complete lattices, after all. Algebra Universalis, 42:49-57, 1999. arXiv:math.LO/9810050

[7] Miroslav Haviar and Miroslav Ploščica. On order-polynomial completeness of lattices. Algebra Universalis, 39, 1998.

[8] R. Wille. Eine Charakterisierung endlicher, ordnungspolynomvollständiger Verbände. Archiv der Mathematik, 28:557–560, 1977.

Institut für Algebra, TU Wien, Wiedner Hauptstr 8-10/118.2, A-1040 Wien

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