Formula for Cardinality of Power Sets | Set Theory

What is the formula for the cardinality of power sets? Why does it work? We go over all of that in today's math lesson! Recall that the power set, of a set A, is the set containing all subsets of A. So, for example, let A = { 1, 2, 3 }. Then, the power set of A, denoted P(A), is

P(A) = { { }, { 1 }, { 2 }, { 3 }, { 1, 2 }, { 1, 3 }, { 2, 3 }, { 1, 2, 3 } }.

Every subset of A is an element of P(A). So how many elements are in P(A)? If we count them up, we see there are 8 elements, which is equal to 2^3. Notice that |A| = 3. So |P(A)| = 2^(|A|). This is true in general. If the cardinality of a set S is n, then the cardinality of P(S) is 2^n. So why does this work?

We have to ask ourselves how many subsets any given set has, as this number is the same as the cardinality of the power set. If our set S has n elements, then how many subsets of S are there? Well, since S has n elements, we can write it like this:

S = { 1, 2, 3, ..., n },

where each number is just a label for each of the n elements of S. Then, if we are creating a subset of S, it could either contain or not contain the element labeled 1. So we have 2 possibilities. Then, for each of those two possibilities, our subset could either contain or not contain the element labeled 2, so now we are up to 2*2 possibilities. This reasoning continues up to the nth element, where we then have 2^n possibilities. This is where the formula comes from. There are 2^n subsets of any set with n elements, so the power set, which is the set of all subsets, has cardinality 2^n.

I hope you find this video helpful, and be sure to ask any questions down in the comments!

********************************************************************
The outro music is by a favorite musician of mine named Vallow, who, upon my request, kindly gave me permission to use his music in my outros. I usually put my own music in the outros, but I love Vallow's music, and wanted to share it with those of you watching. Please check out all of his wonderful work.

Vallow Bandcamp: https://vallow.bandcamp.com/
Vallow Soundcloud: https://open.spotify.com/artist/0fRtu...
Vallow SoundCloud:   / benwatts-3  
********************************************************************

+WRATH OF MATH+

◆ Support Wrath of Math on Patreon:   / wrathofmathlessons  

Follow Wrath of Math on...
● Instagram:   / wrathofmathedu  
● Facebook:   / wrathofmath  
● Twitter:   / wrathofmathedu  

Music Channel:    / seanemusic