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.

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.

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?

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.

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.

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.

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.

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 ifA and B were finite it would be easy but he didn't think he could use that method for infinite 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.