Die Fallunterscheidung muss bei der Menge M ansetzen.
Fall 1: M ist leer.
Fall 2: M ist endlich, aber nicht leer.
Fall 3: M ist unendlich.

Zum Fall 1: Wenn M leer ist, dann gibt es kein \(n\in\mathbb{N}\), so dass für alle \(k\in\mathbb{N}\) gilt: \(a_n \ge a_{n+k}\).
Anders ausgedrückt: Für alle \(n\in\mathbb{N}\) gibt es ein \(k\in\mathbb{N}\), so dass: \(a_n < a_{n+k}\).
Dann setze ich \(n_0=1\).
Dann gibt es ein k, so dass \(a_{n_0} < a_{n_0+k}\). Dann nehme ich so ein k und setze \(n_1=n_0+k\). Es gilt nun \(a_{n_0} < a_{n_1}\).
Dann gibt es ein anderes k, so dass \(a_{n_1} < a_{n_1+k}\). Dann nehme ich so ein k und setze \(n_2=n_1+k\). Es gilt nun \(a_{n_1} < a_{n_2}\).
etc.
So erhalte ich eine monoton steigende Teilfolge.

Zum Fall 2: Hier nehme man das größte Element von M. Nennen wir es m.
Dann nehme ich die Teilfolge \(a_{m+1},\,a_{m+2}, \ldots \). Diese Folge fällt unter Fall 1.

Zum Fall 3: Die Elemente von M, aufsteigend sortiert, liefert mir die \(n_k\). Ich erhalte eine monoton fallende Teilfolge.