The Infinite and the Unknowable ------------------------------- Birth and death bound our lives on one side and the other. Whatever we might accomplish, we must do so in finite time, a fact that presses upon nearly everyone's psyche, especially with advancing age. On the other hand, each of us arrives in a world already populated and most live long enough to survive the passing of others, near or far. Combining this experience with the supposition that a world does exist outside any one individual's personal consciousness, most people reason that time extends back before their birth and continues far beyond their death. In other words, we extrapolate from our limited experience to the concept of eternity, we contemplate time-scales that stretch beyond those of human lives, we consider the life of the universe itself. From such contemplation arises profound questions: did the universe (or even time itself) have a beginning? will it ever end? What we can ask about time, we can also ask about space: does it extend infinitely, like a plane or close off like a sphere? Such questions have humanistic resonances. The world's religions speak to these matters in a variety of ways. Philosophers attempt to clarify the questions, if not actually to answer them. Poets and artists sometimes engage the incomprehensibly infinite in the struggle to render it more comprehensible, and sometime merely invoke it for its distinctive emotional resonance. Cosmologists use tools from theoretical physics to search for empirical answers to these basic questions. Backwards extrapolation from the motion and distribution of the galaxies leads to theories of the origin of the universe, like the Big Bang. Extrapolation so far beyond the realm of daily experience requires delicate mathematical models to aid our thinking, lest we carelessly limit the possibilities by slipping in unproved suppositions. Consider this example: every human being you know has a human mother. Extrapolating backward suggests an infinite chain of mothers stretching as far back in time as one might choose to go. The paleontological record contradicts this because it places the origins of the human race no further back than 5,000,000 years. Indeed some human must not have had a human mother, in contrast to our daily experience. The conceptual pratfalls multiply with the time-scale. How Mathematicians Approach the Infinite ---------------------------------------- If you started counting from the moment of your birth, counted very fast, say three numbers per second, never did anything else and lived to age 148, you would reach the number 14 billion, more or less. One of today's fastest available PCs could reach the 14 quintillion mark in a thousand years. Even so, few people would argue that the counting process ever reaches a logical end. Given any particular number, adding 1 produces a slightly number and the process continues. Nevertheless, a big step separates the mere recognition that the counting process has no logical termination from the decision to treat the total potential production of the counting process as a completed mathematical object. Indeed there exist (a few) mathematicians and philosophers of mathematics who call themselves "strict finitists" and who refuse to take this step. They don't reject the existence any particular number as too large (though some ask whether numbers like 10 to the power 10 to the power 10 to the power 10 really have any meaning), but they refuse to recognize a unique set which collects all possible numbers. One might think of strict finitists as mathematical agorophobics who refuse to leave the safety of finite numbers and venture out into the larger mathematical universe; alternatively you might compare them to that breed of mountain climbers who don't attempt the most difficult peaks, but stake their reputations on climbing smaller mountains without any sophisticated equipment. The history runs something like this. The infinite made a spectacular debut in mathematics with the invention of the calculus 300 years ago. Mathematicians used infinitely large and infinitely small quantities to obtain spectacular solutions to difficult problems before they developed careful rules for manipulating infinities. They also made spectacular mistakes and the infinite thereby earned a reputation as dangerous. Mathematicians gradually decided to ban the infinite. The year 1821 saw the publications of Augustin Louis Cauchy's _Cours d'analyse de l'Ecole Polytechnique_, a treatment of calculus solely in terms of finite quantities where the infinite occurs only as a figure of speech. Come the year 1874, mathematician Georg Cantor generated heated controversy by proposing a rigorous mathematical theory of infinite sets. The elaboration of Cantor's ideas becomes a major theme of mathematics in the 20th century. Nowadays Cauchy's ingenious conservatism lives side-by-side with Cantor's romantic radicalism (Cantor once said, famously, ``The essence of mathematics lies in its freedom!'') in current mathematical practice. A century or more has shown how each approach has its uses, indeed how naturally they fit together to form the subdiscipline of mathematics we now know as analysis. Introduction to Cantor's Theory of the Infinite ----------------------------------------------- Until Cantor, mathematical objects came in two forms, the numerical (numbers of various sorts, functions, algebraic expressions) and the geometrical. Cantor proposes the consideration of much more general entities we call sets (_Menge_ in the original German). By a set, Cantor meant any collection of objects of the world or the imagination (including other sets). The consideration of sets allowed Cantor to develop a theory of the infinite from first principles, uncontaminated with preexisting concepts of number. The concept of bijection lies at the heart of the story. In this course we have seen how bijections can show us the equality of two finite quantities defined in seemingly unrelated ways. The bijective approach involves no counting and so doesn't depend on any concept of number. Instead of counting, a bijection manipulates objects directly, matches up elements of one set with another. Indeed, one may even imagines that bijective approach historically predates the invention of counting. Cantor proposes extending the bijective method to the infinite in a straightforward way. To say that two sets A and B have the same size will mean that there exists a bijection which matches up the elements of A with the elements of B. Now if you've never heard this story before and you try to guess the end, you might jump to the following conclusion: two finite sets have the same size (in the sense of the previous paragraph) exactly when they have the same count, meaning the same number of elements; two infinite sets always have the same size since infinite ought to mean you never run out of elements from either as you match things up. This intuition turns out wrong. Cantor had the outstanding insight that infinite sets could come in various sizes. (Caution: up to this point in our discussion, two sets either have the same size or different sizes; we have yet to introduce notions of ``bigger'' or ``smaller''.) Cantor invented his famous ``diagonal method'' to show that two of the most familiar objects of mathematics, the set {1, 2, 3,...} of positive counting numbers and the set of decimal numbers could not possibly have the same size. Cantor's diagonal method works as follows: if you bring Cantor a matching that pairs of every counting number with a decimal number, Cantor will construct an unpaired decimal number. (In particular, if you claim you've paired off all the counting numbers and _all_ the decimals, Cantor will show you your mistake.) We show how Cantor does this by means of an example: Suppose you come to Cantor with a bijection which begins: 1 <-----> .056758914230014023040... 2 <-----> .450450564503645056401... 3 <-----> .794304256425264526456... 4 <-----> .912734261726145236145... 5 <-----> .145614256147504123413... 6 <-----> .456917462147803145614... 7 <-----> .953987543987543209543... 8 <-----> .935702087542987547387... 9 <-----> .108576307502348572058... 10 <-----> .354507385703487530482... . . . . . . Cantor first assembles a new number by going down the diagonal: \ \| - 1 <-----> . 0 56758914230014023040... 2 <-----> .4 5 0450564503645056401... 3 <-----> .79 4 304256425264526456... 4 <-----> .912 7 34261726145236145... 5 <-----> .1456 1 4256147504123413... 6 <-----> .45691 7 462147803145614... 7 <-----> .953987 5 43987543209543... 8 <-----> .9357020 8 7542987547387... 9 <-----> .10857630 7 502348572058... 10 <-----> .354507385 7 03487530482... . . . . . . in this getting x=.0547175877... . In words: the 1st digit of x equals the 1st digit of the number matched with 1; the 2nd digit of x equals the 2nd digit of the number matched with 2; the 3rd digit of x equals the 3rd digit of the number matched with 3; . . . the nth digit of x equals the nth digit of the number matched with n; . . . Now Cantor produces (any) new number _none_ of whose digits match the digits of x. One (among very many!) ways to do this consists of changing, say, every 7 to a 3 and every other number to a 7. This gives y=.7773737733... Now you cannot possibly have y matched up to any counting number because: the 1st digit of y disagrees with the 1st digit of the number matched with 1; the 2nd digit of y disagrees with the 2nd digit of the number matched with 2; the 3rd digit of y disagrees with the 3rd digit of the number matched with 3; . . . the nth digit of y disagrees with the nth digit of the number matched with n; . . . Notes: 1) The argument above slid over one technical point: we can write some numbers as decimals in two ways, for example, .1000000...= .09999999..., even though NONE of their digits agree. For this to happen, one of the numbers must end in an unending string of 9's. The number y will never have this form, and we can make sure never to use this form when we present the original bijection. 2) The same argument shows that we also can't match all the decimals with any subset of the natural numbers. Since we can easily match the counting numbers with a subset of the decimals, this leads us to say that the infinity of decimals exceeds the infinity of counting numbers. It turns out (by a tricky procedure) that given matchings between each of two sets A and B and some _subset_ of the other, we can match up A and B on the nose. This gives us the confidence to call the size of B greater than or equal to the size of A when we can match A up with a subset of B. A Variation on the Diagonal Argument ------------------------------------ Given any set X , write P(X) for the power set of X , meaning the set of all subsets of X . Cantor proved that the size of P(X) always exceeds the size of X . Think of X as a set of men. To think of P(X) as a set of women, assume each woman holds a list of some subset of the men in X. No two woman shall hold lists with exactly the same men, and for every subset of the men in X, some woman holds a list naming just exactly those men. Now assume you have a way to marry up in pairs all the men and all the women. Cantor reasons that, considering any particular a couple, either the man appears on his wife's list or he doesn't. So Cantor sets Y equal the set containing every man NOT on the list held by his wife. By assumption, exactly one woman, call her w , has a list which contains exactly the men in set Y . Say you have w married to m . Now Cantor asks the question, does m appear on w's list? If no, then m does belong to set Y, so m does appear on w's list, so yes. If yes, then m does not belong to set Y, so m does NOT appear on w's list, so no. In short, if yes, then no; if no, then yes. Coming to an absurdity means we made a false assumption. So we must reject the assumption that you had a way to marry up all the men and women. Note: Why, you might ask, does this argument count as a variation of the diagonal argument? We can write some decimals with just the digits 0 and 1, for example, .101010001010100110101001000... The original diagonal argument works just fine to show that even this RESTRICTED set of decimals outnumbers the counting numbers (except here we change 0's to 1's and 1's to 0's). But a decimal like .101010001010100110101001000... encodes a set of natural numbers, namely the set of places holding a 1; in this instance we'll get {1,3,5,9,11,13,16,17,19,21,24,...} Now you can see that with this little modification, the original argument and the variation have exactly the same mathematical content. The original argument showed only that infinities might come in at least two different sizes, but the variation says much more. Start with any infinite set X, for example the set of counting numbers. Then each of the sets X, P(X), P(P(X)), P(P(P(X))), P(P(P(P(X)))), P(P(P(P(P(X))))), ... exceeds the size of the previous set. Thus we have infinities coming in infinitely many sizes. The union, call it X', of all these sets exceeds the size of any of them, and then we can begin the process afresh. Cantor invented a nomenclature to keep track of all the infinities that come about by taking unions and power sets, but we shall not attempt to explain it here. Between the counting numbers and the real numbers ------------------------------------------------- Cantor asked whether any set could have a size INTERMEDIATE between the size of the natural numbers and the size of the real numbers. To this day, no one knows. We refer to the statement that every infinite subset of the reals has the same size as the reals or the same size as the counting numbers as CANTOR'S CONTINUUM HYPOTHESIS. In 1964, Paul Cohen demonstrated that a resolution of the Continuum Hypothesis question falls outside all the implications of all the standard axioms of set theory. This leaves mathematicians in an awkward situation. Looking for proofs in the usual way will never answer Cantor's question. Since Cantor's question itself certainly has no OBVIOUS answer, the only hope of resolving it lies in discovering some fundamental and fundamentally new OBVIOUSLY true fact about sets which, when we add it to our list of standard axioms, leads to a proof or disproof. You might think of the rational numbers as one candidate for an intermediate infinity. After all, they contain the counting numbers yet fill out the real line (infinitely many rationals occur between every two reals). Cantor shows that the set of all rational numbers has the same size as the set of all counting numbers. Recall that we can write all rational numbers as fractions with integer numerators and (non-zero) integer denominators. So let's make a list. First, the rationals where the maximum of the absolute value of numerator and denominator equals 1: -1 -1 0 0 1 1 - - - - - - -1 1 -1 1 -1 1 Next, the rationals where the maximum of the absolute value of numerator and denominator equals 2: -2 -2 -2 -2 -1 -1 0 0 1 1 2 2 2 2 - - - - - - - - - - - - - - -2 -1 1 2 -2 2 -2 2 -2 2 -2 -1 1 2 Next, the rationals where the maximum of the absolute value of numerator and denominator equals 3: -3 -3 -3 -3 -3 -3 -2 -2 -1 -1 0 0 1 1 2 2 3 3 3 3 3 3 - - - - - - - - - - - - - - - - - - - - - - -3 -2 -1 1 2 3 -3 3 -3 3 -3 3 -3 3 -3 3 -3 -2 -1 1 2 3 Continuing this process, we'll eventually get every possible fraction. Now two different fractions might equal the same rational number, so now let's make a new list by deleting from the old list every number equal to a previous number. The following fractions remain: -1 -1 0 -2 -2 -1 -1 -3 -3 -3 -3 -2 -2 -1 -1 - - - - - - - - - - - - - - - ... -1 1 -1 -1 1 -2 2 -2 -1 1 2 -3 3 -3 3 Now this list will contain every rational number exactly once. Now we can easily match them up with counting numbers: 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 ... ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ ^ | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | v v v v v v v v v v v v v v v -1 -1 0 -2 -2 -1 -1 -3 -3 -3 -3 -2 -2 -1 -1 - - - - - - - - - - - - - - - ... -1 1 -1 -1 1 -2 2 -2 -1 1 2 -3 3 -3 3 Other uses of the diagonal argument ----------------------------------- The diagonal argument has proved very fertile and several major developments in other parts of 20th century mathematics depend on arguments of a similar form. Nowadays we often use computers to help us do mathematics. As far back as the 1930's, British mathematician Alan Turing considered the following question: could a single computer have the power, in principle, to correctly answer all the questions of mathematics? Phrased like that, the question may seem a bit vague. What, after all, should count as a mathematical question. But Turing answered the question with a definitive NO even if we restrict ourselves a rather special class of seemingly tame mathematical questions. Turing's result has aroused considerable interest in the humanities. Various philosophers ponder the nature of truth, the limits of human reason and status of human consciousness. Turing's theorem suggests that certain mathematical truths may lie beyond the reach of reason. Leaving philosophers to debate the ultimate relevance of Turing's theorem, let us now turn to the result itself. Think back to a time when computers cost more than any individual could pay, when a large university might own just one and users across campus would share time on it, when computer time might carried a price tag of hundreds of dollars for a second of CPU time. Even in those days student learned how to program by writing small programs and testing them out. Now sometimes a poorly written program does lots of computation but never produces any result -- the wheels spin but nothing goes anywhere. One says of such a program that it contains an infinite loop. In those days infinite loops made for bad news -- they could ring up a big bill for computer time without producing anything of value, or anything at all for that matter. Clearly one needed a way the prescreen programs, to decide, before running the programs, whether or not they would ever stop. Now let's restrict ourselves to a narrow class of programs, namely, programs that look at some data and just answer a single yes-or-no question for us. The prescreen-for-infinite-loops program we seek would itself have such a form; the data in this case would consist of another computer program with its data. Let us call a prescreen-for-infinite-loops program a UHT, for Universal Halting Tester, since it tests whether any given program processing any given data will ever halt. Mathematicians, for their own reasons, would surely like to get their hands on a UHT. Suppose a mathematician wants to know if any finite structure has a particular property. She could write a program that searches through all possible candidate until it finds one that does. Then instead of actually running the program (which would never stop if no such structure exists) she could feed her program to the UHT, which would then print YES or NO according to whether the desired structure exists or not. But, alas, Turing shows that no UHT could possibly exist, as follows. Recall that a computer program stored in computer memory just consists of lots of 0's and 1's, so we could consider the whole program as a single long binary number. The same applies to whatever computer file holds the data. If a UHT exists then it would give correct answers even when the the program to test (as a number) equals its data (as a number). Now admittedly it hardly ever happens that the program to test (as a number) equals its data (as a number), but if we can't write a program that gives the right answers just in this weird special case, then certainly we can't write a UHT which does the job right regardless of the data. Let's write URHT for Universal Reflexive Halting Tester - program designed to tell us if another program halts when that other program reads itself as its data. We shall show that even URHTs don't exist. Suppose they did. Then somewhere in the program we could find a statement that prints YES to tell us that, yes indeed, the input program, reading itself as data, does stop. Now let's do a strange thing, lets damage the URHT. Let's replace the statement that prints YES with an infinite loop that does nothing. (In practice this turns out an easy thing to do; if you've never programmed a computer of any sort, just take this on faith.) So let's write DURHT for a Damaged Universal Reflexive Halting Tester. Feed a DURHT a program which halts when it treats itself as its a data and a DURHT falls into an infinite loop; feed a DURHT a program which never halts when it treats itself as its a data and a DURHT prints NO and halts. If URHTs exist then DURHTs exist. So if no DURHT exists, no URHT exists either. Now we'll finish by explaining why no DURHT exists. So suppose we have a DURHT. Then, in particular, we can feed the DURHT to the DURHT. What would happen? Lets think this through: first consider what would happen if we fed the DURHT to the undamaged URHT. The URHT would tell us yes-or-no, whether or not the DURHT (reading DURHT as data) would ever halt. Now if the URHT would have printed YES (mean DURHT reading DURHT as data halts), the DURHT (reading DURHT) must, by design, fall into an infinite loop. On the other hand if the URHT would have printed NO (mean DURHT reading DURHT as data never halts), the DURHT (reading DURHT) just prints NO and halts. Do if DURHT reading DURHT halts, it doesn't. If it doesn't, it does. Since that makes no sense, DURHT don't exist, so neither do URHTs or UHTs. (It should take you several passes to sort out what just happened. Persist!) Now lets consider an important implication of Turing's theorem for mathematics. A mathematician who didn't know Turing's theorem might try to create a UHT as follows. She might try to assemble a list of axioms about the ways in which computer programs behave. Then she would write a program that used symbolic logic to enumerate all the logical consequences of her axioms. Her program, given a particular program with particular input data, would search until it found either a proof that it halts or a proof that it doesn't. Turing's theorem says this approach MUST fail. That means that if we start with any finite set of true axioms about the behavior of computers, there exists some statement of the form ``such-and-such a program reading such-and-such data halts'' that we can neither prove nor disprove. Since programs and data amount just to numbers interpreted in various ways, what the previous paragraph says about reasoning about programs applies equally well ot reasoning about numbers: no finite set of axioms forms the basis for deciding the truth of all the statements of arithmetic. The discovery of this startling statement belongs to mathematician Kurt Goedel, a contemporary of Turing, who came to it by quite a different path.