0 added
0 removed
Original
2026-01-01
Modified
2026-02-28
1
<p>The cardinality of a power set represents all possible subsets, including the empty set and the set itself. Take, for example, the set C = x, y, z, w. This set contains 4 elements, so the cardinality of c is 4. The cardinality of its power set is 24 = 16. So the power set of C has 16 subsets.</p>
1
<p>The cardinality of a power set represents all possible subsets, including the empty set and the set itself. Take, for example, the set C = x, y, z, w. This set contains 4 elements, so the cardinality of c is 4. The cardinality of its power set is 24 = 16. So the power set of C has 16 subsets.</p>
2
<p><strong>Power Set Proof</strong></p>
2
<p><strong>Power Set Proof</strong></p>
3
<p>To show that if a set A contains n elements, then its power P(A) has 2n elements. In other words, the cardinality of a<a>finite set</a>A with ‘n’ elements is |P(A)| = 2n.We follow the pattern of<a>mathematical induction</a>for the proof of the power set.</p>
3
<p>To show that if a set A contains n elements, then its power P(A) has 2n elements. In other words, the cardinality of a<a>finite set</a>A with ‘n’ elements is |P(A)| = 2n.We follow the pattern of<a>mathematical induction</a>for the proof of the power set.</p>
4
<p>Let's consider the case of an empty set.</p>
4
<p>Let's consider the case of an empty set.</p>
5
<p><strong>Case 1:</strong>A set with no elements, n = 0 </p>
5
<p><strong>Case 1:</strong>A set with no elements, n = 0 </p>
6
<p>Let A = (empty set)</p>
6
<p>Let A = (empty set)</p>
7
<p>The only subset of the empty set is itself, so P() = .</p>
7
<p>The only subset of the empty set is itself, so P() = .</p>
8
<p>Since there is only 1 element in the set, the cardinality of the set will be 2n = 21 = 1.</p>
8
<p>Since there is only 1 element in the set, the cardinality of the set will be 2n = 21 = 1.</p>
9
<p><strong>Case 2:</strong>We now assume that the rule holds for a set with n elements such that a set 2n has subsets. Let's call this set X, now suppose</p>
9
<p><strong>Case 2:</strong>We now assume that the rule holds for a set with n elements such that a set 2n has subsets. Let's call this set X, now suppose</p>
10
<p>X = nP(X) = 2n</p>
10
<p>X = nP(X) = 2n</p>
11
<p>Now, let's create a new set Y by adding one new element, say an+1, to set X:</p>
11
<p>Now, let's create a new set Y by adding one new element, say an+1, to set X:</p>
12
<p>Y = X U an+1</p>
12
<p>Y = X U an+1</p>
13
<p>So the number of elements in Y is n + 1.</p>
13
<p>So the number of elements in Y is n + 1.</p>
14
<p>There are 2 kinds of subsets in Y: one having the new element an = 1 and the other without it.</p>
14
<p>There are 2 kinds of subsets in Y: one having the new element an = 1 and the other without it.</p>
15
<p>So in total: P(Y) = 2n(without an+1) + 2n(with an+1) =22n = 2n+1 </p>
15
<p>So in total: P(Y) = 2n(without an+1) + 2n(with an+1) =22n = 2n+1 </p>
16
<p>This proves that if the formula holds for n, it also holds for n + 1.</p>
16
<p>This proves that if the formula holds for n, it also holds for n + 1.</p>
17
<p>Let us apply this proof using an example,</p>
17
<p>Let us apply this proof using an example,</p>
18
<p>Let X=a, b, c </p>
18
<p>Let X=a, b, c </p>
19
<p>Let Y=a, b, c, d</p>
19
<p>Let Y=a, b, c, d</p>
20
<p>Here,</p>
20
<p>Here,</p>
21
<p>X = 3, so the number of subsets of X is 23 = 8</p>
21
<p>X = 3, so the number of subsets of X is 23 = 8</p>
22
<p>Y = 4, and we’ll prove that the number of subsets of Y is 24 = 16.</p>
22
<p>Y = 4, and we’ll prove that the number of subsets of Y is 24 = 16.</p>
23
<p>Subsets of X = {}, a,b,c,a,b,a,cb,ca,b,c</p>
23
<p>Subsets of X = {}, a,b,c,a,b,a,cb,ca,b,c</p>
24
<p>So, X has a total of 8 subsets.</p>
24
<p>So, X has a total of 8 subsets.</p>
25
<p>Subsets of Y = {},a,b,c,a,b,a,c,b,c,a,b,c</p>
25
<p>Subsets of Y = {},a,b,c,a,b,a,c,b,c,a,b,c</p>
26
<p>These are 8 subsets that do not include d.</p>
26
<p>These are 8 subsets that do not include d.</p>
27
<p>Now for subsets of Y with d = {d},a,d,b,d,c,d,a,b,d,a,c,d,b,c,d,a,b,c,d</p>
27
<p>Now for subsets of Y with d = {d},a,d,b,d,c,d,a,b,d,a,c,d,b,c,d,a,b,c,d</p>
28
<p>There are 8 more subsets of Y when d is added.</p>
28
<p>There are 8 more subsets of Y when d is added.</p>
29
<p>Total subsets of Y = 16.</p>
29
<p>Total subsets of Y = 16.</p>
30
<p>Here, 4 is the extra element in set Y.</p>
30
<p>Here, 4 is the extra element in set Y.</p>
31
<p>This example confirms that if a set with n elements has 2n subsets, then adding one more element doubles the number of subsets to 2n+1.</p>
31
<p>This example confirms that if a set with n elements has 2n subsets, then adding one more element doubles the number of subsets to 2n+1.</p>
32
32