Пусть есть счётное множество $%A$%, множество $%k$%-элементных подмножеств которого разбито на конечное число классов эвкивалентности. Доказать, что найдётся счётное $%B\subset A,$% все $%k$%-элементные подмножества которого попадут в один класс.

Если число классов равно 1, задача очевидна. Если $%k=1,$% тоже очевидно. Я пробовал индукцией, но что-то не вышло...

задан 27 Ноя '13 21:32

изменен 27 Ноя '13 23:31

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

Это бесконечная теорема Рамсея. Её можно вывести из обычной теоремы Рамсея при помощи средств типа леммы Кёнига. Но можно провести автономное доказательство для бесконечного варианта, проводя индукцию по $%k$%. Случай $%k=1$% очевиден, и пусть теперь $%k\ge2$%, где для раскраски подмножеств мощности $%k-1$% утверждение считается доказанным. Положим $%A_0=A$%, $%a_0\in A_0$% -- произвольный элемент. Раскраска $%k$%-элементных подмножеств для $%A_0$% индуцирует раскраску $%(k-1)$%-элементных подмножеств для $%A_0\setminus\{a_0\}$%: цветом такого подмножества будем считать заданный исходной раскраской цвет подмножества, получаемого добавлением элемента $%a_0$%. По предположению индукции, $%A_0$% обладает бесконечным однородным подмножеством $%A_1$%, то есть все его $%(k-1)$%-элементные подмножества одноцветны. В этом множестве отмечаем элемент $%a_1$% произвольным способом, и далее производим ту же операцию с раскраской $%(k-1)$%-элементных подмножеств для $%A_1\setminus\{a_1\}$%. Этот процесс продолжается до бесконечности, и все участвующие в нём множества $%A_n$% ($%n\ge0$%) бесконечны, и в каждом из них мы выбрали какой-то элемент $%a_n\in A_n$%.

Свяжем с каждым элементом $%a_n$% один из $%k$% цветов -- это тот цвет, для которого мы выбирали однородное подмножество $%A_{n+1}\subseteq A_n\setminus\{a_n\}$%. Теперь в бесконечной последовательности элементов $%a_0$%, $%a_1$%, ... (все они по построению попарно различны) выберем бесконечную подпоследовательность элементов, которым по описанному выше правилу ставится в соответствие один и тот же цвет. Утверждается, что именно в этот цвет будут окрашены (при изначальной раскраске) все $%k$%-элементные подмножества, образованные элементами выбранной подпоследовательности (то есть множество её элементов и будет искомым $%B$%). Рассмотрим произвольные $%k$% элементов $%b_1$%, ..., $%b_k$%, идущих в подпоследовательности именно в этом порядке. При этом $%b_1=a_n$% для некоторого $%n$%, а все остальные элементы в количестве $%k-1$% принадлежат как $%A_n\setminus\{a_n\}$%, так и его однородному подмножеству $%A_{n+1}$%. Этому подмножеству был сопоставлен цвет, который, во-первых, мы ставили в соответствие элементу $%a_n$%, а во-вторых, он совпадает с цветом $%k$%-элементного множества $%\{b_1,...,b_k\}$% при однородной раскраске. Это следует из построения последовательности подмножеств и их элементов: цветом $%\{b_2,...,b_k\}\subset A_n\setminus\{a_n\}$% мы как раз и объявляли "настоящий" цвет подмножества, получаемого добавлением $%a_n=b_1$%. Таким образом, $%\{b_1,...,b_k\}$% в исходной раскраске имеет тот же цвет, который мы сопоставили элементу $%a_n$%, а потому и каждому из элементов подпоследовательности. Тем самым, однородность $%B$% доказана.

ссылка

отвечен 27 Ноя '13 23:41

как, кстати, обычная формулируется?

(27 Ноя '13 23:45) trongsund

Берётся полный граф с $%N$% вершинами, все его $%k$%-элементные (вершинные) подмножества раскрашиваются в $%r$% цветов. Нас интересует однородное (понятно в каком смысле) подмножество из $%d$% элементов. Теорема утверждает, что при достаточно большом $%N=N(k,r,d)$% это возможно.

Конечный вариант, кстати, тоже можно вывести из бесконечного.

(27 Ноя '13 23:57) falcao
10|600 символов нужно символов осталось
Ваш ответ

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

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

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

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

отмечен:

×169

задан
27 Ноя '13 21:32

показан
1080 раз

обновлен
27 Ноя '13 23:58

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

по почте:

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

по RSS:

Ответы

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

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