I saw the angel in the marble
and carved until I set him free
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?
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 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.
We start with the (quantitative) version for finite sequences, which we'll call 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.
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?
*