0
$\begingroup$

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.

  • 0
    @Michael sure thanks. I have just joined the chat may be we can talk there – 2012-09-12

1 Answers 1

2

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.