2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6  След.
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение30.09.2010, 21:34 
Заслуженный участник


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

 Профиль  
                  
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение30.09.2010, 21:41 
Заслуженный участник
Аватара пользователя


07/01/10
2015
Null
Ага. Спасибо.

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

(Оффтоп)

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

 Профиль  
                  
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение01.10.2010, 23:37 
Заслуженный участник
Аватара пользователя


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

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

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

 Профиль  
                  
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение02.10.2010, 10:58 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение02.10.2010, 11:18 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение05.10.2010, 10:49 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение05.10.2010, 11:41 
Заслуженный участник
Аватара пользователя


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

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

 Профиль  
                  
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение05.10.2010, 11:51 
Заслуженный участник


13/12/05
4548
caxap в сообщении #358126 писал(а):
Надеюсь я вас не замучал :wink: Я не буду ждать окончания обсуждения предыдущей задачки, а сразу опубликую решение ещё одной (наверное, последней из этой темы).

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

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

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

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

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

 Профиль  
                  
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение05.10.2010, 20:51 
Заслуженный участник
Аватара пользователя


07/01/10
2015
Хорхе
Спасибо. Посмотрел на формулу чисел Белла и тут же вспомнил (из Конкретной Математики), что числа Стирлинга для подмножеств $\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$ можно было взять любое плотное счётное всюду плотное множество...

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

 Профиль  
                  
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение05.10.2010, 22:29 
Заслуженный участник
Аватара пользователя


07/01/10
2015
Последняя задачка:

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


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

б) :?:

 Профиль  
                  
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение05.10.2010, 22:42 
Заслуженный участник
Аватара пользователя


14/02/07
2648
а) да! (Довольно неожиданно, не так ли?)
Хорхе в сообщении #357615 писал(а):
немало математических фактов противоречат интуиции

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

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

 Профиль  
                  
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение05.10.2010, 23:25 
Заслуженный участник
Аватара пользователя


07/01/10
2015
Хорхе в сообщении #359549 писал(а):
а) да! (Довольно неожиданно, не так ли?)

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

Хорхе в сообщении #359549 писал(а):
В а) легко придумать пример, если вместо $\mathbb N$ взять $\mathbb Q$.

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

 Профиль  
                  
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение05.10.2010, 23:36 
Заслуженный участник
Аватара пользователя


14/02/07
2648
caxap в сообщении #359561 писал(а):
Ну как же? Элементы одной мощности, по-моему, несравнимы:

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

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

 Профиль  
                  
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение06.10.2010, 08:59 
Заслуженный участник


13/12/05
4548
caxap в сообщении #358126 писал(а):
90. Дано бесконечное ЧУМ $X$. Докажите, что в нём всегда найдётся либо бесконечное подмножество попарно несравнимых элементов, либо бесконечное подмножество, на котором индуцированный порядок линеен.

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

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

 Профиль  
                  
 
 Re: Верещагин, Шень. Эквивалентность и порядок
Сообщение06.10.2010, 10:39 
Заслуженный участник


12/08/10
1651
Как нас учили: возьмем $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$ (как мне уже объяснили нужна аксиома выбора) . Какого-то типа бесконечно много, возьмем элементы этого типа. Получим ответ.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 81 ]  На страницу Пред.  1, 2, 3, 4, 5, 6  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group