Proof regarding power sets?

Printable View

May 9th 2013, 02:03 PM
gridvvk

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.
May 9th 2013, 02:48 PM
Plato

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 $A$ is a set, then $2^A$ is the set of all functions $A\to\{0,1\}$ .

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

Working with functions, we can show that $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.
May 9th 2013, 02:59 PM
gridvvk

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 $A$ is a set, then $2^A$ is the set of all functions $A\to\{0,1\}$ .

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

Working with functions, we can show that $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?
May 9th 2013, 03:02 PM
emakarov

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.
May 9th 2013, 03:14 PM
Plato

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.
May 9th 2013, 03:14 PM
gridvvk

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.
May 9th 2013, 03:22 PM
emakarov

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.
May 9th 2013, 03:42 PM
HallsofIvy

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 ifA and B were finite it would be easy but he didn't think he could use that method for infinite sets.
May 9th 2013, 03:45 PM
HallsofIvy

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.