The Sizes of Infinities
In the last article, "How Big is Infinity?", we discussed what it means when something is infinite -- that it has no bound on how large it gets. But when it comes to infinitely large things, is there any way to measure them against each other? Is there a way to see which infinite collections are larger?
Consider the following example: I have two sets of numbers. Set A = {1, 3, 5, 7, 9}, and Set B = {0, 2, 4, 6, 8, 10}. The cardinality, or the size of a set, is the number of elements, or items, in the set. So, the cardinality of Set A, written simply as |A|, is 5, whereas |B| = 6. In this case, B has a higher cardinality than A.
If Set B, instead, were just {0, 2, 4, 6, 8}, then |B| would be 5, and they would have equal cardinality. We say that there is a bijection between two sets if they have the same cardinality (the formal definition of a bijection is more involved, but for our purposes, this definition will be good). A bijection between two sets exists if there is a one-to-one relationship between their elements. In this case, there is a one-to-one relationship:
1↔0, 3↔2, 5↔4, 7↔6, 9↔8
Every item in Set A has exactly one corresponding item in Set B. This may seem kind of boring and obvious, but it becomes very helpful in a moment!
Now that we have a basic understanding of how we compare the sizes finite sets to each other, we can consider how to compare the sizes of infinite sets to each other. Obviously, any infinite set will have a higher cardinality than a finite set, but what happens when we compare two infinite sets?
Let's start with the natural numbers -- the non-negative integers (counting zero). The set of natural numbers looks like this: {0, 1, 2, 3, ...}. Remember, this is an infinitely large set, so there is no upper bound to when we stop. We just keep going on forever. Is this set bigger than, smaller than, or equal in size to the set of positive integers (NOT counting zero)?
Natural numbers: {0, 1, 2, 3, ...}
Positive whole numbers: {1, 2, 3, ...}
You might be tempted to say that the set of natural numbers is bigger, because it includes the entire set of positive whole numbers, as well as zero! But, remember how we compare them -- cardinality, or the number of items in the set. And when dealing with infinities, you can't say "infinity plus one", because infinity isn't a regular number like that.
This is where the concept of a bijection comes in handy. Is there a one-to-one relationship between the items in these two sets? The answer is yes! If we were to write out the elements in both sets as far as we wanted, we would see that every positive whole numbers is exactly 1 larger than the natural number directly above it. A bijection exists, so their cardinality is equal.
We define a countably infinite set, or a countable set for short, to be a set that has a bijection to the set of natural numbers. The set is infinite, but we can "count" them -- we can line them up in a row in such a way that we can, one by one, check them off of a list, and we will be guaranteed to check off any particular item in the set. The the zeroth positive integer is 1, the first positive integer is 2, the tenth positive integer is 11, and so forth. Where in the list is 235? Why, it's the 234th positive integer!
Let's look at another infinite set: the set of integers -- positive whole numbers, negative whole numbers, and zero. The set of integers looks like this: {..., -3, 2, -1, 0, 1, 2, 3, ...}
Is this set countable? It appears not -- after all, if we line them up against the natural numbers with 0↔0, 1↔1, etc, we'll never finish with the positive numbers, so we'll never even start with the negatives!
But what if we rearrange them? As long as we don't make any changes to the set itself, we can rearrange the items inside of it however we want, and the set is still the same. So, if we start with 0, then alternate positive and negative numbers, we can rearrange the integers to look like this:
{0, 1, -1, 2, -2, 3, -3, ...}
In this manner, we can count the integers!
0↔0, 1↔1, 2↔ -1, 3↔2, 4↔ -2, 5↔3, 6↔ -3, etc. Where in the set is 27? If we keep writing it out, we'll eventually get to: 53↔27. Where is -42? If we continue, we'll get to 84↔ -42. And so on and so forth. This means that the set of integers is also countable.
But how about the set of rational numbers -- any integer divided by a positive integer. This set is even wilder! We can pick any integer for the numerator, and any positive integer for the denominator! This set includes, but is not limited to: 0, 1/2, 2/1, 5/16, 42/13, -1234/5678, and so many more that it seems impossible that there can be any way of ordering them. But there is!
Consider the following (incomplete) chart. The top row represents the numerators, and the first column represents the denominators. Every cell in the resulting table is the combination of its specific location. Thus, 4/7 is the 4th column and 7th row:
(You may note that some of these fractions are equal to each other -- the entire main diagonal is equal to 1, for example, but that's not important for this demonstration.)
Zero is omitted in this chart, but for our counting method, it is the zeroth item in the list (paired up with natural number 0).
Note the diagonal-stripe pattern of grey and white cells. In each diagonal, going from the upper-right to the lower-left, the numerator and the denominator sum to the same value (3/1, 2/2, and 1/3 have num/denom pairs sum to 4, for example). We can then list the (positive) rational numbers according to the sum of their numerator and denominator. We start with the zeroth term being
{0, (1/1), (1/2, 2/1), (1/3, 2/2, 3/1), (1/4, 2/3, 3/2, 4/1), ...}
If we then alternate positive and negative rational numbers, we get the following countable set:
{0, (1/1, -1/1), (1/2, -1/2, 2/1, -2/1), (1/3, -1/3, 2/2, -2/2, 3/1, -3/1), (1/4, -1/4, 2/3, -2/3, 3/2, -3/2, 4/1, -4/1), ...}
In this ordering, we will hit every rational number. This counting method is a lot slower than the counting method for the integers, and, for example, -1234/5678 appears at the 47,757,478th term in the set, but every rational number will be listed. This means that there is a bijection between the rationals and the naturals, so the rational numbers are also countable.
Note: if you want to find any particular rational number ±n/d on your own, its location in the set is: (n+d-2)(n+d-1) + 2n for negative rationals, and (n+d-2)(n+d-1) + 2n - 1 for positive rationals. This only works when n is positive and non-zero. Remember that d is always positive and non-zero.
Perhaps you're beginning to wonder if all infinite sets are countable. Is there always going to be some tricky way of arranging the elements in a set so that there is a bijection?
The answer to that question is no, and in the 1800s, a man named Georg Cantor came up with a very clever demonstration of a set that is not countable.
A real number is any number on the number line. It doesn't have to be an integer, it doesn't have to be positive, and it doesn't have to be rational, it just has to be on the number line. Let's look at all the real numbers between 0 and 1. Is the set of real numbers between 0 and 1 countable?
Cantor's "diagonal argument" says that the real numbers between 0 and 1 are not countable. The proof works using a technique called proof by contradiction -- assume that the opposite is true, then show that it leads to a logical contradiction. His proof assumes that this set is countable, and then demonstrates that our ordering is not only incomplete, but cannot be complete. Here's how it works:
For simplicity (and space), we convert all of our numbers to binary -- a counting system using only 0s and 1s. (As a refresher, remember that 1 + 1 = 10; 1 + 11 = 100, and 0.01 + 0.01 = 0.10)
Since all of our numbers are between 0 and 1, let's write out the binary expansion of all of our numbers in our neat ordering scheme:
0.{0 0 0 0 0 0 0 0 ...} 0.{1 1 1 1 1 1 1 1 ...} 0.{0 1 0 1 0 1 0 1 ...} 0.{1 0 1 0 1 0 1 0 ...} 0.{1 1 0 0 1 1 0 0 ...} 0.{0 0 1 0 1 1 0 1 ...} 0.{0 1 1 0 1 1 0 1 ...} 0.{1 0 1 1 0 0 1 1 ...} ...
If we look at the main diagonal (upper-left corner downward to the right), and we write down the number it forms, we get .01001101... Notice that this number is formed by the kth bit in the kth number in our list. If we then flip each bit (0s become 1s and 1s become 0s), we get .10110010... Remember, since every real number between 0 and 1 is in this ordered list, so is our new number. Let's say it's the 8th number in our list. Then, look at the 8th bit in the number -- but when we flipped every bit, we also flipped the 8th bit. That means that the 8th number in our list has a different 8th bit than our new number, which means we have a different number.
No matter what number we thought it was in the list, we actually have a different number. We can't stick this new number in the middle somewhere, because it would create a new diagonal which would also be a new number for the same reason, and we can't stick it at the end, because our list is infinitely long, and infinity has no end. We can never get to a place in our list to put our new number! And since we assumed that our set was countable, we have arrived at a logical contradiction.
The real numbers between 0 and 1 are uncountable! Here we have an infinite set of numbers that does not have a bijection with the natural numbers. Its cardinality, while still infinite, is bigger than the cardinality of our previous infinite set! Objects with infinite size can, in fact, be objectively bigger than each other. What do we call these infinities?
In response, Cantor gave a new "scale" of infinities. He defines
(aleph-null) as the cardinality of the natural numbers, and
(aleph-one) as the cardinality of the smallest set that is larger than it. So is the cardinality of the real numbers
? Sadly, mathematics can't answer that question. This question is called the continuum hypothesis -- "Is the cardinality of the real numbers,
, equal to
?" This question has been shown to be unprovable, either yes or no, given our current rules for set theory. The next lesson, "This Statement is False", will go into more details about what it means for a statement to be unprovable.
The next question is this: does this subset of the real numbers have the same cardinality as the entire real number line? The answer is yes, but the proof isn't particularly illuminating -- the function tan(pi*x + pi/2) strictly increases from -∞ at x = 0 to ∞ at x = 1 in a one-to-one fashion. Thus there exists a bijection (in the form of a function) between the set of real numbers between 0 and 1, and the set of all real numbers.
So what's next? Is there a "bigger" infinity than the real numbers? You shouldn't be surprised to find out that the answer is yes, there are cardinalities larger than that of the real numbers. Consider what the binary expansion of a real number is -- each bit represents a countable number, with 0 being "off" and 1 being "on". Thus, 0.1000... (repeating 0s) can represent the set {1}. 0.11001100... (repeating 1100) can represent {1, 2, 5, 6, 9, 10, 13, 14, ...}. Every real number can be thought of as a subset, (set constructed of elements within a larger set) of the natural numbers. Thus, the set of all real numbers is effectively the set of all subsets of the natural numbers.
Cantor's Theorem states that if you have some set A, and you construct a set B which is the set of all subsets of A, then (remember the notation defined earlier) |B| > |A|. This means that you can create a set with a cardinality bigger than that of the real numbers! All you have to do, is create the set of all subsets of the real numbers. And then, to create a set with a bigger cardinality than that, just create the set of all subsets of that one! There is no limit!