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 Con_c 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 Con_cU L the (∨,0)-subsemilattice of Con_c 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 x₀, x₁ 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 μ: Con_c 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 ℵ₂ by Růžička.

Theorem (Růžička 2008). The semilattice G(Ω) is not isomorphic to Con_c L for any lattice L, whenever the set Ω has at least ℵ₂ 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:

“Certainly, young children can begin to practice making letters and numbers and solving problems, but this should be done without workbooks. Young children need to learn initiative, autonomy, industry, and competence before they learn that answers can be right or wrong.”
—David Elkind (20th century)

“The new concept of the child as equal and the new integration of children into adult life has helped bring about a gradual but certain erosion of these boundaries that once separated the world of children from the word of adults, boundaries that allowed adults to treat children differently than they treated other adults because they understood that children are different.”
—Marie Winn (20th century)