Editing Power set

{{Short description|Mathematical set of all subsets of a set}}
{{For|the search engine developer|Powerset (company)}}
{{Infobox mathematical statement
| name = Power set
| image = Hasse diagram of powerset of 3.svg
| caption = The elements of the power set of {''x'', ''y'', ''z''}  [[order theory|ordered]] with respect to [[Inclusion (set theory)|inclusion]].
| type = [[Set (mathematics)#Basic operations|Set operation]]
| field = [[Set (mathematics)|Set theory]]
| statement = The power set is the set that contains all subsets of a given set.
| symbolic statement = <math>x\in P(S) \iff x\subseteq S</math>
}}

In [[mathematics]], the '''power set''' (or '''powerset''') of a [[Set (mathematics)|set]] {{mvar|S}} is the set of all [[subset]]s of {{mvar|S}}, including the [[empty set]] and {{mvar|S}} itself.{{sfn|ps=|Weisstein}} In [[axiomatic set theory]] (as developed, for example, in the [[ZFC]] axioms), the existence of the power set of any set is [[postulated]] by the [[axiom of power set]].{{sfn|ps=|Devlin|1979|page=50}} 
The powerset of {{mvar|S}} is variously denoted as {{math|{{itco|{{mathcal|P}}}}(''S'')}}, {{math|{{itco|𝒫}}(''S'')}}, {{math|''P''(''S'')}}, <math>\mathbb{P}(S)</math>, or {{math|2<sup>''S''</sup>}}.{{efn|The notation {{math|2<sup>''S''</sup>}}, meaning the set of all functions from {{math|''S''}} to a given set of two elements (e.g., {{math|{{mset|0, 1}}}}), is used because the powerset of {{mvar|S}} can be identified with, is equivalent to, or bijective to the set of all the functions from {{mvar|S}} to the given two-element set.{{sfn|ps=|Weisstein}}}}
Any subset of {{math|{{itco|{{mathcal|P}}}}(''S'')}} is called a ''[[family of sets]]'' over {{mvar|S}}.

== Example ==
If {{mvar|S}} is the set {{math|{{mset|''x'', ''y'', ''z''}}}}, then all the subsets of {{mvar|S}} are

* {{math|{{mset}}}} (also denoted <math>\varnothing</math> or <math>\empty</math>, the [[empty set]] or the null set)
* {{math|{{mset|''x''}}}}
* {{math|{{mset|''y''}}}}
* {{math|{{mset|''z''}}}}
* {{math|{{mset|''x'', ''y''}}}}
* {{math|{{mset|''x'', ''z''}}}}
* {{math|{{mset|''y'', ''z''}}}}
* {{math|{{mset|''x'', ''y'', ''z''}}}}
and hence the power set of {{mvar|S}} is {{math|{{mset|{{mset}},
{{mset|''x''}},
{{mset|''y''}},
{{mset|''z''}},
{{mset|''x'', ''y''}},
{{mset|''x'', ''z''}},
{{mset|''y'', ''z''}},
{{mset|''x'', ''y'', ''z''}}}}}}.{{sfn|ps=|Puntambekar|2007|pages=1–2}}

== Properties ==
If {{math|''S''}} is a finite set with the [[cardinality]] {{math|1={{abs|''S''}} = ''n''}} (i.e., the number of all elements in the set {{math|1=''S''}} is {{math|1=''n''}}), then the number of all the subsets of {{math|''S''}} is {{math|1={{abs|{{itco|{{mathcal|P}}}}(''S'')}} = 2<sup>''n''</sup>}}. This fact as well as the reason of the notation {{math|2<sup>''S''</sup>}} denoting the power set {{math|{{itco|{{mathcal|P}}}}(''S'')}} are demonstrated in the below.
: An [[indicator function]] or a characteristic function of a subset {{math|''A''}} of a set {{math|''S''}} with the cardinality {{math|1={{abs|''S''}} = ''n''}} is a function from {{math|''S''}} to the two-element set {{math|{{mset|0, 1}}}}, denoted as {{math|''I''<sub>''A''</sub> : ''S'' → {{mset|0, 1}}}}, and it indicates whether an element of {{math|''S''}} belongs to {{math|''A''}} or not; If {{math|''x''}} in {{math|''S''}} belongs to {{math|''A''}}, then {{math|1=''I''<sub>''A''</sub>(''x'') = 1}}, and {{math|0}} otherwise. Each subset {{math|''A''}} of {{math|''S''}} is identified by or equivalent to the indicator function {{math|''I''<sub>''A''</sub>}}, and {{math|{{mset|0,1}}<sup>''S''</sup>}} as the set of all the functions from {{math|''S''}} to {{math|{{mset|0, 1}}}} consists of all the indicator functions of all the subsets of {{math|''S''}}. In other words, {{math|{{mset|0, 1}}<sup>''S''</sup>}} is equivalent or [[Bijection|bijective]] to the power set {{math|{{itco|{{mathcal|P}}}}(''S'')}}. Since each element in {{math|''S''}} corresponds to either {{math|0}} or {{math|1}} under any function in {{math|{{mset|0, 1}}<sup>''S''</sup>}}, the number of all the functions in {{math|{{mset|0, 1}}<sup>''S''</sup>}} is {{math|2<sup>''n''</sup>}}. Since the number {{math|2}} can be defined as {{math|{{mset|0, 1}}}} (see, for example, [[von Neumann ordinals]]), the {{math|{{itco|{{mathcal|P}}(''S'')}}}} is also denoted as {{math|2<sup>''S''</sup>}}. Obviously {{math|1={{abs|2<sup>''S''</sup>}} = 2<sup>{{abs|''S''}}</sup>}} holds. Generally speaking, {{math|''X''<sup>''Y''</sup>}} is the set of all functions from {{math|''Y''}} to {{math|''X''}} and {{math|1={{abs|''X''<sup>''Y''</sup>}} = {{abs|''X''}}<sup>{{abs|''Y''}}</sup>}}.
[[Cantor's diagonal argument#General sets|Cantor's diagonal argument]] shows that the power set of a set (whether infinite or not) always has strictly higher [[cardinality]] 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 a [[countable set|countably infinite]] set is [[uncountable|uncountably]] infinite. The power set of the set of [[natural number]]s can be put in a [[bijection|one-to-one correspondence]] with the set of [[real number]]s (see [[Cardinality of the continuum]]).

The power set of a set {{math|''S''}}, together with the operations of [[union (set theory)|union]], [[intersection (set theory)|intersection]] and [[complement (set theory)|complement]], is a [[Σ-algebra]] over {{math|''S''}} and can be viewed as the prototypical example of a [[Boolean algebra (structure)|Boolean algebra]]. In fact, one can show that any ''finite'' Boolean algebra is [[isomorphic]] to the Boolean algebra of the power set of a finite set. For ''infinite'' Boolean algebras, this is no longer true, but every infinite Boolean algebra can be represented as a [[subalgebra]] of a power set Boolean algebra (see [[Stone's representation theorem]]).

The power set of a set {{math|''S''}} forms an [[abelian group]] when it is considered with the operation of [[symmetric difference]] (with the empty set as the identity element and each set being its own inverse), and a [[commutative]] [[monoid]] when considered with the operation of intersection (with the entire set {{math|''S''}} as the identity element). It can hence be shown, by proving the [[Distributive property|distributive laws]], that the power set considered together with both of these operations forms a [[Boolean ring]].

== Representing subsets as functions ==
In [[set theory]], {{math|[[Function (mathematics)#Function space|''X''<sup>''Y''</sup>]]}} is the notation representing the set of all [[function (mathematics)|function]]s from {{mvar|Y}} to {{mvar|X}}.  As "{{math|2}}" can be defined as {{math|{{mset|0, 1}}}} (see, for example, [[von Neumann ordinals]]), {{math|2<sup>''S''</sup>}} (i.e., {{math|{{mset|0, 1}}<sup>''S''</sup>}}) is the set of all [[function (mathematics)|function]]s from {{math|''S''}} to {{math|{{mset|0, 1}}}}. As [[power set#Properties|shown above]], {{math|2<sup>''S''</sup>}} and the power set of {{math|''S''}}, {{math|{{itco|{{mathcal|P}}}}(''S'')}}, are considered identical set-theoretically.

This equivalence can be applied to the example [[Power set#Example|above]], in which {{math|1=''S'' = {{mset|''x'', ''y'', ''z''}}}}, to get the [[isomorphism]] with the binary representations of numbers from 0 to {{math|2<sup>''n''</sup> − 1}}, with {{mvar|n}} being the number of elements in the set {{math|''S''}} or {{math|1={{abs|''S''}} = ''n''}}. First, the enumerated set {{math|1={{mset| (''x'', 1), (''y'', 2), (''z'', 3) }}}} is defined in which the number in each ordered pair represents the position of the paired element of {{math|''S''}} in a sequence of binary digits such as {{math|1={{mset|''x'', ''y''}} = 011<sub>(2)</sub>}}; {{math|1=''x''}} of {{math|''S''}} is located at the first from the right of this sequence and {{math|''y''}} is at the second from the right, and 1 in the sequence means the element of {{math|''S''}} corresponding to the position of it in the sequence exists in the subset of {{math|''S''}} for the sequence while 0 means it does not.

For the whole power set of {{math|''S''}}, we get:
{|class="wikitable"
|-
!scope="col"| Subset
!scope="col"| Sequence<br /> of binary digits
!scope="col"| Binary<br /> interpretation
!scope="col"| Decimal<br /> equivalent
|-
| {{math|1={{mset|                     }} }} || {{math|0, 0, 0}} || {{math|000<sub>(2)</sub>}} || {{math|0<sub>(10)</sub>}}
|-
| {{math|1={{mset| ''x''               }} }} || {{math|0, 0, 1}} || {{math|001<sub>(2)</sub>}} || {{math|1<sub>(10)</sub>}}
|-
| {{math|1={{mset|        ''y''        }} }} || {{math|0, 1, 0}} || {{math|010<sub>(2)</sub>}} || {{math|2<sub>(10)</sub>}}
|-
| {{math|1={{mset| ''x'', ''y''        }} }} || {{math|0, 1, 1}} || {{math|011<sub>(2)</sub>}} || {{math|3<sub>(10)</sub>}}
|-
| {{math|1={{mset|               ''z'' }} }} || {{math|1, 0, 0}} || {{math|100<sub>(2)</sub>}} || {{math|4<sub>(10)</sub>}}
|-
| {{math|1={{mset| ''x'',        ''z'' }} }} || {{math|1, 0, 1}} || {{math|101<sub>(2)</sub>}} || {{math|5<sub>(10)</sub>}}
|-
| {{math|1={{mset|        ''y'', ''z'' }} }} || {{math|1, 1, 0}} || {{math|110<sub>(2)</sub>}} || {{math|6<sub>(10)</sub>}}
|-
| {{math|1={{mset| ''x'', ''y'', ''z'' }} }} || {{math|1, 1, 1}} || {{math|111<sub>(2)</sub>}} || {{math|7<sub>(10)</sub>}}
|}

Such an [[Injective function|injective mapping]] from {{math|{{itco|{{mathcal|P}}}}(''S'')}} to integers is arbitrary, so this representation of all the subsets of {{math|''S''}} is not unique, but the sort order of the enumerated set does not change its cardinality. (E.g., {{math|{{mset| (''y'', 1), (''z'', 2), (''x'', 3) }}}} can be used to construct another injective mapping from {{math|{{itco|{{mathcal|P}}}}(''S'')}} to the integers without changing the number of one-to-one correspondences.)

However, such finite binary representation is only possible if {{math|''S''}} can be enumerated. (In this example, {{math|1=''x''}}, {{math|1=''y''}}, and {{math|1=''z''}} are enumerated with {{math|1}}, {{math|2}}, and {{math|3}} respectively as the position of binary digit sequences.) The enumeration is possible even if {{math|''S''}} has an infinite cardinality (i.e., the number of elements in {{math|''S''}} is infinite), such as the set of integers or rationals, but not possible for example if {{math|''S''}} is the set of real numbers, in which case we cannot enumerate all irrational numbers.

== Relation to binomial theorem ==
The [[binomial theorem]] is closely related to the power set. A {{math|''k''}}–elements combination from some set is another name for a {{math|''k''}}–elements subset, so the number of [[combination]]s, denoted as {{math|C(''n'', ''k'')}} (also called [[binomial coefficient]]) is a number of subsets with {{mvar|k}} elements in a set with {{mvar|n}} elements; in other words it's the number of sets with {{math|k}} elements which are elements of the power set of a set with {{math|n}} elements.

For example, the power set of a set with three elements, has:
* {{math|1=C(3, 0) = 1}} subset with {{math|0}} elements (the empty subset),
* {{math|1=C(3, 1) = 3}} subsets with {{math|1}} element (the singleton subsets),
* {{math|1=C(3, 2) = 3}} subsets with {{math|2}} elements (the complements of the singleton subsets),
* {{math|1=C(3, 3) = 1}} subset with {{math|3}} elements (the original set itself).

Using this relationship, we can compute {{math|{{abs|2<sup>''S''</sup>}}}} using the formula:
<math display="block">\left|2^S \right | = \sum_{k=0}^{|S|} \binom{|S|}{k} </math>

Therefore, one can deduce the following identity, assuming {{math|1={{abs|''S''}} = ''n''}}:
<math display="block">\left |2^S \right| = 2^n = \sum_{k=0}^{n} \binom{n}{k} </math>

== Recursive definition ==
If {{math|''S''}} is a [[finite set]], then a [[recursive definition]] of {{math|{{itco|{{mathcal|P}}}}(''S'')}} proceeds as follows:
* If {{math|1=''S'' = {{mset}}}}, then {{math|1={{itco|{{mathcal|P}}}}(''S'') = {{mset| {{mset}} }}}}.
* Otherwise, let {{math|''e'' ∈ ''S''}} and {{math|1=''T'' = ''S'' &setminus; {{mset|''e''}}}}; then {{math|1={{itco|{{mathcal|P}}}}(''S'') = {{itco|{{mathcal|P}}}}(''T'') ∪ {{mset|''t'' ∪ {{mset|''e''}} : ''t'' ∈ {{itco|{{mathcal|P}}}}(''T'')}}}}.

In words: 
* The power set of the [[empty set]] is a [[singleton (mathematics)|singleton]] whose only element is the empty set.
* For a non-empty set {{math|''S''}}, let <math>e</math> be any element of the set and {{math|''T''}} its [[relative complement]]; then the power set of {{math|''S''}} is a [[union (set theory)|union]] of a power set of {{math|''T''}} and a power set of {{math|''T''}} whose each element is expanded with the {{math|''e''}} element.

== Subsets of limited cardinality ==
The set of subsets of {{math|''S''}} of [[cardinality]] less than or equal to {{math|''κ''}} is sometimes denoted by {{math|{{mathcal|P}}<sub>''κ''</sub>(''S'')}} or {{math|[''S'']<sup>''κ''</sup>}}, and the set of subsets with cardinality strictly less than {{math|''κ''}} is sometimes denoted {{math|{{mathcal|P}}<sub><''κ''</sub>(''S'')}} or {{math|[''S'']<sup><''κ''</sup>}}. Similarly, the set of non-empty subsets of {{math|''S''}} might be denoted by {{math|{{mathcal|P}}<sub>≥1</sub>(''S'')}} or {{math|{{itco|{{mathcal|P}}}}<sup>+</sup>(''S'')}}.

== Power object ==
{{unsourced|section|date=February 2025}}
A set can be regarded as an [[algebra (universal algebra)|algebra]] having no nontrivial operations or defining equations.  From this perspective, the concept of the power set of {{math|''X''}} as the set of all subsets of {{math|''X''}} generalizes naturally to the set to all subalgebras of an [[algebraic 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 the [[lattice (order)|lattice]] 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 an [[algebraic lattice]], and every algebraic lattice arises as the lattice of subalgebras of some algebra.<ref>{{cite journal
 | last1 = Birkhoff
 | first1 = Garrett
 | last2 = Frink
 | first2 = Orrin, Jr.
 | title = Representations of Lattices by Sets
 | journal = Transactions of the American Mathematical Society
 | volume = 64
 | issue = 2
 | pages = 299–316
 | year = 1948
 | doi = 10.1090/S0002-9947-1948-0027263-2
 | url = https://www.ams.org/journals/tran/1948-064-02/S0002-9947-1948-0027263-2/S0002-9947-1948-0027263-2.pdf
}}
</ref> 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 {{math|1={{mset|0, 1}} = 2}}, there is no guarantee that a class of algebras contains an algebra that can play the role of {{math|2}} 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 of [[multigraph]]s.  Given two multigraphs {{math|''G''}} and {{math|''H''}}, a [[homomorphism]] {{math|''h'' : ''G'' → ''H''}} consists of two functions, one mapping vertices to vertices and the other mapping edges to edges.  The set {{math|''H''<sup>''G''</sup>}} of homomorphisms from {{math|''G''}} to {{math|''H''}} 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 multigraph {{math|''G''}} are in bijection with the graph homomorphisms from {{math|''G''}} to the multigraph {{math|Ω}} definable as the [[complete graph|complete 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 of {{math|''G''}} as the multigraph {{math|Ω<sup>''G''</sup>}}, called the '''power object''' of {{math|''G''}}.

What is special about a multigraph as an algebra is that its operations are unary.  A multigraph has two sorts of elements forming a set {{math|''V''}} of vertices and {{math|''E''}} of edges, and has two unary operations {{math|''s'', ''t'' : ''E'' → ''V''}} giving the source (start) and target (end) vertices of each edge.  An algebra all of whose operations are unary is called a [[presheaf]].  Every class of presheaves contains a presheaf {{math|Ω}} that plays the role for subalgebras that {{math|2}} plays for subsets.  Such a class is a special case of the more general notion of elementary [[topos]] as a [[category (mathematics)|category]] that is [[closed category|closed]] (and moreover [[cartesian closed category|cartesian closed]]) and has an object {{math|Ω}}, called a [[subobject classifier]].  Although the term "power object" is sometimes used synonymously with [[exponential object]] {{math|{{itco|''Y''}}<sup>''X''</sup>}}, in topos theory {{math|''Y''}} is required to be {{math|Ω}}.

== Functors and quantifiers ==
There is both a covariant and contravariant power set [[functor]], {{math|{{itco|{{mathcal|P}}}}: Set → Set}} and {{math|{{overbar|{{itco|{{mathcal|P}}}}}}: Set {{sup|op}} → Set}}. The covariant functor is defined more simply as the functor which sends a set {{math|''S''}} to {{math|{{mathcal|P}}(''S'')}} and a morphism {{math|''f'': ''S'' → ''T''}} (here, a function between sets) to the image morphism. That is, for <math>A = \{x_1, x_2, ...\} \in \mathsf{P}(S), \mathsf{P}f(A) = \{f(x_1), f(x_2), ...\} \in \mathsf{P}(T)</math>. Elsewhere in this article, the power set was defined as the set of functions of {{Math|''S''}} into the set with 2 elements. Formally, this defines a natural isomorphism <math>\overline{\mathsf{P}} \cong \text{Set}(-,2)</math>. The contravariant power set functor is different from the covariant version in that it sends {{math|''f''}} to the ''pre''image morphism, so that if <math>f(A) = B \subseteq T, \overline\mathsf{P}f(B) = A</math>. This is because a general functor <math>\text{C}(-,c)</math> takes a morphism <math>h:a \rightarrow b</math> to precomposition by ''h'', so a function <math>h^*: C(b,c) \rightarrow C(a,c)</math>, which takes morphisms from ''b'' to ''c'' and takes them to morphisms from ''a'' to ''c'', through ''b'' via ''h''. <ref>{{Cite book |last=Riehl |first=Emily |title=Category Theory in Context |date=16 November 2016 |publisher=Courier Dover Publications |isbn=978-0486809038}}</ref>

In [[category theory]] and the theory of [[elementary topos|elementary topoi]], the [[universal quantifier]] can be understood as the [[right adjoint]] of a [[functor]] between power sets, the [[inverse image]] functor of a function between sets; likewise, the [[existential quantifier]] is the [[left adjoint]].{{sfn|ps=|Mac Lane|Moerdijk|1992|p=58}}

== See also ==
* [[Cantor's theorem]]
* [[Family of sets]]
* [[Field of sets]]
* [[Combination#Number of k-combinations for all k|Combination]]

== Notes ==
{{notelist}}

== References ==
{{reflist}}

== Bibliography ==
* {{cite book | last=Devlin | first=Keith J. | author-link=Keith Devlin | title=Fundamentals of contemporary set theory | series=Universitext | publisher=[[Springer-Verlag]] | year=1979 | isbn=0-387-90441-7 | zbl=0407.04003 }}
* {{cite book | last=Halmos | first=Paul R. | author-link=Paul Halmos | title=Naive set theory | url=https://archive.org/details/naivesettheory00halm | url-access=registration | series=The University Series in Undergraduate Mathematics | publisher=van Nostrand Company | year=1960 | zbl=0087.04403 }}
* {{citation | last1=Mac Lane | first1=Saunders | author-link1=Saunders Mac Lane | last2=Moerdijk | first2=Ieke | author-link2=Ieke Moerdijk | year=1992 | title=Sheaves in Geometry and Logic |publisher=Springer-Verlag | isbn=0-387-97710-4 }}
* {{cite book | last=Puntambekar | first=A. A. | title=Theory Of Automata And Formal Languages | year=2007 | publisher=Technical Publications | isbn=978-81-8431-193-8 }}
* {{Cite web |last=Weisstein |first=Eric W. |title=Power Set |url=https://mathworld.wolfram.com/PowerSet.html |url-status=dead |archive-url=https://web.archive.org/web/20230406123410/https://mathworld.wolfram.com/PowerSet.html |archive-date=2023-04-06 |access-date=2020-09-05 |website=mathworld.wolfram.com |language=en}}

== External links ==
{{Wiktionary|power set}}
* {{PlanetMath |urlname=powerset |title=Power set}}
* {{nlab|id=power+set|title=Power set}}
* {{nlab|id=power+object|title=Power object}}
* [http://www.programminglogic.com/powerset-algorithm-in-c/ Power set Algorithm] in [[C++]]

{{Mathematical logic}}
{{Set theory}}

[[Category:Operations on sets]]