*I saw the angel in the marble*

*and carved until I set him free*

This fine apocryphal Michelangelo quote has been improved to the point of giving a simple recipe to make a marble David:

*Chip away everything that doesn't look like David.*These fake quotes express the idea that the highly finished result was already virtually present in the raw material and only needed an artist's hand to get exposed. It's a small step from art to mathematics, and we'll give two recipes to expose the*order*virtually present in apparent*chaos*.Whereas the entropy theorems of probability and mathematical physics imply that, in a large universe, disorder is probable, certain combinatorial theorems show thatcomplete disorder is impossible.(p.244)

The very first really surprising theorem in any calculus course is an illustration of this principle:

*from any sequence of real numbers you can chip away terms until you are left with a monotone sequence.*To see how unexpected this is, think of the sequence
sin(1), sin(2), sin(3),...

rising and falling along the sine curve, or of a sequence produced by a random generator.

We start with the (quantitative) version for finite sequences, which we'll call

An example may be useful.

The lowest non-trivial case has n=2:

The

*lists*. The longer the list, the longer the monotone sublist hidden in it! Here it comes, definitions included.An example may be useful.

The lowest non-trivial case has n=2:

*any list of 5 terms contains a monotone sublist of 3*. Less than 5 terms will not do, as shown by the list (2,1,4,3) which does not contain any monotone sublist of 3.The

*infinite*version is the one met in calculus. We also include the definitions.Note that for the infinite case we don't have an effective procedure; it's a typical

*existence*theorem.

To return to Michelangelo: he knew beforehand what would come out of his marble after enough chipping. But we, poor mathematicians! We know we will end up with a

*monotone*list or sequence, but we are unable to decide beforehand what it will be: increasing or decreasing! Frustrating, no?

*