15.6. Power Set

We next define what we call as the power set of a set and we use this notation P(S). So, you are given a set S. And if I take the collection of all subsets of this set S, then that itself is a set because I am just listing down the subsets of S and the elements here the elements of P(S) are the subsets of S.

The power set, denoted as P(S), is a collection of all possible subsets of a given set S. This includes every combination of elements in S, including the empty set and S itself. For example, if S has elements {1, 2}, its subsets are: { } (empty set), {1}, {2}, and {1, 2}. Thus, the power set P(S) is {{ }, {1}, {2}, {1, 2}}.

Think of a power set as a menu of all possible dishes that can be made from a limited set of ingredients. If you have two ingredients, say salt and pepper, you could serve them separately, together, or not at all. The menu (power set) would include the options: just salt, just pepper, both, and none at all.

So, let us try to find out that what will be the powerset of ϕ. So, it turns out that a power set of ϕ will be a singleton set consisting of the empty set, because empty set is always a subset of itself or any set.

The power set of an empty set (ϕ) contains only one subset, which is the empty set itself. Therefore, P(ϕ) = {{ϕ}}. This is fundamental to the definition of power sets, as every set, including the empty set, always has one subset – itself.

Imagine an empty box that can hold items. The only 'subset' it can have is the empty box itself, because it has no items inside. Thus, the power set here only describes that empty box.

What will be the power set of this singleton set which has ϕ as its element, it turns out that the power set will have two elements because ϕ is a subset of any set.

For a singleton set, say S = {ϕ}, there are two subsets: the empty set (ϕ) and the set itself ({ϕ}). Thus, the power set P({ϕ}) contains both: P({ϕ}) = {{ϕ}, { }}. This concept illustrates how even with minimal elements, the power set can still generate multiple subsets.

Think of a single light bulb in a room. The power set includes one option where the light is off (no light) and one where it is on (the bulb). So, you have two states you can have, reflecting the subsets of the set with the light bulb.

Now a very fundamental fact here is that, if the cardinality of your set is n where n is some non-negative integer, then the cardinality of the power set will be 2n.

This fact means that if a set has n elements, the power set will have 2 raised to the power of n subsets. For example, a set with 3 elements {a, b, c} will have a power set P({a, b, c}) with 2³ = 8 subsets: { }, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c}. This exponential growth shows how quickly the number of subsets increases as the size of the initial set increases.

Consider an ice cream shop with 3 flavors: chocolate, vanilla, and strawberry. Each customer can choose to have one flavor, any combination of the three flavors, or none at all. The combinations of flavors reflect the subsets, and the exponential growth illustrates how many different ways customers can choose their combinations.

And since this is a universally quantified statement, applicable for all n, a natural choice here to apply the proof by induction namely we will prove the statement by induction on the value of n.

To prove that the cardinality of the power set is 2 raised to n for all natural numbers, we can use mathematical induction. We start with the base case n=0, where the power set contains one subset – the empty set. For the inductive step, if it holds true for n, we show that it holds for n+1 by demonstrating that adding one more element doubles the number of subsets. This systematic approach solidifies the understanding of power sets' growth.

Imagine stacking books on a shelf. If you start with no books, you have one way to arrange (which is just 'nothing'). When you add one book, you not only keep the previous arrangement but also create new possibilities by having that book either included or not, effectively doubling your arrangements.

--