Google+

Wednesday, November 30, 2011

The infinity

A brief introduction to infinity
The notion of infinity is fundamentally beyond the human ability to comprehend, but that hasn't stopped mathematicians from trying. So just what is infinity, and why is there more than one of them? And just whatis infinity plus one? Last week, we searched for the largest meaningful number in the universe, but all of these must of course pale in comparison to infinity. Mathematicians define "infinity" very strictly. But we'll stick with a broader, everyday definition: Infinity covers any number that isn't finite. Now, without further ado, let's expand our minds and tiptoe towards infinity.



The Beginning of Infinity
In order to talk about infinity, we first have to find a way to define it mathematically. That isn't an easy task - while the concept of infinity was known to the ancient Greeks, and it features prominently in the calculus of Isaac Newton and Gottfried Liebniz, infinity wouldn't be rigorously defined until the late 1800s. Before that, it was just some vast, amorphous concept, more an artifact of certain mathematical operations than something worth understanding in its own right. Indeed, many 19th century mathematicians found infinity to be vaguely distasteful, and they felt it had no place in serious mathematical discussion. At best, infinity was something for philosophers to discuss, and you can imagine the sort of disdain with which such pronouncements were made. It was in that context that Georg Cantor published the first proof of the existence of infinity in 1874. Born in Russia but raised in Germany, Cantor provided a stunning and instantly controversial proof that not only defined the nature of infinity, but it also revealed thatmultiple infinities existed, and some were larger than others. What made his achievement all the more remarkable was that he had built the entire thing out of an ancient and seemingly useless branch of mathematics known as set theory. Basically, it was the mathematical equivalent of building an interstellar drive out of a wheelbarrow.

  Set Theory
Set theory really does seem laughably simple, but it's proven to be among the most powerful tools in modern mathematics. The basic idea can be found as far back as Aristotle, and it's simply this: numbers can be grouped into sets. That's it. Hell, even that can be simplified: thingscan be grouped into sets. You can take the numbers 1, 2, 3, and 4 and put them in the set {1,2,3,4}, which we'll call Set A. You could also take the letter D, a tuna sandwich, a Thomas Hardy novel, and the planet Neptune and put them in the set {D, tuna sandwich, Thomas Hardy novel, Neptune}, which we'll call Set B. Not exactly what you'd call impressive, right? But amazingly, we're only a couple of steps away from the big insight that reveals infinity. Let's say you took those two sets I just described and compared them. Which one is bigger, Set A or Set B? If you think about it in individual terms, that might seem like a nonsense assignment - how could you compare a Thomas Hardy novel to the number 3, for instance? The key here isn't to look at the specific terms, but to look at howmany terms there are. Since there are four terms in both sets, they're of equal size. Let's take nothing for granted though. Howdid we deduce there were four terms in both sets? I'm guessing most of you would have simply counted how many were in each set and then compared them...again, this is basic, basic stuff. But let's say you knewnothing about numbers and didn't know how to count. How then could you compare the two sets? That might seem like a deeply weird question, but part of what makes set theory so interesting and so powerful is that it can be completely separate from all other mathematics, which means we need a way to compare the sets without resorting to counting.

  Building a Correspondence
Even if you had no idea how many terms were in each of those two sets, it would still be easy enough to compare them. All you would need to do is look at Set A, match it to a term in Set B, and repeat the process until no terms are left in either Set A or Set B. Moving left to right, we can pair 1 with D, 2 with tuna sandwich, 3 with Thomas Hardy novel, and 4 with Neptune. Without even having to know precisely how many terms are in each set, we know that the two sets are of equal size. This is known as one-to-one correspondence, and it allows us to compare any two sets without ever needing to count how many terms are in either of them. You can probably see how that last bit takes us to the doorsteps of infinity. Up to now, we've just been pretending that we can't count to four, but how about we create a set with infinitely many terms? The classical example is a set containing the natural numbers, which are all the non-negative integers beginning with zero. Cardinality is the mathematical term for the number of items in a set. So, Set A and Set B both had a cardinality of 4, while this new set of all the natural numbers has an infinite cardinality. But that's imprecise: it's cardinality is actually aleph-null, or aleph-zero, which is the smallest type of infinity. To understand why this infinity is smaller than other, we need to bust out a little transfinite arithmetic.

  The Arithmetics of Aleph-Null
So, we've got aleph-null, the set of all natural numbers. Now, which is bigger: aleph-null, or aleph-null+1? The old "just add 1" canard comes up all the time when we're talking about the largest finite numbers, and with good reason - you can always just add 1 to a finite number and come up with something even bigger. But does that work for aleph-null? Well, let's borrow the tuna sandwich from our earlier set and add it to the set of all natural numbers, so we've now got a set with aleph-null+1 terms. As we've established, the only way to compare these two sets is with one-to-one correspondence. We'll put the tuna sandwich at the start of one set, which we'll call Set C, while Set D will just be the standard set of natural numbers. So then, Set C begins {tuna sandwich, 0, 1, 2, 3, 4...}, while Set D is {0, 1, 2, 3, 4, 5...}. We'll match the tuna sandwich to 0, 0 to 1, 1 to 2, 2 to 3, 3 to 4, 4 to 5...and so on forever. After all, there are still infinitely many terms in both sets, and we can keep up the one-to-one correspondence for as long as we like without ever running out of terms. That means aleph-null and aleph-null plus a tuna sandwich are precisely equal. This is a deeply weird, counterintuitive result. Georg Cantor himself famously remarked "I see it, but I do not believe it" when discussing transfinite arithmetic. And it gets weirder. Here's a question - which is the bigger set, the set of the even natural numbers or all the natural numbers? Our finite perspective would tell us that all the even and odd numbers should be twice as many as all the even numbers, but a little one-to-one correspondence will reveal that, as far as set theory is concerned, the two are equal. When you multiply infinity by 2, you've still just got infinity.

  Infinity Times Infinity
Now for a real challenge. What about the set of all rational numbers - in other words, all the numbers that can be expressed as a fraction of two integers? We're talking about the infinitely large set {1/1, 1/2, 1/3, 1/4, 1/5...}, followed by the infinitely large set {2/1, 2/2, 2/3, 2/4, 2/5...}, followed by the infinitely large set {3/1, 3/2, 3/3, 3/4, 3/5...}, and so on and so forth infinitely many times. We're talking about an infinite amount of infinite sets. Full size If anything is going to get us to an even bigger infinite number than aleph-null, this is going to be it, right? After all, I can do a one-to-one correspondence between all the natural numbers and all the rational numbers with 1 as the numerator, but that still leaves infinite sets worth of infinite numbers still to match up. And yet there'sstill a way to create a one-to-one correspondence between the two sets. In order to illustrate how to do it, I'll need to make a simple table. Let's put all the rational numbers where 1 is the numerator in the first row, all those with 2 as the numerator in the second, and so on and so forth until we have infinitely many rows and columns: 1/1, 1/2, 1/3, 1/4, 1/5 ... 2/1, 2/2, 2/3, 2/4, 2/5 ... 3/1, 3/2, 3/3, 3/4, 3/5 ... 4/1, 4/2, 4/3, 4/4, 4/5 ... 5/1, 5/2, 5/3, 5/4, 5/5 ... ... I know it's not pretty, but what we see here are the beginnings of an infinite table, and that all possible rational numbers will be represented somewhere here, as the denominators grow infinitely large in the rows and the numerators do the same in the columns. The fact that we've been able to make this table at all might be a tip-off that a one-to-one correspondence is possible, but let's see precisely how to do it. First, match the first natural number 0 with 1/1. Next, go down the column and match 1 with 2/1. Now go up diagonally and match 2 with 1/2. Then go back to the first column and match 3 with 3/1. Moving diagonally, 4 matches with 2/2, and 5 with 1/3. We can keep this up infinitely for both sets, and the fact that we're going through the natural numbers much faster than the rational numbers doesn't matter. What does matter is we've found a way to arrange the rational numbers in a single infinite set, which means it too has the cardinality of aleph-null.

  The Uncountably Infinite
All the sets we've discussed so far have been what's known as countable, which simply means it has a cardinality equal to or less than that of the set of natural numbers. The term goes back to Georg Cantor, and the idea is simple enough - a countable set is any set in which all the terms can be associated with a natural number. Even if it would take a, well, infinite amount of time to do it, every term in the set can be counted. We've already determined that the set of all rational numbers is countable, despite seemingly being far bigger than the set of natural numbers - indeed, we've effectively demonstrated that infinity = infinity^2. It seems that, just as adding, multiplying, and even squaring numbers can never produce an infinite number, doing the same operations with aleph-null will never get you to a larger level of infinity. If we want to get to aleph-one, the next order of infinity, we'll need to come up with something that is uncountably infinite.

  Cantor's Diagonals
Georg Cantor provided the most elegant explanation for what an uncountably infinite set actually is. The most famous example is the set of all real numbers, which includes all the natural numbers, all the rational numbers, all the irrational numbers such as the square root of 2, and the transcendental numbers such as the values pi or e. Irrational and transcendental numbers can be expressed, but only as a number with an infinite number of digits after the decimal point. Let's keep this simple and imagine a binary number system, one in which all the digits were either 0 or 1. We could then start creating sequences in which the terms were all the digits of decimal expansions of all the real numbers. It doesn't matter how we arranged these, but let's say we did it like this... Sequence 1 = (1, 1, 1, 1, 1...) = .11111... Sequence 2 = (0, 0, 0, 0, 0...) = .00000... Sequence 3 = (0, 1, 0, 1, 0...) = .01010... Sequence 4 = (1, 0, 1, 0, 1...) = .10101... Sequence 5 = (1, 1, 0, 0, 1...) = .11001... ...and so on and so forth. So, the question is this - if we create an infinite number of these sequences, will we account for all the real numbers? To disprove that, we would need to create a real number that, by definition, cannot be in any of the infinite number of sequences that we've created. Cantor's idea was to take each sequences and associate it with one of its particular terms, so that Sequence 1 is associated with its first term (1), Sequence 2 with its second term (0), Sequence 3 with its third term (0), and so on. In other words, he was drawing a diagonal through the set, and each number the diagonal passes through becomes part of this set. So then, we have Sequence Diagonal, which is (1, 0, 0, 0, 1...). Here's where things get interesting.

  Into the Continuum
Now let's take that sequence and invert it, so that we've got Sequence 0, which is (0, 1, 1, 1, 0...) or .01110..., which we already know is a real number because a real number is simply any number composed of a finite or infinite amount of digits. But is it one of the sets of real numbers we just created? It can't be Sequence 1, because their first terms don't match. It can't be Sequence 2, because their second terms don't match, it can't be Sequence 3 because their third terms don't match, and...well, you get the idea. No matter which set you pull out, one of its terms won't match one of Sequence 0's terms, which means it is not part of the set of real numbers we've created. This means it's impossible to create a set of all the real numbers or to put them in one-to-one correspondence with the natural numbers. This is an even bigger infinity than that of aleph-null. This, my friends, is the continuum. The continuum is the name given to the set of all real numbers, but just how much more infinite is it than aleph-null? As far as Georg Cantor was concerned, there were no sets with a cardinality between that of the set of natural numbers and the set of real numbers. In other words, if the natural numbers were aleph-null, then all the real numbers could be was aleph-one. First proposed in 1877, this became known as the continuum hypothesis...and 134 years later, mathematicians are still trying to figure out whether it's true or not.

  To Aleph-Null And Beyond
Either way, we know we've got aleph-null and (at least) aleph-one, and while they're both infinite, the latter is considerably more infinite than the former. But are those theonly infinities? Can we go still further to aleph-two, aleph-three, and so on and so forth? It is indeed possible to take things further, and all we need is one more concept: power sets. A power set for any number N is the set of all the subsets of set N. That sounds horribly confusing, so let's use a real example. Say you want to figure out the power set for set 3, or {1, 2, 3}. The power set will include all possible subsets: the three-element set {1, 2, 3}; the two-element sets {1, 2}, {1, 3}, and {2, 3}; the one-element sets {1}, {2}, and {3}; and the zero-element set {}. That's a total of 8 subsets, or 2^3 subsets in the power set of 3, and indeed all power sets for any number N will contain 2^N terms. Using the same basic logic as Cantor's diagonal argument (although it's not nearly as straightforward, which is saying something), it's possible to demonstrate that the cardinality a power set for any term X will always be greater than that of a set with X terms. This means that if we take the set of all real numbers - or aleph-one - then the power set of aleph-one will have a greater cardinality, which means it must at least be aleph-two. We can keep doing this forever, with the power set of aleph-two giving us aleph-three, the power set of aleph-three giving us aleph-four, and so on. And here's the really weird part. Since you can repeat the power set operation an infinite number of times, it stands to reason that there must eventually be an aleph-infinity...or, perhaps more accurately, and aleph-aleph-null. And even that might still pale in comparison to Georg Cantor's notion of an absolute infinite that transcended all attempts to express infinity within set theory. For his part, Cantor suspected that the absolute infinite was God. As you might imagine, there's been some disagreement on that point.

No comments:

Post a Comment