Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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

share|improve this question
    
What you wrote is incorrect: the cardinality of the $n$th iterate of the power set operation on a set of size $m$ is $2^{2^{2^{\dots{^{2^m}}}}}$ where we have a tower of $n$ $2$s. –  Arthur Fischer Aug 16 '12 at 8:15
    
You are right I forgot to put the m in the end –  Hernan Aug 16 '12 at 8:25
    
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$. –  Arthur Fischer Aug 16 '12 at 8:29

3 Answers 3

up vote 1 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

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.

share|improve this answer
    
Other notations are linked in the article in Brian M. Scott's answer. –  Mark Bennet Aug 16 '12 at 8:24

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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