Power Set

In the world of set theory and discrete mathematics, the concept of a power set forms a fundamental building block. Whether you're diving into computer science, logic, or pure mathematics, understanding power sets can unlock a deeper grasp of subsets, functions, and advanced theoretical constructs.

In this comprehensive guide, you'll explore:

• What a power set is and its importance
• How to find the power set of any given set
• Key properties and real-world applications
• Practice problems to solidify your understanding

What is a Power Set? 

Formal Definition

A power set of a set S is the collection of all possible subsets of S, including the empty set ∅ and S itself.

Mathematical Notation

• Power Set of S: P(S)
• Other notations: ℘(S), P(A)

Visual Representation of a Power Set

Let's look at a simple example for better visualization:

Extended Example:

Consider the set of primary colors: C = {red, blue, yellow}

The power set P(C) consists of all possible subsets:

• Empty set: ∅ (no colors)
• Singleton sets: {red}, {blue}, {yellow} (individual colors)
• Pairs: {red, blue}, {red, yellow}, {blue, yellow} (color pairs)
• The full set: {red, blue, yellow} (all colors)

Thus, P(C) = {∅, {red}, {blue}, {yellow}, {red, blue}, {red, yellow}, {blue, yellow}, {red, blue, yellow}}

Properties of Power Sets

Understanding the properties of power sets can help you work with them more efficiently.

• Cardinality: If a set S has n elements, then P(S) has 2ⁿ elements.
• Inclusion: Every element of a power set is a subset of the original set.
• Empty Set: The empty set ∅ is always included in P(S).
• Universal Set Inclusion: The set S itself is always an element of its power set.

Example of Cardinality Property:

Power Set Examples (With Step-by-Step Solutions)

Example 1: Power Set of Empty Set P(∅)

Step 1: Identify the original set: The empty set ∅ has 0 elements.

Step 2: The only subset of ∅ is ∅ itself.

Step 3: Therefore, P(∅) = {∅}

Verification: According to our formula, the power set should have 2⁰ = 1 element, which matches our answer.

Example 2: Power Set of a Singleton Set P({a})

Step 1: Identify the original set: S = {a} has 1 element.

Step 2: List all possible subsets:

• The empty set: ∅
• The set itself: {a}

Step 3: Therefore, P({a}) = {∅, {a}}

Verification: Our formula indicates 2¹ = 2 elements, which matches our answer.

Example 3: Power Set of {a,b}

Step 1: Identify the original set: S = {a,b} has 2 elements.

Step 2: List all possible subsets:

• Subset with 0 elements: ∅
• Subsets with 1 element: {a}, {b}
• Subset with 2 elements: {a,b}

Step 3: Therefore, P({a, b}) = {∅, {a}, {b}, {a,b}}

Verification: Our formula predicts 2² = 4 elements, which matches our answer.

Example 4: Power Set of {1,2,3}

Step 1: Identify the original set: S = {1,2,3} has 3 elements.

Step 2: List all possible subsets systematically:

Step 3: Combine all subsets to get:
P({1,2,3}) = {∅, {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}}

Verification: Our formula predicts 2³ = 8 elements, which matches our answer.

Real-world Example: If a restaurant offers soup (S), salad (L), and bread (B) as optional side items, the power set represents all possible combinations a customer can order:

• No sides: ∅
• Single sides: {S}, {L}, {B}
• Pairs of sides: {S,L}, {S,B}, {L,B}
• All sides: {S,L,B}

Power Sets in Set Operations

Power Sets and Union

• P(A ∪ B) is not generally equal to P(A) ∪ P(B).
• Example: Union of two sets usually has more subsets.

Worked Example:
Let A = {1} and B = {2}

1. Find P(A): P({1}) = {∅, {1}}
2. Find P(B): P({2}) = {∅, {2}}
3. Find P(A) ∪ P(B): {∅, {1}, {2}} (note that ∅ appears in both sets but is counted once in the union)
4. Find A ∪ B: {1, 2}
5. Find P(A ∪ B): P({1, 2}) = {∅, {1}, {2}, {1, 2}}

We can see that P(A ∪ B) ≠ P(A) ∪ P(B) since {1, 2} is in P(A ∪ B) but not in P(A) ∪ P(B).

Power Sets and Intersection

• P(A ∩ B) ⊆ P(A) ∩ P(B)

Worked Example:
Let A = {1, 2} and B = {2, 3}

1. Find A ∩ B: {2}
2. Find P(A ∩ B): P({2}) = {∅, {2}}
3. Find P(A): P({1, 2}) = {∅, {1}, {2}, {1, 2}}
4. Find P(B): P({2, 3}) = {∅, {2}, {3}, {2, 3}}
5. Find P(A) ∩ P(B): {∅, {2}}

We can verify that P(A ∩ B) = P(A) ∩ P(B) in this example.

Visual Representations of Power Sets

Hasse Diagrams

A Hasse diagram shows the subsets' ordering. Here is an example for {a, b}:

 {a,b} / \ {a} {b} \ / \emptyset 

Extended Example:
For set S = {1, 2, 3}, the Hasse diagram would be:

 {1,2,3} / | \ {1,2} {1,3} {2,3} / \ / \ / \ {1} {2} {3} \ / \ / \emptyset 

Binary Representation (Bit Vectors)

Each subset can be represented as a binary number:

Algorithmic Application:
This binary representation allows us to generate all subsets of a set by counting from 0 to 2ⁿ-1 in binary and including elements corresponding to 1s in each binary number.

Applications of Power Sets

• Computer Science: Used in Boolean functions and database query optimizations
• Combinatorics: Helps in counting problems and solving complex arrangements
• Probability Theory: Represents sample spaces and events
• Advanced Mathematics: Important in fields like topology and category theory

Database Query Example:
Imagine a database of books with attributes: Fiction (F), Hardcover (H), and Illustrated (I).
The power set P({F, H, I}) represents all possible query filter combinations:

• ∅: No filters (all books)
• {F}: Only fiction books
• {H}: Only hardcover books
• {I}: Only illustrated books
• {F, H}: Fiction hardcover books
• {F, I}: Illustrated fiction books
• {H, I}: Illustrated hardcover books
• {F, H, I}: Illustrated fiction hardcover books

Probability Theory Example:
In flipping a coin twice, the sample space is S = {HH, HT, TH, TT}.
The power set P(S) represents all possible events that could occur, including:

• Getting at least one head: {HH, HT, TH}
• Getting exactly one head: {HT, TH}
• Getting all tails: {TT}

Power Sets in Relation to Other Mathematical Concepts

• Cartesian Products: Power sets differ from the Cartesian product but are interconnected in set operations.
• Relations: Relations can be formed over elements of a power set.
• Functions: Many mathematical functions map between power sets.

Cartesian Product Example:
For sets A = {1, 2} and B = {a, b}:

• The power set P(A) = {∅, {1}, {2}, {1, 2}} contains 4 elements
• The Cartesian product A × B = {(1,a), (1,b), (2,a), (2,b)} contains ordered pairs

Relations Example:
A reflexive relation on set S = {a, b, c} is a subset of S × S that includes all pairs (x,x).
This can be represented as an element of the power set P(S × S).

Functions Example:
For sets X = {1, 2} and Y = {a, b}, the set of all functions from X to Y can be represented using elements of P(X × Y) that satisfy the function property.

Conclusion

• A power set is the collection of all subsets, including the empty set and the original set.
• Cardinality of P(S) is 2ⁿ where n is the number of elements in S.
• Applications extend across mathematics, computer science, and probability theory.

Example of Exponential Growth:
The power set grows exponentially with the original set size:

Next Steps: Explore related topics like Boolean algebra, relations, and functions in set theory.

Practice Problems

Beginner Level

• Find the power set of {x}.
• Find the power set of {1, 2}.

Intermediate Level

• Prove that the cardinality of the power set P(S) is 2ⁿ.

Solution Approach:
For each element in the original set, we have two choices: include it in a subset or exclude it. With n elements, we have 2ⁿ different possible combinations of choices.

Advanced Level

• Apply the concept of power sets to describe sample spaces in probability theory.

Example Solution:
When rolling two dice, the sample space is S = {(1,1), (1,2), ..., (6,6)} with 36 outcomes.
The power set P(S) represents all possible events. For instance:

• "Sum equals 7" is the subset {(1,6), (2,5), (3,4), (4,3), (5,2), (6,1)} ∈ P(S)
• "First die shows 6" is the subset {(6,1), (6,2), (6,3), (6,4), (6,5), (6,6)} ∈ P(S)