1
$\begingroup$

By using Cantor's Theorem: if We have a Set A, with n members the Cardinality of the Power Set is $P(A)=2^n$. There is Formula to calculate n Power Sets $P(...P(P(A))...)$ of a set A with m elements without doing the simple iteration $(((2^2)^2)..)^2^m$ n times? Many thanks

  • 0
    It's not just the missing $m$, it's the order of operations. This is essentially part of Brian's answer below, but if $|A| = m$, then $| P(A) | = 2^{|A|} = 2^m$, and $|P(P(A))|=2^{|P(A)|}=2^{2^m}$; etc. If $m = 3$, then $|P(P(A))| = 2^{2^3} = 2^8 = 256$, while your formula gives $(2^2)^3 = 4^3 = 64$.2012-08-16

3 Answers 3

0

Once you have corrected the formulation of your question as noted in the comments, you have an expression for the cardinality of the power set iterate.

You can express comparable expressions more economically using Knuth's up arrow notation or use a recurrence such as the Ackermann Function to express similar numbers in a different way. Neither of these would change the value or make it more easy to calculate.

The notations would have to be adapted to express the values you want - if such values were common enough in practical work, adapted notations to express them efficiently would no doubt catch on.

  • 0
    Other notations are linked in the article in Brian M. Scott's answer.2012-08-16
1

The term $(((2^2)^2)\ldots)^2$ simplifies to $2^{2^n}$.This follows from the general identity $(x^m)^n=x^{m\cdot n}$ and induction.

However, what you should actually be computing (as S4M points out in the comments) is an expression like $ 2^{2^{2^{2^{2^n}}}} $ which does not simplify any further.

1

The correct formula is $\large{2^{\left(2^{\left(2^{\dots(2^n)}\right)}\right)}}\;.$ That is, you start with $2^n$ for the cardinality of $\wp(A)$ when $|A|=n$, then get $2^{2^n}=2^{(2^n)}$ for the cardinality of $\wp(wp(A))$, and so on. I know of no simpler form for this iterated power.