Congruence Lattice Problem - Solving CLP: The Erosion Lemma

Solving CLP: The Erosion Lemma

The following recent theorem solves CLP.

Theorem (Wehrung 2007). The semilattice G(Ω) is not isomorphic to Conc L for any lattice L, whenever the set Ω has at least ℵω+1 elements.

Hence, the counterexample to CLP had been known for nearly ten years, it is just that nobody knew why it worked! All the results prior to the theorem above made use of some form of permutability of congruences. The difficulty was to find enough structure in congruence lattices of non-congruence-permutable lattices.

We shall denote by ε the `parity function' on the natural numbers, that is, ε(n)=n mod 2, for any natural number n.

We let L be an algebra possessing a structure of semilattice (L,∨) such that every congruence of L is also a congruence for the operation ∨ . We put

 U\vee V=\{u\vee v \mid (u,v)\in U\times V\},\quad \text{for all }U,V\subseteq L,

and we denote by ConcU L the (∨,0)-subsemilattice of Conc L generated by all principal congruences Θ(u,v) ( = least congruence of L that identifies u and v), where (u,v) belongs to U ×U. We put Θ+(u,v)=Θ(u ∨ v,v), for all u, v in L.br />

The Erosion Lemma (Wehrung 2007). Let x0, x1 in L and let, for a positive integer n, be a finite subset of L with . Put

Then there are congruences, for j<2, such that

 z_0\vee x_0\vee x_1\equiv z_n\vee x_0\vee x_1 \pmod{\theta_0\vee\theta_1}\quad\text{and}\quad \theta_j\subseteq\alpha_j\cap\Theta_L^+(z_n,x_j),\text{ for all }j<2.

(Observe the faint formal similarity with first-order resolution in mathematical logic. Could this analogy be pushed further?)

The proof of the theorem above runs by setting a structure theorem for congruence lattices of semilattices—namely, the Erosion Lemma, against non-structure theorems for free distributive extensions G(Ω), the main one being called the Evaporation Lemma. While the latter are technically difficult, they are, in some sense, predictable. Quite to the contrary, the proof of the Erosion Lemma is elementary and easy, so it is probably the strangeness of its statement that explains that it has been hidden for so long.

More is, in fact, proved in the theorem above: For any algebra L with a congruence-compatible structure of join-semilattice with unit and for any set Ω with at least ℵω+1 elements, there is no weakly distributive homomorphism μ: Conc L → G(Ω) containing 1 in its range. In particular, CLP was, after all, not a problem of lattice theory, but rather of universal algebra—even more specifically, semilattice theory! These results can also be translated in terms of a uniform refinement property, denoted by CLR in Wehrung's paper presenting the solution of CLP, which is noticeably more complicated than WURP.

Finally, the cardinality bound ℵω+1 has been improved to the optimal bound ℵ2 by Růžička.

Theorem (Růžička 2008). The semilattice G(Ω) is not isomorphic to Conc L for any lattice L, whenever the set Ω has at least ℵ2 elements.

Růžička's proof follows the main lines of Wehrung's proof, except that it introduces an enhancement of Kuratowski's Free Set Theorem, called there existence of free trees, which it uses in the final argument involving the Erosion Lemma.

Read more about this topic:  Congruence Lattice Problem

Famous quotes containing the words solving and/or erosion:

    Cultural expectations shade and color the images that parents- to-be form. The baby product ads, showing a woman serenely holding her child, looking blissfully and mysteriously contented, or the television parents, wisely and humorously solving problems, influence parents-to-be.
    Ellen Galinsky (20th century)

    Inter-railers are the ambulatory equivalent of McDonalds, walking testimony to the erosion of French culture.
    Alice Thompson (b. 1963)