# How do you solve for the cardinality of a power set of some complex set? (i.e. $|\mathcal P(A^n)|$ , $|\mathcal P(A\cup B)|$ )

Suppose $A$ is some set such that $A = \{a_1,a_2,\dotsb,a_n\}$.

We know that $|A|=n$.

We know that $\mathcal P(A)= 2^n$.

Now let $A^n$ denote the cartesian product of a set A with itself n times. $$\text{(i.e.) }\left[A^n=\underbrace{A\times A\times\dotsb\times A}_\text{n}\right]$$

We know the cartesian product of a sets $A\times B=|A|*|B|$

Thus $|A^n| = \left[\underbrace{|A|* |A|*\dotsb*|A|}_\text{$n$}\right] = |A|^n$

??? $|\mathcal P(A^n)|=\dots$

## Question:

• What is a general way to solve for the cardinality of a power set of some complex set equation?
• If there are general steps for finding the cardinality of a power set of some complex set equation, what are they?
• Is $|\mathcal P(A^n)| = 2^{n^n} =2$^n^n?
• It is $2^{(|A|^n)}$ – palio Feb 13 '14 at 18:07
• A very minor note: be careful when saying $|A|=n$ because that is only true if $a_i\neq a_j$ for all $i\neq j$. I know you probably implied that this was the case for $A$ but it helps to be pedantic when working with this stuff. – Dan Rust Feb 13 '14 at 18:13
• The definition I use for a set does not include repetition of elements. There is another construction deduced from the cartesian product of a set (taking the quotient by the symmetric group permuting the coordinates) this gives a set "the symmetric product" where elements are sets in which repetition is permitted. – palio Feb 13 '14 at 18:17

You already know that $|\mathcal P(X)|=2^{|X|}$.
If $X=n^n$ then $|\mathcal P(X)|=2^{n^n}$. And indeed if $|A|=n$ and $X=A^n$, then $|X|=n^n$.
Generally speaking, finding the cardinality of the power set requires you to find the cardinality of $X$, if $X$ is a union, or product or whatever, then you need to calculate the cardinality of this $X$, and take $2^{|X|}$.
If you think of any subset of a set $Y \subseteq X$ as a binary string, where each character represents an element of $X$ and is $1$ or $0$ if the element is in $Y$ or is not in $Y$ respectively, you find out that all the distinct binary strings of "length" $|X|$ are in 1-1 correspondence with all the distinct subsets of $X$. We know the elements of $\mathcal P \left({X}\right)$ are all the subsets of $X$, and we also know the number of binary strings of "length" $|X|$ is $2^{|X|}$, so: $$|\mathcal P \left({X}\right)| = 2^{|X|}$$ For any set $X$ (finite or not).