Минимальное кольцо над системой множеств

[Anton_Peplov]

Теорема. Пусть $A, B$ - произвольные множества. Минимальным кольцом над двухэлементной системой $\{A, B\}$ является $\Lambda = \{A, B, A \cup B, A \cap B, A \setminus B, B \setminus A, A \Delta B, \varnothing \}$.

То, что все элементы $\Lambda$ входят в минимальное кольцо - очевидно. То, что минимальное кольцо состоит только из них, надо доказывать.
Я доказывал это "в лоб": брал все возможные пары элементов $\Lambda$, применял к ним операции пересечения и симметрической разности и убеждался, что в результате всегда получается элемент $\Lambda$. Сразу отбрасывая пару $\{A, B\}$, а также все пары с пустым множеством, получаем 20 пар, и к каждой применяем две операции. Весьма занудное времяпровождение, даже если учесть, что каждая операция выполняется практически "на автомате".

Невольно возникает вопрос, есть ли более короткое и изящное доказательство. Что-нибудь вроде этого: набор бинарных операций $(\varphi_1, \varphi_2, ... \varphi_n)$ называется уныло однообразным, если для любых $A, B$ множество $\{A \varphi_1 A, A \varphi_2 A, ... A \varphi_n A, B \varphi_1 B, B \varphi_2 B, ... B \varphi_n B, A \varphi_1 B, A \varphi_2 B, ... A \varphi_n B\}$ замкнуто по операциям $\varphi_1, \varphi_2, ... \varphi_n$ (т.е. достаточно применить операции к парам $\{A, A\}$, $\{B, B\}$ и $\{A, B\}$, повторное применение уже не даст новых результатов). Набор операций $(\cap, \cup, \setminus, \Delta)$ уныло однообразен, потому что ... (следует красивое - т.е. не сводящееся к полному перечислению частных случаев - доказательство). Следовательно, минимальным кольцом над двухэлементной системой $\{A, B\}$ является $\Lambda = \{A, B, A \cup B, A \cap B, A \setminus B, B \setminus A, A \Delta B, \varnothing \}$.

Тут сразу приходят на ум базисы булевых функций, но базис еще не является уныло однообразным, что легко проверяется, скажем, для базиса $(\wedge, \vee, \neg)$.

Вопрос: что-нибудь подобное существует в природе или это плод моего воспаленного воображения?

[quartermind]

Про уныло однообразные операции я бы подумал, что это ситуация слишком специфичная. А в самом вопросе дело ещё в том, насколько элементарное и строгое доказательство вы хотите получить. А то при желании можно ограничиться парой слов про булевы алгебры или же рисованием кругов Эйлера.

Но уж приведу попытку придумать более интересное доказательство (то есть эскиз, чтобы выглядело ещё изящнее ):
Покажем, что любой элемент $\Lambda$ представляется в виде дизъюнктного объединения множеств из $\mathcal C = \{A \setminus \! B, \; B \setminus \! A, \; A \cap B \}$. (Тут есть простор для разбора случаев, но не 20 штук.) В силу свойств симметрической разности и пересечения, замкнутость относительно первой уже есть, а относительно второй — достаточно проверить, что, применяя $\cap$ к элементам $\mathcal C$, мы останемся в $\Lambda$.

(Оффтоп)

Вы говорите, что базисы булевых функций не уныло однообразны. Непонятно, что это значит, так как вы сами определяли это для операций. Да и, строго говоря, набор $\{ \wedge, \vee, \neg \}$ базисом не является: можно выкинуть конъюнкцию.

[Anton_Peplov]

quartermind в сообщении #1100730 писал(а):

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

Если я правильно помню, набор булевых функций от двух переменных (или булевых операций, это одно и то же) называется базисом, если любая булева функция от двух переменных (которых 16) представима как суперпозиция функций из этого набора. Возможно, я что-то путаю в терминологии.

quartermind в сообщении #1100730 писал(а):

Да и, строго говоря, набор $\{ \wedge, \vee, \neg \}$ базисом не является: можно выкинуть конъюнкцию.

Ну да, можно. Или дизъюнкцию.

[Xaositect]

Уныло однообразные множества есть в точности пересечения замкнутых классов булевых функций с множеством функций от 2 переменных. В данном случае, все функции от 2 переменных, равные нулю в нуле.

[Someone]

Ну, здесь три конституенты ($A\setminus B$, $B\setminus A$, $A\cap B$), из них можно составить $2^3$ множеств.

[quartermind]

Xaositect, хорошее утверждение, а как его непосредственно здесь применить? Булевы функций двух переменных определены на $\mathbb B \times \mathbb B$, a операции в смыле Anton_Peplov — на $\mathbb B^n \times \mathbb B^n$.

Someone, я бы сказал, не более, чем $2^3$. Например, если изначально множества вложены одно в другое, получится меньше.

(Оффтоп)

Anton_Peplov, я ваше определение базиса видел в гробу теории схем, а в теории замкнутых классов принято другое. Но это не суть.

[Xaositect]

quartermind в сообщении #1100777 писал(а):

Xaositect, хорошее утверждение, а как его непосредственно здесь применить? Булевы функций двух переменных определены на $\mathbb B \times \mathbb B$, a операции в смыле Anton_Peplov — на $\mathbb B^n \times \mathbb B^n$.

Ну тут особой проблемы нет, так как операции на $\mathbb{B}^n$ - это просто покоординатные операции на $\mathbb{B}$.

[Anton_Peplov]

Someone в сообщении #1100773 писал(а):

Ну, здесь три конституенты ($A\setminus B$, $B\setminus A$, $A\cap B$), из них можно составить $2^3$ множеств.

Формально система из восьми множеств порождает 256 конституент. То, что в данном случае среди них не более трех различных, может быть, и видно опытному глазу, но вообще-то надо доказывать. Перебрать 256 частных случаев, чтобы не перебирать 20...

-- 20.02.2016, 16:16 --

Xaositect в сообщении #1100759 писал(а):

Уныло однообразные множества есть в точности пересечения замкнутых классов булевых функций с множеством функций от 2 переменных.

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

[Xaositect]

Anton_Peplov в сообщении #1100793 писал(а):

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

Нет, там более слабое понятие, чем в топологии, см. https://en.wikipedia.org/wiki/Closure_operator. Про пересечение верно, а с объединением не получится - композиции функций из разных объединяемых классов могут порождать новые функции в замыкании.

[Anton_Peplov]

А такое понятие имеет какое нибудь название? Какая-нибудь "предтопология", "квазитопология"...

[Xaositect]

Да вроде просто "оператор замыкания", обычно из контекста понятно, топология имеется в виду или нет.

[Someone]

Anton_Peplov в сообщении #1100793 писал(а):

Формально система из восьми множеств порождает 256 конституент.

Господь с Вами, какие $8$??? У Вас $2$ (прописью: два) множества. $A$ и $B$.

[Anton_Peplov]

Xaositect в сообщении #1100809 писал(а):

Да вроде просто "оператор замыкания", обычно из контекста понятно, топология имеется в виду или нет.

Просто я вижу, что у этого оператора замыкания много общего с оператором замыкания в топологии. Например, $[[A]] = [A]$, $[A \cap U] \subset [A] \cap [U]$ и т.д. Если все эти свойства являются следствием того, что пересечение любой системы замкнутых классов само есть замкнутый класс, то они не зависят от конкретной природы оператора замыкания и замыкаемых множеств - суперпозиция ли это функций или еще что-нибудь. Тогда полезно было бы оформить это в какую-нибудь аксиоматическую структуру, типа как:
Выберем в пространстве-носителе $X$ систему подмножеств $\Omega$ такую, что:
1)$\varnothing, X \in \Omega$
2) пересечение любой подсистемы $\Omega$ само принадлежит $\Omega$.

Назовем эти множества замкнутыми в псевдотопологии.

Теорема 1. Для любого множества $A$ есть минимальное замкнутое множество, включающее $A$. Назовем его замыканием $A$ и обозначим $[A]$.
Следствие. $[[A]] = [A]$

Теорема 2. $[A \cap U] \subset [A] \cap [U]$

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

-- 20.02.2016, 17:32 --

Someone в сообщении #1100810 писал(а):

У Вас $2$ (прописью: два) множества. $A$ и $B$.

Да, что-то я ляпнул... Начал с середины.

[Someone]

(quartermind)

quartermind в сообщении #1100777 писал(а):

я бы сказал, не более, чем $2^3$. Например, если изначально множества вложены одно в другое, получится меньше.

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

[Anton_Peplov]

(Someone)

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