Editing Power set (section)

== 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]].