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 ifA 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.