Proof regarding power sets?

Let A and B be sets. Prove that A ~ B implies that P(A) ~ P(B), where P(A): power set of A and P(B): power set of B.

I'm not sure how to approach this problem. My thoughts are to try to construct a bijective function g: P(A) -> P(B) and then use the fact A~B to help show this is a bijection. But I am not sure how to define g.

Re: Proof regarding power sets?

Quote:

Originally Posted by

**gridvvk** Let A and B be sets. Prove that A ~ B implies that P(A) ~ P(B), where P(A): power set of A and P(B): power set of B.

There are multiple ways this has been done over many years.

You need the Schroder-Bernstein_theorem

If $\displaystyle A$ is a set, then $\displaystyle 2^A$ is the set of all functions $\displaystyle A\to\{0,1\}$.

Then using the Characteristic function you can show that $\displaystyle \mathcal{P}(A) \sim {2^A}$.

Working with functions, we can show that $\displaystyle A \sim B\, \Rightarrow \,{2^A} \sim {2^B}$.

Now there is a huge amount of work to be done there. **This is not an easy problem.**

Re: Proof regarding power sets?

Quote:

Originally Posted by

**Plato** There are multiple ways this has been done over many years.

You need

the Schroder-Bernstein_theorem
If $\displaystyle A$ is a set, then $\displaystyle 2^A$ is the set of all functions $\displaystyle A\to\{0,1\}$.

Then using the

Characteristic function you can show that $\displaystyle \mathcal{P}(A) \sim {2^A}$.

Working with functions, we can show that $\displaystyle A \sim B\, \Rightarrow \,{2^A} \sim {2^B}$.

Now there is a huge amount of work to be done there.

**This is not an easy problem.**

I think I can take for granted (or prove separately) that if A and B are finite, and if |A| = |B| = n. Then |P(A)| = |P(B)| = 2^n; however, I wasn't sure if the same idea would hold if A and B were infinite sets. Does using the characteristic function take care of this problem?

Re: Proof regarding power sets?

Why isn't it easy to define g(X) = {h(x) | x ∈ X} for X ⊆ A? A proof that g is a bijection seems straightforward.

Re: Proof regarding power sets?

Quote:

Originally Posted by

**gridvvk** I think I can take for granted (or prove separately) that if A and B are finite, and if |A| = |B| = n. Then |P(A)| = |P(B)| = 2^n; however, I wasn't sure if the same idea would hold if A and B were infinite sets. Does using the characteristic function take care of this problem?

**You said absolutely nothing about these being **__finite sets__..

All proof about finite sets are trivial.

Re: Proof regarding power sets?

Quote:

Originally Posted by

**emakarov** Why isn't it easy to define g(X) = {g(x) | x ∈ X} for X ⊆ A? A proof that g is a bijection seems straightforward.

Wouldn't we need to use a different letter for a different function that goes from A to B? Like h: A -> B then g(X) = {h(x) | x ∈ X}? Then just show g is injective and surjective?

Quote:

Originally Posted by

**Plato** **You said absolutely nothing about these being **__finite sets__..

All proof about finite sets are trivial.

A and B aren't necessarily finite. You were correct in your interpretation of the problem. Based on what you said working with functions probably doesn't lead to the problems I was thinking.

Re: Proof regarding power sets?

Quote:

Originally Posted by

**gridvvk** Wouldn't we need to use a different letter for a different function that goes from A to B? Like h: A -> B then g(X) = {h(x) | x ∈ X}?

You are right; sorry.

Quote:

Originally Posted by

**gridvvk** Then just show g is injective and surjective?

Yes.

Re: Proof regarding power sets?

Quote:

Originally Posted by

**Plato** **You said absolutely nothing about these being **__finite sets__..

All proof about finite sets are trivial.

Yes, that was his point. gridvvk was saying that **if**A and B were finite it would be easy but he didn't think he could use that method for infinite sets.

Re: Proof regarding power sets?

But emakarov has the right approach. If A and B have the same cardinality, there exist a bijection, h, from A to B. Given X a subset of A, let g(A) be the set {h(x)| where x is in X}.

Show that g is a bijection.