Теория множеств

[Asker Tasker]

Пожалуйста, подскажите, как одолеть следующие доказательства?

3) Пусть множество А содержит n элементов, а его подмножество В содержит k элементов. Сколько существует множеств С, для которых $ A \subset B \subseteq C $?

Я размышлял так (может, неправильно). Зафиксируем множество В. Тем самым мы зафиксируем некоторые k элементов из n. Соответственно n-k останется, и каждый из них может поучаствовать в формировании множества С. Рассмотрим множества, получаемые из множества В присоединением одного из n-k элементов. Таких множеств может быть создано $ C_{n-k}^{1} $ штук. Множеств С, получаемых путём присоединения двух элементов, может быть создано $ C_{n-k}^{2} $ штук. И так далее, вплоть до самого множества В - оно же единственное из $ C_{n-k}^{n-k} $ множеств С, получаемых из В добавлением всех n-k элементов.

Тогда ответ $C_{n-k}^{1} + C_{n-k}^{2} + ... + C_{n-k}^{n-k} = \sum_{i = 1}^{n-k} C_{n-k}^{i}$. Правилен ли он? И если да, то можно ли решать проще?


4) Пусть А - непустое конечное множество. Подмножеств множества А, имеющих чётную мощность, столько же, сколько имеющих нечётную.

Первый вопрос: учитываем ли мы пустое множество? Ведь его можно считать как множество нулевой, то есть чётной мощности, а можно не учитывать вообще. Мне кажется, что учитывать нужно. Как Вы считаете?

Что до решения, то я сначала пробовал как-то через сочетания, но не вышло. В книжке дано указание зафиксировать некоторый элемент а из А и объединять в пары подмножества, которые отличаются только в точке а. Ну, зафиксировали мы его. Вот первые два множества: "чётное" и "нечётное": $ \varnothing $ и $ \left{ a \right} $. А вот как дальше?

[ewert]

Asker Tasker в сообщении #585069 писал(а):

множество А содержит n элементов, а его подмножество В содержит k элементов. Сколько существует множеств С, для которых $ A \subset B \subseteq C $?

Кто кого содержит-то?

Asker Tasker в сообщении #585069 писал(а):

Первый вопрос: учитываем ли мы пустое множество?

Учитываем, иначе равенства не будет. А так оно будет просто по биному Ньютона, т.к. $(1-1)^n=0$.

[Asker Tasker]

Да, извиняюсь. Очепятка вышла, а я своё же условие не перечитал..
Правильное условие такое:
$B\subset C \subseteq A$


Да, по биному оно легко выходит. Смена знаков при соответствующих сочетаниях - и всё такое. Но в книжке предлагают по-другому доказывать: сначала доказываем утверждение, которое я написал, а соответствующее равенство для чётных-нечётных сочетаний, взятых с противоположными знаками, получаем как следствие. Не подскажете, как таким образом доказать можно? А то я пока в трансе.

[ewert]

Asker Tasker в сообщении #585183 писал(а):

Но в книжке предлагают по-другому доказывать:

Это глупость. Бином в совокупности с просто сочетаниями принято в приличном опчестве доказывать более-менее одновременно.

Asker Tasker в сообщении #585183 писал(а):

Правильное условие такое:
$B\subset C \subseteq A$

Тогда Ваша идеология (лень разбираться, в которую сторону Вы там единичку похерили) -- правильна, но неразумна. Достаточно того, что множество всевозможных дополнений до того Бэ -- это множество всех подмножеств из эн минус ка элементов. Т.е. два в соотв. степени (с точностью до той самой единички, обусловленной строгостью одного из вложений).

[Asker Tasker]

ewert в сообщении #585186 писал(а):

Тогда Ваша идеология (лень разбираться, в которую сторону Вы там единичку похерили) -- правильна, но неразумна. Достаточно того, что множество всевозможных дополнений до того Бэ -- это множество всех подмножеств из эн минус ка элементов. Т.е. два в соотв. степени (с точностью до той самой единички, обусловленной строгостью одного из вложений).

Сглупил. Вы правы: такое решение гораздо проще.

ewert в сообщении #585186 писал(а):

Это глупость.

Что ж, книжку писал не я. Может, у меня или у Вас в книжке было бы иначе. Но у авторов: Шеня и Верещагина всё именно так.
В конце концов доказывать теорему Пифагора через диффуры - это тоже для кого-то глупо. А ведь доказательство имеется. И кому-то оно интересно. И кто-то, знакомясь с ним, может быть, чему-то научился. Я вот на этих доказательствах пытаюсь учиться. Хотя как, например в случае с 4-ой задачей, не очень получается.

[Asker Tasker]

Что ж, третья задача отпала. Спасибо ewert'у.
А по четвёртой у кого-нибудь идеи?
Заранее спасибо.

[ИСН]

post576874.html

[Asker Tasker]

Kallikanzarid в сообщении #576975 писал(а):

Keter
Установите явно биекцию между четными и нечетными подмножествами.

Это последнее сообщение из темы, ссылку на которую Вы дали.

Вот именно это я и пытаюсь сделать, но пока не выходит

[ИСН]

Ладно, с Вами можно другим языком. Сколько у n-элементного множества будет k-элементных подмножеств?

-- Сб, 2012-06-16, 17:27 --

Стоп, так через бином Вы это уже сделали! Тогда зачем всё это?

[Asker Tasker]

Цитата:

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

Хотел решить таким образом. Потом на основе этого выводится значение развёрнутого бинома для случая a = 1, b = -1. А уже потом - я так понимаю опять через работу с подмножествами - предлагается доказать сам бином.

Просто не встречал раньше вывода формул для сочетаний не через сами формулы (факториалы и т.д.), а через работу с подмножествами. Стало интересно - решил поиграться. Вот зачем :)

[ИСН]

Хотите явную биекцию? Извольте. Берём подмножество. Если в него входит элемент номер 1, то выкидываем его из него. А если не входит, то добавляем. Получилось другое подмножество. Вот моя биекция.

[Asker Tasker]

Недодумал. Спасибо, ИСН.