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

share|improve this question
add comment

2 Answers

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.

share|improve this answer
    
I think we should clarify how the R1∩R2 is defined. –  Zhiyong Wang Sep 14 '12 at 2:36
add comment

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

share|improve this answer
    
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
add comment

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.