# Thread: Power sets and cardinality

1. ## Power sets and cardinality

Show that if A and B are sets with the same cardinality, then the power set of A and the power set of B have the same cardinality.

Since A and B have the same cardinality there is a bijection between A and B.

Therefore each element of A can be paired with each element of B.

It then follows that every subset of A can be paired with every subset of B.

This means that there is a bijection between the power set of A and the power set of B.

Which proves that the power set of A has the same cardinality as the power set of B.

Can anyone validate or show if and where this proof is wrong? I have a quiz tomorrow.

Thanks

2. Originally Posted by oldguynewstudent
Show that if A and B are sets with the same cardinality, then the power set of A and the power set of B have the same cardinality.

Since A and B have the same cardinality there is a bijection between A and B.

Therefore each element of A can be paired with each element of B.

It then follows that every subset of A can be paired with every subset of B.

This means that there is a bijection between the power set of A and the power set of B.

Which proves that the power set of A has the same cardinality as the power set of B.

Can anyone validate or show if and where this proof is wrong? I have a quiz tomorrow.

Thanks

I'd be a little less verbose and more symbolic: since A, B have the same card., there's a bijection $f:A\rightarrow B$, and this means that if $C\subset A \mbox{ then } C'=\{f(c)\slash\,\, c \in C\}\subset B$

Now just show that $C \longrightarrow C'$ as defined above is a bijection $P(A) \longrightarrow P(B)$ and we're done.

Tonio

3. Originally Posted by tonio
I'd be a little less verbose and more symbolic: since A, B have the same card., there's a bijection $f:A\rightarrow B$, and this means that if $C\subset A \mbox{ then } C'=\{f(c)\slash\,\, c \in C\}\subset B$

Now just show that $C \longrightarrow C'$ as defined above is a bijection $P(A) \longrightarrow P(B)$ and we're done.

Tonio
Thanks for the advice, just getting used to the Latex format. Here is the actual problem from the quiz. Another student came up with the basis of the proof but it wasn't finished. So any critique of the following proof is greatly appreciated.

Given,
|A| = |B|

Prove that | $A^n$| = | $B^n$| where $A^n$ implies the cartesian product.

|A| = |B| $\Rightarrow \exists$ f:A $\to$B | f is bijective

$A^n$={ $(a_1$, $a_2$, ... , $a_n$) | $a_i$ $\epsilon$ $A_i$ for i = 1,2, ... ,n}

B = {b | b = f(a)}

$B^n$= { ( $b_1$, $b_2$, ... , $b_n$) | $b_i$ $\epsilon$ $B_i$ for i = 1,2, ... , n}

but $b_i$ = f( $a_i$)

we can then define a function

g( $a_1$, $a_2$, ... , $a_n$) = ( $b_1$, $b_2$, ... , $b_n$) = (f( $a_1$), f( $a_2$), ... , f( $a_n$))

We need to prove g is bijective in order to show | $A^n$| = | $B^n$|

Let g( $a_1$, $a_2$, ... , $a_n$) = g( $c_1$, $c_2$, ... , $c_n$)

but g( $a_1$, $a_2$, ... , $a_n$) = ( $b_1$, $b_2$, ... , $b_n$)

also g( $c_1$, $c_2$, ... , $c_n$) = ( $b_1$, $b_2$, ... , $b_n$)

obviously ( $b_1$, $b_2$, ... , $b_n$) = ( $b_1$, $b_2$, ... , $b_n$)

Therefore g is injective.

To prove g is surjective:

$\forall$ ( $b_1$, $b_2$, ... , $b_n$) $\epsilon$ $B^n$ $\exists$ ( $a_1$, $a_2$, ... , $a_n$) $\epsilon$ $A^n$ |

g( $a_1$, $a_2$, ... , $a_n$) = ( $b_1$, $b_2$, ... , $b_n$)

but ( $b_1$, $b_2$, ... , $b_n$) = (f( $a_1$), f( $a_2$), ... , f( $a_n$))

since f is bijective this proves g is surjective.

Therefore g is bijective which proves | $A^n$| = | $B^n$|