2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




 
 Разбиения множества и минимальная алгебра
Сообщение01.09.2012, 16:58 
Задача
Пусть задано некоторое множество $E$. Его разбиением будем называть неупорядоченный набор непустых (!) множеств $\left\{ D_{i} \right\}_{i=1}^{n}$, если выполнены следующие два условия:
1. $D_{i} \bigcap D_{j} = \varnothing \left( i \neq j\right) $
2. $\bigcup _{i=1}^{n} D_{i} = E$
Если задано некоторое разбиение $D$ заданного множества $E$, то, добавив к элементам $D$ всевозможные их объединения и пустое множество, получим алгебру, называемую алгеброй, порождённой разбиением $D$. Обозначим её $A \left( D \right)$
С другой стороны, для любой системы подмножеств множества $E$ существует минимальная алгебра, содержащая эту систему. По определению, это алгебра являющаяся пересечением всех алгебра, содержащих данную систему подмножеств. Обозначим её $a \left( D \right)$.

Доказать:
a) $A \left( D \right)$ - действительно алгебра
b) $ A \left( D \right) = a \left( D \right) $
c) $A \left( D \right)$ определяется однозначно
d) Если $A$ - некоторая алгебра подмножеств множества $E$, то найдётся и притом единственное разбиение $D$ множества $E$, множества которого являются элементами алгебры $A$, причём $A = A \left( D \right)$.

Решение
Если честно, пока не очень представляю, как это доказывать.
a) В силу определения системы $D$ и множества $A \left( D \right)$, пустое множество и всё множество $E$ принадлежат $A \left( D \right)$. А также любые объединения и объединения объединений этих множеств и множеств системы $D$. Кроме того, для любого множества $D_{i} \in D$, в силу определения системы $D$, имеем $c \left( \bigcup_{i}D_{i} \right) = \bigcup_{j \neq i}D_{j}$, то есть все дополнения - это тоже объединения некоторых множеств из D. Поскольку $A \left( D \right)$ содержит все возможные объединения множеств из D, то, в силу вышесказанного, $\left( \forall М \in A \left( D \right) \right) cM \in A \left( D \right)$.

b) По определению минимальной алгебры, $ a \left(D \right) \subseteq A \left(D \right) $.
Осталось доказать, что $A \left(D \right) \subseteq a\left(D \right)$.
Возьмём произвольное множество $M \in A \left( D \right)$. По определению $A \left( D \right)$, $M$ - либо пустое множество, либо одно из множеств системы $D$, либо их объединение. А по определению алгебры множеств, в каждом из этих случаев множество $A$ принадлежит $a \left( D \right)$.

c) Для любой системы множеств их объединение определяется однозначно. Значит, множество $A \left( D \right)$, состоящее из множеств системы $D$, их объединений и пустого множества также определяется однозначно.

d) Выберем в алгебре $A$ такие множества $D_{i}$, что для любого множества $M \in A$ либо $D_{i} \bigcap M = \varnothing$, либо $D_{i} \bigcap M = D_{i}$. Попробуем доказать, что система $D$ всех таких множеств $D_{i}$ - искомая.
Во-первых, все множества этой системы, очевидно, не пересекаются. Но проблема у меня возникла с тем, чтобы доказать равенство $\bigcup _{i=1}^{n} D_{i} = E$.
Предположим, что все множества указанного вида собраны в одну систему, а равенство не выполняется. Тогда... А вот что тогда?

 
 
 
 Re: Разбиения множества и минимальная алгебра
Сообщение03.09.2012, 00:28 
Всё ещё надеюсь на Вашу помощь.

 
 
 
 Re: Разбиения множества и минимальная алгебра
Сообщение03.09.2012, 00:41 
Аватара пользователя
$\mathcal{A}$- алгебра подмножеств некоторого фиксированного множества $X$. Докажите сперва, что алгебры, порожденные различными ращбиениями- различны. Выше разбиение для $\mathcal{A}$ можно определить по трансфинитной индукции.
Определите разбиение в указанном Вами смысле для алгебры всех подмножеств прямой.

 
 
 
 Re: Разбиения множества и минимальная алгебра
Сообщение03.09.2012, 09:20 
Уважаемый Asker Tasker, Вам следовало бы уточнить, какие операции Вы предполагаете заданными в алгебре множеств (подмножеств фиксированного множества). В частности: 1. Требуется ли наличие операции дополнения? 2. Требуется ли операция объединения бесконечных семейств (то же про пересечение)?
Пример 1: Для бесконечного множества М отношение равенства разбивает его на отдельные точки. Беря всевозможные конечные объединения, получим систему конечных подмножеств, которая не замкнута относительно дополнений.
Пример 2: С тем же разбиением рассмотрите совокупность конечных множеств и их дополнений. Это алгебра с операциями конечных пересечений, конечных объединений и дополнения, но она не порождается в Вашем смысле никаким разбиением.

 
 
 
 Re: Разбиения множества и минимальная алгебра
Сообщение03.09.2012, 10:45 
Аватара пользователя
Может быть, множество $E$ конечное?

 
 
 
 Re: Разбиения множества и минимальная алгебра
Сообщение03.09.2012, 23:02 
Someone в сообщении #614118 писал(а):
Может быть, множество $E$ конечное?

Перечитал условие - Вы правы, речь идёт именно о конечном множестве.

muzeum в сообщении #614102 писал(а):
Уважаемый Asker Tasker, Вам следовало бы уточнить, какие операции Вы предполагаете заданными в алгебре множеств (подмножеств фиксированного множества). В частности: 1. Требуется ли наличие операции дополнения? 2. Требуется ли операция объединения бесконечных семейств (то же про пересечение)?
Пример 1: Для бесконечного множества М отношение равенства разбивает его на отдельные точки. Беря всевозможные конечные объединения, получим систему конечных подмножеств, которая не замкнута относительно дополнений.
Пример 2: С тем же разбиением рассмотрите совокупность конечных множеств и их дополнений. Это алгебра с операциями конечных пересечений, конечных объединений и дополнения, но она не порождается в Вашем смысле никаким разбиением.

Виноват, действительно стоило уточнить.
"Алгебра" в данном контексте означает, что зафиксировано некоторое конечное множество Х и А - подмножество булеана $2^{X}$, то есть А - некоторая система подмножеств множества Х, причём:
1. $X \in A$
2. Если $M_1 \in A$ и $M_2 \in A$, то $\left( M_1 \bigcup M_2 \right) \in A$
3. Если $M \in A$, то $cM \in A$

 
 
 
 Re: Разбиения множества и минимальная алгебра
Сообщение03.09.2012, 23:15 
Цитата:
Виноват, действительно стоило уточнить.
"Алгебра" в данном контексте означает, что зафиксировано некоторое конечное множество Х и А - подмножество булеана $2^{X}$, то есть А - некоторая система подмножеств множества Х, причём:
1. $X \in A$
2. Если $M_1 \in A$ и $M_2 \in A$, то $\left( M_1 \bigcup M_2 \right) \in A$
3. Если $M \in A$, то $cM \in A$

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

 
 
 
 Re: Разбиения множества и минимальная алгебра
Сообщение05.09.2012, 20:11 
muzeum в сообщении #614481 писал(а):
Если число элементов основного множества конечно, то рассмотрите совокупность 0-минимальных элементов алгебры, т.е. такие элементы, которые не пусты, но которые не содержат другие элементы алгебры в качестве подмножеств. Докажите, что система 0-минимальных элементов дает искомое разбиение для данной алгебры (помните, что в Вашей алгебре имеются операции объединения, дополнения и пересечения, которая выражается через две первых операции).


Вот у меня как раз на этом месте и произошло зависание - пункт d)

muzeum в сообщении #614481 писал(а):
Обратно: покажите, что алгебра, порожденная разбиением замкнута относительно объединений (это по способу порождения разбиением) и дополнений.

Я попробовал это сделать в пункте а) - правда, на мой взгляд, слишком коряво. Попробую ещё раз:
Алгебре, порождённой этим разбиением по условию принадлежат пустое множество и всё множество $E$.
У нас, по определению разбиения $D$, в алгебре, им порождённой, будут содержаться все объединения элементов из $D$. Объединения этих объединений опять-таки не дадут нам ничего нового, кроме как объединения некоторых $D_{i}$. Если же в объединении будет участвовать множество $E$ или пустое множество, то получим либо то же объединение, либо множество $E$ - то есть опять множества, которые принадлежат $A(D)$.
По определению разбиения, также заметим, что дополнения любого объединения множеств из $D$ - это объединение остальных множеств из $D$, а все объединения у нас уже включены, то есть и дополнения включены. Поскольку пустое множество и $E$ - дополнения друг друга, то и для этих множеств дополнения включены в $A(D)$.
Итак, $A$ не пуста, содержит все объединения, все дополнения. Значит, $A$ - это алгебра. А то, что она совпадает с минимальной, доказано в пункте b). Надеюсь, что правильно доказано.

Основной вопрос - d). Наверное, это слишком просто, но клинит: как доказать, что выбрав все "0-минимальные элемента алгебра $A$" я получу разбиение множества $E$?

 
 
 [ Сообщений: 8 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group