7.1. Introduction to Cardinality

Cantor proved that the cardinality of any set A is strictly less than the cardinality of its power set P(A).

Cantor's theorem tells us that if you have a set A, the number of elements in A is always less than the number of subsets that can be formed from A, which is given by its power set P(A). This concept is crucial in understanding different sizes of infinity.

Imagine you have a box with three colored balls: red, green, and blue. The number of ways to make different selections from these balls (the subsets) is more than the number of balls themselves. Even if you can list down all the balls, the combinations you can make with those balls are far more numerous.

If set A is finite and has n elements, its power set will have 2^n elements.

For any finite set with n elements, you can create a total of 2 raised to the power of n different subsets. This is because each element can either be included in a subset or excluded from it, leading to multiple combinations. For example, if A has 3 elements, then the power set has 2^3 = 8 subsets.

Think of a set of friends deciding whether to go for ice cream or not. If you have 3 friends, each can either come or stay home. By combining their decisions, you get 8 possible scenarios: all stay home, one goes, two go, and so on.

Cantor's proof uses contradiction to show that no surjection exists from set A to its power set.

Cantor approaches the problem by assuming the opposite: that a surjection exists from set A to its power set. He then constructs a specific subset S of A, based on the entries in the function's output table. By doing this, he shows that this subset S cannot be mapped back to any element of A, leading to the conclusion that no such surjective function can exist.

Consider a scenario where you try to assign each student in a class to a unique desk that everyone can see. One student, however, has their own special space that does not match any assigned desk. This situation illustrates how not every student can fit into a unique pattern, similar to how not every element in the power set can link back to an element in the original set.

To construct the subset S, Cantor uses the diagonalization argument, flipping entries to show the non-surjective nature of f.

Cantor's diagonalization method involves creating a subset S by examining the output of the assumed function f. By flipping the inclusion of elements based on the diagonal entries (if an entry is 0, include the element; if 1, exclude it), he demonstrates that S cannot be matched with any output from f, thereby proving that f cannot be a surjection.

Imagine a scenario in a voting system where each voter can either vote for a candidate or not. If you flip the votes based on a set rule (like switching from a yes to a no), you might create a whole new preference that no original vote corresponds to, just like how Cantor constructs S that doesn't map back to any original element.

Cantor demonstrated that there is a hierarchy of infinities, showing that some infinities are larger than others.

By suggesting that if you consider the power set of the natural numbers, its cardinality is larger than that of the natural numbers themselves, Cantor established that there are actually different sizes of infinity. This leads to the realization that no matter how many times you take the power set, you keep generating larger infinities.

Imagine climbing a staircase where each step leads to a higher floor. Each higher floor represents a larger infinity. You may start at the ground floor (natural numbers) but can ascend endlessly to higher levels (larger cardinalities, like the power set).

--