1
$\begingroup$

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\,$?

2 Answers 2

0

$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.

  • 0
    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)}$2012-09-17
0

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.

  • 0
    I think we should clarify how the R1∩R2 is defined.2012-09-14