From a Foundations of Mathematics course Determine the cardi

From a Foundations of Mathematics course:


Determine the cardinality of each set and its power set.

Hint: Consider the thereom \" The union of a countable sequence of countable sets is countable\"

Solution

The Cardinality of Finite Power Sets

We might see a pattern with a few power sets. Let’s set up a set of pairs of numbers, the cardinalities of sets and their power sets. Let’s call this set C = { ( |A|, |P (A)| ) } for some small sets. |Ø| = zero, but P (Ø) = { {} }, so |P (Ø)| = 1. The first pair is (0, 1).

If A = {a}, then |A| = 1; P (A) = { {}, {a} }; so |P (A)| = 2. For B = {a, b}, |B| = 2; P (B) = { {}, {a}, {b}, {a, b} }; so |P (B)| = 4. We had already determined that when |A| = 3, then |P (A)| = 8.

So the set C = { (0, 1), (1, 2), (2, 4), (3, 8)… }. This looks like the formula p = 2^m for m = {0, 1, 2…}.

We can prove this by mathematical induction. We already have demonstrated this is true for a starting point, from |A| = m = 0, 1, 2 or 3.

Next we assume it is true for an arbitrary m = |A| for a set A with a larger number of elements. Then we see whether it would still be true for “m + 1, the next larger set.

We are using ‘p’ as the cardinality of the power set of A. We assume that, when |A[m]| = m, p[m] = |P (A[m])| = 2^m. Now we test whether, if |A[m+1]| = m + 1, then |P (A[m+1])| = p[m+1] = 2^(m+1).

When we add the new member to A[m] to form set A[m+1], what happens to the power set? P (A[m+1]) has all the members found in P (A[m]), plus other new sets. In fact, for each member of P (A[m]), we create one new member that includes the new member of A[m+1], effectively doubling the size of the set. Therefore p[m+1] = |P (A[m+1])| = |P (A[m])| * 2 = p[m] * 2.

However, p[m+1] = p[m] * 2 by the above counting argument, and p[m] = 2^m according to the induction assumption. So p[m+1] = 2^m * 2 = 2^(m+1) by the rules governing exponentiation and multiplication. This confirms that |P (A[m+1])| = 2^(m+1). By induction, the general case is proven.

The Cardinality of Power Sets of Countably-Infinite Power Sets

Georg Cantor proved Cantor’s Theorem, stating that the cardinality of any power set is greater than its starting set: |P (A)| > |A|.

Let’s examine the special case for Natural numbers, N = {0, 1, 2…}. Then P (N) = { {}, {0}, {1}, {2}… {0, 1}, {0, 2}… {1, 1}, {1, 2}… {0, 1, 2}… {0, 1, 2, 3}…}. P (N) also contains infinite sets: all even numbers; odd numbers; multiples of three; powers of two; and so on.

Intuitively, we could place N in a one-to-one correspondence with the single-element members of its power set. That leaves all the pairs, triples and so on with no corresponding Natural numbers. But this instinctive approach is insufficient as proof.

Cantor’s approach was to define “selfish” and “non-selfish” correspondences. Assume that we could construct a one-to-one correspondence between N and P (N). Then let’s examine the ith pair. Either ‘i’ is a member of the ith subset, or it is not. (For example, the 5th member of P (N) might be {1, 3, 5, 7…}). If ‘i’ is indeed in the ith subset, then ‘i’ is a “selfish” number. All other numbers are “non-selfish”.

Then Cantor defined U = the set of “non-selfish” numbers under these assumptions, to consist of all the numbers ‘u’ that correspond to P (N) members that do not contain ‘u’.

Clearly the set U is itself a member of P (N). By the opening assumption, there must be a Natural number in correspondence to set U; let’s call it ‘j’.

Is ‘j’ in the set U? If it is, then ‘j’ is a “selfish” number because it is found in its corresponding member in P (N). But we constructed U to consist only of “non-selfish” numbers, so ‘j’ must not be in U. This is a contradiction.

If we assume there are no elements in U, there still is a problem. That would mean that U = Ø = {}, so there is of course some ‘j’ corresponding to it. But if U is empty, then every natural number ‘j’ must be “selfish” and correspond to a non-empty member of P (N) where it is an element. This is another contradiction.

The Cardinality of Any Power Set

Cantor’s general proof may be outlined as follows. First, it is clear that, for any set A, we can map from P (A) to A. Since A = {a, b,…} and P (A) includes {a} and {b}, we can just map {a} to ‘a’, {b} to ‘b’, and so on. It does not matter whether ‘a’ is a number or a complicated set; {a} is simply the set that only contains ‘a’.

Let’s assume that there is a function, f(x), that maps members of a set A to its power set P (A). Let’s define B as a subset of A, with members that meet the criteria: B = {b} where all ‘b’ are in A but ‘b’ are not elements of {f(b)}. (This is very similar to the “non-selfish” set described above).

Therefore every member, b[i], of B is a member of A. However, b[i] is not a member of f(b[i]).

We had assumed that the function f(x) maps from A to P (A); but all the b[i] in B (which also are from A) are not mapped there by the function f(x). (This is the generalized version of the “not-selfish” situation above).

Therefore we have a similar contradiction regardless of the cardinality of set A.