Power Set

While studying mathematical logic, grouping elements into sets and observing the patterns within those sets play an important role. You may have come across types of sets in its theory, such as empty set, universal set, finite and infinite set, equal set, etc. Power Set is one of the important topics in sets. In this article, we focus on some of the fundamental concepts such as Definition, formulas to find number of subsets with the help of an example, set notation, important properties, Algorithm to generate power set, and concepts like How Power-Set Related to Binomial Theorem.

Definition

In set theory, the power set (or powerset) of a Set A is defined as the set of all subsets of the Set A including the Set itself and the null or empty set. It is denoted by P(A). Basically, this set is the combination of all subsets including null set, of a given set.

How many Subsets does a Set Have?

If the given set has n elements, then its Power Set will contains 2ⁿ elements.

Example

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

Number of elements: 3

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(A) = { { } , { a }, { b }, { c }, { a, b }, { b, c }, { c, d }, { a, b, c } }

Now, the Power Set should have 2³ = 8 elements.

Notation

The number of elements of a set is written as |A|, If A has n elements then it can be written as

|P(A)| = 2ⁿ

Properties

• It is much larger than the original set.
• The powerset of a countable finite set is uncountable.
• For a set of natural numbers, we can do one-to-one mapping of the resulted set, P(S), with the real numbers.
• P(s) of set S, if operated with the union of sets, the intersection of sets and complement of sets, denotes the example of Boolean Algebra.

Power Set of a Empty Set

An empty set has zero element. Therefore, powerset of a empty set{ }, can be mentioned as;

• A set containing a null set.
• It contains zero or null elements.
• Empty set is the only subset.

Algorithm

A recursive algorithm is used to generate the powerset 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 powerset 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

It is closely related to the binomial theorem in 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.

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

Related Articles