Доказать, что всякая последовательность на прямой невозрастающую или неубывающую подпоследовательность

задан 11 Июл 3:07

10|600 символов нужно символов осталось
1

Эта задача по сути скорее логическая, или комбинаторная.

Рассмотрим граф, множество вершин которого есть $%\mathbb N$%. Пусть $%m < n$%. Если $%x_m\le x_n$%, то вершины $%m$% и $%n$% соединяем ребром красного цвета. В противном случае, то есть при $%x_m > x_n$%, ребро раскрашиваем в синий цвет.

Бесконечная теорема Рамсея утверждает, что найдётся бесконечное подмножество вершин, любые две из которых соединены ребром одного и того же цвета. Если это красный цвет, но нумеруем вершины множества в порядке возрастания, и члены с этими номерами дают неубывающую последовательность. Если это синий цвет, то аналогично получаем (строго) убывающую подпоследовательность.

Напомним доказательство этой известной теоремы. Рассмотрим первую вершину и её соединения с вершинами, имеющими большие номера. Среди них бесконечно много рёбер одного цвета -- красного или синего. Отбираем эти соединения, а все остальные не рассматриваем. Вершине сопоставляем красный или синий цвет в зависимости от цвета этих соединений.

Первая вершина соединена одним и тем же цветов с вершинами, которым дадим новые номера 2, 3, ... . Рассмотрим вершину 2 и её соединения с вершинами 3, 4, ... . Среди них опять имеется бесконечно много соединений одного цвета. Их оставляем, остальные вершины удаляем. Вершине 2 сопоставляем цвет этих соединений. И так далее.

В итоге у нас получается бесконечно много вершин, каждой из которых сопоставлен красный или синий цвет. Ясно, что хотя бы один из цветов встречается бесконечно много раз. Отбираем эти вершины, и они дают нам искомое бесконечное множество. Для определённости, пусть это красный цвет. Тогда по построению, каждая из отобранных вершин, будучи "красной", соединена рёбрами красного цвета со всеми последующими.

ссылка

отвечен 11 Июл 3:57

10|600 символов нужно символов осталось
1

Можно дать и "анализное" доказательство (правда, оно использует полноту, а утверждение верно для упорядоченного множества). Если последовательность не ограничена, то из нее можно выделить подпоследовательность, сходящуюся к + или - бесконечности. Из такой подпоследовательности монотонная подпоследовательность выделяется совсем легко.

Если же последовательность ограничена, то она содержит сходящуюся подпоследовательность, и тут возникают варианты:

  1. Если в подпоследовательности конечное число членов, то с какого-то момента она стационарна, и все доказано;
  2. Иначе она содержит бесконечное число членов, а значит их бесконечное количество хотя бы с одной стороны от предельной точки, например слева. Беря окрестности радиуса $%1/n$% берем номер $%k_n > k_{n-1}$%, что $%a_{k_n} > a_{k_{n-1}}$%
ссылка

отвечен 11 Июл 11:06

@no_exception: помнится, какой-то вопрос на эту тему уже был -- или похожий, или даже в точности этот. И там доказательство было приведено рамках анализа. А тут я как-то посмотрел "свежим взглядом", и увидел теорему Рамсея.

(11 Июл 15:41) falcao

@falcao, ваше доказательство хорошо тем, что оно совершенно не использует полноту, а только упорядоченность :) Так что задача может быть обобщена

(11 Июл 16:43) no_exception
10|600 символов нужно символов осталось
Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×2,707

задан
11 Июл 3:07

показан
93 раза

обновлен
11 Июл 16:43

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru