Задача о количестве множеств

[Asker Tasker]

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

Задача
Сколько различных выражений для множеств можно составить из n переменных с помощью многократно используемых операций пересечения, объединения и разности? (Два выражения считаются одинаковыми, если они равны при любых значениях переменных). Ответ должен получиться следующий: $2^{2^{n}-1}$

Решение
Воспользуемся диаграммами Эйлера-Венна.
Пусть имеются два множества. Их объединение можно представить в виде трёх непересекающихся "элементарных" (как выразились в соответствующей теме форума) частей. Тут возникает первый вопрос: а что, если одно множество является подмножеством другого? Ведь тогда таких частей уже две или я не так рассуждаю?

Пусть теперь имеются три множества. Тогда таких частей семь (при условии, что ни одна из них не пустая).
В общем случае n множеств, допуская, что все элементарные части не пусты, получим:
- части, принадлежащие только одному из множеств - их n штук ($C^{1}_{n}$);
- части, принадлежащие пересечению ровно двух множеств - их $C^{2}_{n}$ штук;
- и так далее, и так далее;
- части, принадлежащие пересечению всех n множеств - такая часть только одна - $C^{n}_{n}=1$

Учитывая, что из бинома Ньютона легко получается формула $C^{0}_{n} + C^{1}_{n} + C^{2}_{n} + ... + C^{n-1}_{n} + C^{n}_{n} = 2^{n}$ и что $C^{0}_{n}=1$, получаем: в случае n множеств, количество "элементарных частей" равно
$C^{1}_{n} + C^{2}_{n} + ... + C^{n-1}_{n} + C^{n}_{n} = 2^{n} - 1$

Теперь, насколько я понимаю, любое множество, которое можно получить из наших n исходных, является объединением некоторого количества наших "элементарных множеств" И все эти множества различны (при условии, что все "элементарные" не пусты. Каждое из "элементарных" может либо входить, либо не входить в это объединение, поэтому общее число возможных объединений, а значит, и ответ нашей задачи - $2^{2^{n}-1}$

Пожалуйста, подскажите, как доказать утверждение предыдущего абзаца?
И, в частности, как доказать, что все полученные множества различны?
И можно ли перевести это решение (если оно правильно) на более формальный язык?
И что делать (с ранее упомянутым) случаем, в котором какие-то из "элементарных частей" пусты? Можно ли откинуть требование "непустоты"? Ведь нам нужно посчитать количество именно различных множеств.

Заранее всем большое спасибо!

[Xaositect]

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

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

У по определению одинаковости выражений можно рассматривать любые наборы множеств.

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

Пожалуйста, подскажите, как доказать утверждение предыдущего абзаца?
И, в частности, как доказать, что все полученные множества различны?

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

Если заинтересуетесь, почитайте что-нибудь по булевой алгебре, эта задача с ней достаточно сильно связана.

[Asker Tasker]

А что такое глубина формулы? Количество множеств, в ней фигурирующих?


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

[Xaositect]

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

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

Элементарные части есть, просто они пустые.

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

Гораздо более интересная задача получится, если использовать только объединения и пересечения, а разность запретить.

Для $n=8$ ответ тут: A000372. Для $n=9$ ответ до сих пор не известен

[Asker Tasker]

Xaositect,
я понимаю, что они пустые, но ведь ответ-то меняется: уже не 8, а 4 получается. Где же недочёт?! Я уверен, что где-то он есть, но пока не могу понять, где. Подскажите, пожалуйста.

-- 12.06.2012, 01:58 --

(Оффтоп)

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

Гораздо более интересная задача получится, если использовать только объединения и пересечения, а разность запретить.

Для $n=8$ ответ тут: A000372. Для $n=9$ ответ до сих пор не известен

Да мне бы с этой задачей до конца разобраться
Но всё-таки. В случае двух операций, что, непосредственным поиском решаем?

[Xaositect]

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

я понимаю, что они пустые, но ведь ответ-то меняется: уже не 8, а 4 получается. Где же недочёт?! Я уверен, что где-то он есть, но пока не могу понять, где. Подскажите, пожалуйста.

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

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

Если не подбирать множества специально, чтобы было 4 - будет 8.

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

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

Да мне бы с этой задачей до конца разобраться

Вам, собственно, надо найти количество элементов свободной алгебры Ершова (то есть дистрибутивной решётки с относительными дополнениями) с $n$ порождающими. Оно равно половине количества элементов свободной булевой алгебры с $n$ порождающими. Последнее, в свою очередь, равно количеству всех булевых функций от $n$ переменных, которых, очевидно, $2^{2^n}$.

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

Попробуйте проанализировать такую конструкцию.

Берём $X = \{x_1, \ldots, x_n \}$ - множество, составленное из $n$ элементов. Для него берём $Y = \mathcal{P}(X)$ - множество всех подмножеств $X$. Теперь для каждого $i \in [1,n]$ пусть $Y_i = \{ y \in Y : x_i \in y \}$.

1) Какие множества можно соорудить при помощи упомянутых трёх операций из $Y_1, \ldots, Y_n$? Покажите, что их ровно $2^{2^n - 1}$.

2) Обозначим через $A$ совокупность всех множеств, получаемых при помощи трёх операций из $Y_1, \ldots, Y_n$. Пусть $B$ - произвольная система множеств, замкнутая относительно наших операций. Пусть $b_1, \ldots, b_n$ - произвольные элементы $B$. Докажите, что отображение $Y_i \mapsto b_i$ можно продолжить до отображения из $A$ в $B$, сохраняющего все три операции.

Первый пункт показывает, что $2^{2^n-1}$ - нижняя оценка для числа неэквивалентных выражений. Второй пункт показывает, что эта оценка точна.

[xmaister]

(Оффтоп)

См. также К. Куратовский, А. Мостовский- теория множеств, глава 1, Конституенты.

[Asker Tasker]

Всем спасибо. Будем трудиться дальше)