Let $L$ be a lattice and let $a,b,c,d \in L$. Show that:

  1. $\theta(a,b) \subseteq \theta(c,d)$ iff $\langle a,b\rangle \in \theta(c,d)$

  2. $\theta(a,b)=\theta(a \wedge b, a \vee b)$

Where $\theta$ is a congruence. Definition: given a lattice $L$, a congruence $\theta$ on $L$ is an equivalence relation, compatible with the lattice operations, i.e. if $x_1\theta x_2$ and $y_1 \theta y_2$, then $x_1 \wedge x_2 \theta y_1 \wedge y_2$ and $x_1 \vee x_2 \theta y_1 \vee y_2$.

I specially have a problem with the first part, how to prove that it is a subset. The part of $\Leftarrow$ seems "evident", I have 2 elements, $a,b$, I assume they belong to the congruence, so they have to be inside, but I don't get the more formal way to explain this. For the $\Rightarrow$ part, I assume that $\theta (a,b) \subseteq \theta (c,d)$, so I think I have to argue that all the elements of a subset have a certain characteristic, so in particular $a,b$ have it. Again, if this is right, I am having trouble translating it into a proper proof.

About the second one, I can only think of proving it in a way similar to let $a= a\wedge b$ so $b = a\vee b$ (I have a lemma that $a= a\wedge b$ iff $b = a\vee b$). But it seems like there is something missing. I would very much appreciate your help to sort this out, and your input on how I can write this properly.

  • $\begingroup$ What does $\theta(a,b)$ mean? $\endgroup$ – bof Jan 29 '15 at 12:49
  • $\begingroup$ The notation is a bit weird, honestly, it's part of what got me stuck, it doesn't fit with that on most sources. For what I understand, $\langle a,b \rangle$ means exactly the elements a and b, while $\theta (a,b)$ would mean the elements that are delimited by a and b that are part of the congruence. Does that sound plausible? Thank you for your answer. $\endgroup$ – Sara Jan 29 '15 at 12:56
  • $\begingroup$ I can't say it's plausible or not, because I still don't know what it means. "The elements that are delimited by $a$ and $b$ that are part of the congruence" is Greek to me. Sorry. $\endgroup$ – bof Jan 29 '15 at 14:01
  • $\begingroup$ $\theta(a, b)$ is the usual notation for the congruence generated by the pair $\langle a, b \rangle$, but I'm not quite sure. $\endgroup$ – Random Jack Jan 29 '15 at 15:40

First of all, lattice $L$ in your question is not supposed to be distributive (but the title uses this word). If $\theta(a, b)$ means the congruence generated by $\langle a, b \rangle$ then:

  1. If $\theta(a, b) \subseteq \theta(c, d)$ then (since $\theta(a, b)$ is generated by $\langle a, b \rangle$) we have $$\langle a, b \rangle \in \theta(a, b) \subseteq \theta(c, d) \Rightarrow \langle a, b \rangle \in \theta(c, d).$$ Conversely, if $\langle a, b \rangle \in \theta(c, d)$ then since $\theta(a, b)$ is the smallest congruence containing pair $\langle a, b \rangle$ and $\theta(c, d)$ is some congruence containing this pair we have $\theta(a, b) \subseteq \theta(c, d)$.

  2. We want to show two inclusions, which are equivalent (by the first part) to showing that generating pair belongs to congruence. To show that $\langle a, b \rangle \in \theta(a \wedge b, a \vee b)$ observe that: $$a = a \vee (a \wedge b) \theta(a \wedge b, a \vee b) a \vee (a \vee b) = a \vee b,$$ $$b = b \vee (a \wedge b) \theta(a \wedge b, a \vee b) b \vee (a \vee b) = a \vee b,$$ which means that $a \theta(a \wedge b, a \vee b) b$ and hence $\langle a, b \rangle \in \theta(a \wedge b, a \vee b)$. To show that $\langle a \wedge b, a \vee b \rangle \in \theta(a, b)$ observe that: $$ a \wedge b \theta(a, b) a \wedge a = a = a \vee a \theta(a, b) a \vee b,$$ which means that $a \wedge b\theta(a, b)a \vee b$, and hence $\langle a \wedge b, a \vee b \rangle \in \theta(a, b)$. By the first part we have both inclusions and hence $\theta(a, b) = \theta(a \wedge b, a \vee b).$

| cite | improve this answer | |
  • $\begingroup$ Hi thank you very much for the notation explanation and your answer, everything is much clearer now! $\endgroup$ – Sara Jan 30 '15 at 17:08

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.