Чумы, лемма Цорна и попытки её обойти

[Chernoknizhnik]

Доказываю следующую вещь: если $M$ - частично упорядоченное множество и (1) $\forall x\in M \exists y$, который строго больше $x$, то в $M$ есть цепь, не имеющая верхней грани, т.е. линейно упорядоченное подмножество $U$, из которого по любому $x\in M$ можно выбрать $y(\in U)$ такой, что $y>x$.
Теперь заменяем условие (1) следующим условием (2) существует отображение $f:M\rightarrow M$, причем $\forall x\in M$ имеет место строгое неравенство $x<f(x)$.
Во-первых, я понимаю, что условие (2) мгновенно влечет за собой (1).
Во-вторых, я понимаю, что условие (1) влечет за собой (2), если воспользоваться аксиомой выбора.
Вопрос таков: можно ли вывести существование неограниченной цепи из условия (2) (или даже (1)), не используя лемму Цорна и эквивалентные ей утверждения (аксиому выбора, принцип полного упорядочения и т.п.). Конечно, с помощью леммы Цорна всё это очень просто доказывается. Вообще, это должно быть очень просто.

[Someone]

Из (2) можно. Методом математической индукции по натуральным числам (натуральные числа в ZF строятся и их свойства доказываются без аксиомы выбора).
Из (1), скорее всего, нельзя. Без аксиомы выбора возможно существование множества, не равномощного никакому натуральному числу, но не содержащего бесконечных последовательностей с попарно различными элементами. Правда, я не знаю, возможно ли на таком множестве отношение частичного порядка, удовлетворяющее Вашему условию (1).

[muzeum]

Цитата:

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

Пусть множество $X$ таково. Рассмотрим множество конечных цепей (по включению) его конечных подмножеств, таких, что соседние члены в цепи отличаются одним элементом и наименьший элемент цепи - пустое множество.
Это частично упорядоченное множество является контрпримером.

[AGu]

Chernoknizhnik в сообщении #679019 писал(а):

если [...] $\forall x\in M \exists y$, который строго больше $x$, то в $M$ есть цепь, не имеющая верхней грани

Может, я чего-то недопонял, но мне кажется, что это утверждение напрочь эквивалентно лемме Цорна (относительно ZF и даже относительно просто исчисления). Действительно, пусть $\Phi(M) =$(в $M$ любая цепь ограничена сверху), $\Psi(M)=$(в $M$ есть максимальный элемент). Тогда лемма Цорна для $M$ -- это импликация $\Phi(M)\Rightarrow\Psi(M)$, а рассматриваемое утверждение -- это эквивалентная ей импликация $\neg\Psi(M)\Rightarrow\neg\Phi(M)$. Разве не так?

Chernoknizhnik в сообщении #679019 писал(а):

[...] то в $M$ есть цепь, не имеющая верхней грани, т.е. линейно упорядоченное подмножество $U$, из которого по любому $x\in M$ можно выбрать $y(\in U)$ такой, что $y>x$.

Кстати, тут должно быть не $y>x$, а $y\nleqslant x$.

Someone в сообщении #679035 писал(а):

Из (2) можно. Методом математической индукции по натуральным числам

А как это сделать? Что-то у меня с ходу не получилось.

muzeum в сообщении #679041 писал(а):

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

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

[muzeum]

Для господина AGu, которого ниже и цитирую:

Цитата:

muzeum в сообщении #679041 писал(а):
Это частично упорядоченное множество является контрпримером.
Что-то я тут не вижу частично упорядоченного множества без максимальных элементов, в котором все цепи ограничены. Да и было бы странно, если бы оно так легко появилось: ведь существование подобного "контрпримера" противоречит ZFC, а значит, оно может наблюдаться только в какой-то хитрой модели ZF или каком-то хитром относительно совместном расширении ZF, а про такого рода хитрости никаких намеков не было.

Вы немного слишком сократили мой текст при цитировании, у меня местоимение "это" было вполне осмысленно и относилось к тексту процитированного мною предыдущего оратора, который ссылался на возможность (модель Коэна) существования множества, не равномощного натуральному числу и не содержащего бесконечных последовательностей. Проще говоря - дедекиндово конечное, но не конечное множество.
Модель Коэна - это и есть то самое очень хитрое расширение.
Исходя из этого дедекиндово конечного множества мы строим новое множество - множество конечных возрастающих по включению его конечных подмножеств. Причем рассматриваем такие последовательности, что наименьшим элементом в них является пустое подмножество и разность членов с номерами $n+1$ и $n$ содержит ровно один элемент. Множество таких последовательностей упорядочено включением (одна последовательность "расширяет" или "продолжает" другую).

[AGu]

muzeum в сообщении #679288 писал(а):

Вы немного слишком сократили мой текст при цитировании, у меня местоимение "это" было вполне осмысленно и относилось к тексту процитированного мною предыдущего оратора

Похоже, что цитату в том Вашем сообщении я принял за декорацию разделителя между сообщениями. Короче, я ее напрочь не увидел. Честно. Сам себе удивляюсь. Виноват!

Как бы то ни было, вопрос с условием (1), вроде бы, не требует такого рода теоретико-модельных глубин. Что же касается вопроса с условием (2), то ответ на него пока остается для меня непросекаемым.

[Someone]

AGu в сообщении #679457 писал(а):

Что же касается вопроса с условием (2), то ответ на него пока остается для меня непросекаемым.

Да ладно, чего там сложного.

Пусть $M$ - непустое частично упорядоченное множество, и пусть $f\colon M\to M$ - такое отображение, что $f(x)>x$ для всех $x\in M$. Пусть $x_0\in M$ - любой элемент. Определяем по индукции отображение $\varphi\colon\mathbb N\to M$:
1) $\varphi(0)=x_0$;
2) для каждого $n\in\mathbb N$ полагаем $\varphi(n+1)=f(\varphi(n))$.
Тогда $\{\varphi(n):n\in\mathbb N\}$ - искомая цепь, не имеющая наибольшего элемента. (Это множество существует по аксиоме замены.)

Подробнее об определениях по индукции можно посмотреть в книге К. Куратовского и А. Мостовского "Теория множеств", глава III, § 2, который так и называется: "Определения по индукции".

[AGu]

Someone в сообщении #679479 писал(а):

искомая цепь, не имеющая наибольшего элемента.

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

[Someone]

AGu в сообщении #679493 писал(а):

У нас ведь речь идет о цепи без верхней границы (в объемлющем чуме), а не просто о цепи без наибольшего элемента.

Хм... А я понял совсем иначе.

Chernoknizhnik в сообщении #679019 писал(а):

если $M$ - частично упорядоченное множество и (1) $\forall x\in M \exists y$, который строго больше $x$, то в $M$ есть цепь, не имеющая верхней грани, т.е. линейно упорядоченное подмножество $U$, из которого по любому $x\in M$ можно выбрать $y(\in U)$ такой, что $y>x$.

Вот это "по любому $x\in M$" я принял за опечатку вместо "по любому $x\in U$", потому что воспринял это как пояснение в терминах множества $U$. Кстати, в том виде, как это написано, это неверное утверждение, и его нельзя доказать. "Даже" с помощью аксиомы выбора.

Цепь, не имеющую верхней границы, можно построить по трансфинитной индукции:
1) $\varphi(0)=x_0$;
2) если $\varphi(\alpha)$ определено, то $\varphi(\alpha+1)=f(\varphi(\alpha))$;
3) если $\alpha$ - предельный ординал, $\varphi(\beta)$ определено для всех $\beta<\alpha$, и $\sup\{\varphi(\beta):\beta<\alpha\}$ (в множестве $M$) существует, то $\varphi(\alpha)=\sup\{\varphi(\beta):\beta<\alpha\}$.

Построение невозможно продолжить на все ординалы, так как в противном случае по аксиоме выделения $A=\{x\in M:\exists\alpha(x=\varphi(\alpha))\}$ является множеством, а тогда по аксиоме замены совокупность всех ординалов $On=\{\varphi^{-1}(x):x\in A\}$ тоже была бы множеством, что неверно. Поэтому найдётся наименьший (обязательно предельный) ординал $\alpha_{max}$, для которого $\varphi(\alpha_{max})$ не определено.
Тогда $\{\varphi(\alpha):\alpha<\alpha_{max}\}$ - цепь, не имеющая верхней грани в $M$.

Ординалы в ZF определяются без аксиомы выбора, и их свойства благополучно доказываются тоже без аксиомы выбора. Подробности можно посмотреть в той же книжке, глава VII.

Добавление. Исправил погрешности, на которые указал AGu.

Добавление 2. AGu прав, $\sup$ может не существовать, даже если множество ограничено сверху, поэтому доказательство не проходит.

[AGu]

Someone в сообщении #679532 писал(а):

Кстати, в том виде, как это написано, это неверное утверждение

Ага. Я там выше указал на опечатку: вместо $y>x$ должно быть $y\nleqslant x$.

Someone в сообщении #679532 писал(а):

Цепь, не имеющую верхней границы, можно построить по трансфинитной индукции

Да, я тоже об этом размышлял, но...

Someone в сообщении #679532 писал(а):

3) если $\alpha$ - предельный ординал, и $\varphi(\beta)$ определено для всех $\beta<\alpha$, то $\varphi(\alpha)=\sup\{\varphi(\beta):\beta<\alpha\}$.

(В цитате я исправил $\beta$ на $\alpha$ и "veta" на "beta". ) В общем случае супремума может не быть. Тут спасла бы функция, сопоставляющая каждой цепи какую-нибудь ее верхнюю границу, но откуда ей взяться -- непонятно.

[Someone]

AGu в сообщении #679545 писал(а):

(В цитате я исправил $\beta$ на $\alpha$ и "veta" на "beta". )

Правильно исправили. Сейчас тоже исправлю.

AGu в сообщении #679545 писал(а):

В общем случае супремума может не быть.

Как только его нет, построение заканчивается. Забыл написать "если верхняя грань существует", хотя собирался. Тоже исправлю, чтобы не путать тех, кто, возможно, будет читать это потом.

-- Вс фев 03, 2013 16:43:43 --

Дошло. Нельзя там написать $\sup$, поэтому доказательство не проходит.

[AGu]

Someone в сообщении #679561 писал(а):

AGu писал(а):

В общем случае супремума может не быть.

Как только его нет, построение заканчивается.

Ой. А почему тогда полученная цепь не будет иметь верхней границы? (Супремума-то у нее точно не будет, но...)

Может, нас опять попутало недоразумение? Грани, границы... Супремум частенько называют "верхней гранью", но я подумал, что слова топикстартера "не имеющая верхней грани" означают не отсутствие точной верхней границы, а просто неограниченность сверху. (Это мне показалось очевидным из остального текста.)

Добавка. Уфф, зря колошматил по клавишам. Недоразумение само собой отменилось.

[muzeum]

Цитата:

Что же касается вопроса с условием (2), то ответ на него пока остается для меня непросекаемым.

Я думал, что этот вопрос тоже решен. Действительно, пусть $(S,<)$ ч.у.м., как построенное для свойства (1) , построим новое Ч.У.М. из него, вставив на место каждого $x\inS$ цепочку натуральных чисел, т.е. просто возьмем декартово произведение $({S}\times{N},<)$, неравенство сначала устанавливается для первых компонент.
Имеем функцию: $f((s,n))\to\,(s,n+1)$ и, тем не менее, не существует немажорируемая цепь.
Разумеется, все это без АС.

[muzeum]

На тот случай, если в начальной формулировке было не все сказано, дополню свой предыдущий пост следующим (довольно очевидным, впрочем) утверждением.
Предложение (ZF): Следующее утверждение эквивалентно АС:
Для любого частично упорядоченного множества $(P,<)$, такого, что для любого $x$ существует $y$ такой, что $x<y$ , в этом множестве существует немажорируемая цепь.
Доказательство можно рассматривать в одну сторону (в другую оно очевидно уже совершенно), а именно из этого предположения доказывается лемма Цермело. Для чего для произвольного множества $M$ рассматриваем множество $(P,<)$ вполне упорядоченных множеств $x=(X,\rho)$, где $X$ подмножество $M$. Отношение $x<y$ означает, что $x$ является начальным отрезком $y$.
Если множество $M$ не может быть вполнеупорядочено, то $(P,<)$ удовлетворяет посылке предложения, значит, содержит немажорируемую цепь. Но объединение этой цепи является вполне упорядоченным множеством, т.е. принадлежит $(P,<)$, следовательно, имеет мажорирующий элемент. Противоречие доказывает требуемое.
Замечу, что, если преобразовать подходящим образом условие (2), то по форме получится более слабое утверждение. Будет ли и оно эквивалентно АС пока не знаю.

[muzeum]

После раздумия, понял, что и со вторым свойством все просто.
Будем обозначать буквой А следующее утверждение
Для любого частично упорядоченного множества $(P,<)$, такого, что для любого $x$ существует $y$ такой, что $x<y$ , в этом множестве существует не мажорируемая цепь.
Мы уже доказали, что это утверждение эквивалентно аксиоме выбора.
Покажем, что и следующее утверждение В также эквивалентно АС.
Утверждение В:
Если в частично упорядоченном множестве $(P,<)$ определена функция $f$ такая, что для любого $x$ выполнено $x<f(x)$, то в этом ЧУМ имеется не мажорируемая цепь.
Для доказательства достаточно установить, что В влечет А (в ZF).
Доказательство (ZF+B).
Пусть $(S,<)$ ч.у.м., нарушающее утверждение А , построим новое Ч.У.М. из него, вставив на место каждого $x\inS$ цепочку натуральных чисел, т.е. просто возьмем декартово произведение $({S}\times{N},<)$, неравенство сначала устанавливается для первых компонент.
Имеем функцию: $f((s,n))\to\,(s,n+1)$ и, тем не менее, не существует не мажорируемая цепь. Это противоречит предполагаемому предложению В.