Order out of chaos

 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. 

In this (also here) paper from 1967, the mathematician Theodore Motzkin remarked 

Whereas the entropy theorems of probability and mathematical physics imply that, in a large universe, disorder is probable, certain combinatorial theorems show that complete 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.

Here, in three pages, a proof that any sequence, finite or infinite, contains a monotone subsequence.

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?

*