ORDER POLYNOMIALLY COMPLETE LATTICES MUST BE LARGE

MARTIN GOLDSTERN AND SAHARON SHELAH

Abstract. If L is an o.p.c. (order polynomially complete) lattice, then the cardinality of L is a strongly inaccessible cardinal. In particular, the existence of o.p.c. lattices is not provable in ZFC, not even from ZFC+GCH.

Introduction

Let (L_{1}, ≤) and (L_{2}, ≤) be partial orders. We call a map f: L_{1} → L_{2} “monotone” if x ≤ y implies f(x) ≤ f(y).

Notice that if (L, ∧, ∨, ≤) is a lattice, then every polynomial function (i.e., function induced by a lattice-theoretic polynomial) is monotone.

We call a lattice L n-order polynomially complete (o.p.c.) if (∗) every monotone n-ary function is a polynomial function

and we say that L is order polynomially complete if L is n-order polynomially complete for every n.

The question whether there can be an infinite o.p.c. lattice has been the subject of several papers. Kaiser and Sauer [KaSa93] remarked that such a lattice cannot be countable, and Haviar and Ploščica showed in [HaPl97] that such a lattice would have to be at least of size ℶ_{ω}. (Here, ℶ_{0} = ℵ_{0}, ℶ_{n+1} = 2^{ℶ_{n}}, ℶ_{ω} = sup{ℶ_{n} : n ∈ ω}.

We show here that the size of an infinite o.p.c. lattice (if one exists at all) must be a strongly inaccessible cardinal.

In particular, the existence of such a lattice cannot be derived from the “usual” axioms of mathematics, as codified in the Zermelo-Fraenkel axioms for set theory. Moreover, also certain additional assumptions such as the (generalized) continuum hypothesis are not sufficient to prove the existence of an o.p.c. lattice, or in other words, the theory ZFC+GCH+“there is no infinite o.p.c. lattice” is consistent^{1}. In fact, the well-known consistent^{1} theory ZFC+“there is no inaccessible cardinal”, a natural extension of ZFC, proves that there is no o.p.c. lattice.

Date: Oct 6, 1997.

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

Key words and phrases. polynomially complete, inaccessible cardinal, canonization.

The first author is supported by an Erwin Schrödinger fellowship from the Austrian Science Foundation.

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

We still do not know whether the existence of an o.p.c. lattice can be refuted in ZFC alone.

In [GoSh 554] we showed that if we change the original question by relaxing “lattice” to “partial order”, and “polynomial” to “definable”, then we get (consistently) a positive answer, already for a partial order of size ℵ_{1}. Acknowledgement. We are grateful to Lutz Heindorf for his thoughtful comments on an earlier version of this paper, and for alerting us to [HaPl97].

1. Preliminaries

We define here some of the notation that we will use, and we quote several well-known theorems and corollaries from the calculus of partitions. 1.1. Definition. We fix a set R = {<, >, =, ∥} of 4 symbols. For any p.o. (L, ≤) we define R: L × L → R in the obvious way: R(x, y) = < iff x < y, etc. 1.2. Definition. Let (L, ≤) be a partial order.

(1) We say that a set A ⊆ L is “co-well-ordered” iff (A, ≥) is a well-ordered set.

(2) We call a set A ⊆ L “uniform” iff A is either an antichain, or a well-ordered chain, or a co-well-ordered chain.

(3) If A is well-ordered we say that the type of A is “<”. Similarly we define the types “>” and “∥”. [This notation is ambiguous if A is finite. However, we are mainly interested in (large) infinite sets anyway, so this ambiguity will not cause any problems.]

(4) Let A_{i} ⊆ L for i ∈ I. We call (A_{i} : i ∈ I) “canonical” if the following conditions hold:

(a) each A_{i} is uniform, all A_{i} are of the same type,

(b) there is a function F: I × I → R such that:

∀i, j ∈ I : i ≠ j ⇒ ∀a ∈ A_{i} ∀b ∈ A_{j} : R(a, b) = F (i, j).

Loosely speaking, this says that whenever i ≠ j, then either A_{i} lies “completely above” A_{j}, or conversely, or A_{i} is “completely incomparable” with A_{j}.

1Pedants are invited to insert the necessary disclaimer themselves.

1.3. Definition. For any set A, [A]^{2} is the set of unordered pairs from A:

[A]^{2} = {{x, y} : x, y ∈ A, x ≠ y}

When we consider a set A together with an 1-1 enumeration A = {a_{i} : i < κ}, we usually identify the unordered pair {a_{i}, a_{j}} ∈ [A]^{2} with the ordered pair (a_{i}, a_{j}) whenever i < j.

1.4. Definition. Let κ, λ and c be cardinals. The “partition symbol”

λ → (κ)_{c}^{2}

means: Whenever F: [L]^{2} → C, where |L| = λ, |C| = c, then there is an “F -homogeneous set” K ⊆ L of cardinality κ, i.e., a set K such that F ↾[K]^{2} is constant.

(In other words, whenever the edges of the complete graph on λ many vertices are colored with c colors, then there is a complete subgraph with κ many vertices all of whose edges have the same color.)

1.5. Definition. Let (L, ≤) be a partial order. We will try to get some information on the structure of L by considering certain “cardinal characteristics” μ(L) and ν(L), which are defined as follows:

(1) We let μ(L) be the smallest cardinal μ such that there is no uniform set A ⊆ L of cardinality μ. In other words, κ < μ(L) iff there is a uniform subset A ⊆ L of size κ.

(2) We let μ_{n}(L) = μ(L^{n}) for n > 0.

(3) We let ν(L) be the smallest cardinal ν such that there is no family (f_{i} : i < ν) of ν many pairwise incomparable monotone functions from L to L. (Functions are ordered pointwise.)

(4) ν_{n}(L) is the smallest cardinal ν such that there are no pairwise incomparable monotone functions (f_{i} : i < ν) from L^{n} to L.

(5) More generally, ν(L_{1}, L_{2}) is the the smallest cardinal ν such that there are no pairwise incomparable monotone functions (f_{i} : i < ν) from L_{1} to L_{2}.

(6) μ_{∞} = sup{μ_{n} : n ∈ ω}, ν_{∞} = sup{ν_{n} : n ∈ ω}. (Note that trivially μ_{n} ≤ μ_{n+1} and ν_{n} ≤ ν_{n+1} for all n ∈ ω.)

1.6. Fact. Let L be infinite. Then μ_{n}(L) ≤ |L|^{+} and ν(L) ≤ (2^{|L|})^{+}.

1.7. Theorem (Ramsey). For any natural number k, ℵ_{0} → (ℵ_{0})_{k}^{2}.

Proof. See [EHMR, 10.2].

1.8. Theorem (Erdős+Rado). For any infinite κ, (2^{κ})^{+} → (κ^{+})_{κ}^{2}.

Proof. See [EHMR, 17.11(32)].

1.9. Theorem (Erdős+Rado).

(1) If κ is an infinite cardinal, k finite, then (2^{<κ})^{+} → (κ)_{k}^{2}.

(2) If κ is a strong limit cardinal, then

κ^{+} → (κ)_{4}^{2}

Proof. [EHMR, 15.2] proves a theorem that is stronger than (1). (2) is a special case of (1).

1.10. Corollary. Let (L, ≤) be a partial order.

(a) If κ is an infinite cardinal, |L| > 2^{κ}, then μ(L) > κ. (In fact, μ(L) > κ^{+}.)

(a’) |L| ≤ 2^{μ(L)}.

(b) If L is infinite, then μ(L) > ℵ_{0}.

(c) If κ is a strong limit cardinal, then κ ≤ μ(L) iff κ ≤ |L|.

(d) If κ is a strong limit cardinal, then |L| > κ implies μ(L) > κ,

(e) If κ is a strong limit cardinal, then μ(L) = κ implies |L| = κ.

Proof.

(a) Write ρ for (2^{κ})^{+}. Let (a_{i} : i < ρ) be distinct elements of L, and define F: [ρ]^{2} → R by requiring F (i, j) = R(a_{i}, a_{j}) whenever i < j. The Erdős-Rado theorem 1.8 promises us an F -homogeneous set {i_{ζ} : ζ < κ^{+}} of size κ^{+}, which will naturally induce a uniform set {a_{i_{ζ}} : ζ < κ^{+}} of the same cardinality.

(a’) follows from (a).

The proofs of (b) and (d) are similar, using 1.7 and 1.9, respectively, instead of 1.8.

(c) follows easily from 1.6. (e) follows from (c) and (d).

1.11. Canonization Theorem (Erdős+Hajnal+Rado). Let λ be an infinite cardinal, (A_{i} : i < λ) be a family of pairwise disjoint sets. Let (κ_{i} : i < λ) be infinite cardinals satisfying 2^{κ_{i}} < 2^{κ_{j}} whenever i < j, and assume |A_{i}| > 2^{κ_{i}}. Let f be a function with domain [A]^{2}, where A = ⋃_{i<λ} A_{i}, and let the range of f be small (say: finite). Moreover, assume κ_{0} ≥ 2^{λ}.

For α ∈ A write i_{α} for the unique i such that α ∈ A_{i}.

Then there are sets (A′_{i} : i < λ), |A′_{i}| = κ_{i}, A′_{i} ⊆ A_{i}, such that for α, β ∈ A′ (:= ⋃_{i<λ} A′_{i}), f(α, β) depends only on i_{α} and i_{β}.

That is, there is a function F with domain [λ]^{2} ∪ λ such that for all α ≠ β in A′, f(α, β) = F (i_{α}, i_{β}).

Proof. See [EHMR, 28.1].

1.12. Corollary. Let λ = cf(κ) < κ, κ a strong limit cardinal, |L| = κ, (L, ≤) a partial order. Then there is is a family (A_{ζ} : ζ < λ) of subsets of L satisfying (1) (A_{ζ} : ζ < λ) is canonical. (See 1.2(4).)

(2) The sequence (|A_{ζ}| : ζ < λ) is strictly increasing.

(3) sup{|A_{ζ}| : ζ < λ} = κ.

(4) For all ζ < λ: |A_{ζ}| > λ. Proof. Find an increasing sequence (κ_{i} : i < λ) of cardinals such that 2^{κ_{i}} < κ_{i+1} for all i. Let (a_{α} : α < κ) be distinct elements, and let A_{i} := {a_{α} : κ_{i+3} < α < κ_{i+4}} for i < λ. Thus, A := ⋃_{i<λ} A_{i} is a disjoint union, and |A_{i}| = κ_{i+4} > 2^{κ_{i}}. (Note that in this enumeration each set A_{i} comes “before” A_{j} for i < j.)

Define f: [A]^{2} → R by letting f({a_{α}, a_{β}}) = R(a_{α}, a_{β}) for α < β, and apply the canonization theorem 1.11.

The resulting sets (A′_{i} : i < λ) will be canonical. 1.13. Remark. If (κ_{i} : i < λ) is increasing with limit κ, then ∏_{i} κ_{i} = κ^{λ}. If moreover (as in our case) κ is a strong limit cardinal, then κ^{λ} = 2^{κ}. Proof. See [Jech, 6.4]

2. Partial maps

We want to give lower estimates for ν(L), and then translate them to lower estimates for μ(L). (See 1.5 for the definitions of μ and ν.)

Since we will typically only construct many partial functions that are pairwise incomparable, we have to give a sufficient condition that allows us to extend partial monotone functions to total monotone functions. 2.1. Fact. Let L_{1}, L_{2} be partial orders. If f: L_{1} → L_{2} is a partial monotone function whose range is contained in a complete partial order L′_{2} ⊆ L_{2}, then f can be extended to a total monotone function f̂: L_{1} → L_{2}.

Proof. Let f̂(x) = sup_{L′_{2}}{f(y) : y ∈ dom(f), y ≤ x}.

2.2. Corollary. Let L be a partial order, Ā ⊆ L a complete partial order. (Note: We only require that least upper bounds exist in (Ā, ≤), we do not care if these bounds are also least upper bounds in L.)

Then for any A ⊆ Ā we have ν(L) ≥ ν(A). Proof. Every monotone map f: A → A can be extended to a monotone map f̂: L → Ā. If f, g are incomparable, then so are f̂, ĝ.

So we will show that ν(L) is large by showing that ν(A) is large, for some sufficiently “nice” A.

In our treatment, “nice” means in particular “complete” (as a partial order), or at least “contained in a complete p.o.” Here the following lemma, due to Kaiser and Sauer [KaSa93] will be helpful:

2.3. Lemma. If (L, ≤) is an o.p.c. lattice, then L is bounded (i.e., has a greatest and a smallest element).

Proof. See [KaSa93].

Our method to make ν(A) large will be multiplication: If A_{1}, A_{2}, … are sufficiently “independent” (in a sense to be made precise below), and f_{i} : A_{i} → A_{i} are monotone, then we will show that they can be combined to give a monotone function from A := ⋃_{i} A_{i} to A.

2.4. Independence Lemma. Let L be a partial order, A = ⋃_{i<λ} A_{i} ⊆ L and assume that (A_{i} : i < λ) is canonical. Then:

(1) Whenever (f_{i} : i < λ) is a family of functions, each f_{i} : A_{i} → A_{i} monotone, then the function f := ⋃_{i<λ} f_{i} is a monotone function from A to A.

(2) If B is a partial order, (f_{i} : i < λ) is a family of functions, each f_{i} : A_{i} → B monotone, and if ⋃_{i} A_{i} is an antichain, then ⋃_{i} f_{i} is monotone from A to B.

(3) Moreover, if (f_{i} : i < λ) and (f′_{i} : i < λ) are both as in (1) or (2), and for some j the functions f_{j} and f′_{j} are incomparable, then also ⋃_{i} f_{i} and ⋃_{i} f′_{i} are incomparable.

(4) If κ_{i} < ν(A_{i}) for i < λ, then ν(A) > ∏_{i<λ} κ_{i}.

(5) If κ_{i} < ν(A_{i}, B) for i < λ, and A = ⋃_{i<λ} A_{i} is an antichain, then ν(A, B) > ∏_{i<λ} κ_{i} (where B is an arbitrary partial order)

Proof.

(1) Let F: I × I → R witness that (A_{i} : i ∈ I) is canonical. To check that f is monotone, consider an arbitrary pair a ≤ b in A.

Now either there is a single i with a, b ∈ A_{i} then f(a) ≤ f(b) (because f↾A_{i} = f_{i} is monotone), or we have i ≠ j, a ∈ A_{i}, b ∈ A_{j}. But then we must have F (i, j) = <, so (since f(a) ∈ A_{i}, f(b) ∈ A_{j}), we again have f(a) ≤ f(b).

(2) and (3) are easy.

(4) follows from (1) and (3), and (5) follows from (2) and (3).

Now that we know how to get pairwise incomparable functions by multiplication, we have to look more closely at the factors in this product. The factors are of the form ν(A), where A is a uniform set. The computation of this cardinal characteristic turns out to be easy:

2.5. Fact.

(a) If A uniform, |A| > 2, then ν(A) > 2.

(b) If A is uniform, |A| = κ ≥ ℵ_{0}, then ν(A) > 2^{κ}, i.e., there are 2^{κ} many pairwise incomparable monotone functions from A to A.

(c) If A is an antichain, |A| = κ ≥ ℵ_{0}, then 2^{κ} < ν(A, {0, 1}), i.e., there are 2^{κ} many incomparable (necessarily monotone) functions from A into the two-element lattice {0, 1}.

Proof.

(a) Left to the reader.

(b) This is is trivial if A is an antichain. So wlog assume that A is well-ordered. Write A as a union of κ many disjoint convex sets ⋃_{i<κ} A_{i}, each A_{i} of cardinality > 2. Then (A_{i} : i ∈ I) is canonical. So we can apply (a) and the independence lemma 2.4(4), and get ν(A) > ∏_{i<κ} 2 = 2^{κ}.

(c): Let A = ⋃_{i} A_{i}, where each A_{i} is of size > 2, and the A_{i} are pairwise disjoint. Clearly ν(A_{i}, {0, 1}) > 2, so by the independence lemma 2.4 ν(A, {0, 1}) > 2^{κ}.

3. μ and ν

We now turn our attention to the number μ_{n}(L).

3.1. Fact. If A ⊆ L^{n} is well-ordered of order type κ, then there is A′ ⊆ L, also well-ordered of order type κ.

Proof. Let ā^{i} = (a^{i}(1), …, a^{i}(n)) for i < κ, and i < j ⇒ ā^{i} < ā^{j}. For each k ∈ {1, …, n} the sequence (a^{i}(k) : i < κ) is weakly increasing. If the sequence (a^{i}(k) : i < κ) does not contain a strictly increasing sequence of length κ, then it must be eventually constant. However, this cannot happen for every k ∈ {1, …, n}.

Now we finally investigate the relation between μ and ν. It turns out to be slightly simpler if we look at μ_{∞} and ν_{∞} first.

First we show in 3.2 that the existence of many incomparable monotone functions from L^{n} to L (κ < ν_{n}(L)) implies the existence of a large antichain in some L^{m} (κ < μ_{m}(L)), assuming that L is o.p.c. (This is actually the only place in the whole proof where we talk about lattices rather than general partial orders.)

Then we show in 3.3 that a large (anti)chain in L^{m} (κ < μ_{m}(L)) implies the existence of ∗very∗ many incomparable monotone functions from L^{m} to L (2^{κ} < ν_{m}(L)).

These two lemmata are (with minor modifications) taken from [HaPl97]. Finally in 3.4 we combine 3.2 and 3.3 to show that μ = μ_{∞} must be

a strong limit cardinal.

3.2. Lemma. Let (L, ≤) be an o.p.c. lattice, κ a cardinal of uncountable cofinality. If κ < ν_{n}(L), then κ < μ_{∞}(L). In particular:

(A) ν_{∞} ≤ μ_{∞}^{+} (B) ν_{∞} ≤ μ_{∞}, if μ_{∞} has uncountable cofinality.

Proof. Assume κ < ν_{n}(L). Let (f_{i} : i < κ) be pairwise incomparable functions from L^{n} to L. Since L is o.p.c., each of these functions is a polynomial function. Thus, for each i there is some natural number k_{i} and a lattice-theoretic term t_{i}(x_{1}, …, x_{n}, y_{1}, …, y_{k_{i}}) and a k_{i}-tuple b̄^{i} = (b_{1}^{i}, …, b_{k_{i}}^{i}) such that for all a_{1}, …, a_{n} we have f_{i}(a_{1}, …, a_{n}) = t_{i}(a_{1}, …, a_{n}, b_{1}, …, b_{k_{i}}).

Since there are only countably many pairs (t_{i}, k_{i}) and we have assumed cf(κ) > ℵ_{0}, we may assume that they all are equal, say to (t^{∗}, k^{∗}). But then (b̄^{i} : i < κ) must be pairwise incomparable in L^{k^{∗}}, because b̄^{i} ≤ b̄^{j} would imply f_{i} ≤ f_{j}. Hence we have found an antichain of size κ in L^{k^{∗}}.

To get (A), let κ := μ_{∞}^{+}, so cf(κ) > ℵ_{0} and therefore “κ < ν_{∞}” is impossible. To get (B), let κ = μ_{∞}.

From now on we can forget about lattices as long as we only consider partial orders having properties 3.2(A) and 3.2(B).

3.3. Lemma. Let (L, ≤, 0, 1) be a bounded partial order, κ an infinite cardinal. If κ < μ_{n}(L), then 2^{κ} < ν_{n}(L). In particular, κ < μ_{∞} implies 2^{κ} < ν_{∞}.

Proof. Let A ⊆ L^{n} be uniform of size κ.

Case 1: A is a chain, so by 3.1 wlog n = 1. Let Ā = A ∪ {0, 1}. By fact 2.5, ν(A) > 2^{κ}. Since Ā is a complete partial order, we may apply fact 2.1 to get ν(L) ≥ ν(A). Hence ν(L) > 2^{κ}.

Case 2: A is an antichain. Use 2.5(c).

3.4. Conclusion. If L is infinite and o.p.c., (or, slightly more generally, if L is an infinite bounded partial order satisfying the conclusion of 3.2), then

(a) μ_{∞}(L) must be a strong limit cardinal,

(b) μ(L) = μ_{∞}(L)

(c) |L| = μ(L).

(d) ν(L) = |L|.

Proof.

(a) If κ < μ_{∞}(L), then 2^{κ} < ν_{∞}(L) by 3.3. Now 2^{κ} always has uncountable cofinality, so we get 2^{κ} < μ_{∞}(L) by 3.2.

(b) Assume that μ(L) < μ_{∞}(L). Let λ = 2^{2^{μ(L)}} < μ_{∞}(L). By 1.10, |L| ≤ 2^{μ(L)} < λ, so μ_{n}(L) ≤ |L|^{+} ≤ λ for all n ∈ ω, hence μ_{∞}(L) ≤ λ, a contradiction.

(c) Use 1.10(e).

(d) 3.2(B) implies ν(L) ≤ ν_{∞}(L) ≤ μ(L), and 3.3 implies μ_{1}(L) ≤ ν_{1}(L).

4. The main lemma

We have already shown that for an o.p.c. lattice L the cardinal characteristic μ(L) must be a strong limit cardinal. In this section we show that μ(L) must be regular.

Letting κ := μ(L) we first show that the singularity of κ would imply the existence of ≫ κ many incomparable monotone functions, and then show that this would imply μ(L) > κ.

4.1. Main Lemma. Let (L, ≤, 0, 1) be a bounded partial order, and let κ be a singular strong limit cardinal, κ ≤ |L|.

Then ν(L) > κ.

If moreover cf(κ) = ℵ_{0}, then we get even ν(L) > 2^{κ}.

Proof. Let λ = cf(κ). The first step in the proof of 4.1 is to find a canonical family (A_{i} : i < λ) which is large, i.e., | ⋃_{i} A_{i}| = κ, and ∏_{i<λ} |A_{i}| = κ^{λ} = 2^{κ}. If the set A := ⋃_{i} A_{i} happens to be a chain or antichain , we easily get 2^{κ} many pairwise incomparable monotone functions. Using the independence lemma we will show that already the canonicity of A is sufficient to get many monotone functions.

In step 3 we will exhibit many pairwise incomparable (partial) functions from A to A, so in step 2 we may have to massage (A_{i} : i < λ) a bit to guarantee that these functions can be extended to total functions on L.

What actually happens in steps 2 and 3 depends on whether λ is countable or not.

Step 1. Let A = {a_{i} : i < κ} be distinct elements of our partial order. For i < j < κ let f(i, j) = R(a_{i}, a_{j}). (Recall 1.1.)

By the canonization theorem (or rather, by its corollary 1.12) we may (after thinning out our set A) wlog assume that A = ⋃_{ζ<λ} A_{ζ}, where the cardinalities |A_{ζ}| are increasing with supremum κ, λ < |A_{ζ}| < κ, and (A_{ζ} : ζ < λ) is canonical. Let ξ : κ → λ be such that for all i < κ, a_{i} ∈ A_{ξ_{i}}. So there is a function F: [λ]^{≤2} → {<, >, ∥} such that R(a_{i}, a_{j}) = F ({ξ_{i}, ξ_{j}}) for all i < j < κ.

We may assume {0, 1} ∩ A = ∅. Let Ā = A ∪ {0, 1}.

[figure: A_{0}; A_{1}; A_{2}; ⋮; ⋮; ⋮; A_{0}; A_{1}; A_{2}; or; or; A_{0}; A_{1}; A_{2}]

Figure 1

Note that

∏_{ξ<λ} |A_{ξ}| = κ^{cf(κ)} = 2^{κ}.

Step 2, case a. Let us asume λ = ℵ_{0} for the moment. So we have a canonical sequence (A_{n} : n ∈ ω), witnessed by F: [ω]^{2} → {<, >, ∥}. By Ramsey’s theorem 1.7 there is an infinite set X ⊆ ω such that F is constant on [X]^{2}. By dropping some elements of the sequence (A_{n} : n ∈ ω) [i.e., replacing (A_{n} : n ∈ ω) by (A_{n} : n ∈ X), and then for notational simplicity only pretending that X = ω] we may assume that F is constant, say

∀n ∀k : n < k ⇒ ∀a ∈ A_{n} ∀b ∈ A_{k} : R(a, b) = c

There are (at most) 9 possible types of our family (A_{n} : n ∈ ω): Each A_{n} can be well-ordered, co-well-ordered, or an antichain, and there are also 3 possible values for c. For example, if c =“<”, then the set A has one of the 3 forms given in the figure 1.

However, our construction of a large family of incomparable functions will be “uniform”, i.e., be the same in all cases. Note that if c ∈ {<, >} and each A_{n} is an antichain (leftmost possibility in the above picture), then ⋃_{n} A_{n} is not a complete partial order, since every element of A_{n+1} is a minimal upper (or maximal lower) bound for any nontrivial subset of A_{n}.

For each k we let A′_{2k+1} be a singleton subset of A_{2k+1}, and we let A′_{2k} = A_{2k}. Now let B := ⋃_{n} A′_{n} ∪ {0, 1}.

•• A_{0} A_{2} A_{4} A_{1} A_{3} ⋮ Figure 2

Step 3, case a. We are still assuming λ = ℵ_{0}. It is easy to see (by considering cases — one of them is sketched in figure 2) that the set B defined in step 2 (case a) is a complete partial order. We leave the details to the reader.

Note that we still have ∏_{n<ω} |A′_{n}| = ∏_{n∈ω} |A′_{2n}| = κ^{λ} = 2^{κ}, since the cardinalities (|A_{2n}| : n ∈ ω) are also increasing to κ.

By 2.2 and the independence lemma 2.4, ν(L) ≥ ν(A) > 2^{κ}. This concludes the discussion of the case λ = ℵ_{0}.

Step 2, case b. Now we assume λ > ℵ_{0}. Note that now we are only aiming for κ many pairwise incomparable monotone functions. Again let F: λ × λ → {<, >, ∥} witness canonicity.

By dropping some of the sets A_{ζ} we may assume that the function ζ ↦ F (0, ζ) is constant, say with some value c_{0}. Thinning out three more times we may assume that there are constants c_{0}, c_{1}, c_{2}, c_{3} ∈ {<, >, ∥} such that

(a) ∀ζ > 0, F (0, ζ) = c_{0}

(b) ∀ζ > 1, F (1, ζ) = c_{1}

(c) ∀ζ > 2, F (2, ζ) = c_{2}

(d) ∀ζ > 3, F (3, ζ) = c_{3} Choose i_{0} < i_{1} ∈ {0, 1, 2, 3} such that c_{i_{0}} = c_{i_{1}}, write A_{∗} for A_{i_{0}}, let

a_{∗} be any element of A_{i_{1}}, and let c_{∗} = c_{i_{0}}.

Depending on the value of c_{∗} we now have one the following possibilities:

(a) either every element of A_{∗} is incompatible with every element of any A_{ζ}, ζ > 4,

(b) or we have for all ζ > 4:

∀x ∈ A_{∗} ∀y ∈ A_{ζ} : x < a_{∗} < y

(c) or the dual of (b) is true.

Step 3, case b. Since all sets A_{ζ} are infinite, we have ν(A_{ζ}) > |A_{ζ}|, so we can find pairwise incomparable monotone functions (f_{ζ,i} : i ∈ A_{ζ}) from A_{ζ} to A_{ζ}.

Let f^{∗} be the identity function on {a^{∗}}, and let (f_{∗,ζ} : 4 < ζ < λ) be a family of pairwise incomparable monotone functions from A_{∗} to A_{∗}. (Recall that all our sets A_{ζ} had cardinality λ, so it is possible to find that many functions.)

Note that for 4 < ζ the family (A_{∗}, {a_{∗}}, A_{ζ}) is canonical, so by the independence lemma we can conclude that f_{∗,ζ} ∪ f_{∗} ∪ f_{ζ,i} is a monotone function. Moreover, {0, 1, a_{∗}, } ∪ A_{∗} ∪ A_{ζ} is a complete partial order (again we leave the easy task of checking this fact to the reader), so by 2.1 the function f_{∗,ζ} ∪ f_{∗} ∪ f_{ζ,i} can be extended to a total monotone function f̂_{ζ,i} : L → L.

Clearly any two functions f̂_{ζ,i}, f̂_{ζ′,i′} are incomparable: If ζ ≠ ζ′ then this is due to the incomparability of f_{∗,ζ} and f_{∗,ζ′}, and for ζ = ζ′ we use the incomparability of f_{ζ,i} and f_{ζ,i′}.

Note that the cardinality of the index set {(ζ, i) : 4 < ζ < λ, i ∈ A_{ζ}} is κ.

This concludes the discussion of the case λ > ℵ_{0}, and hence also the proof of the main lemma.

4.2. Conclusion. If (L, ≤) is an o.p.c. lattice (or, slightly more generally, if L is a partial order satisfying the conclusion of 3.2), then μ(L) = |L| is an inaccessible cardinal.

Proof. Let κ = μ(L). From 3.4 we know that κ is a strong limit, and that |L| = κ. Assume that κ is singular.

First assume that cf(κ) is uncountable. The main lemma tells us that ν(L) > κ, so by 3.2 we conclude μ_{∞}(L) > κ, a contradiction.

Now we consider the second case: cf(κ) = ℵ_{0}. Here the main lemma tells us ν(L) > 2^{κ}. Since 2^{κ} has uncountable cofinality, we can again apply 3.2 and again get μ_{∞}(L) > 2^{κ} > κ, a contradiction.

4.3. Remark. Note that the cardinality of an o.p.c. lattice cannot be a weakly compact cardinal.

References

[EHMR] 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.

[GoSh 554] Martin Goldstern and Saharon Shelah. A partial order where all monotone maps are definable. Fundamenta Mathematicae, 152:255–265, 1997.

[Jech] Thomas Jech. Set Theory. Pure and Applied Mathematics. Academic Press, New York, San Francisco, London, 1978.

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

[HaPl97] Miroslav Ploščica and Miroslav Haviar. On order-polynomial completeness of lattices. Algebra Universalis, to appear.

Algebra und Diskrete Mathematik, Technische Universität Wien, Wiedner Hauptstraße 8-10/118.2, A-1040 Wien, Austria

Current address: Mathematik WE 2, Freie Universität, Arnimallee 3, D-14195 Berlin, Germany

  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