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.

I was referring to this article here related to the formation of a complete lattice by the partitions of a set. The article has stated that the partitions not only form the lattice for themselves but also for the equivalence relations.

I know that each partition has a corresponding equivalence relation. However, I don't get the derivation here in this article.

Things like the following

$$ a \equiv b(modE) $$

I didn't get the things given in the remarks specially after it says

Correspondingly, the partition lattice of S also defines the lattice of equivalence relations $\Delta$ on S

Any guidance pls?

It mentions that

Given a family $\{E_i|i \in I\}$ of equvialence relations on S , we can explicitly describe the join E:=V $E_i$ of $E_i$ , as follows:

$a\equiv b$(modE) iff there is a finite sequence

$a=c_1,c_2,...c_n=b$ such that

$c_k \equiv c_{k+1}(modE_{i(k)})$ for $k=1,..n−1 $

I didn't get this one as well. Can anyone please provide some examples so that it is easier for me to visualize.

share|improve this question
    
$a \equiv b(\text{mod}E)$ means that $a$ and $b$ lie in the same cell of $E$. –  Michael Greinecker Sep 12 '12 at 11:23
    
@Michael, we have cells only in the partition isn't it? So you mean in the same cell of the partition equivalent to the equivalence relation E isn't it? –  user34790 Sep 12 '12 at 13:27
    
Yes. Actually, in the present context of equivalence relations it simply means $aEb$. –  Michael Greinecker Sep 12 '12 at 13:49
    
@Michael, I have also added one more thing that I didn't understand in the original question. Can you give me some examples like with a set A and make it clear to me. I think if I visualize with examples it will be clear to me –  user34790 Sep 12 '12 at 13:53
    
Please don't change the question. I can explain these things to you on chat: chat.stackexchange.com/rooms/36/mathematics –  Michael Greinecker Sep 12 '12 at 13:54
show 1 more comment

1 Answer

Let $\Pi$ be a partition on a set $X$ and $E(\Pi)$ be the corresponding equivalence relation on $X$ given by $x E(\Pi) y$ iff $x$ and $y$ are in the same element of $\Pi$. We say the partition $\Pi_1$ is finer than the partition $\Pi_2$ if every element in $\Pi_2$ is a union of elements in $\Pi_1$. One can then show that $\Pi_1$ is finer than $\Pi_2$ iff $E(\Pi_1)\subseteq E(\Pi_2)$. So the function that maps each partition to the corresponding equivalence relation is an order isomorphism between "finer than" and $\subseteq$.

Since being a complete lattice is preserved under order isomorphisms, it follows from the set of all partitions on $X$ ordered by "finer" being a complete lattice that the set of all equivalence relations on $X$ ordered by $\subseteq$ is a complete lattice too.

I would recommend for you to take a look on a book containing the basics of order and lattice theory, to understand all the concepts involved. The book Introduction to Lattices and Order by Davey and Priestley is quite readable.

share|improve this answer
add comment

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.