THERE ARE NO INFINITE ORDER POLYNOMIALLY COMPLETE LATTICES AFTER ALL

MARTIN GOLDSTERN AND SAHARON SHELAH

Abstract. If L is a lattice with the interpolation property whose cardinality is a strong limit cardinal of uncountable cofinality, then some finite power L^{n} has an antichain of size κ. Hence there are no infinite opc lattices.

However, the existence of strongly amorphous sets implies (in ZF) the existence of infinite opc lattices.

0. Introduction

We call a lattice L n-order polynomially complete (opc) if every monotone function L^{n} → L is induced by a lattice polynomial, and we say that L is order polynomially complete if L is n-order polynomially complete for every n.

This definition is from Schweigert’s Ph.D. thesis [4]. The survey [3] gives several results and bibliographical references for results on order polynomially complete lattices.

While the finite opc lattices are now well understood, the main question on infinite opc lattices: are there any? has remained open until now. Haviar and Ploscica [2] showed that there is no opc lattice of size < ℶ_{ω}. We showed in [1] that the size of an infinite opc lattice (if one exists at all) must be a strongly inaccessible cardinal.

We now complement this result by showing (in ZFC) that the cardinality of an opc lattice cannot be a strongly inaccessible cardinal. Hence there are no infinite opc lattices.

Again the proof is not algebraic in nature, but based on a counting argument.

Unlike our previous proof, which employed the heavy machinery of partition calculus, this paper uses only very basic set theory (the notions of “cofinality” and “strong limit”) and some baby model theory (the notion of “type”).

We also point out that some version of AC (the axiom of choice) is necessary for our result, since under a strong negation of AC there are pathological sets, which (while being infinite) are sufficiently similar to finite sets that it is still possible to build an opc lattice on them.

Date: Jan 1999.

1991 Mathematics Subject Classification. Primary 06A07; secondary 08A40, 06B99, 03E55.

Key words and phrases. polynomially complete, lattice, interpolation property, inaccessible cardinal, amorphous set, axiom of choice.

The second author is supported by the German-Israeli Foundation for Scientific Research & Development Grant No. G-294.081.06/93. Publication number 688.

1. No opc lattices

1.1. Definition. We say that a lattice L has the unary interpolation property (1-IP), if every monotone function from L into L can be interpolated by a polynomial on any finite set. (Equivalently: Whenever a, b, c, d ∈ L, b ≰ a, c ≤ d, then there is a polynomial p with p(a) = c, p(b) = d.)

1.2. Theorem. Assume that L has the 1-IP. Let κ be the cardinality of L and assume that κ is a strong limit cardinal of uncountable cofinality. Then for some natural number n there is an antichain A ⊆ L^{n} of cardinality κ.

Proof. Let L be a lattice satisfying the assumptions of the theorem, and pick any two distinct comparable elements of L. We will call them 0 and 1, where 0 < 1.

We will define sequences (L_{i} : i < κ), (a_{i} : i < κ), (b_{i} : i < κ), (c̄_{i} : i < κ), (n_{i} : i < κ), (τ_{i} : i < κ) such that the following are satisfied for all i, j < κ:

(1) {0, 1} ⊆ L_{i} ⊆ L, |L_{i}| < κ

(2) If i < j, then L_{i} ⊆ L_{j}.

(3) a_{i} and b_{i} are in L and realize the same (quantifier-free) type over L_{i}, i.e.: whenever σ(x) and τ(x) are unary polynomials with coefficients in L_{i}, then σ(a_{i}) ≤ τ(a_{i}) iff σ(b_{i}) ≤ τ(b_{i}).

(4) b_{i} ≰ a_{i}

(5) n_{i} is a natural number

(6) τ_{i} is an n_{i} + 1-ary term

(7) c̄_{i} = (c_{i}^{1}, …, c_{i}^{n_{i}}) ∈ L^{n_{i}}

(8) τ_{i}(a_{i}, c̄_{i}) = 0, τ_{i}(b_{i}, c̄_{i}) = 1.

(9) For all i < j we have a_{i}, b_{i}, c_{i}^{1}, …, c_{i}^{n_{i}} ∈ L_{j}.

The sequences are defined by induction on i < κ. In stage i we let L_{i} be the set of “everything” used so far: L_{i} = {0, 1, a_{k}, b_{k}, c_{k}^{ℓ} : k < i, ℓ ≤ n_{k}}. Let λ_{i} = max(|L_{i}|, ℵ_{0}).

Since every type over L_{i} can be represented as a set of pairs of polynomials with coefficients in L_{i}, there are at most 2^{λ_{i}} many possible types over L_{i}. By our assumption, λ_{i} < κ implies 2^{λ_{i}} < κ, so we can find two different elements a_{i}, b_{i} which have the same type over L_{i}. Wlog a_{i} ≯ b_{i}.

Now the function that maps the set {x : x ≤ a_{i}} to 0 and everything else (including b_{i}) to 1 is monotone, so it is realized by a polynomial p_{i}(x). Let n_{i} be the number of coefficients of p_{i}, so we can write p_{i}(x) as τ_{i}(x, c_{i}^{1}, … c_{i}^{n_{i}}), where τ_{i}(x, y_{1}, …, y_{n_{i}}) is an (n_{i} + 1)-ary term.

This concludes the construction of our sequences. Note that if (k_{i} : i < κ) is the increasing enumeration of a κ-size subset of κ, then (L_{k_{i}} : i < κ), (a_{k_{i}} : i < κ), etc., also have all the properties listed above.

Since κ has uncountable cofinality, there must be some natural number n such that {i : n_{i} = n} has cardinality κ, so wlog (after thinning out our sequence, if necessary) we may assume that n_{i} = n for all n. Similarly, since there are only countably many n+1-ary terms, we may assume all τ_{i} are equal to some fixed term τ.

Now let d̄_{i} = (a_{i}, b_{i}, c_{i}^{1}, …, c_{i}^{n}). We claim that (d̄_{i} : i < κ) is an antichain in L^{n+2}.

Indeed, pick any i < j and assume that either d̄_{i} ≤ d̄_{j} or d̄_{i} ≥ d̄_{j}. Since τ is monotone in each argument, we either have

0 = τ(a_{i}, c̄_{i}) ≤ τ(a_{j}, c̄_{i}) ≤ τ(a_{j}, c̄_{j}) = 0

or the converse inequality, so in any case τ(a_{j}, c̄_{i}) = 0. Similarly we get τ(b_{j}, c̄_{i}) = 1

However, since a_{j} and b_{j} have the same type over c̄_{i}, 0, 1, the equation τ(a_{j}, c̄_{i}) = 0 implies τ(b_{j}, c̄_{i}) = 0. This is a contradiction, so we conclude that d̄_{i} and d̄_{j} are incomparable.

1.3. Conclusion. There is no infinite opc lattice

Proof. Assume that L is opc. A fortiori, L has the 1-IP. Let κ = |L|. Since L is opc, we know from [1] that κ must be a strongly inaccessible cardinal, so in particular κ is a strong limit cardinal of uncountable cofinality. By our theorem, there is an antichain A ⊆ L of cardinality κ. But this easily implies that there are 2^{κ} > κ many monotone functions from L^{n} to L, and at most κ many of them can be polynomials.

2. The role of AC

2.1. Definition. An infinite set A is called “strongly amorphous” if, for all natural numbers n, all n-ary relations on A are first order definable (with parameters) in the language of equality. Equivalently, A is amorphous if all sets R ⊆ A^{n} are in the Boolean algebra generated by the sets {(x_{1}, …, x_{n}) : x_{i} = x_{j}}, {(x_{1}, …, x_{n}) : x_{i} = a} (a ∈ A).

While the axiom of choice (in fact, already a very weak version of AC) clearly implies that there are no infinite strongly amorphous sets, it is well known that the theory “ZF + there is an infinite strongly amorphous set” is equiconsistent with ZFC. That is, ZF cannot refute the existence of infinite strongly amorphous sets. Hence (as we will see below), ZF cannot refute the existence of infinite opc lattices.

For the rest of this section we promise not to use the axiom of choice.

2.2. Theorem (ZF). For every infinite set L there is a bounded lattice (L, ∨, ∧, 0, 1, ≤) such that:

For all natural numbers n, for all monotone functions f :

L^{n} → L:

If f is definable in (L, ∨, ∧, ≤, 0, 1), then f is induced by a polynomial.

2.3. Remark. (1) The “ZF” above means that this theorem is proved in the usual framework of mathematics (such as given by the Zermelo Fränkel axioms for the underlying set theory) but without invoking the axiom of choice.

(2) By “definable” we mean here: as a relation f ⊆ L^{n+1}, f is definable by a first order formula (with parameters from L) in the language of lattice theory.

Since all our lattices will be bounded, it will be convenient to include the constants (or 0-ary operations) 0 and 1 into the “language of lattice theory”. Thus, “definable with parameters c_{1}, …, c_{k}” will mean the same as “definable with parameters c_{1}, …, c_{k}, 0, 1”.

2.4. Corollary (ZF). Assume that there is an infinite strongly amorphous set. Then there is an infinite order polynomially complete lattice.

2.5. Construction. Let L be an infinite set, 0 and 1 two distinct elements of L. Define a lattice structure on L by requiring 0 ≤ a ≤ 1 for all a ∈ L.

2.6. Fact. Let (L, ∨, ∧, 0, 1, ≤) be a lattice as in construction 2.5. Then every subset R ⊆ L^{n} which is definable in (L, ∨, ∧, 0, 1, ≤) with parameters c_{1}, …, c_{k} ∈ L is also definable (with parameters c_{1}, …, c_{k}, 0, 1) in the language of equality [i.e, in (L, =)].

We will abbreviate a situation as in fact 2.6 by writing “R is definable from (c_{1}, …, c_{k}).” Functions f : L^{n} → L will be treated as relations f ⊆ L^{n+1}.

2.7. Notation. We indicate formal variables or indeterminates by a special typeface, e.g., x, t_{1}, etc.

We abbreviate tuples (c_{1}, …, c_{k}) and (x_{1}, …, x_{n}) as c̄^{k} and x̄^{n}, or sometimes c̄ and x̄. We abbreviate (α, c_{1}, …, c_{k}) by (α, c̄) or sometimes α, c̄.

Mon(L, L′) is the set of all monotone maps from L to L′.

𝕋 is the set of all lattice-theoretic terms in the variables x_{1}, x_{2}, …, s_{1}, s_{2}, …, t_{1}, t_{2}, … (We include the constants 0 and 1 among “lattice-theoretic terms”)

2.8. Definition. Assume that L, L′ are isomorphic lattices, with isomorphism π : L → L′. We extend π canonically to an isomorphism π : L^{n} → L^{n}. For any f : L^{n} → L we write the conjugate function as πf or π(f):

for all ā ∈ L^{n}: (πf)(πā) = π(f(ā))

2.9. Fact. If f : L^{n} → L is definable from c̄ = (c_{1}, …, c_{k}), π : L → L an automorphism which satisfies π(c_{j}) = c_{j} for j = 1, …, k, then πf = f.

2.10. Definition. Let (L, ≤) be a partial order, A ⊆ L. The “monotone characteristic function of A” is the function χ_{A} : L → {0, 1} defined by

χ_{A}(x) = \{ \begin{matrix}1 & if a ≥ b for some b ∈ A \\ 0 & otherwise, \end{matrix}

i.e., χ_{A} is the customary characteristic function of the upward closure of A.

From now on L will be a lattice as in 2.5

2.11. Definition. Let {c_{1}, …, c_{k}} ⊆ L, d̄ = (d_{1}, …, d_{m}) ∈ L^{m}. We say that d̄ is “independent over {c_{1}, …, c_{k}}” (or: over (c_{1}, …, c_{k})) iff

all d_{i} are distinct, and no d_{i} is in {c_{1}, …, c_{k}, 0, 1}. [This is a special case of the usual model-theoretic notion of independence.]

2.12. Definition. (1) Let χ(s, x, t_{1}, t_{2}, t_{3}) be the term

[(x ∧ s) ∨ t_{1}] ∧ [(x ∧ s) ∨ t_{2}].

(2) For α ∈ L \ {0, 1} let χ_{α}(x, t_{1}, t_{2}, t_{3}) = χ(α, x, t_{1}, t_{2}, t_{3}).

(3) If A ⊆ {c_{1} …, c_{k}, 0, 1} ⊆ L, then we define χc̄ ; A(s̄^{k}, x, t̄^{3}) (the “monotone characteristic function of A, given the parameters c̄”) as follows:

(a) If A = ∅, then χc̄ ; A(s̄, x, t_{1}, t_{2}, t_{3}) is the constant term 0.

(b) If A = {1}, then χc̄ ; A(s̄, x, t_{1}, t_{2}, t_{3}) = μ(x ∧ t_{1}, x ∧ t_{2}, x ∧ t_{3}), where μ is the following “majority term”:

μ(x, y, z) = (y ∨ z) ∧ (z ∨ x) ∧ (x ∨ y)
(c) If 0 ∈ A, then χc̄ ; A(s̄, x, t_{1}, t_{2}, t_{3}) is the constant term 1.

(d) Otherwise we let I = Ic̄ ; A = {i : c_{i} ∈ A \ {0, 1}} and we let

χc̄ ; A(x, t̄) = ⋁_{i∈I} χ_{c_{i}}(x, t̄)

(4) If A is cofinite, L \ A ⊆ {c_{1}, …, c_{k}}, then we define χc̄ ; A(s̄, x, t̄) similarly (dually), such that fact 2.13 below holds. We leave the details to the reader.

2.13. Fact. If A ⊆ {c_{1}, …, c_{k}, 0, 1} or L \ A ⊆ {c_{1}, …, c_{k}, 0, 1}, and d̄= (d_{1}, d_{2}, d_{3}) is independent over c_{1}, …, c_{k}, then the function

a ↦ χc̄ ; A(c̄, a, d_{1}, d_{2}, d_{3})

is the monotone characteristic function of A.

Proof. Easy computation.

2.14. Lemma. Let L be as in construction 2.5. Then there is a function

p : (⋃_{n=0}^{∞} Mon(L^{n}, L)) × (⋃_{k=1}^{∞} L^{k}) → 𝕋

that assigns to each pair (f, c̄) a polynomial p^{f;c̄} ∈ 𝕋 such that the following hold:

(1) If c̄ = (c_{1}, …, c_{k}) and f : L^{n} → L, then p^{f;c̄} is a term using (at most) the variables s_{1}, …, s_{k}, x_{1}, …, x_{n}, t_{1}, …, t_{3^{n}}. We will write p^{f;c̄} as p^{f;c̄}(s̄; x̄; t̄).

(2) If c̄ and f are as above, and f is definable from c_{1}, …, c_{k}, then

we have:

Whenever d̄= (d_{1}, … d_{3^{n}}) is independent over {c_{1}, …, c_{k}},

then for all ā ∈ L^{n}: f(ā) = p^{f;c̄}(c̄; ā; d̄),

that is, the function f is induced by the lattice polynomial p^{f;c̄}(c̄; x̄; d̄).

(3) Moreover, the term p^{f;c̄} depends only on the “isomorphism type” of (f, c̄). That is, whenever π : L → L′ is an isomorphism, then p^{f;c̄}(s̄, x̄, t̄) = p^{πf,π(c̄)}(s̄, x̄, t̄).

2.15. Remark. Let L be as above. Then the following is not provable in ZF:

(∗) There is a map p which assigns to each definable monotone function f : L → L a polynomial p^{f}(x) with coefficients in L such that p^{f}(a) = f(a) for all a ∈ L.

This explains why we have to explicitly mention the parameters c̄ in lemma 2.14.

Proof of lemma 2.14. We define the map p by induction on n (the arity of f). We leave the case n = 0 to the reader.

Let f : L^{n+1} → L, c̄ = (c_{1}, …, c_{k}) ∈ L^{k}. (Wlog assume that f is definable from c̄, otherwise set p^{f;c̄} = 0.)

Let A = L \ {c_{1}, …, c_{k}, 0, 1}.

We will now apply the induction hypothesis to the functions f_{α} : L^{n} → L, where f_{α}(ā) = f(ā, α). For each α ∈ L we thus get a term τ_{α} = p^{f_{α}}. We will show that only finitely many different terms actually appear, and that they can be combined to yield a term p^{f}. The cases α ∈ A and α ∉ A have to be treated in different ways.

To save us some cases distinctions, we agree that c_{k+1} = 0, c_{k+2} = 1. For each α ∈ {c_{1}, …, c_{k+2}} the function f_{α} : L^{n} → L, f_{α}(ā) =

f(ā, α) is definable from c̄ = (c_{1}, …, c_{k}). Let

τ_{α}^{f;c̄}(x̄^{n}; s̄^{k}; t̄^{3^{n+1}}) = p^{f_{α},c̄}(x̄^{n}; s̄^{k}; t̄^{3^{n}})

(so the indeterminates t_{3^{n}+1}, …, t_{3^{n+1}} do not appear in τ_{α}^{f,c̄}.) By our inductive assumption we know for all ā ∈ L^{n}:

τ_{α}^{f;c̄}(ā^{n}; c̄^{k}; d̄^{3^{n+1}}) = f_{α}(ā) = f(ā, α) (-1-)

for all α ∈ {c_{1}, …, c_{m+2}}, whenever d̄ is independent over c̄. Let

τ_{constant}^{f;c̄}(x̄^{n}, x_{n+1}; s̄^{k}; d̄^{3^{n+1}}) = ⋁_{i=1}^{m+2}[χ_{c_{i}}(x_{n+1}, t̄^{3}) ∧ τ_{c_{i}}^{f;c̄}(x̄^{n}; s̄^{k}; t̄^{3^{n+1}})].

Hence we have for all ā ∈ L^{n}:

τ_{constant}(ā^{n}, α; c̄^{k}; d̄^{3^{n+1}}) = \begin{cases}f(ā, α) & if α ∈ \{c_{1}, …, c_{k}, 0, 1\} \\ f(ā, 0) & if α ∈ A = L \ \{c_{1}, …, c_{k}, 0, 1\}. \end{cases} (-2-)

whenever d̄ is independent over c̄. This follows easily from equation (-1-) and the monotonicity of f.

For each α ∈ A the function f_{α} : L^{n} → L, f_{α}(ā^{n}) = f(ā^{n}, α) is definable from (α, c̄). Hence the polynomial p^{f_{α};α,c̄}(x̄^{n}; x_{n+1}, s̄^{k}; t̄^{3^{n}}) satisfies for all ā ∈ L^{n}

p^{f_{α};α,c̄}(ā; α, c̄^{k}; d̄) = f(ā, α) (-3-)

for all α ∈ A, whenever d̄ is independent over α, c̄.

We claim that the function α ↦ p^{f_{α};α,c̄}(x̄; x_{n+1}, s̄; t̄) is actually constant on A. The reason is that A is disjoint to the set of parameters from which f is defined.

More formally, let α, β ∈ A. We will show p^{f_{α};α,c̄} = p^{f_{β};β,c̄}. Let π : L → L be an automorphism that fixes {c_{1}, …, c_{k}, 0, 1} pointwise, and maps α to β. Then πf = f, by fact 2.9.

Hence

p^{f_{α};α,c̄} = p^{π(f_{α});π(α),π(c̄)} by induction hypothesis, lemma 2.14(3)
= p^{(πf)_{π(α)};β,c̄}  since π(f_{α}) = (πf)_{π(α)}
= p^{f_{β};β,c̄}  since πf = f

We will write τ_{raw}^{f;c̄}(x̄, x_{n+1}; s̄; t̄) for the common value of this function. So we can rewrite equation (-3-) as: for all ā ∈ L^{n}, α ∈ A:

τ_{raw}^{f;c̄}(ā, α; c̄; d̄) = f(ā, α) (-4-)

whenever d̄ is independent over c̄.

The restriction that d̄has to be independent not only of c̄ but also of α is inconvenient. We get rid of it with the following “error correction” device: Let

σ_{1}^{f;c̄}(x̄^{n}, x_{n+1}; s̄; t_{1}, …, t_{3^{n+1}}) = τ_{raw}^{f;c̄}(x̄^{n}, x_{n+1}; s̄; t̄_{1}, …, t_{3^{n}}) σ_{2}^{f;c̄}(x̄^{n}, x_{n+1}; s̄; t_{1}, …, t_{3^{n+1}}) = τ_{raw}^{f;c̄}(x̄^{n}, x_{n+1}; s̄; t_{3^{n}+1}, …, t_{2·3^{n}}) σ_{3}^{f;c̄}(x̄^{n}, x_{n+1}; s̄; t_{1}, …, t_{3^{n+1}}) = τ_{raw}^{f;c̄}(x̄^{n}, x_{n+1}; s̄; t_{2·3^{n}+1}, …, t_{3·3^{n}})

and let

τ_{clean}^{f;c̄} = μ(σ_{1}^{f;c̄}, σ_{2}^{f;c̄}, σ_{3}^{f;c̄}),

where μ(x, y, z) is a majority term, i.e., μ satisfies

μ(a, a, b) = μ(a, b, a) = μ(b, a, a) = a (-5-)

for all a, b ∈ L, see definition 2.12.

Let

τ_{bounded}^{f;c̄}(x̄^{n}, x; s̄; t̄) = τ_{clean}^{f;c̄}(x̄^{n}, x; s̄; t̄) ∧ τ_{1}^{f;c̄}(x̄^{n}; s̄; t̄) ∧ χc̄ ; A(x, t̄^{3}).

We claim that τ_{bounded}^{f;c̄}(x̄^{n}, x_{n+1}; s̄^{k}; t̄^{3^{n+1}}) satisfies

τ_{bounded}^{f;c̄}(ā^{n}, α; c̄^{k}; d̄^{3^{n+1}}) = \begin{cases}f(ā^{n}, α) & α ∈ A \\ 0 & α ∈ \{c_{1}, …, c_{k}, 0\} \\ ≤ f(ā, 1) & α = 1 \end{cases} (-6-)

for any ā ∈ L^{n}, α ∈ L, whenever d̄ is independent over c̄.

This is clear if α ∈ {c_{1}, …, c_{k}, 0}. For α = 1 recall that τ_{1}^{f;c̄}(ā; c̄; d̄) = f(ā, 1).

Finally, let α ∈ A, and assume that d̄ is independent over c̄. Let

d̄_{1} = (d_{1}, …, d_{3^{n}}) d̄_{2} = (d_{3^{n}+1}, …, d_{2·3^{n}}) d̄_{3} = (d_{2·3^{n}+1}, …, d_{3·3^{n}})

Now since all the d_{j} are distinct, at least two among d̄_{1}, d̄_{2}, d̄_{3} do not contain α and hence are independent over {c_{1}, …, c_{k}, α}. So by equation (-4-), at least two of the equations

f_{α}(ā) = σ_{ℓ}^{f;c̄}(ā, α; c̄; d̄^{3^{n+1}}) ℓ = 1, 2, 3

are true, hence we have (by the property (-5-))

τ_{clean}^{f;c̄}(ā, α; c̄; d̄) = f_{α}(ā)

so τ_{bounded}^{f;c̄}(ā, α; c̄; d̄) = f_{α}(ā) ∧ τ_{1}(ā; c̄; d̄) = f(ā, α) ∧ f(ā, 1) = f(ā, α) for all α ∈ A.

This concludes our discussion of the term τ_{bounded}^{f;c̄}.

We can now define p^{f;c̄} as

p^{f;c̄}(x̄^{n}, x_{n+1}; s̄^{k}; t̄^{3^{n+1}}) = τ_{constant}^{f;c̄}(x̄^{n}, x_{n+1}; s̄; t̄) ∨ τ_{bounded}^{f;c̄}(x̄^{n}, x_{n+1}; s̄; t̄)

From (-2-) and (-6-) we now get the desired property

p^{f;c̄}(ā, α; c̄; d̄) = f(ā, α)

whenever d̄ is independent over c̄.

Theorem 2.2 now immediately follows from lemma 2.14.

References

[1] Martin Goldstern and Saharon Shelah. Order-polynomially complete lattices must be LARGE. Algebra Universalis, 39:197–209, 1998.

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

[3] Hans Kaiser. Interpolation and order polynomially complete lattices. volume 9 of Contributions to general algebra. Hölder-Pichler-Tempsky, Wien, 1995.

[4] Dietmar Schweigert. Zur Theorie der Verbandspolynome. PhD thesis, Technische Universität Wien, 1972.

Institut für Algebra, Technische Universität Wien, Wiedner Hauptstraße 8-10/118.2, A-1040 Wien, Austria

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

Department of Mathematics, Hebrew University of Jerusalem, Givat Ram, 91904 Jerusalem, Israel

  E-mail address: shelah@math.huji.ac.il