No, but they had numbers. Cantor invented set theory, which has to do with measuring the size of sets, and in particular the size of infinite sets. If I lose you in the following, tell me where.
The basic idea is one-to-one correspondence. That is, if you have a big pile of marbles, too big to count in your head, and a big pile of rivets, you can figure out which is bigger by pairing up marbles with rivets. If you have marbles left over, the set of marbles is bigger; if you have rivets etc; if you don't have anything left over, the two sets are the same size.
Okay, that's straightforward for finite sets. But infinite sets can be put in one-to-one correspondence with proper subsets of themselves. ("Proper" means not the set itself.) In fact, this is the definition of an infinite set.
So, for example, let A be the set of positive integers, and let B be the set of even positive integers. So, clearly B is a proper subset of A. But they can be placed in one-to-one correspondence as follows: Pair up the number n from set A with the number 2n in set B. Every number in A is included in this pairing, and so is every number m in set B, because it can be paired with m/2 in set A. (m/2 is an integer because every number in set B is even.)
Still with me? So, what Cantor did that's relevant to rational numbers was to prove that the set of rational numbers is the same size as the set of positive integers.
What does any of this have to do with streams? Well, the way streams work is that you can find any finite item number from the stream with n-1 CDRs and then CAR of that. And, hey, an item number is a positive integer! So: The infinte sets that can be represented as streams are precisely the ones that can be placed in one-to-one correspondence with the positive integers. The integer n is paired with ITEM n OF the stream. So, the correspondence that Cantor invented between the positive integers and the positive rationals is how you write the code for the stream of rationals.
Note: Don't be misled by the even integers example into thinking that the correspondence between two sets of numbers has to follow the size ordering of the numbers. For example, here's how to put the positive integers in one-to-one correspondence with the set of all the integers: You rearrange the integers this way:
0, 1, -1, 2, -2, 3, -3, 4, -4, ...
and then you can line them up with the positive integers.
Now for the exciting part. By this time, Cantor had pretty much convinced himself that all infinite sets would turn out to be the same size, "infinity." But then he proved that the set of real numbers is bigger than the integers!
Ready? Here goes.
To simplify things, we'll actually prove that the set of real numbers in the range 0<r<1 (strictly less than), which is a proper subset of the reals, is bigger than the integers. So the real numbers would be, if anything, bigger than the (0,1) range.
A real number in that range can be represented as a decimal, like this:
0.abcdef...
with an infinite number of digits (maybe mostly 0) after the decimal point. So, proof by contradiction, assume that this set is the same size as the positive integers. Then we can make a one-to-one correspondence between positive integers and decimal fractions. Basically this is an infinite list of decimal fractions. So now we're going to construct a decimal fraction that isn't in the list.
We construct it digit by digit, starting after the decimal point. For the first digit, we look at the fraction that's paired with 1, and we choose any digit that isn't the first digit of that fraction. (And we also don't choose 0 or 9, to avoid the problem that 0.09999... is the same number as 0.10000...) For the second digit, we look at the fraction that's paired with 2, and choose any digit that isn't its second digit or 0 or 9. For the third digit, look at the fraction paired with 3, and choose anything that isn't its third digit or 0 or 9. And so on forever.
So, I claim this fraction we just constructed isn't in the list. Because if it is in the list, it has to be paired with some positive integer n. But the fraction that's paired with n isn't this fraction, because they differ in the nth digit. (Maybe other digits too, but for sure in that digit.) So this decimal fraction isn't in the list, so we can't make a one-to-one correspondence between the positive integers and the real numbers in (0,1), so the reals are bigger than the integers!
Isn't that fantastic? That we can prove such a thing? Cantor himself remarked, "I proved it, but I don't believe it," because it was so counterintuitive that all infinite sets aren't the same size. I was wrong about this; what he said that about was that C²=C.
So, you can construct a stream of all the rational numbers, but you can't construct a stream of all the real numbers.
The numbers that are the sizes of infinite sets are called "transfinite cardinal numbers." (There are also "transfinite ordinal numbers," which have to do with the natural ordering of sets, but they're way more complicated.) The size of the integers is represented as ℵ₀, pronounced "aleph null," and the size of the reals is C, for "continuum" because the reals are continuous on the number line. A set the same size as the integers (or smaller, i.e., finite) is called "countable." So, you can make streams of countable sets.
So, why isn't the size of the reals called ℵ₁? Because Cantor couldn't determine whether there are any infinite sets larger than the integers but smaller than the reals. That question was unsettled until I was in high school, so early '60s, when one day I picked up my copy of the New York Times (I subscribed through the school), and on the front page of the second section was a half-page article saying that someone had just proved that the question C≟ℵ₁ is undecidable, i.e., the axioms of set theory are consistent with either of C=ℵ₁ and C≠ℵ₁. That was the most exciting day of my time in high school.
