Power set

From Wikipedia, the free encyclopedia
Jump to: navigation, search
For the search engine developer, see Powerset (company).

In mathematics, the power set (or powerset) of any set S, written \mathcal{P}(S), P(S), ℙ(S), (S) or 2S, is the set of all subsets of S, including the empty set and S itself. 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.[1]

Any subset of \mathcal{P}(S) is called a family of sets over S.



  • {} (also denoted \varnothing, the empty set)
  • {x}
  • {y}
  • {z}
  • {x, y}
  • {x, z}
  • {y, z}
  • {x, y, z}



If S is a finite set with |S| = n elements, then the number of subsets of S is |\mathcal{P}(S)| = 2^n. This fact, which is the motivation for the notation 2S, may be demonstrated simply as follows,

We write any subset of S in the format \{\omega_1, \omega_2, \ldots, \omega_n\} where \omega_i , 1 \le i \le n, can take the value of 0 or  1. If  \omega_i = 1, the  i -th element of S is in the subset; otherwise, the i-th element is not in the subset. Clearly the number of distinct subsets that can be constructed this way is 2^n.




Representing subsets as functions[edit]

In set theory, XY is the set of all functions from Y to X. As "2" can be defined as {0,1} (see natural number), 2S (i.e., {0,1}S) is the set of all functions from S to {0,1}. By identifying a function in 2S with the corresponding preimage of 1, we see that there is a bijection between 2S and \mathcal{P}(S), where each function is the characteristic function of the subset in \mathcal{P}(S) with which it is identified. Hence 2S and \mathcal{P}(S) could be considered identical set-theoretically. (Thus there are two distinct notational motivations for denoting the power set by 2S: the fact that this function-representation of subsets makes it a special case of the XY notation and the property, mentioned above, that |2S| = 2|S|.)

This notion can be applied to the example above in which S = \{x, y, z\} to see the isomorphism with the binary numbers from 0 to 2n−1 with n being the number of elements in the set. In S, a 1 in the position corresponding to the location in the set indicates the presence of the element. So {x, y} = 110.

For the whole power set of S we get:

  • {x} = 100 = 4
  • {y} = 010 = 2
  • {z} = 001 = 1
  • {x, y} = 110 = 6
  • {x, z} = 101 = 5
  • {y, z} = 011 = 3
  • {x, y, z} = 111 = 7

Relation to binomial theorem[edit]

The power set is closely related to the binomial theorem. The number of sets with k elements in the power set of a set with n elements will be a combination C(n,k), also called a binomial coefficient.


  • C(3, 0) = 1 set with 0 elements
  • C(3, 1) = 3 sets with 1 element
  • C(3, 2) = 3 sets with 2 elements
  • C(3, 3) = 1 set with 3 elements.


If S \! is a finite set, there is a recursive algorithm to calculate  \mathcal{P}(S) .


In English, return the set with the element e \! added to each set X \! in T \!.

  • If S = \{\} \!,then  \mathcal{P}(S) = \{ \{ \} \} is returned.
  • Otherwise:
  • Let e \! be any single element of S \!.
  • Let  T = S \setminus \{ e \} \!, where 'S \setminus \{ e \} \!' denotes the relative complement of \{ e \} \! in S \!.
  • And the result:  \mathcal{P}(S) = \mathcal{P}(T) \cup \mathcal{F}(e,\mathcal{P}(T)) is returned.



Subsets of limited cardinality[edit]

The set of subsets of S of cardinality less than κ is denoted by \mathcal{P}_{\kappa}(S) or \mathcal{P}_{<\kappa}(S) \,. Similarly, the set of non-empty subsets of S might be denoted by \mathcal{P}_{\geq 1}(S) \,.

Power object[edit]






Functors and quantifiers[edit]


See also[edit]


  1. ^ Devlin (1979) p.50
  2. ^ Puntambekar (2007), p. 1-2


External links[edit]