Power sets and cardinality

**oldguynewstudent** · October 21st 2009, 06:32 PM

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

**tonio** · October 21st 2009, 08:37 PM

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

**oldguynewstudent** · October 28th 2009, 12:49 PM

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$ |

Thread: Power sets and cardinality

LinkBack

Thread Tools

Display

Power sets and cardinality

Similar Math Help Forum Discussions

[SOLVED] Cardinality of Sets and Power Sets

Cardinality of these sets!

Induction proof: Cardinality of power sets

Cardinality of sets Q and R

Cardinality of sets

Search Tags