Power set

Power set . In Mathematics , Logic and Discrete Mathematics , it is said of the conjunctual operation that obtains, from a given set as a parameter, another set made up of exactly all the subsets of that one.

In any case its representation may be P (A) , , P ^A , , they are used the first two.

The power set, especially finite sets, has great use in the modeling of phenomena and in the definition of concepts and properties of mathematical figures or other branches of science.

Summary

[ hide ]

• 1 Definition
• 2 Properties
• 3 Subset Construction Algorithm
• 4 Examples
• 5 Importance
• 6 Sources

Definition

Be a set A , is called power set of A and is denoted P (A) , , P ^A , (more extended use of the first two notations) to the set of exactly all subsets of A .

Properties

Let A be a set and P (A) its corresponding power set then it is fulfilled:

• If Ais a finite set such that | A | = n then | P (A) | = 2 ⁿ .
• Yes then
• If and then P (A)is the power set of A .
• All the elements of P (A)are sets.
• If A = {}then P (A) = {{}} .

Subset Construction Algorithm

Let be a finite set A of size n all its subsets can be obtained by the combinatorial method:

1. P = {{}}(the empty set is always a subset of any set).
2. The elements of A = {a ₁, a ₂ , …, a _n } are listed.
3. For each iin the natural range [1,2 ⁿ ] :
   1. S = {}
   2. For each jin the range [1, n] :
      1. If i & 2 ^j== 2 ^j(bitwise AND ) (If the jth position is marked in i ):
      2. , The item is added to the subset i-thof the power set P.

In the conclusion P contains the power set of A .

Examples

• A = {}, P (A) = {{}} .
• A = {a}, P (A) = {{}, {a}}
• A = {a, b}, P (A) = {{}, {a}, {b}, {a, b}}
• C = {v, w, x, y, z}, | P ^C | = 32
• Let P bethe set of natural pairs,

Importance

The power set, especially finite sets, has great use in the modeling of phenomena and in the definition of concepts and properties of mathematical figures or other branches of science.

Just to mention a case, the transformation of nondeterministic finite automaton in deterministic finite automaton is performed by the method of construction of subassemblies (except the null set), with the subsequent removal of inaccessible elements from the initial state according to the closing from Kleene , resulting in an AFD .