ординальная плотность линейного упорядочения

[rishelie]

Сразу извиняюсь, если какую-то ерунду скажу или не тот термин использую, просто не нашел пока ни в одной книжке из тех, что у меня есть, описание вот такой задачки.
Пусть у нас имеется линейно упорядоченное множество $(X,<)$.
$\alpha$-последовательностью в $X$ назовем строго монотонную функцию $f:\alpha\to X$, где $\alpha$ - ординал. Пусть $\gamma=\gamma(X,<)$ - наименьший ординал такой, что в $X$ не существует $\gamma$-последовательность.
Этот вот ординал и хочется обозвать ординальной плотностью $(X,<)$.

В связи с этим можно поставить вопрос: $\gamma(\mathbb R)=\aleph_1$?

Порядки вроде $a_0\omega^n+a_1\omega^{n-1}+\dots+a_n$, где $a_i$ - натуральные числа, строятся довольно легко. За основу берем натуральный ряд, затем его <<упаковываем>> в полуинтервалы $[n,n+1)$ каким-нибудь монотонным отображением вроде $n+2^{-x}$. Потом полученную конструкцию опять пакуем в эти же интервалы тем же отображением, и так далее. Конечное число шагов такой упаковки сохраняет нам порядок без проблем. А когда у нас есть $\omega,\omega^2,\omega^3,\dots$ -последовательности, их снова можно упаковать в те же полуинтервалы и получить $\omega^\omega$ -последовательность (не путать степень ординалов со степенью кардиналов!). Ну и так далее. Можно наращивать степени сколь угодно долго, выстраивая порядок, который можно записать формулой, содержащей конечное число символов $\omega$ в операциях сложения, умножения, возведения в степень.
Покроем ли мы тем самым все порядки ниже $\aleph_1$?

И какова ординальная плотность множества гипердействительных чисел, которое корректно включает в себя бесконечно малые и бесконечно большие величины?

Интересовался ли кто-нибудь этим вопросом или это прописная истина?

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

Да, $\gamma(\mathbb{R}) = \aleph_1$ (кстати, исправьте там у себя, у Вас в скобках аргумент не отображается). Только Вы зря заморочились на каких-то представлениях ординалов в виде сумм и т. п. Всё гораздо-гораздо проще.

1) Любой счётный линейный порядок изоморфно вкладывается в $\mathbb{Q}$. Ну а $\mathbb{Q}$, очевидно, вкладывается в $\mathbb{R}$. Значит, любой счётный ординал вкладывается в $\mathbb{R}$.

2) $\aleph_1$ не вкладывается в $\mathbb{R}$, так как иначе для любого $\alpha \in \aleph_1$ между образами ординалов $\alpha$ и $\alpha + 1$ найдётся рациональное число и в $\mathbb{Q}$ найдётся несчётное бесконечное подмножество.

Так что всё это если и не

rishelie в сообщении #233332 писал(а):

прописная истина

то довольно близко к ней

-- Чт авг 06, 2009 18:03:35 --

rishelie в сообщении #233332 писал(а):

И какова ординальная плотность множества гипердействительных чисел, которое корректно включает в себя бесконечно малые и бесконечно большие величины?

Не знаю, что Вы понимаете под "гипердействительными числами". Неархимедовых расширений упорядоченного поля $\mathbb{R}$ много, Вас какое из них интересует?

-- Чт авг 06, 2009 18:11:22 --

Там по ходу ещё один вопрос возник.

rishelie в сообщении #233332 писал(а):

Покроем ли мы тем самым все порядки ниже $\aleph_1$?

Нет, не покроем. Покроем только порядки ниже $\varepsilon_0 = \omega^{\omega^{\ldots}}$ (возведение в степень происходит счётное число раз). А это счётный ординал. И $\varepsilon_0 + 1 > \varepsilon_0$ --- тоже счётный Где-то там много после $\varepsilon_0$ есть очень важный ординал $\omega_1^{CK}$, он тоже счётный Это наименьший ординал, который нельзя задать конструктивно никаким образом, не то что в виде сумм.

-- Чт авг 06, 2009 18:27:17 --

Насчёт последнего: в Вики про это немного есть.

[rishelie]

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

Вас в скобках аргумент не отображается

по привычке \R написал %)

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

Любой счётный линейный порядок изоморфно вкладывается в $\mathbb{Q}$

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

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

Не знаю, что Вы понимаете под "гипердействительными числами". Неархимедовых расширений упорядоченного поля $\mathbb{R}$ много, Вас какое из них интересует?

то, которое строится через эквивалентные действительные последовательности ($\{f_n\}\sim\{g_n\}$, если $f_n=g_n$ на некотором элементе ультрафильтра на $\omega$).

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

Где-то там много после $\varepsilon_0$ есть очень важный ординал $\omega_1^{CK}$, он тоже счётный Это наименьший ординал, который нельзя задать конструктивно никаким образом, не то что в виде сумм.

о!

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

rishelie в сообщении #233344 писал(а):

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

1) Любой счётный линейный порядок можно расширить до счётного плотного линейного порядка без концов.

2) Все счётные плотные линейные порядки без концов изоморфны.

Какой из пунктов вызывает затруднения?

-- Чт авг 06, 2009 18:34:28 --

rishelie в сообщении #233344 писал(а):

...то, которое строится через эквивалентные действительные последовательности...

По нестандартному анализу я сам не ахти какой эксперт Но не отчаивайтесь, придёт AGu и всё подробно распишет. Он в этом деле специалист.

-- Чт авг 06, 2009 18:37:09 --

rishelie в сообщении #233344 писал(а):

о!

Обратите внимание на ссылку, которую я приписал в самом конце первого сообщения. Хотя, увы, только на аглицком. Кстати, про $\omega_1^{CK}$ есть в спецкурсе, который я читал пару лет назад. Если интересно, могу дать ссылку на констпект.

Ну или в книгах. В Роджерсе всё очень хорошо расписано.

[Инт]

Ординальная плотность действительной прямой определена правильно. Если бы на действительной прямой существовала монотонная последовательность длины алеф-один, то каждый отрезок, с концами в соседних элементах последовательности, содержал бы рациональное число, и тогда оказалось бы рациональных чисел - несчётное количество. С другой стороны, любой счётный ординал вложим в действительную прямую.

Ординальная плотность гиперпрямой или неархимедовой будет действительно зависеть от того, какую из таких прямых рассматривать. Если рассматривать ту, что я указывал, то ординальная плотность равна алеф-два. Выбирая всё более и более "насыщенные" гиперпрямые можно получить в качестве плотности любой кардинал. Ясно, что это будет только кардинал на континуумах.

[rishelie]

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

1) Любой счётный линейный порядок можно расширить до счётного плотного линейного порядка без концов.
2) Все счётные плотные линейные порядки без концов изоморфны.
Какой из пунктов вызывает затруднения?

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

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

Обратите внимание на ссылку, которую я приписал в самом конце первого сообщения. Хотя, увы, только на аглицком. Кстати, про $\omega_1^{CK}$ есть в спецкурсе, который я читал пару лет назад. Если интересно, могу дать ссылку на конспект.

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

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

rishelie в сообщении #233361 писал(а):

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

http://www.nsu.ru/education/podzorov/Comput/Comput.pdf , стр. 87~--~101.

-- Чт авг 06, 2009 23:05:37 --

rishelie в сообщении #233344 писал(а):

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

Не знаю, что Вы понимаете под "гипердействительными числами". Неархимедовых расширений упорядоченного поля $\mathbb{R}$ много, Вас какое из них интересует?

то, которое строится через эквивалентные действительные последовательности ($\{f_n\}\sim\{g_n\}$, если $f_n=g_n$ на некотором элементе ультрафильтра на $\omega$).

Как я уже писал, нестандартным анализом я никогда не занимался. Но определения вроде все понятны, так что давайте немного помыслим.

Итак, пусть $\mathcal{F}$ --- неглавный ультрафильтр на $\mathbb{N}$ и $f,g$ --- произвольные функции из $\mathbb{N}$ в $\mathbb{R}$. Они называются $\mathcal{F}$-эквивалентными, если $\{ n \in \mathbb{N} : f(n) = g(n) \} \in \mathcal{F}$. Классы $\mathcal{F}$-эквивалентности и будут нашими "гипердействительными" числами. Сравниваются они так: $[f] < [g] \Leftrightarrow \{ n \in \mathbb{N} : f(n) < g(n) \} \in \mathcal{F}$.

Для действительного числа $r$ пусть $f_r(n) = r$ для любого натурального $n$. Тогда соответствие $r \mapsto [f_r]$ является изоморфным вложением действительных чисел в "гипердействительные", так что можно отождествлять $r$ и $[f_r]$.

Отсюда мораль: любой счётный ординал изоморфно вкладывается в гипердействительные числа. Нам надо понять, вкладывается ли в гипердействительные числа ординал $\aleph_1$.

Хм... После нескольких минут размышлений пока непонятно даже, с какого бока это начинать. Надо спросить у AGu. AGu, что Вы про это можете сказать? Для начала ответьте на вопрос: зависят ли наши "гипердействительные числа" (взятые, естественно, с точностью до изоморфизма) от выбора $\mathcal{F}$?

-- Чт авг 06, 2009 23:11:11 --

Так... Наверное, можно начать со следующего вопроса. Про две функции $f,g : \mathbb{N} \to \mathbb{R}$ скажем, что $f \ll g$, если $f(n) < g(n)$ почти для всех (то есть для всех за исключением конечного числа) $n$. Какие ординалы вкладываются в $\langle \mathrm{Func}(\mathbb{N}, \mathbb{R}), \ll \rangle$?

[rishelie]

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

Так... Наверное, можно начать со следующего вопроса. Про две функции $f,g : \mathbb{N} \to \mathbb{R}$ скажем, что $f \ll g$, если $f(n) < g(n)$ почти для всех (то есть для всех за исключением конечного числа) $n$. Какие ординалы вкладываются в $\langle \mathrm{Func}(\mathbb{N}, \mathbb{R}), \ll \rangle$?

Я, собственно, для таких функций и хотел построить $\aleph_1$-последовательность. Приблизительно так:
Рассматриваем только сходящиеся к нулю $f_n$ (особого смысла брать разные вещественные пределы нет, т.к. их все равно не хватит для $\aleph_1$-порядка), положительные и всюду ограниченные единицей. То есть, по сути, рассматриваем только бесконечно малые величины.
Имея некоторую начальную строго убывающую последовательность $f^{(0)}$, каждую следующую можно строить, извлекая корень из элементов предыдущей: $f^{(\alpha+1)}=\sqrt{f^{(\alpha)}}$. Если у нас имеются последовательности $g^{(n)}=f^{(\alpha_n)}$, где $\alpha_0<\alpha_1<\dots<\aleph_1$, то $g=f^{(\sup\alpha_n)}$ строится через них следующим способом.
$g_0=\sqrt{g^{(0)}_0}$
Для произвольного $n$ выберем натуральное число $K_n$ так, чтобы для натуральных $k\in[K_n,\infty)$ выполнялись неравенства:
$g_k^{(0)}<\dots<g_k^{(n)}$. Возможность этого следует из определения $\ll$.
Теперь положим $g_{K_n}=\sqrt{g_k^{(n)}}$. А для $K_n<k<K_{n+1}$ положим то же самое значение.
Тогда $g$ будет сравнима с каждой из $g_n$ на интервале $[K_n,\infty)$.
Вроде как для индукции по $\aleph_1$ больше ничего не требуется... И это будет строго возрастающая последовательность бесконечно малых. Так?

Полагаю, до $\aleph_2$ добираться бесполезно ввиду независимости CH от ZFC+Con(ZFC). Однако можно попытаться повторить рассуждения о счетных ординалах для ординалов мощности $\aleph_1$, поскольку $\ll$, очевидно, является плотным.

-- Чт авг 06, 2009 23:17:06 --

Кстати, если уж можно запихать порядок $\aleph_1$ в пучок сходящихся к нулю последовательностей, так это можно сделать с любым действительным числом, так что порядки вида $\alpha\aleph_1$ нам обеспечены, $\alpha<\aleph_1$.

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

Особого смысла брать разные вещественные пределы действительно нет. Но я бы на Вашем месте (если нужно только вложить $\aleph_1$ и ничего более) вместо бесконечно малых рассматривал бы бесконечно большие последовательности. Смысл тот же, а писанины меньше

Да, $\aleph_1$, похоже, действительно можно вложить.

Замечание про независимость CH от ZFC вместе с утверждением о совместности ZFC я, признаться, не понял. Почему не просто ZFC, зачем Вам понадобилось этот Con добавлять?

Но даже если принять отрицание CH, то предложенный для $\aleph_1$ метод, безусловно, не будет работает для $\aleph_2$. Это потому, что не каждый ординал, меньший $\aleph_2$, является пределом счётной последовательности меньших ординалов.

Кстати, если уж добиваться бесконечной малости строящихся последовательностей (хотя бы с целью вложить ординал $\aleph_1+1$), то Вам немного надо подкорректировать конструкцию, наложив дополнительное условие на выбор чисел $K_n$. А то ведь диагональ, построенная по последовательности бесконечно малых последовательностей, не обязана сама быть бесконечно малой. Но всё равно проблемы с $\aleph_2$ это не решает, даже при отрицании континуум-гипотезы. Поскольку выбрать образ бесконечно малым нужное число раз Вы уже не сможете.

Хотя, конечно, надо ещё подумать...

[AGu]

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

Надо спросить у AGu.

Я тут, но пока не готов ничего предложить, кроме очевидных оценок $\aleph_1\leqslant\gamma({}^*\mathbb R)\leqslant\frak c^+$. (Надо подумать, а работа мешает, туды ее растуды.)

-- 2009.08.07 14:23 --

rishelie в сообщении #233413 писал(а):

Полагаю, до $\aleph_2$ добираться бесполезно ввиду независимости CH от ZFC+Con(ZFC).

Я слыхал про независимость CH от ZFC (при мета-предположении о непротиворечивости ZFC, разумеется). Разве независимость CH от ZFC+Con(ZFC) тоже доказана? Или это очевидно из независимости CH от ZFC? Что-то не соображу...

[rishelie]

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

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

На самом деле там все хуже
нельзя требовать ни монотонность, ни равномерную сходимость последовательностей при построении на трансфинитном шаге рекурсии.. возможно, что и впрямь не обойдется без использования других пределов, кроме нуля...

-- Пт авг 07, 2009 11:49:25 --

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

rishelie в сообщении #233413 писал(а):
Полагаю, до $\aleph_2$ добираться бесполезно ввиду независимости CH от ZFC+Con(ZFC).
Я слыхал про независимость CH от ZFC (при мета-предположении о непротиворечивости ZFC, разумеется). Разве независимость CH от ZFC+Con(ZFC) тоже доказана? Или это очевидно из независимости CH от ZFC? Что-то не соображу...

да, пожалуй, я неточно выразился. я имел ввиду, что Коэн доказывал независимость СН от ZFC (!) при условии Con(ZFC) Пожалуй, не стоит смешивать утверждения метатеории с аксиомами или теоремами самой теории

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

rishelie в сообщении #233473 писал(а):

нельзя требовать ни монотонность, ни равномерную сходимость последовательностей при построении на трансфинитном шаге

??? А что, разве "монотонность" и "равномерность" зачем-то нужны? Не понимаю.

rishelie в сообщении #233473 писал(а):

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

Сами же понимаете, что "другие пределы" никак не спасают ситуацию!

По моему, у Вас всё нормально. Просто при выборе $K_n$ каждый раз делайте его настолько большим, чтобы $g_k^{(n)}$ было меньше $1/n$ при всех $k \geqslant K_n$. И будет от этого щастье

[rishelie]

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

По моему, у Вас всё нормально. Просто при выборе $K_n$ каждый раз делайте его настолько большим, чтобы $g_k^{(n)}$ было меньше $1/n$ при всех $k \geqslant K_n$. И будет от этого щастье

да, пожалуй, так оно и есть я засомневался, когда понял, что эти корни поточечно уводят $g^{(n)}$ сильно вверх. но вроде и впрямь все нормально, если на каждом шаге требовать ограничение через $1/n$. И лесенкой продлевать. монотонность я связывал с лесенкой, а равномерность с гарантией того, что все они равномерно стремятся к нулю при $k\to\infty$.

Все-таки, когда есть бумажка под рукой, гораздо проще выкладки прокручивать, чем просто в голове, сидя в автобусе

[AGu]

Наконец-то нашлось время немножко подумать. Делюсь придуманным
(не гарантируя безошибочность и надеясь на снисходительное внимание публики).

Пусть $\mathcal U$ — ультрафильтр на $\omega$, ${}^*\mathbb R:=\mathbb R^\omega/\mathcal U$ и $\gamma({}^*\mathbb R):=\min\{\alpha\in{\rm Ord} : \alpha\not\hookrightarrow{}^*\mathbb R\}$,
где $\rm Ord$ — класс всех ординалов и $\hookrightarrow$ — порядковая вложимость.

Тогда, вроде бы, получается следующее.

(1) Если принять $\rm C_2H_5OH$, то... Тьфу, не то.
Если принять CH, то $\gamma({}^*\mathbb R)=\aleph_2=\frak c^+$.

(2) Без CH дальше оценок $\aleph_2\leqslant\gamma({}^*\mathbb R)\leqslant\frak c^+$ продвинуться, наверное, нельзя.
Есть кое-какие соображения в пользу следующей гипотезы:
ZFC совместно с утверждением о том, что для различных $\mathcal U$
$\gamma(\mathbb R^\omega/\mathcal U)$ может принимать $\frak c$ различных позиций между $\aleph_2$ и $\frak c^+$.

Теперь — выкладки по поводу (1).
(Используемые ниже основные конструкции и идеи заимствованы
из "Теории множеств" Хаусдорфа, 1914 г.)

Счетными условимся называть множества мощности $\leqslant\aleph_0$.

Пусть $X$ — линейно упорядоченное (л.у.) множество.
Для $A,B\subseteq X$ и $x\in X$ будем писать $A<B$ и $A<x<B$
вместо $(\forall\,a\in A)(\forall\,b\in B)(a<b)$ и $(\forall\,a\in A)(a<x)\ \&\ (\forall\,b\in B)(x<b)$.

Счетной дыркой в $X$ назовем такую пару $(A,B)$, что
$A$ и $B$ — счетные подмножества $X$ (случаи $A=\varnothing$, $B=\varnothing$ не исключаются),
$A<B$ и $\neg(\exists\,x\in X)(A<x<B)$.

Если $(A,B)$ — счетная дырка в $X$, то обозначим через ${\rm Fill}_{(A,B)}X$
какое-либо расширяющее $X$ л.у. множество $X\cup\{y\}$, в котором $A<y<B$.

Л.у. множество назовем счетно насыщенным, если в нем нет счетных дырок.

Достаточно легко показать, что ${}^*\mathbb R$ — счетно насыщенное л.у. множество.

Известно [Хаусдорф], что счетно насыщенные л.у. множества мощности $\aleph_1$
попарно изоморфны.

Итак, покажем, что из CH следует $\gamma({}^*\mathbb R)=\aleph_2$.

Поскольку CH влечет $|{}^*\mathbb R|=\aleph_1$, достаточно показать, что $(\forall\,\alpha<\aleph_2)(\alpha\hookrightarrow{}^*\mathbb R)$.

Пусть $\alpha<\aleph_2$. Покажем, что $\alpha\hookrightarrow{}^*\mathbb R$.

Построим возрастающую последовательность $(X_\beta)_{\beta<\aleph_1}$ л.у. множеств $X_\beta$
следующей трансфинитной рекурсией.

Положим $X_0:=\alpha$.

Пусть построены $(X_\gamma)_{\gamma<\beta}$, где $0<\beta<\aleph_1$.
Положим $U:=\bigcup_{\gamma<\beta}X_\gamma$.
Если $U$ счетно насыщено, положим $X_\beta := U$.
В противном случае положим $X_\beta:={\rm Fill}_{(A,B)}U$,
где $(A,B)$ — какая-либо счетная дырка в $U$.

Положим $X:=\bigcup_{\beta<\aleph_1}X_\beta$.
Тогда $X$ — счетно насыщенное л.у. множество мощности $\aleph_1$,
а значит (с учетом CH), $X$ изоморфно ${}^*\mathbb R$.
Осталось заметить, что $\alpha=X_0\hookrightarrow X$.

[rishelie]

Да, вроде все точно... Даже утверждение, что $X$ - счетно насыщенное, не вызывает сомнений

-- Ср авг 12, 2009 21:32:41 --

Интересно, можно ли аналогично говорить о $\tau$ насыщенности и изоморфизме $\tau$ насыщенных л.у. множеств мощности $\tau^+$, где $\tau$ - несчетный кардинал? Кстати, а не надо ли для изоморфизма требовать, чтобы порядок был без $\tau$-концов, как и в случае плотных (т.е. конечно-насыщенных) л.у. множеств требуется отсутствие (просто) концов? Под $\tau$-концом здесь следует понимать полуинтервал $\{x\geqslant x_0\}$ или $\{x\leqslant x_0\}$, если его мощность равна $\tau$.