[figure]

1-opc lattices

Martin Goldstern TU Wien

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

[figure]

opc lattices

Definition: A lattice 𝔏 = (L, ∨, ∧) is called “order-polynomially complete” (opc) iff

For all n, every monotone function f : 𝔏^{n} → 𝔏 is induced by a lattice polynomial.

𝔏 is called 1-opc if

Every unary monotone function f : 𝔏 → 𝔏 is induced by a lattice polynomial.

[figure]

Finite opc lattices

Theorem A: (Schweigert 1972) If L is finite, then

𝔏 is 1-opc ⟺ 𝔏 is opc

Proof: Lagrange interpolation. (Note: this yields a

very effective or explicit proof)

Example: Let A be any finite set with ≥ 3 elements. Then 𝔐_{A} is opc, where 𝔐_{A} = (M_{A}, ≤), M_{A} = A ˙∪ {0, 1}, A an antichain between 0 and 1.

⋯1 0A  𝔐_{A}

[figure]

Infinite opc lattices

[figure]

Theorem B: (G∗+Shelah, 1997-98) There are no infinite opc lattices. The proof of theorem B analyzes the properties that the cardinality of an infinite opc lattice must have: It cannot be countable, cannot be a successor cardinal (Erdős-Rado used here), cannot

be a singular limit (more infinite combinatorics used

here) and cannot be a limit of uncountable cofinality — hence does not exist. This approach made many people unhappy.

Problem 1:

Find a “purely algebraic” proof of theorem B.

Meta-Problem:

What does “purely algebraic” mean?

Problem 2:

Show that there are no infinite 1-opc lattices.

[figure]

What is “purely algebraic”?

An approximation to “purely algebraic”:

Let’s use less set theory!

Definition: We call a proof “explicit”, if it does not use the axiom of choice, i.e., if it can be carried out in ZF (Zermelo-Fraenkel axioms of set theory without the axiom of choice.)

Theorem “-B”: (G∗+Shelah, 1998)

There is no “explicit” proof of theorem B.

(Proof sketch see slide 9/11)

We can interprete this as a hint that there is no “purely algebraic” proof of theorem B.

[figure]

opc vs 1-opc

Conjecture C:

There are no infinite 1-opc lattices. Conjecture C’:

Every (infinite) 1-opc lattice is opc. Recall that for finite lattices: C=false, C’=true. By theorems A and B, we have: C ⇔ C’. Conjecture C trivially implies theorem B, so: By theorem -B, there is no explicit proof of C. But perhaps it is easier to find a proof of C’?

Theorem -C’: There is no explicit proof of C’.

[figure]

Proof of theorems -B and -C’ (sketch) An infinite set A is called “amorphous” if all subsets of A are either finite or cofinite; equivalently, if all subsets of A are definable with parameters from A in predicate logic with no predicates except equality. An infinite set A is called “strongly amorphous” if: for all n, all subsets of A^{n} are definable in predicate logic with equality, or equivalently, if all subsets of A^{n} are in the Boolean algebra generated by the sets

{(x_{1}, …, x_{n}) : x_{i} = x_{j}}: i, j ∈ {1, …, n}

{(x_{1}, …, x_{n}) : x_{i} = a}: i ∈ {1, …, n}, a ∈ A.

[figure]

Fact: If A is strongly amorphous, then all maps f : M_{A}^{n} → M_{A} (so in particular: all monotone maps f : 𝔐_{A}^{n} → 𝔐_{A}) are definable in predicate logic with equality. This can be used to show

If A is strongly amorphous, then 𝔐_{A} is infinite and opc.

Note: The existence of strongly amorphous sets is consistent with ZF (i.e., cannot be “explicitly” refuted).

[figure]

Similarly, the existence of a an infinite set A with an equivalence relation E satisfying

(a) All E-classes have exactly 3 elements

(b) All maps f : A^{n} → A, and even all maps f : M_{A}^{n} → M_{A}, can be defined in predicate logic using the predicates “E” and “=” only

is consistent with ZF. Now check that for such a set A, all unary monotone maps f : 𝔐_{A} → 𝔐_{A} are either almost constant or almost the identity, which in turn shows that they are represented by lattice polynomials. ⇒ 𝔐_{A} is 1-opc However, the binary map

f(x, y) = \{ \begin{matrix}1 & if x = 1 ∨ y = 1 ∨ x ∼_{E} y \\ x & otherwise \end{matrix}

is monotone and not represented by a lattice polynomial. ⇒ 𝔐_{A} is not opc

[figure]

Open Questions

Question: Show that there are no infinite 1-opc lattices.

(Equivalently, that 1-opc implies opc)

[We know that there is no explicit proof.]

The proof of theorem -C’ tells us that really there is no explicit proof of 1-opc ⇒ 2-opc. Question:

Is there an explicit proof of 2-opc ⇒ opc?

The proof of theorem -B really showed (explicitly) that 𝔐_{A} is definably opc, i.e.: .

Whenever f : 𝔐_{A}^{n} → 𝔐_{A} is a monotone function which is first order definable in the structure (𝔐_{A}, ≤), then f is represented by a polynomial.

Question: Find a lattice which is definably 1-opc but not definably opc.