Help visualize set of all equivalence relations

166 Views Asked by At

I want to prove that the poset $Eq(A)$ with $\subseteq$ as the partial ordering is a complete lattice.

But before even beginning to prove it, I have trouble visualizing the poset of $Eq(A)$. Kindly help me with providing a set of equivalence relations on a finite set $S = (a,b,c)$

1

There are 1 best solutions below

2
On BEST ANSWER

First you should recognize that each equivance relation on a set S can be identified with a partition of S into equivalence classes. For example, the equivance relation {(a,a), (b, b), (c, c), (a, c), (c, a)} corresponds to the partition |a, c|b|.

It is less tedious to write down all the partitions than it is to write down all the equivalence relations, and we can draw the Hasse diagram of partitions of the set {a, b, c}, which will be isomorphic to Eq(3):

|a, b, c|

|a, b|c| |a, c|b| |a|b, c|

|a|b|c|

Now you should try to draw Eq(4). Hint: it is a 15 element lattice of height 3 (I.e. there are 4 "levels").

Update: (in response to your request for more details)

The set of equivalence relations on the set $S = \{a, b, c\}$ is $Eq(S) = \{0_S, \alpha_1, \alpha_2, \alpha_3, 1_S\}$, where

$$1_S= \{(a,a), (b, b), (c, c), (a, c), (c, a), (a,b), (b,a), (c,b), (b,c)\},$$

$$\alpha_1 = \{(a,a), (b, b), (c, c), (a, c), (c, a)\},$$

$$\alpha_2 = \{(a,a), (b, b), (c, c), (a, b), (b, a)\},$$

$$\alpha_3 = \{(a,a), (b, b), (c, c), (b, c), (c, b)\},$$

$$ 0_S = \{(a,a), (b, b), (c, c)\}.$$

As you know, binary relations are subsets of the set $S\times S$, and as such they can be partially ordered under set inclusion. Clearly, $0_S \subseteq \alpha_i \subseteq 1_S$ for each $i = 1,2,3,$ and $\alpha_i \nsubseteq \alpha_j$ for $i\neq j$.

Define the meet and join operations on $Eq(S)$ in terms of the $\subseteq$ partial order.

The Hasse diagram looks something like this:

$$1_S$$

$$\alpha_1 \quad \alpha_2 \quad \alpha_3$$

$$0_S$$