Верещагин, Шень. Фундированные множества

[caxap]

Проверьте, пожалуйста.

108. Имеется конечная последовательность нулей и единиц. За один шаг разрешается сделать такое действие: найти в ней группу $01$ и заменить на $100{\dots}00$ (при этом можно написать сколько угодно нулей). Докажите, что такие шаги нельзя выполнять бесконечно много раз.

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

Каждой последовательности из нулей и единиц, содержащей $k$ единиц, сопоставим набор $(n_1,\ldots,n_k)$, где $n_i$ -- местоположение $i$-ой единицы в последовательности (считая слева). Например, последовательности $011001$ соответствует набор $(2,3,6)$. Рассмотрим множество всех таких наборов и введём порядок: сначала сравниваем первые координаты; если они равны, то вторые; если они равны, то третьи и т. д. Напр. $(2,3,6)>(2,1,6)>(1,7,8)$. Это множество фундировано (в любом непустом подмножестве можно найти минимальный элемент: сначала по первой координате, из них -- по второй и т. д.).

В результате преобразования $01\to 10\ldots$ набор, соответствующий последовательности, уменьшится (единица сдвинулась влево). Так как множество этих наборов фундировано, то не существует бесконечной убывающей последовательности этих наборов. Ч. т. д.

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

Рассмотрим произвольное непустое подмножество слов русского алфавита. Из всех элементов выберем сначала элементы с минимальной первой буквой. Затем из выбранных выберем элементы с минимальной второй буквой. И т. д. Раз все слова состоят из конечного число букв, то когда-нибудь мы остановимся и найдём минимальный элемент. Значит, множество всех русских слов фундировано.

[Null]

б
аб
ааб
аааб
ааааб
аааааб
...........

[caxap]

Null
То есть существует подмножество, в котором нет минимального элемента. Получается, ответ на 109-ую задачу "нет"?

[caxap]

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

Возьмём произвольный элемент этого множества $a_0$, номер его последнего ненулевого члена обозначим $n_0$. Возьмём меньший элемент $a_1<a_0$. Пусть номер члена, за счёт которого $a_0>a_1$ будет $n_1$ (т. е. наименьшее $k$ такое, что $k$ член $a_0$ больше $k$ члена $a_1$). Тогда $n_0\geqslant n_1$. Возьмём следующий член $a_2<a_1$. Номер члена, за счёт которого это неравенство осуществляется обозначим $n_2$. Тогда $n_1\geqslant n_2$. Покажем, что последовательность $n_0 \geqslant n_1\geqslant \ldots$ не может вечно убывать.

Т. к. $\mathbb N$ фундировано, то последовательность $n_0 \geqslant n_1\geqslant \ldots$ когда-нибудь стабилизируется, т. е. все члены после некоторого станут одинаковы. Но если $n_k=n_{k+1}=n_{k+2}=\ldots$, то значит неравенство $a_k>a_{k+1}>a_{k+2}>\ldots$ должно осуществляются за счёт того, что $n_k$-й член $a_k$ больше $n_k$-го члена $a_{k+1}$ и т. д. Из-за фундированности $\mathbb N$, такое не может продолжаться вечно: когда-нибудь $a_{k+l}>a_{k+l+1}$ будет выполнено за счёт $(n_k-1)$-го члена. Таким образом, последовательность $n_0 \geqslant n_1\geqslant \ldots$ когда-нибудь станет нулю и дальше меняться не будет. Но это значит, что последовательность $a_0>a_1>\ldots$ конечна. Ч. т. д.

---
Буду признателен за проверку (вышенаписанных задач тоже).

[Null]

Почему $n_1\geqslant n_2$ ?

[caxap]

Извиняюсь, ошибся. А как там можно ещё попробовать доказать?

-- Пт окт 08, 2010 15:41:05 --

Кстати, 109-я задача очень похожа на эту. Точно в 109-ой множество не фундировано?

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

caxap в сообщении #360158 писал(а):

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

Кстати, какой там ординальный тип у порядка получается, $\omega^\omega$, или что-то другое?

[caxap]

(Оффтоп)

Профессор Снэйп
это вы мне? Без понятия. Я даже не знаю, что такое ординальный тип.

[caxap]

Ладно, пока забью на предыдущие. Вот эта, по-моему, простая:

111. Рассмотрим множество всех многочленов от одной переменной $x$, коэффициенты которых -- натуральные числа. Упорядочим его так: многочлен $P$ больше многочлена $Q$, если $P(x)>Q(x)$ для достаточно больших $x$. Покажите, что это определение задаёт линейный порядок и что получающееся упорядоченное множество фундировано.

Сначала покажем, что порядок линейный. Действительно, какие бы мы многочлены $P,Q$ ни взяли, всегда при достаточно больших $x$ будет $P(x)\leqslant Q(x)$ или наоборот.
Теперь покажем фундированность. Возьмём произвольное непустое подмножество $X$ таких многочленов. Выберем из них многочлены минимальной степени $p$, а из них выберем многочлен $R(x)$ с минимальным коэффициентом при $x^p$. Это можно сделать, ибо $\mathbb N$ фундировано. $R(x)$ будет минимальным элементом в множестве $X$: при достаточно больших $x$ все остальные многочлены будет больше $R(x)$ -- либо за счёт больше степени, либо за счёт большего коэффициента при $x^p$, если рассматриваемый многочлен той же степени, что и $R(x)$. Ну а раз есть минимальный элемент в любом непустом множестве, то множество всех многочленов с натуральными коэффициентами фундировано.

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

caxap в сообщении #361383 писал(а):

Выберем из них многочлены минимальной степени $p$, а из них выберем многочлен $R(x)$ с минимальным коэффициентом при $x^p$.

Многочлен $R$ может оказаться не единственным. К примеру, что Вы возьмёте в качестве $R$ для множества многочленов $\{ x^2 + 2x + 1, x^2 + x + 100 \}$?

-- Ср окт 13, 2010 15:30:42 --

P. S. Вообще, у задачи 111 есть очень изящное решение. Замените в каждом многочлене $x$ на $\omega$ и переставьте местами множители в каждом одночлене, получите ординал $\omega^\omega$ с тем же порядком

-- Ср окт 13, 2010 15:55:37 --

caxap в сообщении #360187 писал(а):

Я даже не знаю, что такое ординальный тип.

Для каждого вполне упорядоченного множества $\langle W, < \rangle$ существует единственный ординал $\alpha$, такой что $\langle W, < \rangle \cong \langle \alpha, \in \rangle$. Этот ординал называется ординальным типом.

[Null]

Задача 110 = задаче 111
$(\alpha_1,\dots,\alpha_k,0,\dots)=x^{\alpha_1-1}+\dots+x^{\alpha_k-1}$

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

Null в сообщении #361593 писал(а):

Задача 110 = задаче 111
$(\alpha_1,\dots,\alpha_k,0,\dots)=x^{\alpha_1-1}+\dots+x^{\alpha_k-1}$

В-принципе да, только свободный член в многочленах пропадает.

[Null]

хм $(1,1,1,1,1,0,0,0,\dots)=5$

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

Null в сообщении #361607 писал(а):

хм $(1,1,1,1,1,0,0,0,\dots)=5$

В $\alpha_i -1$ единицу не заметил

[caxap]

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

Многочлен $R$ может оказаться не единственным. К примеру, что Вы возьмёте в качестве $R$ для множества многочленов $\{ x^2 + 2x + 1, x^2 + x + 100 \}$?

Извиняюсь. Значит так: если первые коэффициенты равны, сравниваем вторые; если они равны -- третьи и т. д. В вашем примере за $R(x)$ возьмём второй многочлен.

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

P. S. Вообще, у задачи 111 есть очень изящное решение. Замените в каждом многочлене $x$ на $\omega$ и переставьте местами множители в каждом одночлене, получите ординал $\omega^\omega$ с тем же порядком

Что такое $\omega$? Вы тут все умные конечно, но книжка Верещагина, Шеня -- первая книжка по теории множеств, которую я читаю и многие умные слова, которыми тут раскидываются я не понимаю.

(Оффтоп)

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

caxap в сообщении #360187 писал(а):

Я даже не знаю, что такое ординальный тип.

Для каждого вполне упорядоченного множества $\langle W, < \rangle$ существует единственный ординал $\alpha$, такой что $\langle W, < \rangle \cong \langle \alpha, \in \rangle$. Этот ординал называется ординальным типом.

Спасибо. Интересно. В В.Ш., наверное, про это вскоре что-то будет.

Null в сообщении #361593 писал(а):

Задача 110 = задаче 111

Ок, но 110 я так и не решил.