Теорема Рамсея

[Профессор Снэйп]

Утверждение известное и широко применяемое в теории моделей. Но, может быть, кто-то захочет доказать его сам, не заглядывая в учебники. По крайней мере, в книге "Теория моделей" Чэна и Кейслера оно даётся как упражнение.

Для произвольного множества $X$ и $n \in \mathbb{N}$ пусть $[X]^n$ обозначает множество всех подмножеств множества $X$, состоящих из $n$ элементов.

Пусть $I$ --- бесконечное множество, $n,k \in \mathbb{N}$ и $[I]^n \subseteq A_1 \cup \ldots \cup A_k$. Доказать, что существуют натуральное $i$ от $1$ до $k$ и бесконечное $J \subseteq I$, такие что $[J]^n \subseteq A_i$.

[Kid Kool]

Сделаем индукцию по n.

Рассмотрим какой-нибудь элемент $x_1$ из $I$ и рассмотрим все n-элементные подмножества $I$, содержащие $x_1$. Выделим в каждом из них (n-1)-элементое подмножество (путем выкидывания $x_1$) и раскидаем их по множествам $B_i$ естественным образом. По индукционному предположению, найдется бесконечное $J \subseteq I$ и индекс $i$, такие что $[J]^{n-1} \subseteq B_i$. Покрасим $x_1$ в цвет $i$. Далее, рассматривая лишь множество $J$, покрасим $x_2$ и т.д.

В последовательности $x_i$ найдется одноцветная подпоследовательность. Она-то и будет искомой.

[Профессор Снэйп]

Что за $B_i$-ые, откуда они берутся? В условии их вроде нет.

[вздымщик Цыпа]

$X \in B_i \Leftrightarrow X \cup \{x_1\} \in A_i$. Я так понял, именно это подразумевается под «естественным образом».
Вообще, очень симпатичное доказательство. Базируется на взаимнооднозначном соответствии между $\{X\in [I]^n\,\vert\, x_1 \in X\}$ и $[I\backslash \{x_1\}]^{n-1}$.