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 stumbled upon a seemingly rudimentary proposition that I am having trouble writing out a proof for. The proposition goes something like,

Proposition: If $\{A_i|i\in I\}$ is a partition of $\mathcal A$, then there is an equivalence relation on $\mathcal A$ whose equivalence clases are precisely the sets $A_i, i \in I$.

Where $I$ is some indexing set.


How do I prove the statement ? I can't even decide on a good place to start.


Any Help is much Appreciated,
Thanks in Advance!

share|improve this question
    
To be honest, I can't wrap my head around the proposition at all. How is it that no matter what kind of partition I choose to work with, I always end up with some collection of equivalence classes? –  Bidit Acharya Aug 6 '12 at 14:53
1  
Write down carefully the definition of an equivalence relation. Write down carefully what this equivalence relation would have to satisfy in order for this to be true. –  Qiaochu Yuan Aug 6 '12 at 15:46
1  
BTW, and very importantly in some contexts, the other direction is true as well, so that we have a 1-1 correspondence between all equivalence relations and all partitions on a given set. –  DonAntonio Aug 6 '12 at 15:57
    
oh, I got it now. Thanks –  Bidit Acharya Aug 6 '12 at 16:02
    
Relation induced by partition at ProofWiki –  Martin Sleziak Aug 6 '12 at 16:07

2 Answers 2

up vote 1 down vote accepted

When $I$ is an arbitrary "index set" then a set-vauled function $$f:\quad I\to {\cal P}(A)\ ,\quad i\mapsto A_i\ ,$$ where ${\cal P}(A)$ denotes the power set of $A$, is called a family of subsets of $A$ and is denoted by $(A_i)_{i\in I}\ $. Such a family is called a partition of $A$, if (i) all $A_i$ are nonempty, (ii) the $A_i$ are pairwise disjoint, i.e., $A_i\cap A_j=\emptyset$ when $i\ne j$, and (iii) $\bigcup_{i\in I} A_i=A$.

Given a partition $(A_i)_{i\in I}$ of $A$, for each $x\in A$ there is a unique $i\in I$ such that $x\in A_i$. This defines a function $\iota: A\to I$ which returns for each $x\in A$ the unique $i$ with $x\in A_i$.

Now it is easy to check that $$x\sim y\quad:\Leftrightarrow\quad \iota(x)=\iota(y)$$ defines an equivalence relation on $ A$ whose equivalence classes are exactly the $A_i$.

share|improve this answer
    
You say that "$\ldots$ for each $x∈A$ there is a unique $i∈I$ such that $x∈A_i \ldots$" Doesn't this mean that there has to be as many partitions as the order of $I$? Am I missing something? –  Bidit Acharya Aug 6 '12 at 16:11
    
@Bidit Acharya: Yes; see my edit. –  Christian Blatter Aug 6 '12 at 16:22
    
I am sorry, I meant "Doesn't this mean that there has to be as many partitions as the order of $A$ ?" –  Bidit Acharya Aug 6 '12 at 18:16
    
@Bidit Acharia: We are talking about just one partition $(A_i)_{i\in I}$. The number of parts (= the cardinality of $I$) is at least one and at most as large as the cardinality of $A$. –  Christian Blatter Aug 7 '12 at 7:52

Here is what to do. Define $x\sim y$ iff for some $i$ in the index set, $x,y\in A_i$. This is an equivalence relation.

share|improve this answer
    
I am not sure if I follow. What do you mean by "for some $i\in A_i$"? –  Bidit Acharya Aug 6 '12 at 15:08
    
Also, do I define an arbitrary equivalence relation? Could you please elaborate, I am a high school student. I hope you understand. –  Bidit Acharya Aug 6 '12 at 15:08
    
Check it out. Choose $x\in\mathcal{A}$. Then there is some $i$ so $x\in A_i$. Thus, $x\sim x$. Suppose that $x\sim y$. Then for some $i$, $x, y \in A_i$ (x and y belong to the same element of the partition). Thus $y, x\in A_i$; therefore $y\sim x$. You can develop transitivity similarly. –  ncmathsadist Aug 6 '12 at 15:16
    
I have edited the definition of the equivalence relation so that hopefully it is more clear. –  Code-Guru Aug 6 '12 at 15:40
    
I have clarified things by adding "in the index set". Yeah, my faulty typesetting made it appear that $i\in\mathcal{A}$. –  ncmathsadist Aug 6 '12 at 15:49

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.