Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

$\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.

share|improve this question

1 Answer 1

up vote 5 down vote accepted

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$.

share|improve this answer
    
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. –  Miha Habič May 8 '12 at 9:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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