Ability Set

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

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

All The Subsets

power set of {a,b,c}

For the set {a,b,c}:

  • The empty prepare {} is a subset of {a,b,c}
  • And these are subsets: {a}, {b} and {c}
  • And these are also subsets: {a,b}, {a,c} and {b,c}
  • And {a,b,c} is a subset of {a,b,c}

And altogether we get the Ability 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 unlike ways we tin select the items (the order of the items doesn't matter), including selecting none, or all.

ice cream

Example: The store has banana, chocolate and lemon water ice cream.

What practice y'all society?

  • Nothing at all: {}
  • Or perchance only banana: {banana}. Or just {chocolate} or only {lemon}
  • Or two together: {banana,chocolate} or {banana,lemon} or {chocolate,lemon}
  • Or all three! {banana, chocolate,lemon}

Question: if the shop also has strawberry season what are your options? Solution later.

How Many Subsets

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

Example: {a,b,c} has three members (a,b and c).

So, the Power Set should have 2iii = eight, which it does, as we worked out before.

Notation

The number of members of a set is ofttimes written as |Due south|, so when Due south has n members we can write:

|P(S)| = twon


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

Well, South has 5 members, so:

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

Y'all will see in a minute why the number of members is a power of 2

It'southward Binary!

And here is the near amazing affair. To create the Power Ready, write down the sequence of binary numbers (using north digits), so allow "1" mean "put the matching fellow member into this subset".

So "101" is replaced by 1 a, 0 b and 1 c to get us {a,c}

Like this:

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

Well, they are not in a pretty lodge, but they are all at that place.

Another Example

ice cream

Let's swallow! We have four flavors of ice cream: banana, chocolate, lemon, and strawberry. How many different means tin we have them?

Let'due south use letters for the flavors: {b, c, l, due south}. Instance selections include:

  • {} (nothing, you are on a diet)
  • {b, c, fifty, s} (every flavor)
  • {b, c} (banana and chocolate are good together)
  • etc

Permit's make the table using "binary":

bcls Subset
0 0000 {}
i 0001 {s}
2 0010 {l}
3 0011 {50,s}
... ... etc .. ... etc ...
12 1100 {b,c}
13 1101 {b,c,south}
14 1110 {b,c,l}
fifteen 1111 {b,c,50,south}

And the issue is (more neatly arranged):

P = { {}, {b}, {c}, {50}, {s}, {b,c}, {b,50}, {b,south}, {c,l}, {c,s}, {l,due south}, {b,c,l}, {b,c,south},
{b,l,south}, {c,fifty,southward}, {b,c,l,south} }


yin yang

Symmetry

In the table above, did yous observe that the first subset is empty and the concluding has every member?

But did you also discover that the second subset has "due south", and the second last subset has everything except "s"?
binary symmetry

In fact when nosotros mirror that tabular array near the middle we see there is a kind of symmetry.

This is because the binary numbers (that we used to assist us become all those combinations) take a beautiful and elegant pattern.

A Prime Example

The Power Set can exist useful in unexpected areas.

I wanted to find all factors (non only the prime factors, merely all factors) of a number.

I could examination all possible numbers: I could check 2, 3, iv, five, vi, vii, etc...

That took a long fourth dimension for large numbers.

But could I try to combine the prime factors?

Allow me see, the prime number factors of 510 are 2×iii×5×17 (using prime factor tool).

Then, all the factors of 510 are:

  • 2, 3, 5 and 17,
  • ii×3, ii×5 and two×17 every bit well, and
  • ii×3×5 and two×iii×17 and ...
  • .. aha! Just like water ice cream I needed a Power Fix!

And this is what I got:

2,3,5,17 Subset Factors of 510
0 0000 { } 1
1 0001 {17} 17
two 0010 {5} 5
3 0011 {5,17} five × 17 = 85
4 0100 {three} 3
5 0101 {3,17} 3 × 17 = 51
... etc ... ... etc ... ... etc ...
15 1111 {two,3,5,17} ii × 3 × 5 × 17 = 510


And the consequence? The factors of 510 are 1, ii, iii, 5, 6, 10, xv, 17, thirty, 34, 51, 85, 102, 170, 255 and 510 (and −1, −2, −3, etc as well). Run across the All Factors Tool.

Automatic

I couldn't resist making Ability Sets available to yous in an automated way.

And so, when y'all demand a power set, try Ability Set Maker.