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.

Given an equivalence relation $\sim$ with equivalence classes $C_1,\dots,C_n$, show that $$\mathbin{\sim} = \bigcup_{i=1}^n(C_n\times C_n)\;.$$

I could use a hint on where to start approaching this from.

The beginnings of my proof:

Suppose that $\langle a,b \rangle\in\sim$. This implies that $a\sim b$, and by the transitivity of $\sim$, $b\sim a$. The equivalence classes of $a$ and $b$ are defined $\bar{a}=\{b\in A | a\sim b\}$ and $\bar{b}=\{a\in A | b\sim a\}$. It follows from the properties of the equivalence relation that $a\sim b\iff \bar{a}=\bar{b}$. $\bar{a}=\bar{b}\implies \{b\in A | a\sim b\}=\{a\in A | b\sim a\}$.

Now suppose that $\langle a,b\rangle\in\bigcup_{i=1}^n(C_i\times C_i)$. This means there exists $i\in\{1,\dots,n\}$ such that $\langle a,b \rangle\in C_i\times C_i$. Consequently, $\langle a,b \rangle\in C_i\times C_i\implies a\in C_i$ and $b\in C_i$.

share|improve this question
1  
What are your thoughts? What did you try so far? What is the standard way of proving that two sets are equal? –  N. S. Feb 6 '13 at 3:40
    
I'm not entirely sure what I need to show. Is it that all elements $a\in\sim$ exist in$C_1\cup C_2\cup C_3\dots\cup C_n$? –  tacoTaco Feb 6 '13 at 3:52

1 Answer 1

HINT: Let $A$ be the underlying set for the equivalence relation $\sim$; then $\sim$ is a subset of $A\times A$. $\bigcup_{i=1}^n(C_i\times C_i)$ is also a subset of $A\times A$, and you’re to show that these two subsets of $A\times A$ are actually the same subset. You can approach it as you would approach any other problem of showing that two sets are equal: try to show that each is a subset of the other.

  • Suppose that $\langle a,b\rangle\in\;\sim$, i.e., that $a\sim b$; you want to show that there is an $i\in\{1,\dots,n\}$ such that $\langle a,b\rangle\in C_i\times C_i$. This is the case if and only if $a\in C_i$ and $b\in C_i$, i.e., if and only if $a$ and $b$ are in the same equivalence class. Is this true if $a\sim b$? Why?

  • Then suppose that $\langle a,b\rangle\in\bigcup_{i=1}^n(C_i\times C_i)$, and try to show that $\langle a,b\rangle\in\;\sim$, i.e., that $a\sim b$. If $\langle a,b\rangle\in\bigcup_{i=1}^n(C_i\times C_i)$, then $\langle a,b\rangle\in C_i\times C_i$ for some $i\in\{1,\dots,n\}$. Does that imply that $a\sim b$? Why?

share|improve this answer
    
I understand the first part as you have it written, but I can't seem to recognize the method to prove that $i\in \{1,\dots,n\}|(a,b)\in C_i\times C_i$. Perhaps I'm not entirely clear on how it relates to $C_i\times C_i$. –  tacoTaco Feb 6 '13 at 17:11
    
@tacoTaco: Suppose that $a\sim b$. Then by definition $b\in[a]$, where $[a]$ is the $\sim$-equivalence class of $a$. And $a\sim a$, so $a\in[a]$ as well. Thus, $\langle a,b\rangle\in[a]\times[a]$. $C_1,\dots,C_n$ are all the equivalence classes, so $[a]$ is one of them, say $C_i$, and therefore $\langle a,b\rangle\in C_i\times C_i$. That proves that $\sim~\subseteq\bigcup_{k=1}^n(C_k\times C_k)$; now you just have to prove the other direction. –  Brian M. Scott Feb 6 '13 at 22:18

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.