1 Definition

A power set is the collection of all subsets of a given set. It always includes the empty set and the original set itself, since both are subsets of every set. Power sets are central in set theory because they gather every possible selection that can be made from the elements of a set.

1.1 Formal definition

For a set \(S\), the power set of \(S\) is the set of all subsets of \(S\). It is commonly written as \(\mathcal{P}(S)\) or \(2^S\). Thus, \[ \mathcal{P}(S)=\{A \mid A \subseteq S\}. \] Each element of the power set is itself a set.

1.2 Notation

Two notations are especially common. The symbol \(\mathcal{P}(S)\) emphasizes that the result is a set of subsets, while \(2^S\) reflects the fact that a finite set with \(n\) elements has \(2^n\) subsets. The latter notation is also used in more abstract mathematical settings.

1.3 Examples

1.3.1 Power set of a finite set

If \(S=\{a,b\}\), then its power set is \[ \mathcal{P}(S)=\{\varnothing,\{a\},\{b\},\{a,b\}\}. \] This example shows that every subset is included, from the smallest possible one to the full set.

1.3.2 Power set of the empty set

The empty set has exactly one subset: itself. Therefore, \[ \mathcal{P}(\varnothing)=\{\varnothing\}. \] This is an important base case in many inductive arguments.

1.3.3 Power set of an infinite set

For an infinite set, the power set is much larger than the set itself. For example, the power set of the natural numbers contains all finite subsets, all infinite subsets, and many other collections. Its size is strictly greater than the size of the original infinite set.

2 Basic properties

Power sets have several simple but powerful structural properties. These properties make them useful in counting, algebraic reasoning, and the study of order relations among sets.

2.1 Cardinality of a power set

If a set has \(n\) elements and \(n\) is finite, then its power set has \(2^n\) elements. This follows because each element may either be included in a subset or excluded from it, giving two choices per element. Multiplying these independent choices yields \(2^n\) possible subsets.

2.2 Inclusion relation

If \(A \subseteq B\), then every subset of \(A\) is also a subset of \(B\). In other words, \[ \mathcal{P}(A) \subseteq \mathcal{P}(B). \] This monotonic behavior reflects how inclusion among sets is preserved at the level of their power sets.

2.3 Boolean algebra structure

The power set of a fixed set can be viewed as a Boolean algebra when equipped with union, intersection, and complement relative to the underlying set. Under these operations, subsets behave much like truth values in formal logic. This structure makes power sets a natural setting for algebraic and logical arguments.

2.4 Closure properties

The power set is closed under the formation of subsets in the following sense: if \(X\) is an element of \(\mathcal{P}(S)\), then \(X\subseteq S\) by definition. However, operations performed on subsets, such as union and intersection, may produce another subset of \(S\), so these operations stay within the power set. Complement also remains inside the power set when taken relative to \(S\).

3 Construction and enumeration

Power sets can be built and listed in several systematic ways. These methods are especially useful for finite sets, where all subsets can be explicitly enumerated.

3.1 Listing subsets

A direct way to construct a power set is to list every subset by size. One may begin with the empty set, then list all single-element subsets, then all two-element subsets, and so on until the full set is reached. This method is straightforward but becomes cumbersome as the number of elements increases.

3.2 Binary representation method

For a finite set with \(n\) elements, each subset can be encoded by a binary string of length \(n\). For each element, a 1 may indicate inclusion and a 0 exclusion. This gives a one-to-one correspondence between subsets and binary numbers from \(0\) to \(2^n-1\). The method provides an efficient way to count and generate subsets.

3.3 Recursive construction

A power set can also be built recursively. Starting with a set \(S\), choose one element \(x\in S\). Every subset of \(S\) either contains \(x\) or does not contain \(x\). Thus, the power set can be formed from the power set of \(S\setminus\{x\}\) by creating two copies: one with \(x\) added and one without it. This recursive view underlies many proofs by induction.

4 Examples in discrete mathematics

Power sets appear frequently in combinatorics and related branches of discrete mathematics. They provide a natural language for describing choices, selections, and collections of objects.

4.1 Counting subsets

Counting subsets of a finite set is a standard application of power sets. If a set has \(n\) elements, then the number of subsets of size \(k\) is \(\binom{n}{k}\), and summing over all possible \(k\) gives \[ \sum_{k=0}^{n}\binom{n}{k}=2^n. \] This identity connects power sets with binomial coefficients.

4.2 Combinatorial interpretation

The power set of a set may be interpreted as the set of all possible selections from that set. Each subset represents a possible outcome of choosing some elements and rejecting others. This viewpoint is useful in probability, counting, and the analysis of finite structures.

4.3 Use in relations and functions

Power sets are often used to describe families of relations and functions. Since relations and functions can be represented as sets of ordered pairs, power sets provide a convenient ambient space for collecting them.

4.3.1 Sets of possible relations

A relation from \(A\) to \(B\) is a subset of \(A\times B\). Therefore, the set of all such relations is the power set \(\mathcal{P}(A\times B)\). This observation makes the study of relations a problem about subsets of a Cartesian product.

4.3.2 Sets of possible mappings

Functions from one set to another are special relations that satisfy additional conditions. They also belong to the power set of the corresponding Cartesian product, but only certain subsets qualify as functions. The power set thus serves as the larger space in which all possible mappings can be considered.

Several basic ideas are closely connected to power sets. These related notions often appear together in elementary set theory and discrete mathematics.

5.1 Subset

A subset is any set whose elements all belong to another set. Power sets are built entirely from subsets, so the concept of subset is the foundation of the definition.

5.2 Cartesian product

The Cartesian product of two sets consists of ordered pairs formed from their elements. It is important because relations and functions are subsets of Cartesian products, and power sets describe all such subsets.

5.3 Boolean lattice

A Boolean lattice is the ordered structure formed by the subsets of a set under inclusion. The power set of a finite set naturally forms such a lattice, with union, intersection, and complement as key operations.

5.4 Complement and set operations

Complement, union, and intersection are standard operations on subsets. When applied relative to a fixed set, these operations keep results inside the same power set and support algebraic manipulation of subsets.

6 Applications

Power sets are used in several areas of mathematics and computer science because they organize all possible choices from a collection of items.

6.1 Logic and propositional reasoning

In logic, subsets can represent truth assignments or collections of satisfied conditions. The Boolean structure of a power set mirrors logical operations such as conjunction, disjunction, and negation. This makes power sets a useful tool for formal reasoning and truth-table style analysis.

6.2 Computer science and algorithms

Power sets arise in algorithms that search through all combinations of items, such as subset generation, backtracking, and exhaustive search. They also appear in data structures and combinatorial optimization, where the task is often to inspect or compare many possible selections. Because power sets grow rapidly, they also illustrate the limits of brute-force computation.

6.3 Probability and event spaces

In elementary probability, the collection of all possible events is often modeled as a set of subsets of a sample space. Each event corresponds to a subset of outcomes, and probabilities are assigned to those subsets. This makes the power set a natural starting point for defining event spaces in simple probability models.