Teacher resources and professional development across the curriculum
Teacher professional development and classroom resources across the curriculum
After the dual assault by Hipassus and Zeno, mathematicians were forced to accept a world that admits both the discrete and the continuous, the rational and the irrational. We consider rational numbers to be discrete quantities of fundamental units, such as "three"-"sixths" (understood as the quantity three of the fundamental unit one-sixth) or "twenty-five"-"hundredths." Irrational numbers are trickier, requiring an infinite number of non-repeating digits to be expressed in decimal form. The fact that both of these types of things count as "numbers" can be somewhat puzzling. Nevertheless, Cauchy and some of his contemporaries had shown that irrationals, as represented by non-repeating, non-terminating decimals, were essential building blocks for calculus and associated areas of mathematics. Moreover, these innovative mathematicians extended the traditional rules of arithmetic to these number newcomers in such a seamless way that it became clear that the irrationals deserved to be considered numbers every bit as much as their rational predecessors.
At this stage of the development of mathematical thought, the idea of number had been extended from the counting numbers (the naturals) to the rationals (by way of ratios of counting numbers) and on to irrationals (by way of infinite sequences of rationals). All of these numbers, rational and irrational together, formed a large set that came to be called the "real numbers." At each step of this categorizing process, the set of "acceptable" numbers had been enlarged— or had it? Were these new sets really any bigger than their predecessors? Is the set of rationals really bigger than the set of counting numbers? Is the set of real numbers really bigger than the set of rationals? Is it possible that they are all simply instances of the mysterious "size" called infinity?
The man who first tackled these questions was Georg Cantor. Cantor was a German mathematician working in the second half of the 19^{th} century and the first two decades of the 20th century. He was a contemporary of luminaries such as Poincaré, Kronecker, and Hilbert. The first two of these men refused to acknowledge his great contributions to mathematics; the third was an ally of tremendous standing. Cantor's work was controversial and his life was one of much struggle and little recognition. Denied employment at the more-respected universities in Germany, he was forced to work at smaller, less-prestigious institutions. Despite this, he helped set mathematics on firmer footing by fully examining the implications of using actually infinite sets. His first breakthrough was to re-define the concept of a number.
If you were asked to define the number 3, you could very well say "1, 2, 3", or "the number of things in the set {a, b, c}." Both of these responses are instances of the number three—both of them enumerate sets having three members, but neither of them defines the concept without referring to either "3" or "number." In general, we should be wary of definitions that must reference themselves. A better line of reasoning is required in order to come up with a true definition of a particular number.
Imagine that you are a ballroom dance teacher. As you begin a lesson, you want to make sure that you have the same number of girls and boys, so that each will have a dance partner of the opposite sex. You could take the time to count the boys, and then count the girls, and then compare the two numbers. A faster way would be simply to pair them off, one boy with one girl, until everyone has a partner. If there is no one left over, you have demonstrated that there are the same number of boys as girls. In mathematician's terms, you have shown a one-to-one correspondence between the set of boys and the set of girls in your dance class.
Going back to our troublesome definition, the most that we can say about the number three is that it is the property shared by the sets {1, 2, 3} and {a, b, c}, and all other sets that can be put into one-to-one correspondence with these sets. Hence, any set that can be put into one-to-one correspondence with these sets also shares the property of "three-ness". This is what we really mean when we say "three." Three is the common property of the group of sets containing three members. This idea is called "cardinality," which is a synonym for "size." The set {a,b,c} is a representative set of the cardinal number 3.
This all sounds like a bunch of semantics, but it is necessary to think of numbers in this way to gain a firm hold on the concept of infinity. We can use the technique of setting up one-to-one correspondence to compare the sizes of different sets without having to "count" all the members of the sets. This is indeed handy when it comes to infinity.
To get a sense of the tools we'll need to answer tough questions about infinity, we can start with a relatively straightforward example. Note that only 4 of the first 16 whole numbers are squares:
It would be tempting to use this as evidence that there isn't one-to-one correspondence between the sets, as there seem to be more whole numbers than square numbers. However, in the 16^{th } and 17^{th} centuries, Galileo, famous for his work in astronomy and physics, demonstrated that there are, in fact, the same number of whole numbers and square numbers. To do so, he pointed out that every whole number can be made into a square number, after which it is possible to line up the two sets of numbers as so:
Galileo's simple exercise made it clear that the set of whole numbers can be put into one-to-one correspondence with the set of square numbers. According to our new definition of number, this means that there must be the same number of each. What Galileo did was essentially to put the square numbers in a list and use the natural numbers to count them. Does this strategy also work for other types of numbers?
Let's consider the ratonal numbers for a moment. Given any fraction, we can always find a smaller one by taking half of it. So, if we want to list all of the rational numbers in sequence from least to greatest, which one should be first? We could say that is pretty small and could potentially be first, but is smaller—should it be first? This line of thinking obviously will not get us very far, as we can easily generate smaller and smaller fractions. Perhaps, because rational numbers are all expressible in terms of two quantities, a "counter" and a "namer," a single, linear list is not sufficient for the task at hand. It might be useful to organize fractions not in a list but, rather, in a two-dimensional array.
To accomplish this, imagine putting all of the fractions that have a 1 as their denominator in the first column of a table. Then let's put all the fractions that have a denominator of 2 in the second column, all those with a denominator of 3 in the third column, and so on. We will generate a table like this:
We could list every positive rational number if we were to continue this grid. Does this mean that the rational numbers cannot be put into a list, as is possible with the square numbers? Cantor, remarkably, showed that it is indeed possible to put rationals into a list format. This concept is now known as Cantor's "first diagonal" argument.
To compose such a list, we can trace out a weaving path through the table above, skipping over fractions that really are the same as ones we've already encountered (such as , etc.).
This strategy creates a list that looks like this:
1/1, 2/1, 1/2, 1/3, 2/2, 3/1, 4/1, 3/2, 2/3, 1/4,...
It should be clear that writing the rationals in this fashion will account for every possible rational for as long as we care to continue.
What's the advantage of having this list? It's easy to start counting them. We can assign the number 1 to , the number 2 to , the number 3 to , and so forth for as long as we like. We see that there is a one-to-one correspondence between the natural numbers and the rational numbers. As with the boys and girls in the dance class example, the one-to-one correspondence indicates that the two sets are the same size.
So, the answer to the question, "How many rationals are there?" is "an infinite number," but it is a "countable" infinity. That is, it would be possible, in theory, to list all the rationals and to number them using the natural numbers. Any set that can be put into one-to-one correspondence with the set of natural numbers is considered to be countably infinite. Note that we have not mentioned negative rational numbers yet. However, through the same strategy they too can be put into a list that can be shown to have one-to-one correspondence with the set of natural numbers.
It might seem that we can put anything into a list that can then be matched up with the set of natural numbers. How about the set of all real numbers? Again, we can look for a one-to-one correspondence with the natural numbers. Suppose we could list all of the real numbers, rational and irrational, between 0 and 1. Such a list, expressing both rationals and irrationals in decimal form, might look like this:
0.36264934…
0.11192737…
0.33333333…
0.66736270…
0.98800034…
…
Even though we are limiting ourselves to looking only between 0 and 1, Zeno made it clear that this list would be infinite. Furthermore, because we have put the numbers in a list, there should be a "first", "second", etc., on up to the "n^{th}" number. So, it would appear that this list, as we have imagined it, is in one-toone correspondence with the natural numbers and is, therefore, countable.
However, at this point, Cantor had a second epiphany. He asked, "What if we create a new decimal by the following method?": In the columnar list of real numbers in decimal form, consider an array of diagonal digits—that is, the first digit of the first decimal, the second digit of the second decimal, the third digit of the third decimal, and so on.
In each case, if the digit is anything other than 1, put a 1 in the corresponding place of the new decimal number. If the digit on the diagonal is 1, put a 2 in the corresponding decimal place of the new number. The new decimal number formed in this way is different from every other number on this list by at least one digit.
How can that be? The list we imagined was supposed to be complete, but we can clearly create a number that was not on that list! This reasoning is similar to the reasoning we employed with Euclid's proof of the infinitude of primes in the unit on prime numbers; namely, we start with a list that is assumed to be complete and then show that it isn't actually complete.
We now call this line of reasoning Cantor's "second diagonal" argument—it involves constructing a new number by following a diagonal path through the digits of a "complete" set.
Following this process proves that the original list was incomplete, because we were able to construct a number not in the list. This new number cannot be paired up with any of the natural numbers, because each of them is already paired up with a number from the original list. One could argue that we should simply make room for the new number on our original list and re-assign the pairings, but this could be done ad infinitum, and at every step we could still create a new number not in the list.
The only alternative explanation is that there must in some sense be more real numbers than natural numbers! In other words, the reals are not countable. Such a set is considered to be uncountably infinite.
We now have two distinct types of infinity, countable and uncountable. If we consider something that we cannot count to be larger than something that we can count (which seems logical), then it makes sense to say that the uncountable type of infinity is larger than the countable type.
Cantor called the cardinality of all the sets that can be put into one-to-one
correspondence with the counting numbers
, or "Aleph Null." The cardinality
of sets that cannot be put into one-to-one correspondence with the counting
numbers, such as the set of real numbers, is referred to as c. The designations and c are known as "transfinite" cardinalities. The cardinality c is also known
as the "cardinality of the continuum," denoting that these sets are best thought
of as a continuous, unbroken line, as opposed to a discretely enumerated line.
Such a line is akin to the Greek idea of a magnitude: infinitely divisible, with no
discrete points. Both cardinalities are complete, actual infinities, rather than
potential infinities, but they are not equal in size to one another.
The idea that there are different types of infinity might seem strange, but Cantor pushed his exploration even further into the realm of novel ideas. To understand more completely what Cantor contributed, we should ask at least two more questions.
First, we said that uncountable infinities, such as those with a cardinality of c, are "bigger" than countable infinities, such as those with a cardinality of , but we didn't prove it. Which is bigger, or c? What does it mean for one number, finite or not, to be larger than another?
Second, we must wonder whether there are any more types of infinity. That is, are there any more transfinite cardinalities? If not, why are there only two types?
These two questions are actually related. In the next section, we will see how their resolution leads to even more bizarre conclusions about the nature of the infinite.
Next: 3.6 Cantors Theorem