# Proof of a Proposition on Partitions and Equivalence Classes

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,

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

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

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