Кольцо, порождённое системой множеств

[Nick111]

Доброго времени суток Вам.
У меня не получается разобраться с одним вопросом и я очень надеюсь на Вашу помощь.

Вопрос такой. Предположим, что зафиксировано какое-то множество $\Omega$ и задана непустая система его подмножеств: $S \subset 2^\Omega$. Кольцо множеств, порождённое системой $S$ определим как пересечение всех колец, содержащихся в $2^\Omega$ и содержащих систему $S$. Затем доказываем, что такое кольцо действительно существует. Но мне непонятен "состав" кольца, т.е. как при заданной системе $S$ я могу это кольцо построить? Как сконструировать из множеств системы $S$ множества её минимального кольца? Может, есть какой-то алгоритм действия хотя бы для случая конечной системы $S$?

[Joker_vD]

Это кольцо, которое с пересечениями и симметрической разностью? Ну, так и строите:

1. Полагаем $S_0=S$, $S_i=\varnothing$;
2. Для каждой пары множеств $A,B\in S_0$ добавляем $A,B,A\cap B,A\mathbin{\triangle} B$ в $S_1$;
3. Для каждой пары множеств $A,B\in S_1$ добавляем $A,B,A\cap B,A\mathbin{\triangle} B$ в $S_2$;
4. Для каждой пары множеств $A,B\in S_2$ добавляем $A,B,A\cap B,A\mathbin{\triangle} B$ в $S_3$;
5. ???
6. PROFIT!

-- Сб фев 23, 2013 16:02:12 --

Ну, что $\bigcup\limits_{i=0}^{\infty}S_i$ и будет наименьшим кольцом, думаю, ясно.

[Nick111]

Да, вроде бы ясно.
Спасибо.

А можно ли доказать, что для конечной системы множеств алгоритм прервётся за конечное число шагов? Есть ли гарантии того, что у нас не будут на каждом шаге добавляться новые и новые множества?

[VAL]

Nick111 в сообщении #687319 писал(а):

А можно ли доказать, что для конечной системы множеств алгоритм прервётся за конечное число шагов? Есть ли гарантии того, что у нас не будут на каждом шаге добавляться новые и новые множества?

Ну у Вас же конечное число множеств.
Если у нас изначально $n$ множеств, используя пересечение и симметрическую разность (и даже дополнительно объединение, обычную теоретико-множественную разность и дополнение), можно получить не более чем $2^{2^n}$ множеств.

Здесь прямая аналогия с классами эквивалентных формул исчисления высказываний от $n$ высказывательных букв.

[Nick111]

К сожалению, мои познания мат. логики слишком скромные, чтобы понять аналогию.
Не могли бы Вы немного подробнее объяснить, как можно получить это число? Буду очень благодарен, если посоветуете, где об этом можно почитать в доступной форме.
Я правильно понимаю, что вопрос как-то связан с конечными алгебрами?

[kakaskin]

число булевых функций от n переменных.
Верещагин, Шень. Начала теории множеств - тут задачка была на эту тему.