Максимальное количество элементов в сигма-алгебре

[Бабай]

Пусть дано семейство из $n$ множеств. Какое максимальное количество элементов содержит $\sigma$-алгебра, порождённая этим семейством? Как это эффективней всего подсчитать?

[мат-ламер]

$n$ множеств в общем положении порождают $2^n-1$ "элементарных" непересекающихся множеств. Теперь каждое из этих элементарных множеств может принадлежать, а может и не принадлежать множествам, из которых состоит $\sigma-$алгебра. Что-то много элементов получается.

[Бабай]

Я не уверен, но вроде бы "на пальцах" вот так получилось:
Пусть $\mathcal{F}=\{A_1,...,A_n\}$, и все они пересекаются. Тогда по определению $\emptyset,\Omega\in\sigma(\mathcal{F})$ - уже два.
Далее по одному множеству можно выбрать ${n \choose 1}=n$ раз. Каждое из них дает и дополнение, т.е. всего $2n$ множеств.
Пересечение из $k$, $2\le k \le n$ множеств можно выбрать $n \choose k$ раз. Причём для каждого $k$ на любом месте в пересечении может стоять либо $A_i$ либо $A_i^c$, $2\le i \le k$, то есть имеем ${n \choose k}2^k$ множеств. Опять же, с каждым пересечением из $k$ множеств, дополнение к этому пересечению входит в $\sigma(\mathcal{F})$, то есть надо домножить на два.

Итого : $2(n+1)+\sum_{k=2}^{n} {n \choose k}2^{k+1}$.

[мат-ламер]

Поскольку у Вас достаточно сложно записано, я не проверял. Но можно проверить на конкретном примере. Пусть $n=3$. Из того, что я написал, результат $2^{2^n-1}=2^7=128$. У Вас получается $8+3*8+16=48$. Нарисуйте чертёж и проверьте.

[Бабай]

Какой чертёж?

Кстати по вашей формуле для $n=2$ получается всего 8 множеств - по-моему слишком мало.

[IE]

для n=2, имхо, 8 самое то:${\emptyset,\Omega,A\overline{B},\overline{A}B,AB,A,B,A\overline{B}\cup\overline{A}B}$

[Бабай]

нет, их 16...Вы забыли взять к каждому (кроме пустого) из множеств дополнение. Кроме того, не хватает $A^c \cap B^c$ со его дополнением.

Я со своей "формулой" тоже просчитался.

А ларчик действительно просто открывался!

Вопрос: А что такое лето?

или, что то же самое:

Сколькими способами можно покрасить $2^n-1$ дед морозов в два цвета (красный и зелёный)?

Ответ: $2^{2^n-1}$. А теперь, и это самое главное, умножаем на два!

Итого: $2^{2^n}$.

Спасибо, Мат-ламер, за наводку!

[IE]

Бабай в сообщении #327830 писал(а):

Вы забыли взять к каждому (кроме пустого) из множеств дополнение.

Если просят построить сигма-алгебру порожденную двумя множествами, то $\Omega=A\cup B$. Потому как ни про какие еще точки вне A и B я не знаю.

[Бабай]

Ой, да, в условии оплошался...думал что понятно будет, что это какие-то подмножества из $\Omega$. Извиняюсь.

Ну да, а так вы правы.