7. Cantor's Theorem

Cantor proved a very interesting result as well. He showed that you take any set A then the cardinality of that set is strictly less than the cardinality of its power set. So remember the notation P(A) denotes the power set of A.

Cantor’s theorem states that for any set A, the number of subsets (the power set, denoted as P(A)) is always greater than the number of elements in A. This means if you have a set A, no matter how many elements it has, the collection of all possible subsets of A will always contain more elements.

Think of a box of toys. If you have 3 toys, you can make several groups of subsets: one toy by itself, two toys, all three together, and the empty set (no toys). Even though you had only 3 toys, the different combinations (subsets) you can make from them are more than just three – there are 8 in total.

This statement is true if your set A is finite; namely, if your set A has n number of elements, then its power set will have 2n elements.

For a finite set with n elements, the power set will contain 2 raised to the power of n (2^n) subsets. For example, if A has 3 elements (like {1, 2, 3}), its power set will have 2^3 = 8 subsets.

If you have a set of 3 colored balls—red, blue, and green—you can create subsets in multiple ways: just the red ball, red and blue together, or all three together, among others. When you count all these combinations, you see that the total is more than just the single balls themselves.

What if A is an infinite set? Can we conclude that this theorem is true even for infinite sets? Cantor showed yes, using a proof by contradiction and the diagonalization argument.

Cantor extended his theorem to infinite sets by assuming the opposite: that an infinite set A could have the same cardinality as its power set P(A). However, he proved that this leads to a contradiction, thereby confirming that even for infinite sets, the cardinality of A is less than that of P(A).

Imagine trying to list all real numbers between 0 and 1. Cantor's diagonalization method shows that no matter how thorough your list is, you can always create a new number that will not be included in your original list, illustrating that the set of all real numbers is much larger than any countable set.

Assuming that the cardinality of A is greater than equal to the cardinality of its power set implies there exists a surjective function from A to P(A). Here, I denote that function by f.

A surjective function means every element in the power set P(A) is mapped to by some element in set A. However, Cantor constructed a set S that cannot be an image of any element of A, showing a contradiction in the existence of such a function.

Imagine a classroom where every student must choose a project topic—the assumption is that every possible topic is covered. Cantor's argument demonstrates that even if the students collectively pick a variety to cover, there will always be a unique topic that someone hasn’t selected, proving that not all topics can be chosen by the students.

I construct a subset S using the diagonalization argument based on the entries related to the function f. If the diagonal entry is 0, I include the corresponding element; if it's 1, I exclude it.

This method of constructing set S involves looking at how elements of f correspond to the elements of A and flipping the choice for each diagonal entry. This guarantees that S will differ from every f(x), which results in proving that S can’t be an image, opposing our initial assumption.

Think of a password system where each user's choice must not directly match with what is already taken. If each user can see a pattern of chosen passwords (like the entries in a diagonal), they can pick a new password that differs enough to ensure it’s not used, just like S ensures there’s always a new entry different from f(x).

The implication of Cantor’s theorem is that there are infinitely many different sizes of infinite sets; this leads to the concept that there is not just one infinity, but a hierarchy of infinities.

Cantor's theorem illustrates that infinite sets, like the set of natural numbers, are less than their power set, which is uncountable. Each level of power set produces a new, larger infinity, creating a structure of infinite sizes.

Imagine the different sizes of containers for water: a cup, a bucket, and an ocean. While all are containers, each can hold a different amount of water, just as Cantor’s theorem shows that not all infinities are of the same size.

--