Принцип крайнего

Рассмотрим последовательность чисел Пусть — длина наибольшей возрастающей цепочки с началом в а — длина наибольшей убывающей цепочки с началом в Докажем, что или Заметим, что не существует таких что и (то есть хотя бы одна из компонент при отличается). Предположим, что нашлись такие различные и для которых и Предположим, что Но тогда есть цепочка с началом в длины В эту цепочку можно добавить и получить цепочку с началом в длины что противоречит определению Аналогичное противоречие получается в случае Если теперь для любых было верно, что и то различных пар всего не может быть более, чем Но чисел значит, для каких-то получаем и — противоречие.