4

I'm blocked on a question about sets:

if $2^X= 2^Y$ holds for two sets $X$ and $Y$, then can we say that $X=Y$ ?

I know how to prove it with two integers a and b but how can i show it with two sets?

Thanks

The Count
  • 3,620
Tom92
  • 49
  • 1
    I think you're confused about the notation $2^X$. For a set $X$, we denote the power set $\mathcal P(X)$ of $X$ as $2^X$. – Prasun Biswas Oct 08 '17 at 18:37
  • It's most literally interpreted as the set of functions $X \to {0,1}$. – Patrick Stevens Oct 08 '17 at 18:37
  • 1
    Are you talking about equations between cardinalities? Or does $2^X = 2^Y$ mean that $X$ and $Y$ have the same power set? – Rob Arthan Oct 08 '17 at 18:37
  • @PatrickStevens, each element of the set of functions $X\to{0,1}$ can be thought of (or more precisely, can be mapped) to a unique subset of $X$ (we have an obvious bijection here). So, it's equivalent to think of $2^X$ as $\mathcal P(X)$. – Prasun Biswas Oct 08 '17 at 18:40
  • Hi, i wanted to mean that 2^X is for "2 to the power of X" equals to "2 to the power of Y" with X,Y sets – Tom92 Oct 08 '17 at 19:26
  • 1
    So if it's an equation between the power sets, Patrick Stevens has given you an answer. – Rob Arthan Oct 08 '17 at 20:37

1 Answers1

4

Yes. We show that $X \subseteq Y$, and then $Y \subseteq X$ follows by symmetry.

Let $x \in X$. Then $\{x\} \in \mathcal{P}(X)$. So, since $\mathcal{P}(X) = \mathcal{P}(Y)$, have $\{x\} \in \mathcal{P}(Y)$; so $x \in Y$.

Actually, faster way which skips out one quantifier: $X \subseteq X$, so $X \in \mathcal{P}(X)$, so $X \in \mathcal{P}(Y)$, so $X \subseteq Y$.

Patrick Stevens
  • 36,135