Day 47 – Powerset of a Set

Notations

Subset(recap)

A set can have another set as its element.

\{1,2,3,4\}\,\subseteq\,A\,but\,\{1,2,3,4\}\,\in\,B

\{5,6\}\,\subseteq\,A\,but\,\{5,6\}\,\in\,B

\{7,8,9\}\,\subseteq\,A\,but\,\{7,8,9\}\,\in\,B

Quick Review:

• Any set is considered to be a subset of itself.
• No set is a proper subset of itself.
• The empty set is a subset of every set.
• The empty set is a proper subset of every set except for the empty set.

Difference between subset and proper subset:

subset\,\subseteq\\proper\,subset\,\subset

Subset: If every element of 1st set is contained in the 2nd set, then the 1st set is called the subset of the 2nd set.

For example: If A={2,3,5,6} and B={2,3,5,6} then A is the subset of B.

Proper Subset: If every element of 1st set is contained in the 2nd set and there is atleast one element in the 2nd set that is not there in the 1st set, then the 1st set is called the proper subset of the 2nd set.

For example: If A={2,3,5,6} and B={2,3,5,6,7} then A is the proper subset of B, since all the elements of A are contained in B and B has one more element that is not there in A.

Powerset of a set

• given a set S, the powerset of S, P(S), is the set containing all the subsets of S.
• n set theory, the power set (or power set) 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.
• A power set is defined as the set or group of all subsets for any given set, including the empty set

For the set {a,b,c}:

• The empty set {} is a subset of {a,b,c}
• And these are subsets: {a}, {b} and {c}
• And these are also subsets: {a,b}, {a,c} and {b,c}
• And {a,b,c} is a subset of {a,b,c}
• And altogether we get the Power Set of {a,b,c}:

P(S) = { {}, {a}, {b}, {c}, {a, b}, {a, c}, {b, c}, {a, b, c} }

Think of it as all the different ways we can select the items (the order of the items doesn’t matter), including selecting none, or all.

Example:

Given a set S = {1,2,3}

The subsets of S are:

\emptyset,\{1\},\{2\},\{3\},\\\{1,2\},\{1,3\},\{2,3\},\\\{1,2,3\}\\P(S)\,=\,\{\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}

Exercise 1:

Given a set S = {a,b}

Write down the P(S).

P(S)\,=\,\{\emptyset,\{a\},\{b\},\{a,b\}\}

Is {a} a subset or an element of P(S)?

\{a\}\,\in\,P(S)\\element

Is the empty set an element or a subset of P(S)?

\emptyset\,\subseteq\,P(S)\\subset\\also\,an\,element\\\emptyset\,\in\,P(S)

Empty Set

P(\emptyset)\,=\\\emptyset\subseteq\emptyset\\P(\emptyset)\,=\,\{\emptyset\}\\\emptyset\subseteq\,P(\emptyset)\\\{\emptyset\}\subseteq\,P(\emptyset)\\P(P(\emptyset))\,=\,\{\emptyset,\{\emptyset\}\}

Empty set is a subset of any set

1. The empty set, is the only subset of the empty set.
2. The power set of the empty set is the set containing the empty set.
3. The empty set, is a subset, of a power set, of the empty set.
4. The set, containing the empty set, is a subset of the power set of the empty set.
5. The power set, of the power set, of the empty set contains the empty set, its first element, and the set containing the empty set as its second element.

Cardinality of a Powerset

Cardinality denotes the total number of elements in the power set. It is denoted by |P(X)|. The cardinality of a power set for a set of ‘n’ elements is given by ‘2n‘. For example, if set X = {a,b,c}, then the cardinality of the power set is |P(X)| = 23 or 8. This means there will be 8 subsets present in the power set: { {}, {a}, {b}, {c}, {a,b}, {a, c}, {b, c}, {a, b, c} }.

Example:

S\,=\,\{1,2,3\}\\|S|\,=\,3\\P(S)\,=\,\{\emptyset,\{1\},\{2\},\{3\},\{1,2\},\{1,3\},\{2,3\},\{1,2,3\}\}\\|P(S)|\,=\,8\,=\,2^3\,=\,2^{|S|}

Given a set A, if |A| = n, find |P(P(P(A)))|

|P(A)|\,=\,2^{|A|}\,=\,2^n\\|P(P(A))|\,=\,2^{|P(A)|}\,=\,2^{2^n}\\|P(P(P(A)))|\,=\,2^{|P(P(A))|}\,=\,2^{2^{2^n}}