A theorem about infinite sequences of numbers

Theorem.  An infinite sequence of (real) numbers contains an infinite monotonic subsequence. (End of Theorem.)

Proof.  Let the sequence be x(i: 0 i). Element x(i) is "dominant" means (A j: i+1 j: x(i) x(j)). We distinguish two cases.

The number of dominant elements is infinite.  In this case the dominant elements form an infinite subsequence, which is monotonic (viz. descending).

The number of dominant elements is finite.  In this case an N exists such that from x(N) onwards, no dominant element occurs, i.e. (A i: i N: (E j: i+1 j: x(i) < x(j))). Hence each x(i) with i N is the starting element of an infinite subsequence that is increasing, and therefore monotonic.

(End of Proof.)

I found this proof last Sunday evening; the day before I had heard the theorem together with the rumour that it might require a fancy proof. Quod non.

Plataanstraat 5
The Netherlands
16 August 1982
prof.dr. Edsger W. Dijkstra
Burroughs Research Fellow

Transcriber: Kevin Hely.
Last revised on Thu, 19 Jun 2003.