Power set

{{FORMULA: expr=|P(A)| = 2ⁿ | symbols=P(A): The power set of A, n: The number of elements in set A (|A|), |...|: Cardinality or size}}

The Power Set: A Set of All Sets

Imagine you have a set of toppings for a pizza: A = {mushroom, onion, olive}. What are all the possible pizzas you could make? You could have a plain pizza (no toppings), one with just mushrooms, one with mushrooms and onions, and so on, all the way to a pizza with all three toppings. The collection of all these possible combinations of toppings forms a new, bigger set. This "set of all possible subsets" is what we call the Power Set.

In mathematics, the power set of any given set A, denoted as P(A), is the set of all possible subsets of A, including the empty set {} (also denoted by ∅) and the set A itself. It’s a fundamental concept in set theory and combinatorics, with surprising applications in computer science, particularly in areas like database theory and algorithm design, where we often need to work with all possible combinations of a collection of items.

What Exactly is a Power Set?

Let's formalize the definition. For any set A, its power set P(A) is a set whose elements are all the subsets of A.

{{KEY: type=definition | title=Formal Definition of Power Set | text=If A is a set, then the power set of A, denoted P(A), is the set defined as: P(A) = {X | X is a subset of A}. In symbols: P(A) = {X | X ⊆ A}.}}

Let's break this down with our pizza example. If A = {mushroom, onion, olive}, then its subsets are:

• The empty set (plain pizza): {}
• Subsets with one element: {mushroom}, {onion}, {olive}
• Subsets with two elements: {mushroom, onion}, {mushroom, olive}, {onion, olive}
• The set itself (all toppings): {mushroom, onion, olive}

The power set P(A) is the collection of all these 8 subsets: P(A) = { {}, {mushroom}, {onion}, {olive}, {mushroom, onion}, {mushroom, olive}, {onion, olive}, {mushroom, onion, olive} }

Notice that the elements of P(A) are themselves sets. This is a crucial point to remember.

{{VISUAL: diagram: A set A = {1, 2} on the left. Arrows point from it to a larger box on the right labeled P(A), which contains four smaller boxes: {}, {1}, {2}, and {1, 2}, illustrating that the elements of the power set are all the subsets of A.}}

Cardinality of a Power Set

A very common question in JEE exams is to find the number of elements in a power set. As we saw in the opening formula, this is directly related to the number of elements in the original set.

If a finite set A has n elements (i.e., its cardinality is |A| = n), then the number of elements in its power set is |P(A)| = 2ⁿ.

Derivation: Why is it 2ⁿ?

Let's understand where this formula comes from using a simple combinatorial argument. This is a classic proof style you should be comfortable with.

1. Consider a set A = {a₁, a₂, a₃, ..., aₙ} with n elements.

2. To form any subset X of A, we must make a decision for each element of A: should we include it in our subset X or not?

3. For the first element, a₁, we have two choices:

   • Yes, include a₁ in the subset.
   • No, do not include a₁ in the subset.

4. Similarly, for the second element, a₂, we again have two independent choices (Yes/No).

5. This pattern continues for all n elements. For each of the n elements, there are 2 independent choices.

6. By the fundamental principle of counting (multiplication rule), the total number of ways to form a subset is the product of the number of choices for each element.

   Total number of subsets = 2 × 2 × 2 × ... × 2  (n times)
   

7. Therefore, the total number of possible subsets is 2ⁿ. Since the power set is the set of all these subsets, its cardinality is 2ⁿ.

   |P(A)| = 2ⁿ
   

{{CALLOUT: type=tip | text=This "binary choice" (include/exclude) for each element is a powerful way to think about subset problems. It connects set theory to binary numbers and combinatorics.}}

Properties of Power Sets

Power sets have several important properties that are frequently tested. Let's summarize them in a table.

{{VISUAL: diagram: A Venn Diagram showing two overlapping circles A and B. A smaller region P(A ∪ B) is shaded. Inside it, two overlapping regions P(A) and P(B) are shown, illustrating that P(A) ∪ P(B) is a proper subset of P(A ∪ B).}}

Solved Examples

Let's work through some examples, from basic to JEE Advanced level.

Example 1: Listing a Power Set

Given: A set B = {x, y}.

To Find: The power set P(B).

Solution:

1. The number of elements in B is n = 2. Therefore, the number of elements in P(B) will be 2² = 4.

2. List subsets with 0 elements: {}

3. List subsets with 1 element: {x}, {y}

4. List subsets with 2 elements: {x, y}

5. Combine all these subsets into a single set, which is the power set.

P(B) = { {}, {x}, {y}, {x, y} }

Final Answer: P(B) = { {}, {x}, {y}, {x, y} }

Example 2: Working Backwards from Cardinality

Given: A set A for which |P(A)| = 64.

To Find: The number of elements in set A, i.e., |A|.

Solution:

1. We know the formula relating the cardinality of a set and its power set:

   |P(A)| = 2^|A|
   

2. Substitute the given value:

   64 = 2^|A|
   

3. To solve for |A|, we need to express 64 as a power of 2. 64 = 2 × 32 = 2 × 16 × 2 = 2 × 8 × 2 × 2 = 2 × 4 × 2 × 2 × 2 = 2 × 2 × 2 × 2 × 2 × 2

   64 = 2⁶
   

4. Now, we can equate the exponents:

   2⁶ = 2^|A|
   

   Therefore, |A| = 6.

Final Answer: The number of elements in set A is 6.

Example 3: Subsets with Specific Constraints (JEE Main Level)

Given: A set S = {1, 2, 3, 4, 5, 6}.

To Find: The number of subsets of S that contain the element 3 but do not contain the element 6.

Solution:

1. This problem is about constructing a specific type of subset. Let's use the binary choice method derived earlier. For each element, we have a choice: include it or not.

2. Analyze the constraints for each element:

   • For element 3: It must be in the subset. There is only 1 choice (include).
   • For element 6: It must not be in the subset. There is only 1 choice (exclude).
   • For the remaining elements {1, 2, 4, 5} (which are 4 elements), there are no constraints. For each of these 4 elements, we have 2 choices (include or exclude).

3. Apply the multiplication principle to find the total number of ways to form such a subset.

   Total subsets = (Choices for 1) × (Choices for 2) × (Choices for 3) × (Choices for 4) × (Choices for 5) × (Choices for 6)
   

   Total subsets = 2 × 2 × 1 × 2 × 2 × 1
   

   Total subsets = 2⁴ = 16
   

Final Answer: There are 16 such subsets.

Example 4: Power Sets of Power Sets (JEE Advanced Level)

Given: The set A = {∅, {∅}}.

To Find: The number of elements in P(P(A)).

This is a classic question designed to test your understanding of nested sets and the power set definition. Let's solve this on the whiteboard.

{{SOLVE: {"problem":"Given A = {∅, {∅}}, find the number of elements in P(P(A)).","type":"numerical","subject":"math","intro":"This looks tricky, but it's just a repeated application of the formula. Chalo, whiteboard pe step-by-step karte hain.","outro":"So, the final answer is 16. The key was to apply the formula twice, carefully. Ok, ab class mein wapas chalte hain.","steps":[{"explanation":"First, we need to find the number of elements in A itself. The elements are ∅ (the empty set) and {∅} (a set containing the empty set). These are two distinct elements.","write":"A = {∅, {∅}} => |A| = 2","tough":false},{"explanation":"Now, we find the number of elements in the power set of A, which is P(A). We use the formula |P(X)| = 2^|X|. Here, X is A.","write":"|P(A)| = 2^|A| = 2² = 4","tough":false},{"explanation":"The question asks for the number of elements in P(P(A)). This means we are taking the power set of the set P(A). We apply the formula again, but this time our base set is P(A).","write":"Let B = P(A). We need to find |P(B)|.","tough":true,"alt_explanation":"So, we're finding the power set of another power set. We just use the same rule. The size of P(P(A)) is 2 raised to the power of the size of P(A)."},{"explanation":"We already found that the size of P(A) is 4. So, we substitute this into the formula.","write":"|P(P(A))| = 2^|P(A)| = 2⁴","tough":false},{"explanation":"Finally, we calculate the value of 2⁴ to get our answer.","write":"2⁴ = 2 × 2 × 2 × 2 = 16","tough":false}]}}}

Common Mistakes to Avoid

Students often make a few recurring errors when dealing with power sets. Being aware of them can save you valuable marks.

Tips & Tricks for JEE

Tricky Practice Problems

Test your understanding with these JEE-level questions.

1. Two finite sets have m and n elements. The total number of subsets of the first set is 112 more than the total number of subsets of the second set. Find the values of m and n.

   💡 Answer: We are given 2ᵐ - 2ⁿ = 112. Factoring, 2ⁿ(2ᵐ⁻ⁿ - 1) = 112. Since 112 = 16 × 7 = 2⁴ × 7, we can equate the even and odd parts. 2ⁿ = 2⁴ implies n = 4. And 2ᵐ⁻ⁿ - 1 = 7 implies 2ᵐ⁻⁴ = 8 = 2³, so m - 4 = 3, which gives m = 7. Thus, m = 7, n = 4.

2. If A and B are two sets such that A ∩ B has 3 elements, and A ∪ B has 6 elements. What is the minimum possible value of |P(A) Δ P(B)|? (Here Δ denotes the symmetric difference).

   💡 Answer: |P(A) Δ P(B)| = |P(A)| + |P(B)| - 2|P(A) ∩ P(B)|. We know P(A) ∩ P(B) = P(A ∩ B), so |P(A) ∩ P(B)| = 2|ᴬ∩ᴮ| = 2³ = 8. Also, |A| + |B| = |A∪B| + |A∩B| = 6 + 3 = 9. We need to minimize 2|ᴬ| + 2|ᴮ| - 16 subject to |A|+|B|=9 and |A|,|B| ≥ 3. The function f(x) = 2ˣ is convex, so the sum is minimized when the values are as close as possible. But here, they are integers. Let's check cases: (|A|, |B|) can be (3,6), (4,5). Case 1: |A|=3, |B|=6. Value = 2³+2⁶-16 = 8+64-16 = 56. Case 2: |A|=4, |B|=5. Value = 2⁴+2⁵-16 = 16+32-16 = 32. The minimum value is 32.

3. Let S = {1, 2, ..., n}. Let A be a randomly chosen non-empty subset of S. Let B be a randomly chosen non-empty subset of A. What is the probability that |B| = 1?

   💡 Answer: The number of ways to choose a non-empty subset A of size k is C(n, k). The number of ways to choose a non-empty subset B from A is 2ᵏ - 1. The number of ways to choose a subset B of size 1 from A is k. The total number of pairs (A, B) is Σ (k=1 to n) [C(n,k) * (2ᵏ - 1)]. The number of favorable pairs is Σ (k=1 to n) [C(n,k) * k]. Total pairs = Σ C(n,k)2ᵏ - Σ C(n,k) = (1+2)ⁿ - 1 - (2ⁿ - 1) = 3ⁿ - 2ⁿ. Favorable pairs = Σ k * C(n,k) = n * 2ⁿ⁻¹. Probability = (n * 2ⁿ⁻¹) / (3ⁿ - 2ⁿ).

Mini Cheatsheet

{{FLASHCARD: q="If a set A has 5 elements, how many non-empty proper subsets does it have?" | a="Total subsets = 2⁵ = 32. Proper subsets = 32 - 1 = 31. Non-empty proper subsets means we also exclude the empty set. But the proper set exclusion already removed A. If A is non-empty, the empty set is also a proper subset. So, non-empty proper subsets = (Total Subsets) - (The set A) - (The empty set) = 32 - 1 - 1 = 30."}}