# Power set

The power set of a set \( A \) is the set of all subsets of \( A \), written \( \mathcal{P}(A) \) or \( 2^A \).<sup>[1](https://math.libretexts.org/Bookshelves/Analysis/A_Primer_of_Real_Analysis_%28Sloughter%29/03%3A_Cardinality/3.03%3A_Power_Sets)</sup> It always contains the empty set \( \emptyset \) and \( A \) itself, since both are subsets of \( A \).<sup>[2](https://math.libretexts.org/Courses/Monroe_Community_College/MTH_220_Discrete_Math/4%3A_Sets/4.2%3A_Subsets_and_Power_Sets)</sup> The power set is one of the basic set-forming operations of mathematics, and [Cantor's theorem](https://www.edgepedia.org/cantors-theorem), which states that a set is always strictly smaller than its power set, is the standard route to the hierarchy of infinite sizes.<sup>[3](https://www.math.toronto.edu/~weiss/Set_Theory.pdf)</sup>

| Key fact | Detail |
|---|---|
| Definition | \( \mathcal{P}(A) \) is the set of all subsets of \( A \); it always contains \( \emptyset \) and \( A \).<sup>[1](https://math.libretexts.org/Bookshelves/Analysis/A_Primer_of_Real_Analysis_%28Sloughter%29/03%3A_Cardinality/3.03%3A_Power_Sets)</sup><sup> • </sup><sup>[2](https://math.libretexts.org/Courses/Monroe_Community_College/MTH_220_Discrete_Math/4%3A_Sets/4.2%3A_Subsets_and_Power_Sets)</sup> |
| Finite size | If \( A \) has \( n \) elements, then \( |\mathcal{P}(A)| = 2^n \).<sup>[4](https://mathstats-materials.uncg.edu/mat253/web/section-power-sets.html)</sup> |
| Cantor's theorem | For every set \( x \), \( |x| < |\mathcal{P}(x)| \); the proof resembles the argument behind Russell's paradox.<sup>[3](https://www.math.toronto.edu/~weiss/Set_Theory.pdf)</sup> |
| Origin | Cantor published the theorem in a short 1892 paper, formulating it with the set of functions \( f: S \to \{0, 1\} \), which is equivalent to the power set.<sup>[5](https://plato.stanford.edu/entries/settheory-early/)</sup> |
| Axiomatic status | In Zermelo's 1908 axiomatization, the Power Set Axiom asserts that the collection of all subsets of any set is itself a set; together with the Axiom of Infinity it yields uncountable sets.<sup>[6](https://plato.stanford.edu/archives/sum2023/entries/zermelo-set-theory/)</sup> |
| Continuum Hypothesis | The statement \( |\mathcal{P}(\omega)| = \omega_1 \) is independent of ZFC: it cannot be proved from the other axioms (Cohen, 1963) and cannot be refuted by them (Gödel, 1938).<sup>[3](https://www.math.toronto.edu/~weiss/Set_Theory.pdf)</sup> |
| Algebraic structure | \( \mathcal{P}(U) \) with union, intersection, and complementation is a Boolean algebra.<sup>[7](https://mathresearch.utsa.edu/wiki/index.php?title=Unions_and_Intersections_of_Sets)</sup> |

## Definition and basic properties

For a set \( A \), an element of \( \mathcal{P}(A) \) is a subset of \( A \), not an element of \( A \); the distinction between membership and inclusion matters here. A small example makes the construction concrete. For the three-element set \( \{0, 1, 2\} \), the power set is

\[ \mathcal{P}(\{0,1,2\}) = \{\emptyset, \{0\}, \{1\}, \{2\}, \{0,1\}, \{0,2\}, \{1,2\}, \{0,1,2\}\}, \]

eight subsets in all.<sup>[8](https://courses.grainger.illinois.edu/cs476/sp2020/readings/meseguer-set-theory-algebra-computer-science.pdf)</sup> Each element of \( A \) is either in or out of a given subset, so the subsets correspond to the \( 2^n \) binary choices over \( n \) elements, and \( |\mathcal{P}(A)| = 2^n \) for finite \( A \).<sup>[4](https://mathstats-materials.uncg.edu/mat253/web/section-power-sets.html)</sup><sup> • </sup><sup>[8](https://courses.grainger.illinois.edu/cs476/sp2020/readings/meseguer-set-theory-algebra-computer-science.pdf)</sup> The growth is fast: the power set of a ten-element set has more than a thousand elements.<sup>[9](https://theory.stanford.edu/~trevisan/cs103-14/keith.pdf)</sup>

The power set also behaves predictably under inclusion: if \( A \subseteq B \), then \( \mathcal{P}(A) \subseteq \mathcal{P}(B) \), and \( \mathcal{P}(A) \cap \mathcal{P}(B) = \mathcal{P}(A \cap B) \).<sup>[8](https://courses.grainger.illinois.edu/cs476/sp2020/readings/meseguer-set-theory-algebra-computer-science.pdf)</sup>

## Cantor's theorem

**Cantor's theorem** states that for every set \( x \), \( |x| < |\mathcal{P}(x)| \).<sup>[3](https://www.math.toronto.edu/~weiss/Set_Theory.pdf)</sup> There is always an injection from \( A \) into \( \mathcal{P}(A) \), sending each \( a \in A \) to the singleton \( \{a\} \), so the content of the theorem is that no surjection \( A \to \mathcal{P}(A) \) exists.<sup>[10](https://www.math.wustl.edu/~chi/310notesVI.pdf)</sup> The diagonal argument shows why: given any function \( g: x \to \mathcal{P}(x) \), the set \( \{a \in x : a \notin g(a)\} \) cannot be a value of \( g \), since if it equaled \( g(a) \) for some \( a \), then \( a \in g(a) \) exactly when \( a \notin g(a) \).<sup>[3](https://www.math.toronto.edu/~weiss/Set_Theory.pdf)</sup> The source notes the similarity of this argument to [Russell's paradox](https://www.edgepedia.org/russells-paradox), which was patterned after it.<sup>[3](https://www.math.toronto.edu/~weiss/Set_Theory.pdf)</sup>

Cantor published the theorem in a short paper in 1892. He did not use the power set notation; he worked with the set of all functions \( f: S \to \{0, 1\} \), which is equivalent, since each function of this kind picks out one subset of \( S \).<sup>[5](https://plato.stanford.edu/entries/settheory-early/)</sup> The same paper contained his diagonalisation proof that the real numbers \( \mathbb{R} \) are non-denumerable, a method he then extended to prove the theorem.<sup>[5](https://plato.stanford.edu/entries/settheory-early/)</sup> The theorem guarantees that for any cardinal \( \alpha \) there is a least cardinal greater than \( \alpha \), written \( \alpha^+ \), and it implies \( |\mathcal{P}(\omega)| \geq \omega_1 \), where \( \omega_1 \) is the first uncountable cardinal.<sup>[3](https://www.math.toronto.edu/~weiss/Set_Theory.pdf)</sup>

## The Power Set Axiom and the continuum problem

In axiomatic set theory the existence of power sets is not automatic; it is postulated. Zermelo's 1908 axiomatization includes the Power Set Axiom, which says that for any set, the collection of all subsets of that set is also a set.<sup>[6](https://plato.stanford.edu/archives/sum2023/entries/zermelo-set-theory/)</sup> In the modern ZF formulation the axiom reads \( \forall x \, \exists y \, \forall z \, (z \in y \leftrightarrow z \subseteq x) \), and since the resulting set is unique it is denoted \( \mathcal{P}(x) \).<sup>[11](https://plato.stanford.edu/archives/fall2015/entries/set-theory/ZF.html)</sup> The Stanford Encyclopedia of Philosophy's account of Zermelo's system identifies the Axioms of Infinity and Power Set as the two that together show the existence of uncountable sets.<sup>[6](https://plato.stanford.edu/archives/sum2023/entries/zermelo-set-theory/)</sup>

In the foundations of analysis, this axiom also matters: the 1872 Cantor and Dedekind constructions of the reals made implicit use of set theory, and hindsight reveals that they presupposed a Power Set principle.<sup>[5](https://plato.stanford.edu/entries/settheory-early/)</sup>

The size of \( \mathcal{P}(\omega) \), the power set of the natural numbers, is the subject of the Continuum Hypothesis (CH), proposed by Cantor in the nineteenth century: the claim that \( |\mathcal{P}(\omega)| = \omega_1 \).<sup>[3](https://www.math.toronto.edu/~weiss/Set_Theory.pdf)</sup> Its status is settled only in a negative sense. [Kurt Gödel](https://www.edgepedia.org/kurt-godel) showed in 1938 that adding CH to ZFC produces no new inconsistencies, and [Paul Cohen](https://www.edgepedia.org/paul-cohen) showed in 1963 that CH does not follow from the other ZFC axioms, so ZFC alone does not determine its truth.<sup>[3](https://www.math.toronto.edu/~weiss/Set_Theory.pdf)</sup> Hilbert had placed both the Continuum Hypothesis and the well-ordering problem first on his 1900 list of mathematical problems.<sup>[5](https://plato.stanford.edu/entries/settheory-early/)</sup>

## Algebraic structure

For a set \( U \), the power set \( \mathcal{P}(U) \) together with the operations of union, intersection, and complementation is a [Boolean algebra](https://www.edgepedia.org/boolean-algebra).<sup>[7](https://mathresearch.utsa.edu/wiki/index.php?title=Unions_and_Intersections_of_Sets)</sup> It is closed under all these operations, and the complement of \( U' \subseteq U \) is \( U \setminus U' \).<sup>[8](https://courses.grainger.illinois.edu/cs476/sp2020/readings/meseguer-set-theory-algebra-computer-science.pdf)</sup> The laws include the complement laws \( U' \cap U'^{c} = \emptyset \) and \( U' \cup U'^{c} = U \), and [De Morgan's laws](https://www.edgepedia.org/de-morgans-laws).<sup>[8](https://courses.grainger.illinois.edu/cs476/sp2020/readings/meseguer-set-theory-algebra-computer-science.pdf)</sup> The same structure can be presented as a [Boolean ring](https://www.edgepedia.org/boolean-ring), with symmetric difference as addition and intersection as multiplication.<sup>[8](https://courses.grainger.illinois.edu/cs476/sp2020/readings/meseguer-set-theory-algebra-computer-science.pdf)</sup>

Finite power-set Boolean algebras are rigidly determined by size: there is exactly one Boolean algebra of each finite power-of-2 cardinality, and it is isomorphic to the Boolean algebra of a power set \( 2^X \) of that cardinality under union, intersection, and complement relative to \( X \).<sup>[12](https://plato.stanford.edu/archives/sum2007/entries/algebra/)</sup>

## Uses in topology and computation

In topology, the power set supplies the largest possible topology on a set. The discrete topology on \( X \) is the topology equal to \( \mathcal{P}(X) \), and a space is discrete exactly when every subset is open.<sup>[13](https://www.math.ucla.edu/~sharifi/topology.pdf)</sup> At the other extreme, the trivial topology \( \{\emptyset, X\} \) is the smallest.<sup>[13](https://www.math.ucla.edu/~sharifi/topology.pdf)</sup>

In automata theory, the subset construction, also called the powerset construction, converts a nondeterministic finite automaton (NFA) into a deterministic finite automaton (DFA) recognizing the same language: each DFA state is a set of NFA states, namely the states the NFA could simultaneously occupy after reading some input prefix.<sup>[14](https://web.cs.ucdavis.edu/~doty/ecs120slides/04a_Equivalence-deck.html)</sup> The construction is the standard proof that NFAs and DFAs accept the same class of languages, but it can be exponentially costly: there exist \( k \)-state NFAs for which the smallest equivalent DFA has \( 2^k \) states.<sup>[14](https://web.cs.ucdavis.edu/~doty/ecs120slides/04a_Equivalence-deck.html)</sup>

The same exponential shows up whenever a power set is enumerated. Generating all subsets of an \( n \)-element set takes \( O(n \cdot 2^n) \) time, and the power-set tree, with exactly two children per internal node, is the simplest backtracking structure.<sup>[15](https://davidespataro.dev/chapters/power-set/)</sup> This exponential size is intrinsic, since the output itself has \( 2^n \) elements.<sup>[15](https://davidespataro.dev/chapters/power-set/)</sup>

## References

1. [Power Sets, Mathematics LibreTexts (Sloughter, A Primer of Real Analysis)](https://math.libretexts.org/Bookshelves/Analysis/A_Primer_of_Real_Analysis_%28Sloughter%29/03%3A_Cardinality/3.03%3A_Power_Sets)
2. [Subsets and Power Sets, Mathematics LibreTexts (Monroe Community College, MTH 220)](https://math.libretexts.org/Courses/Monroe_Community_College/MTH_220_Discrete_Math/4%3A_Sets/4.2%3A_Subsets_and_Power_Sets)
3. [An Introduction to Set Theory (W. Weiss, University of Toronto)](https://www.math.toronto.edu/~weiss/Set_Theory.pdf)
4. [Power sets, UNC Greensboro MAT 253 course materials](https://mathstats-materials.uncg.edu/mat253/web/section-power-sets.html)
5. [The Early Development of Set Theory, Stanford Encyclopedia of Philosophy](https://plato.stanford.edu/entries/settheory-early/)
6. [Zermelo's Axiomatization of Set Theory, Stanford Encyclopedia of Philosophy (Summer 2023 edition)](https://plato.stanford.edu/archives/sum2023/entries/zermelo-set-theory/)
7. [Unions and Intersections of Sets, UTSA Mathematics Research Wiki](https://mathresearch.utsa.edu/wiki/index.php?title=Unions_and_Intersections_of_Sets)
8. [Set Theory and Algebra in Computer Science (J. Meseguer, University of Illinois CS 476)](https://courses.grainger.illinois.edu/cs476/sp2020/readings/meseguer-set-theory-algebra-computer-science.pdf)
9. [Chapter 1: Sets and Cantor's Theorem (Stanford CS 103 course notes)](https://theory.stanford.edu/~trevisan/cs103-14/keith.pdf)
10. [310notesvi.dvi](https://www.math.wustl.edu/~chi/310notesVI.pdf)
11. [Zermelo-Fraenkel Set Theory, Stanford Encyclopedia of Philosophy (Fall 2015 edition)](https://plato.stanford.edu/archives/fall2015/entries/set-theory/ZF.html)
12. [algebra (stanford encyclopedia of philosophy/summer 2007 edition)](https://plato.stanford.edu/archives/sum2007/entries/algebra/)
13. [Point-Set Topology (A. Sharifi, UCLA)](https://www.math.ucla.edu/~sharifi/topology.pdf)
14. [ECS 120 Theory of Computation: Equivalence of Computational Models (UC Davis)](https://web.cs.ucdavis.edu/~doty/ecs120slides/04a_Equivalence-deck.html)
15. [Power Set (D. Spataro, algorithm notes)](https://davidespataro.dev/chapters/power-set/)

---
*Topic: Encyclopedia › Physical world and mathematics › Mathematics and statistics › Logic and discrete mathematics › Formal logic and foundations › Set theory › Elementary set theory*

*Initially written Sep 17, 2026 · Reviewed: Oct 15, 2026 · Edited: Oct 15, 2026 · Last review: Oct 15, 2026*

*Copyright 2026 EdgeChat AI, a subsidiary of Biostate AI.*

License: Edgepedia Community License 1.0, https://www.edgepedia.org/edgepedia/license