HOME

A-Z Listing

MathsIsFun.com

# Power Set

A Power Set is a set of all the subsets of a set.

OK? Got that? Maybe an example would help...

## All The Subsets

If we have a set {a,b,c}:

• Then a subset of it could be {a} or {b}, or {a,c}, and so on,
• And {a,b,c} is also a subset of {a,b,c} (yes, that's true, but its not a "proper subset")
• And the empty set {} is also a subset of {a,b,c}

In fact, if you list all the subsets of S={a,b,c} you will have the Power Set of {a,b,c}:

P(S) = { {}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} }

Think of it as all the different ways you can select the items (the order of the items doesn't matter), including selecting none, or all.

## How Many Subsets

Easy! If the original set has n members, then the Power Set will have 2n members

Example: in the {a,b,c} example above, there are three members (a,b and c of course).

So, the Power Set should have 23 = 8, which it does!

### Notation

The number of members of a set is often written as |S|, so we can write:

|P(S)| = 2n

Example: for the set S={1,2,3,4,5} how many members will the power set have?

Well, S has 5 members, so:

|P(S)| = 2n = 25 = 32

You will see in a minute why the number of members is a power of 2

## It's Binary!

And here is the most amazing thing. If you want to create the Power Set, just write down the sequence of binary numbers (using n digits), and then let "1" mean "put the matching member into this subset" OK, it is easier to show with an example:

abc Subset
0 000 { }
1 001 {c}
2 010 {b}
3 011 {b,c}
4 100 {a}
5 101 {a,c}
6 110 {a,b}
7 111 {a,b,c}

Well, they are not in a pretty order, but they are all there.

## Another Example

 Let's eat! We have four flavors of icecream: banana, chocolate, lemon, and strawberry. How many different ways can you have them? Let's use letters for the flavors: {b, c, l, s}. Example selections would be {} (nothing, you are on a diet) {b, c, l, s} (every flavor) {b, c} (banana and chocolate are good together)
Let's make the table:
bcls Subset
0 0000 {}
1 0001 {s}
2 0010 {l}
3 0011 {l,s}
... ... etc .. ... etc ...
12 1100 {b,c}
13 1101 {b,c,s}
14 1110 {b,c,l}
15 1111 {b,c,l,s}

And the result is (more neatly arranged):

P = { {}, {b}, {c}, {l}, {s}, {b,c}, {b,l}, {b,s}, {c,l}, {c,s}, {l,s}, {b,c,l}, {b,c,s},

{b,l,s}, {c,l,s}, {b,c,l,s} }

### Symmetry

In the table above, did you notice that the first subset is empty and the last has every member?

But did you also notice that the second subset has "s", and the second last subset has everything except "s"?

In fact if you mirror that table about the middle you will see there is a kind of symmetry.

This is because the binary numbers that we used to help us get all combinations have a beautiful and elegant symmetry.

## A Prime Example

The Power Set can be useful in unexpected areas. I wanted to find out the factors (not just the prime factors, but all factors) of a number.

One way would have been to test every possibility. So to find the factors of, say 330, you could check 2,3,4,5,6,7,8,9,10 ... etc! Well, there are ways to improve that, but it still takes a long time for large numbers (in my tests, the computer just sat there for ages).

But I could already find the prime factors very quickly, so couldn't I somehow combine the prime factors to make all factors?

Let me see, 330 = 2×3×5×11 (using prime factor tool).

So, all the factors of 330 would be: 2,3,5, and 11 ... and 2×3, 2×5 and 2×11 as well, and 2×3×5 and 2×3×11 ... ? Aha! I need a Power Set!

So, my oriignal set is {2,3,5,11} and the power set can be worked out using:

2,3,5,11 Subset Factor
0 0000 { } 1
1 0001 {11} 11
2 0010 {5} 5
3 0011 {5,11} 5 × 11 = 55
4 0100 {3} 3
5 0101 {3,11} 3 × 11 = 33
... etc ... ... etc ... ... etc ...
15 1111 {2,3,5,11} 2 × 3 × 5 × 11 = 330

And the result? The factors of 330 are 1, 2, 3, 5, 6, 10, 11, 15, 22, 30, 33, 55, 66, 110, 165, 330, and -1, -2, -3, etc as well (using the All Factors Tool).

## Automated

I couldn't resist making this available to you in an automated way.

So, if you need a power set, try Power Set Maker