Salvador писал(а):
Дано бесконечное частично упорядоченное множество. Доказать, что в нем всегда найдется либо бесконечное подмножество попарно несравнимых элементов, либо бесконечное подмножество, на котором индуцированный порядок линеен.
Это утверждение очень походит на лемму Кёнига (о цепях в графе)
и, вроде бы, доказывается почти так же.
Пусть
-- частично упорядоченное множество.
Подмножество
назовем
цепью (соответственно
коцепью) в
,
если любые два различных элемента
сравнимы (соответственно несравнимы) в
.
Предположим, что
бесконечно, причем все цепи и коцепи в
конечны.
Наша цель -- получить противоречие.
Для любого подмножества
обозначим символом
множество всех минимальных элементов
,
т.е.
.
Условимся записывать конечность и бесконечность множества
формулами
и
соответственно.
Лемма 1. .
Достаточно заметить, что
является коцепью в
.
Лемма 2. .
Всякая цепь в
, будучи цепью в
, конечна и тем самым ограничена снизу.
Стало быть, утверждение леммы 2 вытекает из леммы Цорна.
Для любого
положим
и
.
Сразу заметим, что
согласно лемме 1.
Лемма 3. .
Вытекает непосредственно из леммы 2.
Положим
.
Лемма 4. .
Согласно лемме 3 мы имеем
.
Остается учесть, что
.
Благодаря аксиоме выбора из леммы 4 следует существование такой функции
, что
для всех
.
Согласно леммам 1 и 2 мы имеем
и
.
С другой стороны,
, а значит,
.
Пусть
.
Рекурсивно определим последовательность
элементов
,
полагая
для
.
Тогда множество
является бесконечной цепью в
.
Противоречие.
P.S. Писал на скорую руку, так что мог наошибаться. Проверьте, плиз.