$\newcommand{\r}[1]{\mathrel{#1}}$ First, a few definitions. Given a lattice $L$, a congruence on $L$ is an equivalence relation $\theta$, compatible with the lattice operations, i.e. if $x_1\r{\theta}x_2$ and $y_1\r{\theta}y_2$, then $x_1\wedge x_2\r{\theta}y_1\wedge y_2$ and $x_1\vee x_2\r{\theta}y_1\vee y_2$. The congruences on $L$ form a lattice, with meet being intersection and join being the equivalence envelope.

I'm trying to prove that this lattice of congruences is distributive. So let's take three congruences $\theta_1,\theta_2,\theta_3$ and attempt to prove that $$\theta_1\cap(\theta_2\vee\theta_3)\subseteq (\theta_1\cap\theta_2)\vee(\theta_1\cap\theta_3)$$

For a start, let's try to prove something easier which should lead me to the general idea. Take elements $x,y,z$ such that $x\r{\theta_1}y,x\r{\theta_2}z$ and $z\r{\theta_3}y$. We want to prove that $x(\r{(\theta_1\cap\theta_2)\vee(\theta_1\cap\theta_3)})y$.

Start with $(x\wedge z)\r{\theta_1}(y\wedge z)$, which gives $x\r{\theta_1}((y\wedge z)\vee x)$. Similarly, $(x\wedge y)\r{\theta_2}(z\wedge y)$ and $x\r{\theta_2}((y\wedge z)\vee x)$. This gives $$x\r{(\theta_1\cap\theta_2)}((y\wedge z)\vee x)$$

I expect a similar manipulation should now give $$((y\wedge z)\vee x)\r{\theta_1\cap\theta_3} y$$ but I can't see how to manage this. Is this even in the right direction? I suppose something other than $((y\wedge z)\vee x$ could be the middle link, but nothing obviously better comes to mind.


I would use the fact that if $\theta_1$ and $\theta_2$ are congruences on $L$, and $x,y\in L$, then $x\,(\theta_1\lor\theta_2)\,y$ iff there is a chain $$x\land y=z_0\le z_1\le\dots\le z_n=x\lor y$$ such that whenever $0\le k<n$, $z_k\,\theta_2\,z_{k+1}$ or $z_k\,\theta_3\,z_{k+1}$.

Suppose that $x\,(\theta_1\cap(\theta_2\lor\theta_3))\,y$. Then $x\,(\theta_2\lor\theta_3)\,y$, so there is a chain $$x\land y=z_0\le z_1\le\dots\le z_n=x\lor y$$ such that whenever $0\le k<n$, $z_k\,\theta_2\,z_{k+1}$ or $z_k\,\theta_3\,z_{k+1}$. You also have $x\,\theta_1\,y$, so $(x\land y)\,\theta_1(x\lor y)$, and therefore $(x\land y)\,\theta_1\,z_k\,\theta_1(x\lor y)$ for $0\le k<n$. It follows that for $0\le k<n$, $z_k\,(\theta_1\cap\theta_2)\,z_{k+1}$ or $z_k\,(\theta_1\cap\theta_3)\,z_{k+1}$ and hence that $x\,\big((\theta_1\cap\theta_2)\lor(\theta_1\cap\theta_3)\big)\,y$.

| cite | improve this answer | |
  • $\begingroup$ Thanks! I didn't know this characterization of joins of lattice congruences; it took some thought to prove it, but after that things went smoothly. $\endgroup$ – Miha Habič May 8 '12 at 9:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.