Tuesday, September 11, 2012

Finite Power Sets

Consider the set A = {0,1,2,3,4,5,6,7}. How many subsets of A are there? You can list all possible subsets of A and then count your list, but this isn't very efficient. Remember, any subset of A can only contain elements from A. A subset of a set cannot have elements that are not in the original set otherwise it wouldn't be a subset of that set.

For example {1,2,3,9} is not a subset of A, because 9 is not in A.

Let's think about how we can count all the subsets more efficiently. Consider all subsets of A with a single element. Immediately you should think 8, because there are 8 elements in A. That makes 8 subsets with a single element.

How about all subsets with two elements? How do we figure out how many there are without listing them all? Let S = {_,_}. The first empty spot in S can filled with 1 of 8 elements. Once we fill the first spot with an element from the original set we can't use that same element again. That leaves us 7 more elements to chose from to fill the second empty spot. Therefore, there are 8*7/2! = 28 subsets that have 2 elements.


The subsets S1 = {6,7} and S2 = {7,6} are the same since they have the same elements, therefore S1 and S2 are same. The order in which the elements of a subset appear does not matter. That's why we divide 8*7 by 2! to get 28, where 2! represent the number of ways two objects can be arranged.

Let's move on to counting subsets with 3 elements. Let S = {_,_,_}. Using the same argument we see that the first empty spot can be filled with 8 possible elements from the original set, the second empty spot has 7 possibilities and the third spot 6 possibilities. There are 8*7*6/3! = 56 subsets with 3 elements.

We keep doing these simple calculations until we find the number of subsets with 8 elements, because we cannot make subsets of A with more than 8 elements. Without doing any calculations we know that there is only 1 set containing all 8 elements, namely A. Any set is a subset of itself that's why we include the original set.

We end up getting 8 + 28 + 56 + 70 + 56 + 28 + 8 + 1 = 255. Did we get all of the subsets of A? No! Those of you who have taken a course in discrete math or basic set theory know that all possible subsets of a finite set must be a power of 2. Our result, 255 is an odd number and is not a power of 2. What did we do wrong?

We didn't do anything wrong we just forgot to consider the possibility of having a subset with nothing in it. This is the same as asking, "How many possible subsets of A are there with no elements?" The answer is 1. There is only 1 way to select a subset with nothing in it. We do not select anything from the original set and move on. This is called the empty set and we can write it as { }.

This brings the total number of subsets to 256, which is a power of 2.

Is there a quicker way to do this? Yes! We can use combinations to count all possible subsets. For any two nonnegative integers n and r where n r, the total number of ways of selecting r objects from a collection of n objects is C(n,r) = n!/r!(n-r)!

Going back to our original problem of counting all possible subsets from A we get

C(8,0) + C(8,1) + ... + C(8,7) + C(8,8) = 1 + 8 + ... + 8 + 1 = 256, where n = 8 and r ranges from 0 to 8.

There is an even quicker way to do this. Notice that for each element of A we have 2 possibilities; it is either in our subset or it is not in our subset. Therefore the total number of subsets of A is 2*2*2*2*2*2*2*2 = 2^8 = 256. This is why the total number of subsets of a set with a finite number of elements must be a power of 2. The set of all subsets of a set is called the power set, hence the name of this post. If your set contains n elements where n ≥ 0, then there are 2^n possible subsets.

What about infinite sets? How do you count the number of subsets of a set with an infinite number of elements? Technically you can't, because you cannot count to infinity. For example, the set of natural numbers N = {1,2,3, ...} is a countably infinite set. We call it a countably infinite set, because we can place all the elements of N on a list and be confident that all of them are on our list. Our list will be infinitely long, but mathematicians are used to dealing with lists that are infinitely long.

So how many subsets of N are there? Without thinking too hard about this question your gut should tell you the number of subsets is infinite. You would be right in this case, but this is where things get tricky. Remember how I said N is a countably infinite set? There is such thing as an uncountably infinite set. If I tried to make a list of a set that is uncountably infinite I couldn't do it. No matter how meticulous I am about creating this list there will always be something that is not on my list. In other words there is no way to list everything from a set that is uncountably infinite. In fact the power set of N is a classic example of a set that is uncountable. I cannot make a list of every subset of N and be 100% certain that every subset is on my list. I will always find something that I don't have on my list.

Why not add to my list that which was not on my list, you ask. That is where the problem lies! Once you update your list with the new item you will always find another one. And you will keep finding more and more items that weren't there before. You will keep finding new items until the end of time, but your list will never be complete. You cannot call such a set a countable set. Countable implies that you can find a way to list every element from that set (without actually listing every element) and be 100% certain that list you made is complete.

There is a way to prove this, but I will save it for another post on another day!

No comments:

Post a Comment