Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of GraphSearch.
Concept
Power set
Summary
In mathematics, the power set (or powerset) of a set S 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.
The powerset of S is variously denoted as P(S), P(S), P(S), , , or 2S. The notation 2S, meaning the set of all functions from S to a given set of two elements (e.g., {0, 1}), is used because the powerset of S can be identified with, equivalent to, or bijective to the set of all the functions from S to the given two elements set.
Any subset of P(S) is called a family of sets over S.
If S is the set , then all the subsets of S are
(also denoted or , the empty set or the null set)
and hence the power set of S is .
If S is a finite set with the cardinality S = n (i.e., the number of all elements in the set S is n), then the number of all the subsets of S is P(S) = 2n. This fact as well as the reason of the notation 2S denoting the power set P(S) are demonstrated in the below.
An indicator function or a characteristic function of a subset A of a set S with the cardinality |S| = n is a function from S to the two elements set {0, 1}, denoted as IA: S → {0, 1}, and it indicates whether an element of S belongs to A or not; If x in S belongs to A, then IA(x) = 1, and 0 otherwise. Each subset A of S is identified by or equivalent to the indicator function IA, and S as the set of all the functions from S to consists of all the indicator functions of all the subsets of S. In other words, S is equivalent or bijective to the power set P(S). Since each element in S corresponds to either 0 or 1 under any function in S, the number of all the functions in S is 2n. Since the number 2 can be defined as (see, for example, von Neumann ordinals), the P(S) is also denoted as 2S. Obviously = 2 holds. Generally speaking, XY is the set of all functions from Y to X and XY = XY.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.