2
$\begingroup$

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.

  • 0
    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?2012-08-06
  • 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.2012-08-06
  • 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.2012-08-06
  • 0
    oh, I got it now. Thanks2012-08-06
  • 0
    [Relation induced by partition](http://www.proofwiki.org/wiki/Definition:Relation_Induced_by_Partition) at ProofWiki2012-08-06

2 Answers 2

2

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

  • 0
    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?2012-08-06
  • 0
    @Bidit Acharya: Yes; see my edit.2012-08-06
  • 0
    I am sorry, I meant "Doesn't this mean that there has to be as many partitions as the order of $A$ ?"2012-08-06
  • 0
    @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$.2012-08-07
6

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.

  • 0
    I am not sure if I follow. What do you mean by "for some $i\in A_i$"?2012-08-06
  • 0
    Also, do I define an arbitrary equivalence relation? Could you please elaborate, I am a high school student. I hope you understand.2012-08-06
  • 0
    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.2012-08-06
  • 0
    I have edited the definition of the equivalence relation so that hopefully it is more clear.2012-08-06
  • 0
    I have clarified things by adding "in the index set". Yeah, my faulty typesetting made it appear that $i\in\mathcal{A}$.2012-08-06