7.3. Construction of the Subset S

Cantor proved that for any set A, the cardinality (size) of that set is strictly less than the cardinality of its power set P(A), which is the set of all subsets of A.

Cantor's theorem tells us that no matter how many elements a set A has, when you create a power set of A (P(A)), which includes all possible subsets of A, that power set will always have more elements than A itself. For example, if you have a finite set with n elements, the power set will have 2^n elements. This relationship holds true even for infinite sets, which is a surprising result.

Think of a box of chocolates as set A. You can take out different combinations of chocolates to create subsets. The total number of ways to select chocolates (the power set, P(A)) is far greater than the number of chocolates in the box itself. Even if you have just a few chocolates, you can create many possible combinations.

Assuming the cardinality of set A is greater than or equal to its power set P(A), we denote a surjective function from A to P(A) as f.

To explore the implications of Cantor's theorem, we start by assuming that the size of set A is at least as large as the size of its power set. This assumption leads us to define a function f that supposedly creates a mapping from each element in A to a subset in P(A). However, this assumption forms the basis for a contradiction, as we will show that this function cannot exist.

Imagine you have a box of crayons (set A), and you are trying to create a system to map each crayon to a specific drawing you can make with it (P(A)). You think you can assign each crayon to a unique drawing. However, as we’ll discover, no matter how many crayons you have, some drawings will always remain unassigned.

We run a diagonalization argument to construct a subset S of A that is not covered by the function f.

Using the diagonalization approach, we can create a new subset S by examining the diagonal entries of the supposed function f. For each entry along the diagonal, we flip 0s to 1s and 1s to 0s, which means that the constructed subset S will differ from every subset f(x) that was supposed to be covered by f. Hence, S cannot be the image of any element in A under f, proving that our initial assumption about f being a surjective function is false.

Consider a library where every book represents a different subset of a collection (P(A)). Think of the main characters of each book as the diagonal entries. By changing the character features (flipping 0s and 1s), you create a new book that doesn't match any existing one. Just like the new book is different from all others, the constructed subset S is not assigned to any crayon originally mapped, thereby proving our contradiction.

Since the constructed subset S does not have any pre-image, the assumption of a surjective function being valid is contradicted.

The existence of the subset S, which cannot be represented as f(x) for any x in A, shows a fundamental flaw in our assumption that there is a surjective function from A to P(A). Therefore, it confirms that the cardinality of A is indeed less than that of its power set, validating Cantor's theorem.

Returning to our library analogy, every book represented by function f has certain characters. When we create a new book (S), we find that it cannot be categorized under any existing mapping. This reinforces our understanding that our library of books (A) is always smaller than the infinite possibilities (P(A)) of the stories that could be told with those characters.

Cantor’s theorem implies that there are infinite sizes of infinity—showing that the power set of any infinite set is uncountable.

Cantor's theorem reveals that there are different 'sizes' or cardinalities of infinity. For example, the set of natural numbers is countable and has a cardinality denoted as א₀. However, its power set is uncountable, meaning there are more subsets than natural numbers. This concept leads to a hierarchy of infinities, where you can continue constructing power sets indefinitely, each leading to a larger cardinality.

Consider a bug (natural numbers) that always hops to higher ground (power set). Each time it hops, it finds more ground (larger power sets) than it can ever reach in its previous state, illustrating how infinities can be of different 'sizes' and how there is no end to how large they can grow.

--