Confusion about the lattice formed by an equivalence relation

Question

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.

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

Answer 1

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.

Answer 2

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.