# What is the number of equivalence classes formed by a merge

I have this question related to the number of equivalence classes of equivalence relations. If $R_1$ and $R_2$ are two equivalence relations on a set $A$ with number of equivalence classes of $R_1 = n_1$ and number of equivalence classes of $R_2= n_2$. What is the number of equivalence classes formed by $R_1 \cap R_2\,$?

-

$R_1\cap R_2$ could have as few as $\max\{n_1,n_2\}$ and as many as $n_1n_2$ equivalence classes, depending on how $R_1$ and $R_2$ interact. Let $n$ be the number of equivalence classes of $R_1\cap R_2$.

1. If $R_1\subseteq R_2$, then $n_2\le n_1$, and $\langle x,y\rangle\in R_1\cap R_2$ iff $\langle x,y\rangle\in R_1$, so $n=\max\{n_1,n_2\}$.

2. If every $R_1$-class has non-empty intersection with every $R_2$-class, then $R_2$ divides each $R_1$-class into $n_2$ $(R_1\cap R_2)$-classes, and $n=n_1n_2$.

Added: A simple example of the the latter case is given by $A=\{0a,0b,0c,1a,1b,1c\}$, where for $\alpha,\beta\in A$ we set $\alpha\,R_1\,\beta$ if $\alpha$ and $\beta$ have the same first character, and $\alpha\,R_2\,\beta$ if $\alpha$ and $\beta$ have the same second character. In the table below, the rows within the body of the table are the $R_1$-equivalence classes, the columns within the body of the table are the $R_2$-equivalence classes, and each of the six cells within the body of the table is an $(R_1\cap R_2)$-equivalence class.

$$\begin{array}{c|ccc} &a&b&c\\ \hline 0&0a&0b&0c\\ 1&1a&1b&1c \end{array}$$

Here $n_1=2$, $n_2=3$, and $n=6$. (In fact in this case $R_1\cap R_2$ is the identity relation on $A$.)

Added2: $\operatorname{trans}(R_1\cup R_2)$ can have as few as $1$ and as many as $\min\{n_1,n_2\}$ equivalence classes. In the example that I added above, the transitive closure of $R_1\cup R_2$ has only one equivalence class.

-
Let A={a,b,c}. R1= {(a,a),(b,b),(c,c),(a,c),(c,a)} with n1=2 , R2={(a,a),(b,b),(c,c),(a,b),(b,a)} with n2=2. Then R1 $\cap$ R2 = {(a,a),(b,b),(c,c)} which has equivalence relation of 3<n1*n2. So I think the relation u gave with as many as n1n2 equivalence classes is not right is it? – user34790 Sep 13 '12 at 4:32
@user34790: I didn’t say that $n_1n_2$ was the only possibility: I said that it was the largest possibility. Your example does not contradict that. – Brian M. Scott Sep 13 '12 at 4:38
what is the case when we take trans($R1 \cup R2$) where trans is the transitive closure. I know the maximum is min(n1,n2). What is the minimum. I guess it is $\frac{min(n1,n2)}{max(n1,n2)}$ – user34790 Sep 17 '12 at 4:40

It is less than or equal to $max\{n1,n2\}$.

The equivalent class formed by is $R_1 \cap R_2$ is $span(R_1 \cap R_2)$. However, $span(R_1 \cap R_2)\subseteq R_1$ and $span(R_1 \cap R_2)\subseteq R_2$.

Because $R_1$ and $R_2$ are all equivalent classes, the span cannot have more elements than $R_1$ and $R_2$ at the same time.

-
I think we should clarify how the R1∩R2 is defined. – Zhiyong Wang Sep 14 '12 at 2:36