# 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 $\displaystyle f:A\rightarrow B$, and this means that if $\displaystyle C\subset A \mbox{ then } C'=\{f(c)\slash\,\, c \in C\}\subset B$

Now just show that $\displaystyle C \longrightarrow C'$ as defined above is a bijection $\displaystyle 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 $\displaystyle f:A\rightarrow B$, and this means that if $\displaystyle C\subset A \mbox{ then } C'=\{f(c)\slash\,\, c \in C\}\subset B$

Now just show that $\displaystyle C \longrightarrow C'$ as defined above is a bijection $\displaystyle 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 |$\displaystyle A^n$| = |$\displaystyle B^n$| where $\displaystyle A^n$ implies the cartesian product.

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

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

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

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

but $\displaystyle b_i$ = f($\displaystyle a_i$)

we can then define a function

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

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

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

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

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

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

Therefore g is injective.

To prove g is surjective:

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

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

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

since f is bijective this proves g is surjective.

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