Cardinality

Last week I had forgotten that I still had to get through a section on Cardinality to get to Sequences and Series. Cardinality is all about sizes, though finite sizes aren’t super interesting when it comes to cardinality. What’s interesting is the infinitude of infinitely larger cardinalities.

The main two ideas from this week were Cantor’s Diagonalization proof and the cardinality of power sets. So we will discuss:

1. Showing that the real numbers are uncountable with Cantor’s diagonalization method

2. Showing that the power set of a set has a higher cardinality

To explain 1, I’ll explain the diagonalization proof. So if the real numbers are countable, then we should be able to list them out such that each line in our list is a natural number mapping to that real number. Previously in the book we proved that the numbers from (0,1) have the same cardinality as the real numbers, so let’s just make a list of numbers in that range using their decimal expansions. Remember that each number can have an infinite decimal expansion (e.g. 54.7000…). So each real number in the list has infinite length. Now if we think of this list, it is a list of infinitely long decimal expansions, so we can think of the diagonal as a number with the first decimal as the first decimal in the first number in the list, the second number in our new number as the second decimal from the second number in the list, etc. taking a new decimal moving down the diagonal. Now Cantor had the idea to use this number to create a new real number and show that the new number couldn’t be in the list, thus the list didn’t have all the real numbers in (0,1). Let the new number have a decimal digit of 3 for each of the original digits from the diagonal that were 2 and otherwise have a 2. The idea is to make sure that none of the digits of our new number match the digits of the real number we formed taking digits from the diagonal. Since this new number we formed doesn’t share any digits with any of the elements in the diagonal, we know it isn’t in the list. The reason is that for every number in our list, the new number is different from that number in the list at the position in the diagonal. For example, our number will be different from the 1st decimal digit of the 1st number in the list, it’ll be different from the 2nd decimal digit of the 2nd number in the list, and it’ll be different from the nth decimal digit of the nth number in the list…

So the diagonalization method shows that the real numbers aren’t countable. We showed another way last week, but this one is less math-definition-intense.

For 2 (showing that power sets have larger cardinality than their original sets), first let’s define a power set. A power set of a set is the set that contains all subsets of the original set. So items in a set are elements (can be sets) and items in a powerset are sets necessarily. Take the set {0,1}. It just has those two elements. The powerset of this set is {{0}, {1} {0,1}, {}}. Notice that we have an empty set in there, each element as a set, and the full set as an element. Since for each element in the original set we have subsets with and without that element, we have 2^n elements in the powerset of each set. The proof that this has larger cardinality is based on the fact that a function mapping a set to a powerset is always 1-1 but not onto. This means every element in the set always maps all of its inputs to unique outputs in the powerset, but it can’t ever cover all of them with a 1-1 relationship. Thus, the powerset has a higher cardinality. This is cool because it shows that there are infinitely different sizes of infinity and there’s also no “largest” set since every set always has a powerset that’s larger than it.

This week was a bit of a slog working through proofs, but the underlying concepts about cardinality are deeply related to computer science theory which is neat. They’re also somewhat intuitive unlike some of the other real analysis I’ve explained in the past weeks. Given how much of a slog real analysis is getting, I might change subjects temporarily to bring back some energy into my personal exploration.

Hope everyone is safe (especially on the east coast) and hope you had a great week! See you next week!