Верещагин, Шень. Эквивалентность и порядок

[Null]

На множестве $B$ некоторые элементы могут быть уже упорядоченны.

[caxap]

Null
Ага. Спасибо.

Я не знаю, можно ли так поступать в доказательствах, но попробую: если $B$ является чумом, то действовать с ним также, как и с $A$, т. е. получается как бы рекурсия. Раз множества все конечные, то рекурсия когда-нибудь оборвётся.

(Оффтоп)

Где-то я видел доказательсвта, оформленные в виде "программы". Вроде бы даже видел с рекурсией. (Не у Кнута ли?)

[caxap]

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

90. Дано бесконечное ЧУМ $X$. Докажите, что в нём всегда найдётся либо бесконечное подмножество попарно несравнимых элементов, либо бесконечное подмножество, на котором индуцированный порядок линеен.

Разобьём $X$ на линейно упорядоченные подмножества (напр. для конечного $X=\{a,b,c,d\}$, где $a\leqslant b$, $c\leqslant d$ таких подмножеств будет два: $\{a,b\}$, $\{c,d\}$). То есть элементы одного подмножества не сравнимы с элементами другого, а внутри каждого подмножества все элементы сравнимы. Если таких подмножеств конечное число, то, раз $X$ бесконечно, хотя бы одно из них должно быть бесконечным. Если же таких подмножеств бесконечное число, то взяв по одному элементу (напр. минимальному) из каждого подмножества, получим бесконечное множество попарно несравнимых элементов.

[Хорхе]

Deja vu. Поищите в форуме по "Рамсею" и его падежам.

[caxap]

Хорхе
Да, нашёл. Но там используется теорема Рамсея, о которой я не знаю. Мне хотелось бы решать задачки только в рамках того, что уже пройдено по В.Ш. (авторы, видимо, это учитывают при составлении задач). А чем плохо моё доказательство?

А предыдущая задачка верно решена?

[caxap]

79. Сколько различных отношений эквивалентности существует на множестве $\{1,2,3,4,5\}$.

Вроде бы простая задача, а не соображу.
Каждое отношение эквивалентности можно описать как отношение "лежать в одном подмножестве", если $X=\{1,2,3,4,5\}$ разбить на непересекающиеся подмножества. Никак не получается посчитать число таких разбиений. Не подскажите, куда думать?

[Хорхе]

Да напрямую посчитать: количество разбиений на 1,2,3,4,5 множеств. Проще ничего не знаю.

(Это называется числом Белла $B_5$, если что. Есть рекуррентная формула, но не уверен, что она лучше для маленьких $n$. Можно еще через экспоненциальную производящую функцию, но для этого ее надо знать.)

[Padawan]

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

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

90. Дано бесконечное ЧУМ $X$. Докажите, что в нём всегда найдётся либо бесконечное подмножество попарно несравнимых элементов, либо бесконечное подмножество, на котором индуцированный порядок линеен.

Разобьём $X$ на линейно упорядоченные подмножества. То есть элементы одного подмножества не сравнимы с элементами другого, а внутри каждого подмножества все элементы сравнимы.

Такое разбиение невозможно, например, для $X=\{a,b,c\}$ с $a\leqslant b$, $a\leqslant c$.

-- Вт окт 05, 2010 14:11:10 --

http://dxdy.ru/topic19246.html Как-то в той теме с доказательством перемудрили. По-моему всё гораздо проще. Не буду писать, пусть сахар сам решит.

[caxap]

Хорхе
Спасибо. Посмотрел на формулу чисел Белла и тут же вспомнил (из Конкретной Математики), что числа Стирлинга для подмножеств $\left\{{n\atop k}\right\}$ -- это число способов разделить $n$-элементное множество на $k$ непустых подмножеств. Т. е. для решения задачи надо просто просуммировать их по $k$ от $1$ до $n$. Получается $52$.

Padawan в сообщении #359338 писал(а):

Такое разбиение невозможно, например, для $X=\{a,b,c\}$ с $a\leqslant b$, $a\leqslant c$.

Ага, спасибо за исправление.
Я всё же нашёл в Верещагине, Шене теорему Рамсея:

Множество всех $k$-элементных подмножеств бесконечного множества $A$ разбито на $l$ классов. Найдётся бесконечное множество $B\subset A$, все $k$-элементные подмножества которого принадлежат одному классу.

(Вопрос про формулировку)

Я видел несколько формулировок т. Рамсея и все разные. Нет ли такой, которая легче всего понимается и запоминается?

При $k=l=2$ сразу получаем решение 90-й задачи (два класса -- это попарно сравнимых и попарно несравнимых).

------

(Вопрос не по теме)

Вопрос не по теме: в чём разница между "всюду плотно" и "плотно"? В В.Ш. есть определение плотного лума -- это когда между любыми двумя элементами есть третий (т. е. нет соседних элементов).
Просто в той же книжке встретил такое предложение:

Цитата:

... вместо множества $\mathbb Q$ можно было взять любое плотное счётное всюду плотное множество...

То есть тут либо описка, либо "всюду плотно" и "плотно" -- разные понятия.

[caxap]

Последняя задачка:

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

а) Нет. Чтобы получить лум, нужно взять по одному элементу каждой мощности из $\mathcal P(\mathbb N)$ (элементы $\mathcal P(\mathbb N)$ одной мощности не сравнимы). Т. е. получим только счётное число элементов.

б)

[Хорхе]

а) да! (Довольно неожиданно, не так ли?)

Хорхе в сообщении #357615 писал(а):

немало математических фактов противоречат интуиции

б) тем более да.

В а) легко придумать пример, если вместо $\mathbb N$ взять $\mathbb Q$. Похожий (как ни абсурдно это звучит) пример подойдет и для б).

[caxap]

Хорхе в сообщении #359549 писал(а):

а) да! (Довольно неожиданно, не так ли?)

Ну как же? Элементы одной мощности, по-моему, несравнимы: $a\subset b$, когда $|a|=|b|$ возможно только, когда они равны (иначе будет элемент, на который они отличаются). Если же брать в лум по элементу из каждой мощности, их получится счётное число, ибо каждому элементу лума мощности $k$ соответствует ровно одно натуральное число $n=k$, и наоборот.

Хорхе в сообщении #359549 писал(а):

В а) легко придумать пример, если вместо $\mathbb N$ взять $\mathbb Q$.

М... не соображу. А что принципиально изменится, если заменить натуральные на рациональные? И там счётно и там. "Плотность" тоже, по-моему, ни на что не влияет (кстати, не могли бы вы ответить на вопрос из "оффтопа" про плотные множества?). Отсутствие наим. и наиб. элемента -- тоже...

[Хорхе]

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

Ну как же? Элементы одной мощности, по-моему, несравнимы:

Это если мощность конечная. А ежели бесконечная, и не такое бывает.

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

[Padawan]

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

90. Дано бесконечное ЧУМ $X$. Докажите, что в нём всегда найдётся либо бесконечное подмножество попарно несравнимых элементов, либо бесконечное подмножество, на котором индуцированный порядок линеен.

Приведу своё решение. Предположим, что не существует бесконечного подмножества, на котором индуцированный порядок линеен. Тогда каждая цепь (линейно упорядоченное подмножество) конечна. Так как множество $X$ бесконечно, то нетрудно построить счетное семейство попарно непересекающихся конечных цепей, каждая из которых оканчивается максимальным элементом исходного ЧУМа. Множество концевых элементов этих цепей и будет искомым бесконечным подмножеством, никакие два элемента в котором несравнимы.

Upd Это неправильное доказательство Каждая из цепей оканчивается максимальным элементом не всего множества, а $X$ минус уже построенные цепи.

[Null]

Как нас учили: возьмем $A_1$-само множество $a_1$- любое из $A_1$
Если есть $a_i\in A_i$ и $A_i$-бесконечное возьмем 2 подмножества $A_i/\{a_i\}$: сравнимых с $a_i$ и не сравнимых. Одно из них бесконечно. Обозначим его $A_{i+1}$. В нем есть $a_{i+1}$. Назовем его 1ого типа если оно сравнимо с $a_i$, иначе второго.

Получим бесконечную последовательность из $a_i$ (как мне уже объяснили нужна аксиома выбора) . Какого-то типа бесконечно много, возьмем элементы этого типа. Получим ответ.