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 am a beginner in this field. Actually, I am studying about equivalence relation. I found that the set of all equivalence relations possible on set A form a relation.

If R1 and R2 are two equivalence relations on set A, the least upper bound is given by trans($R1 \cup R2$) and the greatest lower bound is given by $R1 \cap R2$ where trans is the transitive closure.

I couldn't get what that means. Any insights examples that could help me?

I referred to this wiki article here

They have given the example of the is refinement of relation on the partitions of a set {1,2,3,4}. Since each partition has a corresponding equivalence relation, I want to know about the meet and join of the partitions.

enter image description here

For eg in the above is given the lattice formed by the partitions of set {1,2,3,4}. I want to know if I want to find the join and meet of any two elements in the lattice lets say

1/2/3/4 and 1/23/4 then what would the join and meet be for these two elements? And what it means when it says least upper bound and greatest lower bound

share|improve this question
    
Don't you mean $R_1\cup R_2$ and $R_1\cap R_2$? –  joriki Sep 12 '12 at 8:59
    
Yeah. I have changed it –  user34790 Sep 12 '12 at 9:17
    
But $R_1\cup R_2$ is not necessarily an equivalence relation! Try $\bigcap\{R\mid R\mathrm{\ is\ eq.rel.}, R_1\cup R_2\subseteq R\}$ instead. –  Hagen von Eitzen Sep 12 '12 at 9:20

2 Answers 2

This answers the version of the question before the edit.

If $R_1$ and $R_2$ are equivalence relations on a set $X$, then the union $R_1\cup R_2$ will in genral be symmetric and reflexive, but fail to be transitive.

For example you might have the set $X=\{0,1,2\}$ and $R_1=\{(0,0),(0,1),(1,0),(1,1),(2,2)\}$ and $R_2=\{(0,0),(1,2),(2,1),(1,1),(2,2)\}$. Then we have $(0,1)\in R_1\cup R_2$ and $(1,2)\in R_1\cup R_2$, but $(0,2)\notin R_1\cup R_2$.

So we have to add some elements to make the set transitive. This is done by taking the transitive closure of $R_1\cup R_2$, the smallest set under set inclusion that contains $R_1\cup R_2$ and is transitive. it is the intersection of all transitive supersets of $R_1\cup R_2$. This intersection is not over the empty set, since $X\times X$ is a transitive relation.

The transitive closure $T$ can be described by $x T y$ iff there exists a finite sequence $x,x',\ldots, y$ such that $x R_1 x' R_2 x'' R_1\ldots y$. Taking the transitive closure preserves symmetry and reflexivity, so the transitive closure of $R_1\cup R_2$ is indeed the smallest equivalence relation larger than both $R_1$ and $R_2$.

Remark: One can take the supremum over arbitrary sets of equivalence relations, they form a complete lattice. This has first been pointed out by Ore in the paper Theory of equivalence relations (locked) in 1942.

share|improve this answer

And this deals with the specific example that was added.

In any lattice the meet of two elements $a$ and $b$ is the largest element $c$ such that $c\le a$ and $c\le b$; it’s generally denoted by $a\land b$. The join of $a$ and $b$, denoted by $a\lor b$, is the smallest element $c$ such that $a\le c$ and $b\le c$. In your example, $1/2/3/4\le p$ for all partitions $p$ of $\{1,2,3,4\}$, so $$1/2/3/4\le1/23/4$$ and $$1/2/3/4\le1/2/3/4\;.$$ No other partition is less than or equal to $1/2/3/4$, so $$1/2/3/4=1/2/3/4\;\land\;1/23/4\;:$$ $1/2/3/4$ is the meet of $1/2/3/4$ and $1/23/4$. In fact, $1/2/3/4\;\land\;p=1/2/3/4$ for every partition $p$ of $\{1,2,3,4\}$.

The fact that $1/2/3/4\le1/23/4$ also implies that $$1/23/4=1/2/3/4\;\lor\;1/23/4\;,$$ the join of $1/2/3/4$ and $1/23/4$: we have $$1/2/3/4\le1/23/4$$ and $$1/23/4\le1/23/4\;,$$ and obviously if $p$ is a partition such that $1/2/3/4\le p$ and $1/23/4\le p$, then $1/23/4\le p$. That is, $1/23/4$ is the smallest partition (in terms of this ordering) that is an upper bound for both $1/2/3/4$ and $1/23/4$.

Here are a couple more examples:

$$\begin{align*} &1/23/4\;\land\;12/3/4=1/2/3/4\quad\text{and}\quad 1/23/4\;\lor\;12/3/4=123/4\\ &1/23/4\;\land\;12/34=1/2/3/4\quad\text{and}\quad 1/23/4\;\lor\;12/34=1234\;. \end{align*}$$

Using the diagram of the lattice, try to work out why these are true.

share|improve this answer

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.