0
$\begingroup$

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?
$\endgroup$
  • 2
    $\begingroup$ It is $2^{(|A|^n)}$ $\endgroup$ – palio Feb 13 '14 at 18:07
  • 1
    $\begingroup$ 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. $\endgroup$ – Dan Rust Feb 13 '14 at 18:13
  • $\begingroup$ 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. $\endgroup$ – palio Feb 13 '14 at 18:17
1
$\begingroup$

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

$\endgroup$
0
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.