Proof: Number of Subsets using Induction | Set Theory

We prove that a set A with n elements has 2^n subsets. Thus, we're also proving that the cardinality of a power set is 2 to the power of the cardinality of the set we're taking the power set of. If |A|=n then |P(A)|=2^n. We prove this using mathematical induction. Give it a try yourself - this is a great basic example of an induction proof! #SetTheory

★DONATE★

Thanks to Robert Rennie, Barbara Sharrock, and Rolf Waefler for their generous support on Patreon!

Follow Wrath of Math on...

[red]

Your videos are very helpful, thank you so much!!!
You speak slowly and clearly and are easy to follow along with.
I just wanted to say thank you again!!!

[WrathofMath]

Thanks for watching and share the video if you enjoy the Christmas lessons!

[rinubehera]

Question;prove by method of induction that if A has n elements, then |P(A)|=2the power n.
answer please sir

[mahmoudalbahar]

Please, make video about cardinality of real irrational numbers.
Also thank you very much for this great video...since it contains cool proof.

[jinbai]

I think you are missing one part of provement for the total count of subsets that includes a(k+1) is 2^k. I understand for every subset of {a1, a2, ... ak}, if we throw a a(k+1), it would definitely be a subset of the total set S, but why are you sure the total count of subsets that includes a(k+1) is just 2^k? Why could not be another subset which is not coming from throwing a a(k + 1) into the existing subsets of {a1, a2, ... ak}? I think for this part, we can prove it using contradiction. I mean this contradiction might seem to be simple, but it needs this contradiction provement to rigorously prove the statement.

In another words, there is a hidden theorem or something in this statement, which is for the total subsets of {a1, a2, ... a(k+1)}, there are exactly half would contains a(k+1) and exactly another half would not. The distribution of it should be right on 50/50. But there should be a provement for it. I would think using contradiction can prove it very easily.

[cowliver]

Thank you for this video! I was just wondering, when you combine the subsets from k and k + 1, what happens to the empty set? Is it counted twice?

[whitestar]

I have understood it ! Thanks..
I have a question ..
Number of subsets of set A= 2 n(A)
( 2 n to the power A)
Number of subsets of set A=32
Then n(A)=??
Can you say how to do this...

[aidanmokalla]

im confused wouldn't {a vk+1} also be counted in the cardinality of S? So wouldn't | P(s) | = 2 ^k+1 + 1?

[carchang]

5:03 how did you know to even think of union?

[edhelton]

I do not understand if we are proving the a set a will havd 2^n subsets why do you prove that it has 2^(n+1)? I don't get it. Thanks