Given a set , the power set of is the set of all subsets of . Equivalently, it is the set of all functions from to the set of truth values. This is often written , since there are (at least in classical logic) exactly truth values.
One generally needs a specific axiom in the foundations of mathematics to ensure the existence of power sets. In predicative mathematics the existence of power sets (along with other “impredicative” axioms) is not accepted. One can use power sets to construct function sets; the converse also works using excluded middle (or anything else that will guarantee the existence of the set of truth values). In particular, power sets exist in any theory containing excluded middle and function sets; thus predicative theories which include function sets must also be constructive. Note that we can still speak of a power set as a proper class, sometimes called a power class.
The power set is in fact a poset ordered by containment: precedes means that is a subset of ().
Cantor's theorem states that there exists no surjection from to ; as there does exist such an injection, one concludes that
in the usual arithmetic of cardinal numbers.
Power sets live in the category Set. Given an object of any category, one can similarly form a poset of subobjects of ; the category is called well-powered when this poset is small. One also has an internal notion of power set (a power object) in a topos.