Ramble, Part 65: The Whole and the Part
Jan. 27th, 2009 07:51 pm![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
stoutfellowIt was Galileo who had observed that there are just as many perfect squares as there are positive whole numbers - that, in other words, a whole (all the positive whole numbers) could be equal to a part (those positive whole numbers which happen to be perfect squares). Given that one of Euclid's "Common Notions" was that the whole is greater than the part, this was disturbing, which probably accounts for the failure of Galileo's successors to investigate further. Georg Cantor dared to do so, with even more disturbing results.
How do we decide that two collections have the same number of elements? Ultimately, by pairing off the members of one collection with the members of the other. (We may do this indirectly, by pairing both collections off with members of the set consisting of "one, two, three, ..." - or perhaps with our fingers.) This is the commonsensical procedure with finite sets, but applying it to infinite sets, as Galileo did, leads to surprising results. Cantor proposed to take the bull by the horns, and follow the procedure wherever it might lead.
First, we must allow "number of elements" to include possibilities besides the usual, since we need a name for the number of elements - Cantor said the cardinality or the power - of the set of positive whole numbers. He called it ℵ0 - "aleph-zero" - resorting to the Hebrew alphabet, since the letters of the Latin and Greek alphabets were already in use for more ordinary numbers. A set with this cardinality can be paired off with the totality of the natural numbers; in other words, it can be listed. (Write the name of the element that gets paired off with 1, then the name of the one paired with 2, and so on.) These sets are thus "countably infinite". What sets are countably infinite?
The set of all the integers is; we can list them thus:
Suppose that you have a list of real numbers between 0 and 1. Cantor's claim is that there must be a real number in that range which isn't on your list; in other words, any list of real numbers between 0 and 1 must be incomplete - so the set of all real numbers in that range isn't countable. Let the first number on your list be 0.a1a2a3a4a5.... I begin to construct a real number not on your list by setting its first digit to something other than a1. For definiteness' sake (and to dodge one tiny technicality), we'll do it this way: if a1 is one of 0, 1, 2, 3, or 4, we set the first digit to 7; otherwise, we set it to 3. Now we look at the second number on your list, 0.b1b2b3b4b5.... We set the second digit of our not-on-your-list number to differ from b2, as before. We choose the rest of our number in the same way, making it differ from, say, the 128th number on your list in the 128th digit. Clearly, this number can't be on your list, and your list must be incomplete.
Cantor's diagonalization argument shows that it is possible, after all, for one infinite set to be larger than another - that there is more than one infinite cardinality. Indeed, it can be adapted to show that there are infinitely many infinite cardinalities. (One might be tempted to ask how many there are - but that way, as we shall see, lies madness....)
Previous Next
Ramble Contents
How do we decide that two collections have the same number of elements? Ultimately, by pairing off the members of one collection with the members of the other. (We may do this indirectly, by pairing both collections off with members of the set consisting of "one, two, three, ..." - or perhaps with our fingers.) This is the commonsensical procedure with finite sets, but applying it to infinite sets, as Galileo did, leads to surprising results. Cantor proposed to take the bull by the horns, and follow the procedure wherever it might lead.
First, we must allow "number of elements" to include possibilities besides the usual, since we need a name for the number of elements - Cantor said the cardinality or the power - of the set of positive whole numbers. He called it ℵ0 - "aleph-zero" - resorting to the Hebrew alphabet, since the letters of the Latin and Greek alphabets were already in use for more ordinary numbers. A set with this cardinality can be paired off with the totality of the natural numbers; in other words, it can be listed. (Write the name of the element that gets paired off with 1, then the name of the one paired with 2, and so on.) These sets are thus "countably infinite". What sets are countably infinite?
The set of all the integers is; we can list them thus:
0, 1, -1, 2, -2, 3, -3, ....The set of all pairs of positive integers is; we list them according to the sum of the two integers.
(1,1), (1,2), (2,1), (1,3), (2,2), (3,1), (1,4), (2,3), (3,2), (4,1), ....The set of all positive rational numbers is also countably infinite; take the pairs just above, discard those which have a common factor, and make them fractions:
1/1, 1/2, 2/1, 1/3, 3/1, 1/4, 2/3, 3/2, 4/1, ....Combining the first trick with the third, we find that the set of all rational numbers also has this cardinality:
0/1, 1/1, -1/1, 1/2, -1/2, 2/1, -2/1, ....At this point one begins to wonder if every infinite set is countable. One of Cantor's first great discoveries was that this is not true - that, in fact, infinite sets can have different sizes, notwithstanding the occasional part equalling the whole. The set of all real numbers between 0 and 1 is not countable. Cantor's proof of this fact introduced a technique called "diagonalization", which has proven quite useful.
Suppose that you have a list of real numbers between 0 and 1. Cantor's claim is that there must be a real number in that range which isn't on your list; in other words, any list of real numbers between 0 and 1 must be incomplete - so the set of all real numbers in that range isn't countable. Let the first number on your list be 0.a1a2a3a4a5.... I begin to construct a real number not on your list by setting its first digit to something other than a1. For definiteness' sake (and to dodge one tiny technicality), we'll do it this way: if a1 is one of 0, 1, 2, 3, or 4, we set the first digit to 7; otherwise, we set it to 3. Now we look at the second number on your list, 0.b1b2b3b4b5.... We set the second digit of our not-on-your-list number to differ from b2, as before. We choose the rest of our number in the same way, making it differ from, say, the 128th number on your list in the 128th digit. Clearly, this number can't be on your list, and your list must be incomplete.
Cantor's diagonalization argument shows that it is possible, after all, for one infinite set to be larger than another - that there is more than one infinite cardinality. Indeed, it can be adapted to show that there are infinitely many infinite cardinalities. (One might be tempted to ask how many there are - but that way, as we shall see, lies madness....)
Previous Next
Ramble Contents
![[identity profile]](https://www.dreamwidth.org/img/silk/identity/openid.png){kind=small}
no subject
Date: 2009-01-28 06:56 am (UTC)