cantors-attic

Climb into Cantor’s Attic, where you will find infinities large and small. We aim to provide a comprehensive resource of information about all notions of mathematical infinity.

View the Project on GitHub neugierde/cantors-attic

Quick navigation
The upper attic
The middle attic
The lower attic
The parlour
The playroom
The library
The cellar

Sources
Cantor's Attic (original site)
Joel David Hamkins blog post about the Attic
Latest working snapshot at the wayback machine

The playroom

Tate Slides, photo by Tom Jenkins

Here in the playroom, you will find a variety of stimulating entertainments.

Hilbert’s Grand Hotel

Diary of Tristram Shandy

On the number of possible finite books

Let us define, in precise mathematical style, that a book is a finite sequence of pages, the first containing the title of the book and the author’s name, and the subsequent pages each containing a finite sequence of text, written in a normal size with a normal font, with margins at the side and a page number at the bottom. Let us suppose there is no funny business with these books, with increasingly small text, for example: each page consists of at most 50 lines, with each line consisting of at most 100 characters (from the ASCII character set, say), and there are margins at all four sides and the page numbers, written in the usual decimal manner, start at 1 and increment by 1 with each page. In short, a normal book.

How many books are there? It may seem at first that there should be infinitely many possible books, since we would have the book consisting entirely of the letter A, repeated endlessly to any desired length, and the book with B, and so on, of any desired length.

But further thought will reveal that that in fact, there are only finitely many possible books. The reason is that it is not actually possible to have arbitrarily long books that obey the requirements set out. This is because once the book becomes very long, the page numbers become larger and larger, using up more and more of the available space, just for the page number. Eventually, the entire page is filled just with the page number, with no room for additional text. Indeed, eventually, the page number is too large to fit, and the book must end. So there is a finite bound of the length of a book, and thus only finitely many books altogether.

Supertasks

A supertask is a task involving infinitely many steps, and many of the other entries on this page can be classified as supertasks.

Zeno’s paradox

Perhaps Zeno of Elea (ca. 450 B.C.) was the first to grapple with the supertask concept in his famous paradoxical argument, now known as Zeno’s paradox, that it is impossible to go from here to there. Before arriving, one must first get halfway there, and before that one must get halfway to the halfway point, and so on, ad infinitum. Because one cannot accomplish these infinitely many tasks, Zeno argued, all motion is impossible. Thus, he takes the impossibility of completing a supertask as the foundation of his reductio.

Thomson’s lamp

In the twentieth century philosophical literature, the puzzles and paradoxes continue. Take Thomson’s lamp (Thomson 1954), for example, which is on for $1/2$ minute, off for $1/4$ minute, on for $1/8$ minute, and so on. After one minute (the sum of the series $1/2+1/4+1/8+\cdots$), is it on or off? The literature is full of answers. Another toy example is the super-$\pi$ machine, which writes out the successive digits of $\pi$ on a tape, the first in $1/2$ minute, the next in $1/4$ minute, and so on, so that all the digits are written in a finite amount of time. Because there can be no last or final step in such a process, Chihara (1965) has criticized the completion of such an algorithm as unintelligible.

Deal with the devil

In a more entertaining example, let’s suppose that you have infinitely many one dollar bills (numbered 1, 3, 5, $\ldots$) and upon entering a nefarious underground bar, you come upon the Devil sitting at a table piled high with money. You sit down, and the Devil explains to you that he has an attachment to your particular bills and is willing to pay you a premium to buy them from you. Specifically, he is willing to pay two dollars for each of your one-dollar bills. To carry out the exchange, he proposes an infinite series of transactions, in each of which he will hand over to you two dollars and take from you one dollar. The first transaction will take $1/2$ hour, the second $1/4$ hour, the third $1/8$ hour, and so on, so that after one hour the entire exchange will be complete. The Devil takes a sip of whiskey while you mull it over; should you accept his proposal? Perhaps you think you will become richer, or perhaps you think with infinitely many bills it will make no difference? At the very least, you think, it will do no harm, and so the contract is signed and the procedure begins. How could the deal harm you?

It appears initially that you have made a good bargain, because at every step of the transaction, he pays you two dollars and you give up only one. The Devil is very particular, however, about the order in which the bills are exchanged. The contract stipulates that in each sub-transaction he buys from you your lowest-numbered bill and pays you with higher-numbered bills. Thus, on the first transaction he accepts from you bill number 1, and pays you with bills numbered 2 and 4. On the next transaction he buys from you bill number 2 (which he had just paid you) and gives you bills numbered 6 and 8. Next, he buys bill number 3 from you with bills 10 and 12, and so on. When all the exchanges are completed, what do you discover? You have no money left at all! The reason is that at the $n^{\rm th}$ exchange, the Devil took from you bill number $n$, and never subsequently returned it to you. So while it seemed as though you were becoming no poorer with each exchange, in fact the final destination of every dollar bill in the transaction is under the Devil’s ownership. The Devil is a shrewd banker, and you should have paid more attention to the details of the supertask transaction to which you agreed. And similarly, the point is that when we design supertask algorithms to solve mathematical questions, we must take care not to make inadvertent assumptions about what may be true only for finite algorithms.

Supertasks in physics

Supertasks have also been studied by the physicists. In classical mechanics under the Newtonian gravity law (neglecting relativity), it is possible to arrange finitely many stars in orbiting pairs, each pair orbiting the common center of mass of all the pairs, and a single tiny moon racing faster around, squeezing just so between the dual stars so as to pick up speed with every such transaction. Assuming point masses (or collapsing stars to avoid collision), the arrangement can be made to lead by Newton’s law of gravitation to infinitely many revolutions in finite time.

Other supertasks reveal apparent violations of the conservation of energy in Newtonian physics: imagine infinitely many billiard balls of successively diminishing size, converging to a point (see Laraudogoitia 1996). The balls are initially at rest, but then the first is set rolling. It collides with the next, transferring all its energy, and that ball begins to roll. Each ball in turn collides with the next, transferring all its energy. Because of the physical arrangements of the system, the motion disappears in a sense into the singularity; after a finite amount of time all the collisions have taken place, and the balls are at rest. So we have described a physical process in which energy is conserved at each step, in every interaction, but not overall through time.

Another arrangement has the balls spaced further and further out to infinity, pushing the singularity out to the point at infinity. The first ball knocks the second, which sends the next flying, and so on out to infinity. If the balls speed up sufficiently fast, under Newtonian rules it can be arranged that all the motion is completed in a finite amount of time. The interesting thing about this example and the previous one is that time-symmetry allows them to run in reverse, with static configurations of balls suddenly coming into motion without violating conservation of energy in any interaction.

More computationally significant supertasks have been proposed by physicists in the context of relativity theory (Pitowsky 1990, Earman 1995, Earman, et. al. 1993, Hogarth 1992, Hogarth 1994). Suppose that you want to know the answer to some number theoretic conjecture, such as whether there are additional Fermat primes (primes of the form $2^{2^n}

With more complicated arrangements of rockets flying around rockets, one can solve more complicated number theoretic questions. Hogarth (1994) has explained how to determine in this way the truth of any arithmetic statement. More unusual relativistic Malament-Hogarth spacetimes can be (mathematically) constructed to avoid the unpleasantness of unbounded acceleration required in these rocket examples (see also Hogarth 1992, Pitowsky 1990).

These computational examples speak to a widely held strengthening of Church’s thesis, namely, the view that the classical theory of computability has correctly captured the notion of what it means to be effectively computable. Because the relativistic rocket examples provide algorithms for computing functions, such as the halting problem, that are not computable by Turing machines, one can view them as refuting this thesis. Supporters of this view emphasize that when thinking about what is in principle computable, we must attend to the computational power available to us as a consequence of the fact that we live in a relativistic or quantum-mechanical universe. To ignore this power is to pretend that we live in a Newtonian world.

Library of Babel

[libraryofbabel.info]

Ross-Littlewood paradox

Metagame

Several of the sections above contained material from (Hamkins, 2002).

References

  1. Hamkins, J. D. (2002). Infinite time Turing machines. Minds and Machines, 12(4), 521–539. http://boolesrings.org/hamkins/turing-mm/
Main library