Бесконечное частично упорядоченное множество

[Salvador]

Дано бесконечное частично упорядоченное множество. Доказать, что в нем всегда найдется либо бесконечное подмножество попарно несравнимых элементов, либо бесконечное подмножество, на котором индуцированный порядок линеен.

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

[Хорхе]

Используйте теорему Рамсея.
В частной формулировке, которая относится к этой задаче, она звучит так: для любого $n$ найдется $m(n)$ такое, что если все ребра полного графа на $m(n)$ вершинах раскрашены в два цвета, то в нем найдется одноцветный подграф на $n$ вершинах.

[Salvador]

А как отсюда следует, что найдется бесконечное подмножество попарно сравнимых/несравнимых элементов?

[Хорхе]

Salvador писал(а):

А как отсюда следует, что найдется бесконечное подмножество попарно сравнимых/несравнимых элементов?

А Вы сами подумайте, как это следует. Предположите обратное, сделайте вывод.

[Salvador]

Вот это как раз не понятно. Насколько я понимаю, из теоремы Рамсея следует только, что для любого $n$ можно найти $n$ попарно (не)сравнимых элементов. (Я, например, могу доказать, что в любом частично упорядоченном множестве из $(n-1)^2+1$ элементов найдется либо $n$ попарно сравнимых, либо $n$ попарно несравнимых элементов, откуда это тоже будет следовать.)

Если Вам не сложно, обьясните, пожалуйста, как правильно "перейти к бесконечности".

[Хорхе]

Сорри, не сразу понял, где именно загвоздка. Перейти к бесконечности можно, например, по лемме Цорна, где в качестве ч.у.м. взять либо цепи, либо антицепи (чего бесконечно много).

[Salvador]

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

[Хорхе]

Salvador писал(а):

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

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

[Salvador]

Хорхе писал(а):

Salvador писал(а):

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

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

Каким образом мы получим в результате полный подграф одного цвета, совершенно непонятно.

[AGu]

Salvador писал(а):

Дано бесконечное частично упорядоченное множество. Доказать, что в нем всегда найдется либо бесконечное подмножество попарно несравнимых элементов, либо бесконечное подмножество, на котором индуцированный порядок линеен.

Это утверждение очень походит на лемму Кёнига (о цепях в графе)
и, вроде бы, доказывается почти так же.

Пусть $(X,\leqslant)$ -- частично упорядоченное множество.

Подмножество $Y\subseteq X$ назовем цепью (соответственно коцепью) в $X$,
если любые два различных элемента $Y$ сравнимы (соответственно несравнимы) в $X$.

Предположим, что $X$ бесконечно, причем все цепи и коцепи в $X$ конечны.
Наша цель -- получить противоречие.

Для любого подмножества $Y\subseteq X$ обозначим символом $Y_\circ$
множество всех минимальных элементов $Y$,
т.е. $Y_\circ := \{y_\circ\in Y : \neg(\exists\, y\in Y)(y < y_\circ)\}$.

Условимся записывать конечность и бесконечность множества $Y$
формулами $|Y|<\infty$ и $|Y|=\infty$ соответственно.

Лемма 1. $(\forall\,Y\subseteq X)(|Y_\circ|<\infty)$.

$\triangleleft$ Достаточно заметить, что $Y_\circ$ является коцепью в $X$. $\triangleright$

Лемма 2. $(\forall\,Y\subseteq X)(\forall\, y\in Y)(\exists\,z\in Y_\circ)(z\leqslant y)$.

$\triangleleft$ Всякая цепь в $Y$, будучи цепью в $X$, конечна и тем самым ограничена снизу.
Стало быть, утверждение леммы 2 вытекает из леммы Цорна. $\triangleright$

Для любого $x\in X$ положим $x{\uparrow} := \{y\in X : y > x\}$ и $x^+ := (x{\uparrow})_\circ$.
Сразу заметим, что $|x^+|<\infty$ согласно лемме 1.

Лемма 3. $(\forall\, x\in X)(\forall\,y\in x{\uparrow})(\exists\,z\in x^+)(z\leqslant y)$.

$\triangleleft$ Вытекает непосредственно из леммы 2. $\triangleright$

Положим $X_\infty := \{x\in X : |x{\uparrow}|=\infty\}$.

Лемма 4. $(\forall\,x\in X_\infty)(\exists\,y\in X_\infty)(y\in x{\uparrow})$.

$\triangleleft$ Согласно лемме 3 мы имеем $x{\uparrow}=x^+\cup\bigcup_{z\in x^+}z{\uparrow}$.
Остается учесть, что $|x^+|<\infty$. $\triangleright$

Благодаря аксиоме выбора из леммы 4 следует существование такой функции
$f:X_\infty\to X_\infty$, что $f(x)\in x{\uparrow}$ для всех $x\in X_\infty$.

Согласно леммам 1 и 2 мы имеем $|X_\circ|<\infty$ и $X=X_\circ\cup\bigcup_{z\in X_\circ}z{\uparrow}$.
С другой стороны, $|X|=\infty$, а значит, $X_\infty\ne\varnothing$.
Пусть $x_1\in X_\infty$.
Рекурсивно определим последовательность $(x_n)_{n\in\mathbb N}$ элементов $X$,
полагая $x_{n+1} := f(x_n)$ для $n\in\mathbb N$.
Тогда множество $\{x_n : n\in\mathbb N\}$ является бесконечной цепью в $X$.
Противоречие.

P.S. Писал на скорую руку, так что мог наошибаться. Проверьте, плиз.

[Salvador]

Вроде все верно. Огромное Вам спасибо!

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

AGu писал(а):

Это утверждение очень походит на лемму Кёнига (о цепях в графе)
и, вроде бы, доказывается почти так же.

А лемма Кёнига --- это утверждение о том, что в бесконечном конечно ветвящемся дереве существует бесконечная цепь.

Да, согласен.

Доказательство проверил. Вроде всё правильно. У меня у самого в уме выстроилось что-то похожее, только я "сверху вниз" шёл, выделяя максимальные, а не минимальные элементы

[AGu]

Salvador в сообщении #178393 писал(а):

Вроде все верно.

Профессор Снэйп в сообщении #178894 писал(а):

Доказательство проверил. Вроде всё правильно.

Спасибо.
P.S. И все же зря я назвал антицепи коцепями.

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

AGu писал(а):

P.S. И все же зря я назвал антицепи коцепями.

Да, я хотел сказать об этом, но забыл.

Вот интересно: нет ли чего-нибудь проще? Задача-то вроде просто выглядит, и утверждение естественное. А доказывается неожиданно... нет, не то, чтобы действительно сложно, но при взгляде на задачу ожидается что-то более простое.