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
Power Sets: • What is a Power Set? |...
Formula for Cardinality of Power Sets: • Formula for Cardinalit...
How many Proper Subsets does a Set Have? • How Many Proper Subset...
Finding Number of Subsets of a Set: • Finding the Number of ...
★DONATE★
◆ Support Wrath of Math on Patreon for early access to new videos and other exclusive benefits: / wrathofmathlessons
◆ Donate on PayPal: www.paypal.me/wrathofmath
Thanks to Robert Rennie, Barbara Sharrock, and Rolf Waefler for their generous support on Patreon!
Thanks to Crayon Angel, my favorite musician in the world, who upon my request gave me permission to use his music in my math lessons: crayonangel.bandcamp.com/
Follow Wrath of Math on...
● Instagram: / wrathofmathedu
● Facebook: / wrathofmath
● Twitter: / wrathofmathedu
My Music Channel: / @emery3050

[@WrathofMath]

If you're looking for more, I've got about a million other videos on power sets and subsets. Here is a fun one, the power set of the power set of the power set of the empty set: ua-cam.com/video/d6k-qSbys4g/v-deo.html
Thanks for watching and share the video if you enjoy the Christmas lessons!

[@red3987]

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 so much, I'm glad you've found my lessons helpful! Let me know if you ever have any questions!

[@rinubehera516]

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

[@Vyola08]

Awesome lecture..... So very clear!!!!! Thankyou sir!

[@WrathofMath]

My pleasure, thanks for watching!

[@cowliver1032]

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?

[@nuche3931]

Brilliant!!
Thank you so much

[@WrathofMath]

My pleasure, thanks for watching!

[@carchang4843]

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

[@aidanmokalla7601]

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

[@mahmoudalbahar1641]

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

[@WrathofMath]

Thanks for watching and for the request! I'll be making some lessons about cardinality, rationals and irrationals and so on, to go at the beginning of my real analysis playlist. I'm not sure when it will be though, I'll see what I can do this month!

[@rinubehera516]

Thank you so much sir

[@WrathofMath]

Glad to help, thanks for watching!

[@whitestar9710]

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

[@arpitadas6322]

2^5
So 5 elements

[@rafyyd461]

thanks boss

[@WrathofMath]

You're very welcome!

[@jinbai4867]

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.

[@edhelton6757]

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

[@WrathofMath]

Thanks for watching and good question! This is a proof by induction, so if you aren’t familiar with that technique I’d watch a couple videos on it with other examples too. I have plenty. The idea is that we prove it holds for n=0 (and maybe n=1? i don’t remember the video exactly). The idea is that we’re trying to prove an infinite “ladder” of statements (the rungs of the ladders are cardinalities of sets: n=0,1,2,3,…). When we prove the n=0 case, we’re proving that we can get on the ladder.
What remains to be proven is that if we are on any rung of the ladder, we can move to the next one. Thus, we assume the statement is true for some n (which is valid because we proved it was true for n=0), then show it must be true for the next n [that is, a set with n+1 elements has 2^(n+1) subsets.
EDIT: The short answer to your question is that the “it” you refer to is a set with n+1 elements.

[@Vyola08]

@@WrathofMath you are a teacher every student would dream to have🙏