Мощность алгебры событий

[Jiggy]

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

Интуитивно это понятно. Со строгим доказательством испытываю трудности.

Ход мыслей был в двух направлениях.
1) Минимальная алгебра состоит из двух подмножеств: \left\lbrace \varnothing, \Omega \right\rbrace, то есть это степень двойки. При добавлении множества $A$ нужно добавить также и дополнение к нему, то есть получится алгебра: \left\lbrace \varnothing, \Omega, A, \overline{A} \right\rbrace. При добавлении еще одного множества $B$ нужно добавить дополнение, все пересечения и объединения: \left\lbrace \varnothing, \Omega, A, \overline{A}, B, \overline{B}, A\cap B, A\cup B \right\rbrace. Но здесь не учтены дополнения пересечения и объединений и другие порождаемые элементы. Думал в сторону доказательства по индукции. База индукции верна, предположим, что при наличии $n$ чистых множеств порождается алгебра мощности степени 2, докажем, что при добавлении очередного множества степень также будет 2. Но здесь тупиковый путь у меня.

2) Возьмем множества $A_1, ..., A_n$ и сформируем из них алгебру. Для этого нужно сформировать множество из исходных множеств, их дополнений, всевозможных пересечений и объединений, а также добавить пустое множество и все пространство элементарных исходов.
Кол-во всевозможных пересечений:

$$\sum\limits_{k=2}^{n} \binom{n}{k} = 2^n - n -1$$

Тоже самое с объединениями. Исходных множеств $n$, а пустое и полное дают 2. Итого: $|\mathcal{A}| = (2) + (2^n - n -1) + (2^n - n -1) + (n) + (n) = 2^{n+1}$, что является степенью двойки.

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

Собственно прошу подсказать, какой из этих 2 путей более корректный для дальнейшего копания. А если нужно избрать другой способ доказательства, то прошу направить. Заранее спасибо.

[мат-ламер]

Можно ввести понятие элементарных множеств. То есть, это система непересекающихся множеств такая, что каждое множество нашей алгебры множеств есть объединение некоторой конечной системы элементарных множеств. Пусть этих множеств $n$ штук. Тогда всевозможных объединений конечного числа их есть $2^n$ штук.

[Jiggy]

мат-ламер

Другими словами, мы говорим о пространстве элементарных исходов $\Omega$ размера $n$. И каждое множество(элемент) в алгебре есть подмножество множества $\Omega$. Всевозможных таких подмножеств, действительно, $2^n$. Но это пример максимальной алгебры. Минимальная алгебра состоит из 2 элементов, максимальная из $2^n$. Как же все-таки показать, что любая конечная алгебра содержит степень 2 элементов?

Если я неправильно понял, поправьте, пожалуйста.

[mihaild]

Так действительно не получится - нам ничего не известно про структуру наших событий.
1. Пусть в алгебре можно выбрать $k$ непустых попарно непересекающихся множеств, таких что любое непустое множество из алгебры представляется как их объединение. Сколько тогда множеств в алгебре?
2. Всегда ли в конечной алгебре можно найти такой набор множеств?

[Jiggy]

mihaild

1. Если любое множество представимо в виде объединения, то тогда в алгебре должны быть всевозможные объединения этих $k$ непустых и попарно непересекающихся множеств. Таких объединений с учетом самих этих множеств и пустого множества $2^k$, которое получаем как $1 + k + \sum\limits_{i=2}^{k}\binom{k}{i}$

2. Именно в алгебре не всегда. Например, минимальная алгебра из пустого множества и всего пространства $\Omega$. В любой другой неминимальной алгебре, кажется, это можно сделать. Если добавить в минимальную алгебру произвольное непустое множество $A$, то оно породит еще и $\overline{A}$, это как раз и будут 2 искомых множествa, порождающих алгебру мощностью $2^k = 4$. Если же добавить еще одно множество $B$, то два случая возникает.

Если $A \cap B = \varnothing$, то тогда $k = 3$, а именно: $A, B, \overline{A} \cap \overline{B}$.
Если $A \cap B \ne \varnothing$, то тогда $k = 4$, а именно: $A \cap \overline{B}, \overline{A} \cap B, A \cap B, \overline{A} \cap \overline{B}$.

Получается, что если мы можем выбрать из алгебры конечное число непустых попарно непересекающихся множеств, то все остальные являются конечным объединением определенного количества множеств из такого набора, правильно?

[mihaild]

Jiggy в сообщении #1519490 писал(а):

Например, минимальная алгебра из пустого множества и всего пространства $\Omega$

А в ней почему нельзя? Возьмем $\Omega$ в качестве такого множества.

Jiggy в сообщении #1519490 писал(а):

Если добавить в минимальную алгебру

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

Jiggy в сообщении #1519490 писал(а):

Получается, что если мы можем выбрать из алгебры конечное число непустых попарно непересекающихся множеств, то все остальные являются конечным объединением определенного количества множеств из такого набора, правильно?

Тут написано что-то странное. Возьмем максимальную алгебру на 10-элементном множестве и выберем два разных одноэлементных. Их конечное число, они непусты и попарно не пересекаются, но остальные не являются их объединением.

[Jiggy]

mihaild в сообщении #1519491 писал(а):

А в ней почему нельзя? Возьмем $\Omega$ в качестве такого множества.

Да, согласен, ошибся.

mihaild в сообщении #1519491 писал(а):

Тут написано что-то странное. Возьмем максимальную алгебру на 10-элементном множестве и выберем два разных одноэлементных. Их конечное число, они непусты и попарно не пересекаются, но остальные не являются их объединением.

Да, неправильно написал. Если в алгебре ровно $k$ непустых попарно непересекающихся множеств, то тогда все остальные являются объединением некоторых из них (все пространство = полное объединение).


Для меня пока не очевидно в строгом смысле, как сформировать такие k множеств в общем случае. К примеру, у нас есть алгебра $\mathcal{A} = \left\lbrace A_1, ..., A_n \right\rbrace$. Не могу пока понять, как сформировать из произвольной алгебры нужные множества. Хочется опять итеративно здесь идти, отталкиваясь от множества $A_1$.

Графически это можно отобразить на плоскости, если представить полное пространство прямоугольником, а $A_i$ через круги, то тогда искомые множества - элементарные области деления всего пространства. И вроде бы так и есть, но в строгом смысле без визуализации не осознаю, как это сделать.

[marie-la]

Jiggy в сообщении #1519492 писал(а):

К примеру, у нас есть алгебра $\mathcal{A} = \left\lbrace A_1, ..., A_n \right\rbrace$. Не могу пока понять, как сформировать из произвольной алгебры нужные множества. Хочется опять итеративно здесь идти, отталкиваясь от множества $A_1$.

Вам ведь просто нужно выписать те множества алгебры, которые не содержат в себе другие. Берете $A_1$, сравниваете с остальными. Если оно не содержит в себе никакое другое, добавляете его в список элементарных "кирпичиков". Переходите к $A_2$.

[мат-ламер]

Jiggy в сообщении #1519492 писал(а):

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

Мы можем танцевать исходя не из нашей алгебры, а из пространства элементарных исходов, на котором разворачивается всё действие. На этом пространстве рассмотрим всевозможные системы $C_i$ непересекающихся множеств. Каждой такой системе сопоставим алгебру множеств $D_i$ , которую она порождает. Мы тем самым породим всевозможные алгебры множеств, которые можно задать на исходном пространстве элементарных исходов. Среди этих алгебр будет и алгебра $\mathcal{A}=D_j$ , которая для нас является исходной . Соответствующая ей система элементарных множеств $C_j$ и будет тем набором элементарных множеств, который мы ищем.

-- Сб май 22, 2021 07:19:16 --

marie-la в сообщении #1519498 писал(а):

Если оно не содержит в себе никакое другое,

А так даже проще.

[Jiggy]

Кажется, истина начинает проясняться. Попробую полностью описать 2 подхода на базе ответов выше.

1. Имеем пространство элементарных исходов $\Omega$ и рассматриваем всевозможные системы непересекающихся подмножеств $\mathrm{C_i}$ . Каждая из таких систем порождает алгебру $\mathrm{D_i}$. Рассмотрим лишь конечные алгебры. Если алгебра $\mathrm{D_i}$ порождена системой $\mathrm{C_i}$ мощности $k$, то мощность алгебры равна $2^k$ в силу ранее посчитанного количества всевозможных объединений. При этом наша конкретная конечная алгебра является одной из алгебр, которая порождена какой-то системой. Таким образом ее мощность является степенью 2.

2. Рассмотрим конечную алгебру $\mathcal{A} = \left\lbrace A_1, A_2, ..., A_n \right\rbrace\. Хотим выделить из нее систему непересекающихся непустых множеств, которые образуют порождающую систему. Идем итеративно. Рассматриваем $A_1$. Если она хоть с кем-то пересекается, переходим к $A_2$. Таким образом, находим первое множество $A_{k_1}$, которое ни с кем не пересекается. Дойдя до конца конечной алгебры получим ту самую систему $\left\lbrace A_{k_1}, ..., A_{k_m} \right\rbrace$. И так как наша исходная алгебра - реально алгебра, поэтому $n = 2^m$.


Кажется, нигде логических пробелов нет.

[marie-la]

Jiggy в сообщении #1519501 писал(а):

Рассматриваем $A_1$. Если она хоть с кем-то пересекается, переходим к $A_2$.

Она всегда пересекается, как минимум с $\Omega$. Надо, чтоб не имела собственных подмножетсв.

[Jiggy]

marie-la
Да, конечно. Другими словами, на текущей итерации $i$ рассмотрим непустое множество $A_i$ и какое-то другое непустое $A_j$. Тогда если $A_i \cap A_j \ne \varnothing$ и $A_i \cap A_j \ne A_i$, то переходим на итерацию $i+1$, иначе проверяем множество $A_i$ дальше.

[мат-ламер]

Jiggy в сообщении #1519501 писал(а):

Кажется, истина начинает проясняться. Попробую полностью описать 2 подхода на базе ответов выше.

1. Имеем пространство элементарных исходов $\Omega$ и рассматриваем всевозможные системы непересекающихся подмножеств $\mathrm{C_i}$ . Каждая из таких систем порождает алгебру $\mathrm{D_i}$. Рассмотрим лишь конечные алгебры. Если алгебра $\mathrm{D_i}$ порождена системой $\mathrm{C_i}$ мощности $k$, то мощность алгебры равна $2^k$ в силу ранее посчитанного количества всевозможных объединений. При этом наша конкретная конечная алгебра является одной из алгебр, которая порождена какой-то системой. Таким образом ее мощность является степенью 2.
...
Кажется, нигде логических пробелов нет.

Именно это я имел в виду.

[Jiggy]

мат-ламер

Ага, я просто воедино все попытался свести. Думаю, все прояснили.

Большое спасибо, коллеги. Замечательный форум!

[Someone]

Jiggy в сообщении #1519507 писал(а):

marie-la
Да, конечно. Другими словами, на текущей итерации $i$ рассмотрим непустое множество $A_i$ и какое-то другое непустое $A_j$. Тогда если $A_i \cap A_j \ne \varnothing$ и $A_i \cap A_j \ne A_i$, то переходим на итерацию $i+1$, иначе проверяем множество $A_i$ дальше.

Почему таким способом получится семейство множеств, порождающее всю алгебру? Мне это как-то не очевидно.

Вам может помочь понятие конституенты.
Пусть у нас есть некоторое (конечное) семейство множеств $\mathscr X=\{X_i:1\leqslant i\leqslant N\}$ (вообще говоря, не обязательно алгебра). Обозначим $\Omega=\bigcup\limits_{i=1}^NX_i$, и дополнение будем брать относительно этого множества $\Omega$, то есть, $\bar X_i=\Omega\setminus X_i$ при всех $i$, $1\leqslant i\leqslant N$.
Конституентой семейства $\mathscr X$ называется непустое множество вида $X_1\cap\bar X_2\cap X_3\cap X_4\cap\ldots\cap\bar X_N$, где в пересечение входят все множества семейства $\mathscr X$, а "чёрточки" над ними расставлены произвольно.
Число различных конституент, очевидно, не превосходит $2^N$.

Конституенты обладают следующими свойствами:
1) различные конституенты не пересекаются;
2) конституента с каждым множеством из $\mathscr X$ либо не пересекается, либо в нём содержится;
3) каждое множество из $\mathscr X$ является объединением содержащихся в нём конституент.

Все доказательства остаются на вашу долю.