Power Set: Subsets, Cardinality, Proof & Binomial Theorem

Power set contains the original set, the empty set, and all other subsets. Usually, the letter P is used to represent it.

• The number of subsets that can be generated from a given set determines the cardinality of a power set. 
• If the set A = {x, y, z} is one set, then all of its subsets {x}, {y}, {z}, {x, y}, {y, z}, {x, z}, {x, y, z} and {} are the components of the power set.

For example:

Power set of A, P(A) = { {x}, {y}, {z}, {x, y}, {y, z}, {x, z}, {x, y, z}, {} }

Read More: Sets Important Questions

Key Terms: Power Set, Subset, Countable Set, Uncountable Set, Superset, Set, Empty Set, Cardinality

---

What is Power Set?

[Click Here for Sample Questions]

A power set is a set or a group of all subsets and the empty set included in a set. It is denoted by {} or ϕ . There are 2ⁿ subsets in a set that contains ‘n’ elements.

For instance, set A = {1,2,3} contains 2³ in the power set.

Set A = {1,2,3}

Subsets of set A = {}, {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3}

Power set P(A) = { {}, {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3} }

Power Set Diagram

Read More: 

---

What are Subsets?

[Click Here for Previous Year Questions]

If every element in a set A is also an element in a set B, then the set A is a subset of the set B. The set A is therefore contained within the set B. A⊂B is used to represent the subset connection.

For example, if a set has {x, y, z} as variables.

The empty set {} is a subset of {x,y,z}.

{x}, {y} and {z} are also subsets

{x,y}, {y,z} and {x,z} are also subsets

And {x,y,z} is also a subset.

---

Properties of Power Set

[Click Here for Sample Questions]

Following are the properties of a power set:

• The Power Set is significantly larger than the Original Set.
• The Power Set A has 2ⁿ elements, where n is the total number of elements in Set A.
• If a set is finite and countable, it has a power set.
•  One-to-one mapping of the resulting set, P(S) can be done using real numbers for a set of natural numbers.
• If operations like union, intersection, and complement are carried out on Set S, P(S) of Set S implies the Boolean Algebra.

Read Also: Associative Property

---

Cardinality of Power Set

[Click Here for Previous Year Questions]

The total number of items in a set is referred to as the set's cardinality. The list of the number of subsets of a set will be the cardinality in the case of a power set. 

|P (A)|, where A is any set, is the notation for the number of elements in a power set. The following formula can be used to determine how many subsets of a set there are in a power set if A has 'n' elements:

|P (A)| = 2ⁿ

For example, set A = {1, 2, 3}

n = number of elements of A = 3

So, the number of subsets in a power set of A will be:

Subsets of A = {}, {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3}

|P (A)| = 2³ = 8

Hence, P(A) = { {}, {1}, {2}, {3}, {1,2}, {2,3}, {1,3}, {1,2,3} }

Read Also: Commutative Property: Formula, Properties, Sample Questions 

---

Power Set Proof

[Click Here for Sample Questions]

For a finite set A with ‘n’ elements, the cardinality is |P(A)| = 2ⁿ. The proof of power set adheres to the rules of mathematical induction. An empty set, that is, a set with no elements is to be considered for the same.

Case 1

An empty set. Let A = {}

Since there is just one element, which is the empty set, the power set of A, indicated by P(A)={}, has a cardinality of |P(A)| = 1 in this situation. Also, according to the formula for a power set's cardinality, there will be 2ⁿ power sets, which is equal to 2⁰ or 1.

Case 2

This is an inductive procedure. P(n) → P(n+1) must be proved in this step. This means that if a set of elements contains n elements and 2n subsets, then a set having n+1 elements will have 2ⁿ⁺¹ subsets.

Two sets, "X" and "Y," with the following components are to be considered in order to demonstrate this.

X = {a¹, a², a³, a⁴, aⁿ}

Y = {a¹, a², a³, a⁴, aⁿ, aⁿ⁺¹}

There are 2ⁿ subsets for the set "X" since the two sets "X" and "Y" have cardinality of |X| = n.

|Y| = n + 1

Thus, Y = X U {a_n+1} which means that every subset of set "X" is also a subset of set "Y."

The element a n+1 may or may not be present in a subset of set Y. It is obvious that a_n+1 is an element of set X if it is not present in set Y. Also, if the element a_n+1 is present in the subset of "Y," then any of the 2ⁿ subsets of "X" also contain the element a_n+1. It may be concluded that set "Y" has 2ⁿ subsets with element a_n+1. As a result, set Y has 2ⁿ subsets that contain element a_n+1 and 2ⁿ subsets that do not.

Check Also: 

---

Power Set of Empty Set

[Click Here for Previous Year Questions]

The power set will include 2n elements when the number of elements in a set is "n". An empty set is a set that is devoid of any elements. 

• It is symbolised by the curly brackets {} or the symbol Ø. This implies that {} is a subset of all sets. 
• An empty set is one without any elements. The power set of the empty set is therefore just that—an empty set.
• The power set of an empty set will have 2⁰ items since an empty set contains no elements. 
• The power set of an empty set is an empty set containing a single element, in this case, 2⁰ = 1. So, P(E) = {}.

Read More: Data Sets

---

Power Set of Countable Set

[Click Here for Sample Questions]

When the elements of a set can be counted, it is referred to as countable. It should be noted that a countable set can be infinite or finite. 

For example, set S₁ = {B, C, D, F, G, H, J, K, L, M, N, P, Q, R, S, T, V, W, X, Z, Y} representing all consonants is a countably finite set.

S₂ = {1, 2, 3, 4, 5, 6, ……} which represents a set of natural numbers, on the other hand, is a countably infinite set. The Power set of countably finite sets is always finite and thus, countable. 

For instance, the consonant set S₁ has 21 elements, and its power set will include 2²¹ = 2,097,152 elements. As a result, it is finite and countable. It is impossible to count the power set of countably infinite sets.

---

Power Set of Uncountable Set

[Click Here for Previous Year Questions]

When the elements of a set cannot be numbered, the set is said to be uncountable. A set that cannot be counted is always infinite. 

• It is to be noted that the power set of an uncountable set is always uncountable.
• For instance, it is impossible to count the set S₃ that represents all fractional values between 1 and 10. 
• The power set of uncountable sets is therefore uncountable without exception.

Read Also: Union of Sets: Representation, Formula and Sample Questions 

---

Recursive Algorithm of Power Set

[Click Here for Sample Questions]

It is possible to create the power set P(S) of any finite set S using a recursive technique.

The definition of the operation F (e, T) is: 

F (e, T) = { X ∪ {e} | X ∈ T }

This returns every member of the set X in T that contains the element x.

For Set S = {}, the return is P(S) = { {} }

If not, the algorithm below is applied.

The following procedure produces the power set if e is an element of Set S and T = S {e} such that S {e} is the relative complement of the element e in Set S:

P(S) = P(T) ∪ F ( e, P(T))

In conclusion, the null set will be the lone element of the power set if set S is empty. In that case, the power set will be the union of all subsets that contain the specific element and all subsets that do not.

Relation of Power Set with Binomial Theorem

Power set and the binomial theorem are interrelated. The number of subsets with k elements for a set with n elements can be calculated from the number of C (n, k) combinations.

The power set of a set with 5 elements is provided as an example below.

1. C (4, 0) = Since we obtain 1 from the combination there will only be one subgroup. The subset will include 0 entries because k = 0. Thus, it denotes a single empty subset.
2. C (4, 1) = Since the combination would be 4, there will be 4 subsets each containing one element.
3. C (4, 2) = Since the combination is 6, there will be 6 subsets, each with two elements.
4. C (4, 3) = There would only be 4 subsets with 3 elements.
5. C (4, 4) = Only one subset with four items would exist.

The power set therefore equals the total of all the subsets. Which is:

P(S) = 1 subset (0 element) + 4 subsets (1 element) + 6 subsets (2 elements) + 4 subsets (3 elements) + 1 subset (4 elements)

Consequently, there will be a total of 16 elements in the power set.

The relation | 2S| may be represented using the following formula:

---

Things to Remember

• A power set is a set that includes the empty set and all of the subsets of a particular set. For instance, if set A = {a, b}, then the power set of A is { {}, {a}, {b}, {a,b} }.
• The total number of elements in a power set is indicated by the term "cardinality."
• The symbol for cardinality is |P(X)|.
• For a set of 'n' items, the cardinality of a power set is given by '2ⁿ'.
• An empty set is one that possesses no elements. 
• The empty set is a constant element of a power set. The power set of an empty set is therefore just an empty set. It only contains one element. P(ϕ) = {ϕ}.

---

Previous Year Questions

1. For any two sets A and B, A-(A−B) equals… (WBJEE - 2009)
2. In a certain town… [KEAM]
3. In a class of … [KCET 2014]
4. If A and B are non-empty sets such that… (KEAM)
5. Let A and B be two sets then (A∪B)′… (BITSAT - 1990)
6. Two finite sets have m and n elements. The total number…
7. Which of the following sets is a finite set…
8. If A\B = {a, b}, B\A = {c, d} and A\B = {e, f}… [KEAM]
9. If n(A) = 43, n(B) = 51… [KEAM]