Power Set

While studying mathematical logic, grouping elements into sets and observing the patterns within those sets play an important role. Power sets form an important topic in sets. In this article, we focus on some of the fundamental concepts such as definition, example, and power set algorithm. It also examines how a power set is related to binomial theorem.

Power Set Definition

In set theory, the power set of a Set S is defined as the set of all subsets of the Set S including the Set S itself and the null or empty set.

Axiomatic set theory postulates the existence of power set through the axiom of the power set.

Power set of a set S is denoted by P(S). And the family of sets over set S is any subset of the power set.

Power Set Example

Let us say Set S = { a, b, c }

Therefore, the subsets of the set are:

{ } which is the null or the empty set

{ a }

{ b }

{ c }

{ a, b }

{ b, c }

{ c, d }

{ a, b, c }

The power set P(S) = { { } , { a }, { b }, { c }, { a, b }, { b, c }, { c, d }, { a, b, c } }

Power Set Algorithm

A recursive algorithm is used to generate the power set P(S) of any finite set S.

The operation F (e, T) is defined as

F (e, T) = { X ∪ {e} | X ∈ T }

This returns each of the set X in T that has the element x.

If Set S = { }, then P(S) = { { } } is returned.

If not, the following algorithm is followed.

If e is an element in Set S, T = S\ {e} such that S\ { e } forms the relative complement of the element e in Set S, the power set is generated by the following algorithm:

P(S) = P(T) ∪ F ( e, P(T))

To conclude, if the set S is empty then the only element in the power set will be the null set. If not, the power set will the union of all the subsets containing the particular element and the subsets not containing the particular element.

How is Power Set Related to Binomial Theorem

A Power set is closely related to binomial theorem is terms of the notation.

Let us consider a set of three elements S = { a, b, c }

Number of subsets with zero elements (the null or the empty set) = 1

Number of subsets with one element (the singleton subsets) = 3

Number of subsets with two elements (the complements of singleton subsets) = 3

Number of subsets with three elements (the actual set) = 1

From the above relationship we can calculate |2^s| as follows:

|2^s| = \(\sum_{k=0}^{|s|}(^{|s|}_{k})\)

If |S| = n then,

|2^s| = 2ⁿ = \(\sum_{k=0}^{n}(^{n}_{k})\)

This is the relationship between a power set and the binomial theorem.

Related Articles

Learning about set theory and related topics can be so much fun. Download BYJU’S – The Learning App and discover innovative ways to learn science and math.