Definition
Basic Concept
Power set of a set S: collection of all subsets of S, including empty set and S itself.
Formal Definition
Given set S, power set P(S) = { A | A β S }.
Set Inclusion
Every element of P(S) is a subset of S. P(S) β β(U) if S β U.
Notation and Terminology
Symbol
Power set denoted by π«(S), 2^S, or β(S).
Subsets
Elements of power set called subsets or members of π«(S).
Universal Set Context
Power set depends on base set S; universal set U may contain S, but irrelevant to definition.
Cardinality
Formula
|π«(S)| = 2^|S|, where |S| is cardinality of S.
Finite Sets
If S finite with n elements, π«(S) has 2^n elements.
Infinite Sets
For infinite S, |π«(S)| > |S| by Cantor's theorem (uncountably infinite).
Construction Methods
Iterative Approach
Start with empty set; add elements one by one; generate subsets by union.
Recursive Definition
π«(β ) = {β }; for x β S, π«(S βͺ {x}) = π«(S) βͺ { A βͺ {x} | A β π«(S) }.
Algorithmic Generation
Use bitmask or backtracking to enumerate all subsets.
Examples
Empty Set
π«(β ) = {β } with cardinality 1.
Singleton Set
For S = {a}, π«(S) = {β , {a}}.
Set with Two Elements
For S = {a,b}, π«(S) = {β , {a}, {b}, {a,b}}.
| Set S | Power Set π«(S) | Cardinality |
|---|---|---|
| β | {β } | 1 |
| {a} | {β , {a}} | 2 |
| {a,b} | {β , {a}, {b}, {a,b}} | 4 |
Binary Representation
Mapping to Bit Strings
Each subset corresponds to an n-bit binary vector; bit 1 means element included.
Example
For S = {a,b,c}, subset {a,c} maps to 101 (a=1,b=0,c=1).
Enumeration Algorithm
Iterate i = 0 to 2^n -1; i's binary form indicates subset.
for i in 0..2^n-1: subset = {} for j in 0..n-1: if (i >> j) & 1 == 1: subset.add(S[j]) output subsetProperties
Containment
π«(S) always contains β and S.
Closure
Closed under union, intersection, complement (with respect to S).
Partial Order
Ordered by β; forms a partially ordered set (poset).
Boolean Algebra
π«(S) with union, intersection, complement forms Boolean algebra.
Algebraic Structure
Lattice
π«(S) is a lattice with meet = intersection, join = union.
Distributivity
Lattice is distributive: meet and join distribute over each other.
Complementation
Complement of subset A is S \ A; unique complement exists.
Given A β S: complement(A) = { x β S | x β A }Applications
Combinatorics
Counting subsets, combinations, binomial coefficients.
Logic and Boolean Algebra
Modeling propositions, truth assignments, logical expressions.
Computer Science
State space exploration, power set construction in automata theory.
Probability
Event space representation, sigma-algebras start from power sets.
Computational Aspects
Algorithmic Complexity
Generating π«(S) takes O(2^n) time and space for |S|=n.
Data Structures
Bit vectors, arrays, trees used to store or traverse π«(S).
Practical Limitations
Exponential growth limits use to small or structured sets.
Limitations and Complexity
Exponential Growth
Size doubles with each new element; infeasible for large sets.
Memory Constraints
Storing 2^n subsets requires exponential memory.
Computational Hardness
Many problems on subsets are NP-hard due to power set size.
| Set Size (n) | Power Set Size (2^n) | Remarks |
|---|---|---|
| 10 | 1,024 | Manageable |
| 20 | 1,048,576 | High resource use |
| 30 | 1,073,741,824 | Impractical |
References
- Halmos, P.R., Naive Set Theory, Springer, 1974, pp. 37-45.
- Enderton, H.B., Elements of Set Theory, Academic Press, 1977, pp. 55-60.
- Rosen, K.H., Discrete Mathematics and Its Applications, McGraw-Hill, 7th Ed., 2011, pp. 164-170.
- Simmons, H., Introduction to Topology and Modern Analysis, McGraw-Hill, 1963, pp. 21-27.
- GrΓ€tzer, G., General Lattice Theory, BirkhΓ€user, 2003, pp. 5-15.