 | |
| Type | Set operation |
|---|---|
| Field | Set theory |
| Statement | The power set is the set that contains all subsets of a given set. |
| Symbolic statement | |
Inmathematics, thepower set (orpowerset) of asetS is the set of allsubsets ofS, including theempty set andS itself.[1] Inaxiomatic set theory (as developed, for example, in theZFC axioms), the existence of the power set of any set ispostulated by theaxiom of power set.[2] The powerset ofS is variously denoted asP(S),𝒫(S),P(S),, or2S.[a]Any subset ofP(S) is called afamily of sets overS.
IfS is the set{x,y,z}, then all the subsets ofS are
and hence the power set ofS is{{},{x},{y},{z},{x,y},{x,z},{y,z},{x,y,z}}.[3]
IfS is a finite set with thecardinality|S| =n (i.e., the number of all elements in the setS isn), then the number of all the subsets ofS is|P(S)| = 2n. This fact as well as the reason of the notation2S denoting the power setP(S) are demonstrated in the below.
Cantor's diagonal argument shows that the power set of a set (whether infinite or not) always has strictly highercardinality than the set itself (or informally, the power set must be larger than the original set). In particular,Cantor's theorem shows that the power set of acountably infinite set isuncountably infinite. The power set of the set ofnatural numbers can be put in aone-to-one correspondence with the set ofreal numbers (seeCardinality of the continuum).
The power set of a setS, together with the operations ofunion,intersection andcomplement, is aσ-algebra overS and can be viewed as the prototypical example of aBoolean algebra. In fact, one can show that anyfinite Boolean algebra isisomorphic to the Boolean algebra of the power set of a finite set. Forinfinite Boolean algebras, this is no longer true, but every infinite Boolean algebra can be represented as asubalgebra of a power set Boolean algebra (seeStone's representation theorem).
The power set of a setS forms anabelian group when it is considered with the operation ofsymmetric difference (with the empty set as the identity element and each set being its own inverse), and acommutativemonoid when considered with the operation of intersection (with the entire setS as the identity element). It can hence be shown, by proving thedistributive laws, that the power set considered together with both of these operations forms aBoolean ring.
Inset theory,XY is the notation representing the set of allfunctions fromY toX. As "2" can be defined as{0, 1} (see, for example,von Neumann ordinals),2S (i.e.,{0, 1}S) is the set of allfunctions fromS to{0, 1}. Asshown above,2S and the power set ofS,P(S), are considered identical set-theoretically.
This equivalence can be applied to the exampleabove, in whichS = {x,y,z}, to get theisomorphism with the binary representations of numbers from 0 to2n − 1, withn being the number of elements in the setS or|S| =n. First, the enumerated set{ (x, 1), (y, 2), (z, 3) } is defined in which the number in each ordered pair represents the position of the paired element ofS in a sequence of binary digits such as{x,y} = 011(2);x ofS is located at the first from the right of this sequence andy is at the second from the right, and 1 in the sequence means the element ofS corresponding to the position of it in the sequence exists in the subset ofS for the sequence while 0 means it does not.
For the whole power set ofS, we get:
| Subset | Sequence of binary digits | Binary interpretation | Decimal equivalent |
|---|---|---|---|
| { } | 0, 0, 0 | 000(2) | 0(10) |
| {x } | 0, 0, 1 | 001(2) | 1(10) |
| {y } | 0, 1, 0 | 010(2) | 2(10) |
| {x,y } | 0, 1, 1 | 011(2) | 3(10) |
| {z } | 1, 0, 0 | 100(2) | 4(10) |
| {x,z } | 1, 0, 1 | 101(2) | 5(10) |
| {y,z } | 1, 1, 0 | 110(2) | 6(10) |
| {x,y,z } | 1, 1, 1 | 111(2) | 7(10) |
Such aninjective mapping fromP(S) to integers is arbitrary, so this representation of all the subsets ofS is not unique, but the sort order of the enumerated set does not change its cardinality. (E.g.,{ (y, 1), (z, 2), (x, 3) } can be used to construct another injective mapping fromP(S) to the integers without changing the number of one-to-one correspondences.)
However, such finite binary representation is only possible ifS can be enumerated. (In this example,x,y, andz are enumerated with1,2, and3 respectively as the position of binary digit sequences.) The enumeration is possible even ifS has an infinite cardinality (i.e., the number of elements inS is infinite), such as the set of integers or rationals, but not possible for example ifS is the set of real numbers, in which case we cannot enumerate all irrational numbers.
Thebinomial theorem is closely related to the power set. Ak–elements combination from some set is another name for ak–elements subset, so the number ofcombinations, denoted asC(n,k) (also calledbinomial coefficient) is a number of subsets withk elements in a set withn elements; in other words it's the number of sets withk elements which are elements of the power set of a set withn elements.
For example, the power set of a set with three elements, has:
Using this relationship, we can compute|2S| using the formula:
Therefore, one can deduce the following identity, assuming|S| =n:
IfS is afinite set, then arecursive definition ofP(S) proceeds as follows:
In words:
The set of subsets ofS ofcardinality less than or equal toκ is sometimes denoted byPκ(S) or[S]κ, and the set of subsets with cardinality strictly less thanκ is sometimes denotedP<κ(S) or[S]<κ. Similarly, the set of non-empty subsets ofS might be denoted byP≥1(S) orP+(S).
 | This sectiondoes notcite anysources. Please helpimprove this section byadding citations to reliable sources. Unsourced material may be challenged andremoved. Find sources: "Power set" – news ·newspapers ·books ·scholar ·JSTOR(February 2025) (Learn how and when to remove this message) |
A set can be regarded as analgebra having no nontrivial operations or defining equations. From this perspective, the concept of the power set ofX as the set of all subsets ofX generalizes naturally to the set to all subalgebras of analgebraic structure or algebra.
The power set of a set, when ordered by inclusion, is always a complete atomic Boolean algebra, and every complete atomic Boolean algebra arises as thelattice of all subsets of some set. The generalization to arbitrary algebras is that the set of subalgebras of an algebra, again ordered by inclusion, is always analgebraic lattice, and every algebraic lattice arises as the lattice of subalgebras of some algebra.[4] So in that regard, subalgebras behave analogously to subsets.
However, there are two important properties of subsets that do not carry over to subalgebras in general. First, although the subsets of a set form a set (as well as a lattice), in some classes it may not be possible to organize the subalgebras of an algebra as itself an algebra in that class, although they can always be organized as a lattice. Secondly, whereas the subsets of a set are in bijection with the functions from that set to the set{0, 1} = 2, there is no guarantee that a class of algebras contains an algebra that can play the role of2 in this way.
Certain classes of algebras enjoy both of these properties. The first property is more common; the case of having both is relatively rare. One class that does have both is that ofmultigraphs. Given two multigraphsG andH, ahomomorphismh :G →H consists of two functions, one mapping vertices to vertices and the other mapping edges to edges. The setHG of homomorphisms fromG toH can then be organized as the graph whose vertices and edges are respectively the vertex and edge functions appearing in that set. Furthermore, the subgraphs of a multigraphG are in bijection with the graph homomorphisms fromG to the multigraphΩ definable as thecomplete directed graph on two vertices (hence four edges, namely two self-loops and two more edges forming a cycle) augmented with a fifth edge, namely a second self-loop at one of the vertices. We can therefore organize the subgraphs ofG as the multigraphΩG, called thepower object ofG.
What is special about a multigraph as an algebra is that its operations are unary. A multigraph has two sorts of elements forming a setV of vertices andE of edges, and has two unary operationss,t :E →V giving the source (start) and target (end) vertices of each edge. An algebra all of whose operations are unary is called apresheaf. Every class of presheaves contains a presheafΩ that plays the role for subalgebras that2 plays for subsets. Such a class is a special case of the more general notion of elementarytopos as acategory that isclosed (and moreovercartesian closed) and has an objectΩ, called asubobject classifier. Although the term "power object" is sometimes used synonymously withexponential objectYX, in topos theoryY is required to beΩ.
There is both a covariant and contravariant power setfunctor,P: Set → Set andP: Setop → Set. The covariant functor is defined more simply as the functor which sends a setS toP(S) and a morphismf:S →T (here, a function between sets) to the image morphism. That is, for. Elsewhere in this article, the power set was defined as the set of functions ofS into the set with 2 elements. Formally, this defines a natural isomorphism. The contravariant power set functor is different from the covariant version in that it sendsf to thepreimage morphism, so that if. This is because a general functor takes a morphism to precomposition byh, so a function, which takes morphisms fromb toc and takes them to morphisms froma toc, throughb viah.[5]
Incategory theory and the theory ofelementary topoi, theuniversal quantifier can be understood as theright adjoint of afunctor between power sets, theinverse image functor of a function between sets; likewise, theexistential quantifier is theleft adjoint.[6]
{{cite journal}}: CS1 maint: multiple names: authors list (link)
| General | |||||||||
|---|---|---|---|---|---|---|---|---|---|
| Theorems (list) and paradoxes | |||||||||
| Logics |
| ||||||||
| Set theory |
| ||||||||
| Formal systems (list), language and syntax |
| ||||||||
| Proof theory | |||||||||
| Model theory | |||||||||
| Computability theory | |||||||||
| Related | |||||||||
| Overview |  | |
|---|---|---|
| Axioms | ||
| Operations | ||
| ||
| Set types | ||
| Theories | ||
| ||
| Set theorists | ||
