Наименьшая неподвижная точка

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

Пусть $\mathcal{L}$ --- полная решётка и $\varphi : \mathcal{L} \to \mathcal{L}$ --- монотонное отображение (то есть такое, что $a \leqslant b$ влечёт $\varphi(a) \leqslant \varphi(b)$ для любых $a,b \in \mathcal{L}$). Доказать, что множество $\{ x \in \mathcal{L} : \varphi(x) = x \}$ не пусто и имеет наименьший (а также наибольший) элементы.

[terminator-II]

рассмотрим максимальный элемент $L$ -- $y$; множество $\{y,\varphi(y)\}$ имеет $\sup$; ясно, что это $y$.
следовательно множество $\{\varphi(x)\le x\}$ не пусто. рассмотрим минимальный элемент этого множества

в порядке компенсации: доказать, что если каждое монотонное отображение частично упорядоченного множества обладает неподвижной точкой, то (любая) максимальная цепь этого множества является полной решеткой

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

terminator-II в сообщении #224018 писал(а):

рассмотрим максимальный элемент $L$ -- $y$; множество $\{y,\varphi(y)\}$ имеет $\sup$; ясно, что это $y$.
следовательно множество $\{\varphi(x)\le x\}$ не пусто. рассмотрим минимальный элемент этого множества

Минимальный элемент --- это как?

Поскольку решётка полная, то у каждого множества есть инфимум. Вы, вероятно, инфимум множества $\{ x : \varphi(x) \leqslant x \}$ и имели в виду. А вот почему этот инфимум сам должен этому множеству принадлежать?

-- Пн июн 22, 2009 22:31:24 --

terminator-II в сообщении #224018 писал(а):

доказать, что если каждое монотонное отображение частично упорядоченного множества обладает неподвижной точкой, то (любая) максимальная цепь этого множества является полной решеткой

Ну это, кстати, не сложно.

Предположим противное. Пусть $\langle P, \leqslant \rangle$ --- частично упорядоченное множество и $L \subseteq P$ --- максимальная цепь в нём, не являющаяся полной решёткой. Тогда существует разбиение $L = X \cup Y$, такое что все элементы $X$ строго меньше всех элементов $Y$, $X$ не имеет наибольшего, а $Y$ не имеет наименьшего элементов.

Покажем, что существует линейное упорядочение $\leqslant'$ множества $P$, такое что

1) $x \leqslant y \Rightarrow x \leqslant' y$ для всех $x,y \in P$.
2) не существует $p \in P$, для которого $x \leqslant' p \leqslant' y$ при всех $x \in X$ и $y \in Y$.

Рассмотрим множество всех частичных порядков на $P$, продолжающих исходный порядок и обладающих свойством 2. Оно частично упорядоченно по включению, причём каждая цепь в нём имеет верхнюю грань (равную объединению этой цепи). Значит, по лемме Цорна, среди таких упорядочений существует максимальное. Оно, очевидно, обладает свойствами 1 и 2. Если оно не линейно, то можно легко получить противоречие с его максимальностью, опираясь на максимальность цепи $L$.

Теперь наше $P$ относительно порядка $\leqslant'$ представляет собой линейно упорядоченное множество, не являющееся полным (множество $\{ p : (\exists x \in X)(p \leqslant' x) \}$ не имеет супремума). Нетрудно построить монотонное (относительно $\leqslant'$) отображение $P$ в себя, не имеющее неподвижной точки. Это же отображение будет монотонным относительно исходного порядка $\leqslant$.

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

По поводу моего предыдущего сообщения.

То, что инфимум множества $\{ x : \varphi(x) \leqslant x \}$ сам принадлежит этому множеству и является наименьшей неподвижной точкой доказать, безусловно, можно. Причём достаточно легко. Так что решение, предложенное terminator-II, с некоторой натяжкой можно засчитать. Хотя он, конечно, крайне неаккуратен в использовании терминов.

То решение, которое я изначально имел в виду, совсем другое. Причём оно более сложное.

Что же касается предложенной им задачи, то моё вчерашнее решение некорректно в одном месте: из монотонности относительно порядка $\leqslant'$ не следует монотонность относительно исходного порядка. Надо строить отображение из $P$ в $P$ так, чтобы из $x \leqslant' y$ следовало $\varphi(x) \leqslant \varphi(y)$. Сделать это, безусловно, можно. Но, начав это делать, я заметил, что приводить всё $P$ к линейному упорядочению совсем не обязательно.

Итак, расскажу идею решению.

1) Берём ЧУМ $P$ и в нём максимальную цепь $L$, не являющуюся полной. Задаём её разбиение $L = X \cup Y$, такое же, как и ранее.

2) Возможны 3 случая: $X = \varnothing$, $Y = \varnothing$ и $X \neq \varnothing \neq Y$. Принципиального различия между ними нет, но с формальной точки зрения каждый из случаев требует отдельного изложения. Разберём второй случай, остальные "аналогично" (взял слово в кавычки, ибо полной аналогии нет, но идеи те же). Итак, пусть $Y = \varnothing$.

3) Берём подходящий предельный ординал $\alpha$ и вкладываем его в $X$. Другими словами, задаём монотонное инъективное соответствие $\gamma \mapsto x_\gamma$ из $\alpha$ в $X$. Причём вкладываем так, чтобы образ этого вложения не имел верхней границы в $X$.

4) Для каждого $p \in P$ пусть $\gamma(p)$ есть наименьший элемент $\gamma \in \alpha$, такой что $p \leqslant x_\gamma$, если оный существует. Если же не существует, то пусть $\gamma(p) = 0$.

5) Полагаем $\varphi(p) = x_{\gamma(p)+1}$. Получаем, что $\varphi$ --- монотонное отображение $P$ в себя, не имеющее неподвижной точки. Что, собственно, и требовалось.

[terminator-II]

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

То, что инфимум множества $\{ x : \varphi(x) \leqslant x \}$ сам принадлежит этому множеству и является наименьшей неподвижной точкой доказать, безусловно, можно. Причём достаточно легко. Так что решение, предложенное terminator-II, с некоторой натяжкой можно засчитать. Хотя он, конечно, крайне неаккуратен в использовании терминов.

засчитывать не надо. я не знаю как доказывать ,что $\{ x : \varphi(x) \leqslant x \}$ имеет мин. элемент .
сдаюсь. расскажите ,пожалуйста, доказательство

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

terminator-II в сообщении #224170 писал(а):

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

То, что инфимум множества $\{ x : \varphi(x) \leqslant x \}$ сам принадлежит этому множеству и является наименьшей неподвижной точкой доказать, безусловно, можно. Причём достаточно легко. Так что решение, предложенное terminator-II, с некоторой натяжкой можно засчитать. Хотя он, конечно, крайне неаккуратен в использовании терминов.

засчитывать не надо. я не знаю как доказывать ,что $\{ x : \varphi(x) \leqslant x \}$ имеет мин. элемент .
сдаюсь. расскажите ,пожалуйста, доказательство

Не, ну это совсем просто! Хотя я тоже не сразу догадался

Пусть $X = \{ x : \varphi(x) \leqslant x \}$ и $x_0 = \inf X$. Для любого $x \in X$ имеем $x_0 \leqslant x$ и, из монотонности $\varphi$, $\varphi(x_0) \leqslant \varphi(x) \leqslant x$. Значит, $\varphi(x_0)$ --- нижняя грань для $X$. А так как $x_0$ --- наибольшая среди всех нижних граней $X$, то $\varphi(x_0) \leqslant x_0$ и $x_0 \in X$.

[terminator-II]

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

так как $x_0$ --- наибольшая среди всех нижних граней $X$, то $\varphi(x_0) \leqslant x_0$

а почему $$\varphi(x_0)$ должно быть сравнимо с $x_0$?

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

terminator-II в сообщении #224181 писал(а):

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

так как $x_0$ --- наибольшая среди всех нижних граней $X$, то $\varphi(x_0) \leqslant x_0$

а почему $$\varphi(x_0)$ должно быть сравнимо с $x_0$?

Инфимум --- это, по определению, наибольшая нижняя грань. Он обязан быть сравним со всеми остальными нижними гранями.

[terminator-II]

инфимум это максимальный элемент в множестве нижних граней, разве он должен быть сравним со всеми нижними гранями?

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

terminator-II в сообщении #224185 писал(а):

инфимум это максимальный элемент в множестве нижних граней, разве он должен быть сравним со всеми нижними гранями?

Не максимальный, а наибольший. Совершенно разные вещи!

[terminator-II]

ok переклинило

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

Во! Придумал, как переделать задачу, чтобы предложенное terminator-II решение не проходило, а то, которое я изначально имел в виду,оставалось в силе.

Пусть $\mathcal{P}$ --- частично упорядоченное множество с наименьшим элементом, в котором каждое линейно упорядоченное подмножество имеет супремум. Доказать то же самое: множество неподвижных точек произвольного монотонного отображения $\mathcal{P}$ в себя не пусто и содержит наименьший элемент.

[AGu]

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

Пусть $\mathcal{P}$ --- частично упорядоченное множество с наименьшим элементом, в котором каждое линейно упорядоченное подмножество имеет верхнюю грань. [...] Доказать то же самое: множество неподвижных точек произвольного монотонного отображения $\mathcal{P}$ в себя не пусто [...]

Пусть $\mathcal P = [0,1]\backslash\{\tfrac12\}$ и $f(x)=\tfrac12x+\tfrac14$.
Что-то неподвижной точки не видать...

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

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

...Что-то неподвижной точки не видать...

Упс, прошу прощения! Некий аналог полноты всё же нужен Сейчас исправлю условие.

[terminator-II]

Профессор Снэйп
к нашей беседе в личке, Профессор: topic23767.html