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.

Is $\mathcal{P}(X) / \sim \; = \mathcal{P} (X / \sim ) $ with $\sim$ induced by an equivalence relation on $X$ ?

share|improve this question
    
Have you tried any examples? –  Gerry Myerson Dec 7 '12 at 12:50
2  
What is the equivalence relation that $\sim$ induces on $\mathcal{P}(X)$? –  Rhys Dec 7 '12 at 12:50
    
I think this is the right idea: Let $U , V \subset X$ such that for all $ u \in U$ there exists $v \in V $ such that $ u \sim v $. Then $U \sim V $. –  dhr84 Dec 7 '12 at 12:53
    
Let $X = \{ \{1 \} , \{2 \} , \{3 \} \}$. I write $[1,2]$ for the equivalence class containing $1$ and $2$. $\mathcal{P} (X) = \mathcal{P} (\{ \{1 \} , \{2 \} , \{ 3 \} \} $ –  dhr84 Dec 7 '12 at 12:57
    
I think you meant equipotent not equal –  Amr Dec 7 '12 at 12:58

1 Answer 1

up vote 2 down vote accepted

$\def\P{\mathscr P}$Define, as suggested by @dhr84, a equivalence relation $\sim_\P$ on $\P(X)$ by $$ U \preceq V \iff \forall u \in U \; \exists v \in V: u \sim v $$ and $$ U \sim_\P V \iff (U \preceq V) \land (V \preceq U) $$ We can rephrase this as (denoting by $[x]_\sim$ the equivalence class of an element $x \in X$) $$ U \sim_\P V \iff \forall x \in X : ([x]_\sim \cap U \ne\emptyset) \Leftrightarrow ([x]_\sim \cap V \ne \emptyset) $$ that is $U$ and $V$ intersect exactly the same equivalence classes of $\sim$. Define a map $f \colon \P(X/\sim) \to \P(X)/\sim_\P$ by $$ f(A) := \left[\bigcup A\right]_{\sim_\P}, \quad A \subseteq X. $$ Then

  • $f$ is one-to-one: Suppose $f(A) = f(B)$, let $[x]_\sim \in A$, then as $\bigcup A \sim_\P \bigcup B$, and $[x]_\sim \cap \bigcup A \ne \emptyset$, we have $[x]_\sim \cap \bigcup B \ne \emptyset$. Since equivalence classes are either disjoint or equal, we must have $[x]_\sim \in B$. So $A \subseteq B$, by symmetry $A = B$.
  • $f$ is onto: Let $U \in \P(X)$. Set $A = \{[x]_\sim \mid x \in U\}$, we will show $f(A) = [U]_{\sim_\P}$, that is $U \sim_\P \bigcup A$. If $x \in U$, we have $x \in [x]_\sim \subseteq \bigcup A$, so $U \subseteq \bigcup A$, and therefore $U \preceq \bigcup A$. If $y \in \bigcup A$, there is an $x \in U$ with $y \in [x]_\sim$, hence $y \sim x$. That proves $\bigcup A \preceq U$. So $U \sim_\P \bigcup A$ and we are done.
share|improve this answer
    
Thanks very much! –  dhr84 Dec 7 '12 at 13:40

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.