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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Some notation first. Let $E_X$ be the equivalence relation that you can obtain from a partition $X$, that is $\{p:\exists x\exists y\exists z(p=\langle x,y\rangle,z\in X,x\in z,y\in z)\}$. Instead, let $\text{dom}(\mathord{\sim})/\mathord{\sim}$ be the partition that you can obtain from an equivalence $\mathord{\sim}$.

I'd like to prove that if $X$ is a partition, then $\text{dom}(E_X)/E_X=X$.

My strategy is to prove separately that:

  1. $\text{dom}(E_X)/E_X\subseteq X$
  2. $X\subseteq\text{dom}(E_X)/E_X$.

This is what I managed to prove so far.

  1. Suppose $c\in\text{dom}(E_X)/E_X$. Then $\exists x(x\in\text{dom}(E_X),c=[x]_{E_X})$. Suppose $a\in\text{dom}(E_X),c=[a]_{E_X}$. Then $[a]_{E_X}\in\text{dom}(E_X)/E_X$. Then $a\in[a]_{E_X}$. Then $a\in c$. Then?
  2. Suppose $c\in X$. Then $c\not=\emptyset$. Then $\exists z(z\in c)$. Suppose $a\in c$. Then $\langle a,a\rangle\in E_X$. Then $a\in\text{dom}(E_X)$. Then $a\in[a]_{E_X}$. Then $[a]_{E_X}\in\text{dom}(E_X)/E_X$. Then $a\in\bigcup\text{dom}(E_X)/E_X$. Then?


share|cite|improve this question
up vote 2 down vote accepted
  1. You need to use the fact that $X$ is a partition, which you haven't.

    So, you have an equivalence class $[a]_{E_X}$. You want to show that this class is equal to some element of $X$. Since $a\in \mathrm{dom}(X)$, then there exists $P\in X$ such that $a\in P$. Now show that $[a]_{E_X} = P$; since they are both subsets of $\mathrm{dom}(X)$, you do this by showing that $[a]_{E_X}\subseteq P$ and that $P\subseteq [a]_{E_X}$. For example: if $p\in P$, then since $a,p\in P$ then $(a,p)\in E_X$, hence $p\in [a]_{E_X}$. Thus, $P\subseteq [a]_{E_X}$. Etc.

  2. In this part you want to prove that $c\in \mathrm{dom}(E_X)/E_X$. That is, you want to show that there exists $a\in\mathrm{dom}(E_X)$ such that $c=[a]_{E_X}$. You already have a candidate; so now you must show that $c=[a]_{E_X}$; to do this, since both $c$ and $[a]_{E_X}$ are subsets of $\mathrm{dom}(E_X)$, you do this by showing that $c\subseteq [a]_{E_X}$ and that $[a]_{E_X}\subseteq c$. For example, suppose $x\in c$; then $x,a\in c\in X$, so by definition of $E_X$ you have $(a,x)\in E_X$; therefore, $x\in[a]_{E_X}$, proving $c\subseteq [a]_{E_X}$. Etc.

share|cite|improve this answer
Perfect. Thank you! – user9297 Apr 8 '11 at 16:08

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.