Power Set

The power set is a collection of all possible subsets of a given set, including the empty set. The power set of S is written as P(S) or 2S. For example, if S =a,b, then the power set of S is:
P(S)=,a,b,a,b

We can build a power set step by step using recursion. The recursive definition is a way of defining a set where each new element is built based on the elements already in the set. The recursive definition of a finite power set S is:
For S = , P(S) =  or, it can also be represented as:
If the set is empty, S = , then the only subset is the empty set itself:
P() =.
If the set is not empty, then we use the recursive algorithm of the power set.
Here, S =T{t}, which means that we add the element t to set T, then the recursive definition of power set S is:
 P(S)=P(T){Xt|XP(T)}
P(S) is the power set of the new set
P(T) is the power set of the smaller set T, without the new element t
XP(T) refers to each subset X that is already in the power set of T
Xt represents a new subset for each subset X, it includes the element t.
We know the power set of A; we will use it to build the power set of S.
To do so, first take all the subsets of A; these subsets do not include x. Then, make a second copy of these subsets and add x to each of them. Finally, join both groups together. This will give us the complete power set of S. Let us take an example to understand:

Question: Build the power set of a,b:

1. Start with, power set P({a})=,a
2. Now add b, b,a,b
3. Combine them all, P(a,b)=,a, b, a,b

This method can be used on any set. This method builds the power set step-by-step by adding one element at a time and expanding all existing subsets with it.
 

The following properties characterize a power set:

• Power set of empty set: the empty, or null set, is also included in the power set. It contains no elements and is denoted by We know that the number of elements in a power set is given by the formula 2n, where n is the number of elements in the original set. Since the empty set has n = 0 elements, its power set will have 20 = 1 element.This means that the power set of any empty set has only one subset, which is the empty set itself, P() = 

• The cardinality of power set: Cardinality of a set refers to the total count of elements it contains. For example, take the set B=x,y, since there are 2 elements in this set, the cardinality of set B is 2. The total number of subsets is calculated using formula 2n, since here the set B has 2 elements, the cardinality of its power set is 22 = 4.

• Power set of countable sel. A=a,b,c,d,e is countably finite because it has a limited number of elements. Whereas, the set B=1,2,3,4. . . is countably infinite as its elements keep going on, but they can still be listed in order. If a set has finite elements, then the power set is finite; if the set has infinite elements, then the set is uncountably infinite.

• Power set of uncountable sets: An uncountable set has elements that cannot be counted or listed completely. Real numbers are an example of an uncountable set; there is no way to list all real numbers. These sets are always infinite. The power set of an uncountable set is uncountable, infinite, and larger than the original set. 
   

The binomial theorem helps us determine how many subsets of each size exist in a set. In a set with n elements, the number of subsets that contain k elements is given by C(n, k).
Let’s take an example to understand how the binomial theorem helps in counting subsets.
Let’s take a set S=a,b,c with 3 elements. 
The power set of S includes all possible subsets from the empty set to the full set.
We can use binomial coefficients to count how many subsets exist at each level based on the number of elements in the subset:
C(3,0)=1 
One subset with 0 elements, which means this is the empty subset.
C(3,1)=3 
Three subsets with one element each.
C(3,2)=3 
Three subsets with two elements each.
C(3,3)=1 
One subset with all three elements
Now, we add all these subsets, 1+3+3+1=8
So, the power set of a 3-element set contains 23 = 8.
This leads us to the general formula
2S=k=0SS,K
If S is equal to n, then we have,
2S=2S=k=0Sn,K
Where, 
N is the number of elements in a set
(n,k) counts the number of subsets with exactly k elements, and
2n gives the total number of subsets in the power set
 

The cardinality of a power set represents all possible subsets including the empty set and the set itself. Take, for example, the set C=x, y, z, w. This set contains 4 elements, so the cardinality of c is 4. The cardinality of its power set is 24 = 16. So the power set of C has 16 subsets.

Power Set Proof

To show that if a set A contains n elements, then its power P(A) has 2n elements. In other words, the cardinality of a finite set A with ‘n’ elements is |P(A)| = 2n.
We follow the pattern of mathematical induction for the proof of the power set.
Let's consider the case of an empty set.

Case 1: A set with no elements, n = 0 
Let A =  (empty set)
The only subset of the empty set is itself, so P() = .
Since there is only 1 element in the set, the cardinality of the set will be 2n = 21 = 1.

Case 2: We now assume that the rule holds for a set with n elements such that a set 2n has subsets.
Let's call this set X, now suppose
X=nP(X)=2n
Now, lets create a new set Y by adding one new element, say an+1, to set X:
Y = X U an+1
So the number of elements in Y is n + 1.
There are 2 kinds of subsets in Y: one having the new element an=1 and the other without it.
So in total: P(Y)=2n(without an+1)+2n(with an+1) =22n=2n+1  
This proves that if the formula holds for n, it also holds for n + 1.
Let us apply this proof using an example,
Let X=a, b, c 
Let Y=a, b, c, d
Here,
X=3, so the number of subsets of X is 23 = 8
Y=4, and we’ll prove that the number of subsets of Y is 24 = 16.
Subsets of X = {}, a,b,c,a,b,a,cb,ca,b,c
So, X has a total of 8 subsets.
Subsets of Y = {},a,b,c,a,b,a,c,b,c,a,b,c
These are 8 subsets that do not include d.
Now for subsets of Y with d = {d},a,d,b,d,c,d,a,b,d,a,c,d,b,c,d,a,b,c,d
There are 8 more subsets of Y when d is added.
Total subsets of Y = 16.
Here, 4 is the extra element in set Y.
This example confirms that if a set with n elements has 2n subsets, then adding one more element doubles the number of subsets to 2n+1.
 

According to the rule of set theory, if a set has n elements, then its power set will have 2n elements. An empty set is represented by  or . Since it contains 0 elements, the number of subsets it has is 20 = 1.
The empty set is considered a subset of every set, including itself, even though it has no elements. So the power set of the empty set has just one subset, the empty set itself, P()= and it contains one element.
 

From organizing schedules in day-to-day life to working with computer logic, power sets help in the selection and grouping of items. A few real-life applications of power sets are listed below:

Survey and questionnaire analysis

When analyzing survey data with multiple options, a power set helps in modelling all possibilities of response combinations.

Database queries

In databases, power sets are used to find all possible combinations of filters or search criteria.

Circuit design in electronics

Engineers use power sets in designing circuits to evaluate all possible input combinations.

Event planning

Events require multiple activities like food, venue, music, games, etc. Power sets list every possible combination of activities to choose from. This helps event management companies in planning events accordingly.

Computer science testing and security
 

Power sets are used in software testing and cybersecurity to test every possible combination of features or permissions for security.