Двойственность в булевой алгебре и не только

[juna]

Потому, что это другая алгебраическая система - не решетка. Это само по себе уже интересно.

[Профессор Снэйп]

juna писал(а):

Потому, что это другая алгебраическая система - не решетка. Это само по себе уже интересно.

В решётках дополнений не предусмотрено

А решётка с дополнениями --- булева алгебра. Но! В булевых алгебрах выполняются тождества

1) $x \cap (y \cup \overline{y}) = x$;
2) $x \cup (y \cap \overline{y}) = x$;

которые из наших тождеств $+$ дистрибутивности похоже что никак не выводятся.

Но я не спорю с тем, что наша система интересна сама по себе. На мой взгляд она очень интересна. И Вашу поправку к определениям операций, дающую свойства идемпотентности, я бы принял, ибо идемпотентность --- хорошее свойство.

Вообще, у нашей системы тождеств есть модели, отличные от $F^+$, где $F$ --- упорядоченное поле?

[juna]

Профессор Снэйп в сообщении #145486 писал(а):

Вообще, у нашей системы тождеств есть модели, отличные от $F^+$, где $F$ --- упорядоченное поле?

Например?

[Профессор Снэйп]

juna писал(а):

Например?

Обратите внимание: в конце предложения, которое Вы цитируете, стоит вопросительный знак. Это был вопрос, а не утверждение

[Свободный Художник]

Профессор Снэйп писал(а):

Да, при

$$ x \bullet y = \frac{x+y}{2} \text{ и } x \circ y = \frac{2xy}{x+y} $$

идемпотентность будет. Но дистрибутивности всё равно не будет

К сожалению, добавленные двоечки не такие уж и безобидные, поскольку разрушают ассоциативность. Например, для операции $\bullet$:
$\dfrac{\dfrac{x + y}{2} + z}{2} = \dfrac{x + y + 2z}{4}\,, \text{ тогда как }\; \dfrac{x + \dfrac{y + z}{2}}{2} = \dfrac{2x + y + z}{4}\,.$

[juna]

Да, за идемпотентность приходится платить ассоциативностью. Без последнего свойства система выглядит слишком экзотической.
Действительно интересно, чему могут быть изоморфны эти системы (есть ли какой-нибудь аналог теоремы Стоуна?).

[Свободный Художник]

вздымщик Цыпа писал(а):

Предлагаю пополнить $\mathrm{Q^+}$ ($\mathrm{R^+}$) элементами $0$ и $\overline{0}$
$x \bullet 0 = x$
$x \circ 0 = 0$
$x \circ \overline{0} = x$
$x \bullet \overline{0} = \overline{0}$

Уж лучше вместо $\overline{0}$ ввести новый выделенный элемент $\infty$. Красивше будет.
Да и по смыслу подходит.
$x \bullet 0 = x\,, \; x \circ \infty = x \,;$
$x \bullet \infty = \infty\,, \; x \circ 0 = 0 \,;$
$\overline{0} = \infty\,, \; \overline{\infty} = 0\,;$
$\overline{1} = 1\,.$
$0$ двойственен $\infty$. $1$ самодвойственна.

[вздымщик Цыпа]

Свободный Художник в сообщении #145542 писал(а):

Уж лучше вместо $\overline{0}$ ввести новый выделенный элемент $\infty$. Красивше будет.

$\infty$ выглядит как-то попсово и не подчеркивает двойственности с $0$. Может лучше $0_\bullet$ и $0_\circ$ ? Наглядно — нейтральные элементы относительно соответствующих операций.

А пополнение «отрицательными» элементами Вам нравится? Все таки «самодуальная группа по двум операциям» лучше «самодуальной полугруппы с единицами»

[Профессор Снэйп]

Свободный Художник писал(а):

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

Ха! В натуре так!!!

Нет уж, лучше тогда отказаться от двоечек. Ассоциативность ценнее идемпотентности

Добавлено спустя 2 минуты 53 секунды:

juna писал(а):

Действительно интересно, чему могут быть изоморфны эти системы (есть ли какой-нибудь аналог теоремы Стоуна?).

Вот именно этот вопрос меня и интересовал в первую очередь.

Но, прежде чем говорить об "этих системах", надо чётко зафиксировать их класс. Выписать систему аксиом. Причём мне почему-то хочется, чтобы аксиомы состояли исключительно из тождеств.

Какие-то тождества я накидал в список. Может, кто-нибудь видит другие, столь же простые и естественные?

[вздымщик Цыпа]

Профессор Снэйп в сообщении #145550 писал(а):

Какие-то тождества я накидал в список. Может, кто-нибудь видит другие, столь же простые и естественные?

$(x\circ x\circ x) \bullet (x\circ x\circ x) \bullet (x\circ x\circ x) = (x\bullet x \bullet x) \circ (x\bullet x \bullet x) \circ (x\bullet x \bullet x) = x$
И вообще:

$$y = \underbrace{x\circ \ldots \circ x}\limits_{n\ \text{раз}}\ \Leftrightarrow \ x = \underbrace{y \bullet \ldots \bullet y}\limits_{n\ \text{раз}}$$

Из аксиом что-то не удается вывести. На этот раз вроде без промахов
Похоже, не хватает какой-то более общей, чем (8,9) аксиомы, связывающей операции.

Добавлено спустя 9 минут:

Впрочем, для $n=2^m$ выводится $m$-кратным применением.
И если доказано для $n_1$ и $n_2$, то для $n = n_1n_2$ тоже доказывается.

Добавлено спустя 19 минут 45 секунд:

И еще $((x \bullet x)\circ x) \bullet (x\circ x\circ x) = x$.

[juna]

Свободный Художник писал(а):

Красивше будет.
Да и по смыслу подходит.
$x \bullet 0 = x\,, \; x \circ \infty = x \,;$
$x \bullet \infty = \infty\,, \; x \circ 0 = 0 \,;$
$\overline{0} = \infty\,, \; \overline{\infty} = 0\,;$
$\overline{1} = 1\,.$
$0$ двойственен $\infty$. $1$ самодвойственна.

Может лучше
$-\infty$ - единичный элемент группы $<\mathbb Q, \circ>$. При этом $\forall x\in \mathbb Q (x^{-1}=-x)$
$0$ - единичный элемент группы $<\mathbb Q, \bullet >$. Т.е. для любого элемента одинаковые обратные как по первой, так и по второй операции.

Добавлено спустя 58 минут 31 секунду:

Вот, если не наврал, еще одно тождество:
$(y \bullet z)\circ(\overline{y}\bullet \overline {z}})=(y\circ \overline{z})\bullet (\overline{y}\circ z)$ и двойственное.
Не знаю, выводится ли из предыдущих...

[Свободный Художник]

Профессор Снэйп писал(а):

Но, прежде чем говорить об "этих системах", надо чётко зафиксировать их класс. Выписать систему аксиом. Причём мне почему-то хочется, чтобы аксиомы состояли исключительно из тождеств.
Какие-то тождества я накидал в список. Может, кто-нибудь видит другие, столь же простые и естественные?

Для наглядной верификации кандидатов на тождества, истинные в системе $\mathbf{Q^+}$, можно предложить следующую вспомогательную систему $\mathbf{RA}$ (от “Rectangles Algebra”):
$\mathbf{RA} = \langle \, \mathrm{RA}, \bullet, \circ, \overline{\phantom{a}}, \parallel \; \rangle \,,$
где $\mathrm{RA}$ есть множество всех упорядоченных пар натуральных чисел (пара $<a, b>$ интерпретируется как прямоугольник с длиной горизонтальной стороны $a$ и длиной вертикальной стороны $b$; или же как обыкновенная дробь с числителем $a$ и со знаменателем $b$);
$\bullet$ есть (частичная) бинарная операция на множестве $\mathrm{RA}$, именуемая “операцией горизонтального сложения прямоугольников” и определяемая на прямоугольниках с одинаковой длиной вертикальных сторон следующим образом: если $x = <a, b>$ и $y = <c, b>$, то $x \bullet y = <(a+c), b>$;
$\circ$ есть (частичная) бинарная операция на множестве $\mathrm{RA}$, именуемая “операцией вертикального сложения прямоугольников” и определяемая на прямоугольниках с одинаковой длиной горизонтальных сторон следующим образом: если $x = <a, b>$ и $y = <a, c>$, то $x \circ y = <a, (b+c)>$;
$\overline{\phantom{a}}$ есть (всюду определенная) унарная операция на множестве $\mathrm{RA}$, именуемая “операцией обращения прямоугольников” и определяемая следующим образом: если $x = <a, b>$, то $\overline{x} = <b, a>$;
$\parallel $ есть бинарное отношение на множестве $\mathrm{RA}$, именуемое “отношением пропорциональности на прямоугольниках” и определяемое следующим образом: если $x = <a, b>$ и $y = <c, d>$, то $x \parallel y$ тогда и только тогда, когда $ad = bc$.

Давайте разберем процедуру верификации на примере тождества $(x \bullet x) \circ (x \bullet x) = x$, предложенного Профессор Снэйп. Свяжем с переменной $x$ прямоугольник $<a, b>$ из $\mathrm{RA}$. Тогда терму $(x \bullet x)$ будет соответствовать прямоугольник $<2a, b>$. Осуществив вертикальное сложение двух таких прямоугольников, мы получим прямоугольник $<2a, 2b>$, соответствующий терму $(x \bullet x) \circ (x \bullet x)$.
Отметим, что $<2a, 2b> \parallel <a, b>$,
т. е. в нашей вспомогательной системе $\mathbf{RA}$ имеет место соотношение $((x \bullet x) \circ (x \bullet x)) \parallel x$, а из этого следует истинность тождества $(x \bullet x) \circ (x \bullet x) = x$ в системе $\mathbf{Q^+}$.

Т. е. можно сводить верификацию тождеств в системе $\mathbf{Q^+}$ к мысленно производимым простым манипуляциям с прямоугольниками. Лично я как увидел тождество $(x \bullet x) \circ (x \bullet x) = x$, то вот так его сразу в уме и верифицировал. :)

[Профессор Снэйп]

вздымщик Цыпа писал(а):

$(x\circ x\circ x) \bullet (x\circ x\circ x) \bullet (x\circ x\circ x) = (x\bullet x \bullet x) \circ (x\bullet x \bullet x) \circ (x\bullet x \bullet x) = x$
И вообще:

$$y = \underbrace{x\circ \ldots \circ x}\limits_{n\ \text{раз}}\ \Leftrightarrow \ x = \underbrace{y \bullet \ldots \bullet y}\limits_{n\ \text{раз}}$$

Из аксиом что-то не удается вывести. На этот раз вроде без промахов
Похоже, не хватает какой-то более общей, чем (8,9) аксиомы, связывающей операции.

Пытался найти "недостающую аксиому" --- нифига не вышло. Стал склоняться к мысли, что это невозможно. Решил показать, что конечным списком тождеств обойтись просто невозможно.

Н-да... пока что пытаюсь построить конечную модель тождеств 1 -- 9. Есть одноэлементная модель, это без базара. А ещё какие-нибудь есть?

Добавлено спустя 2 минуты 22 секунды:

Свободный Художник писал(а):

Т. е. можно сводить верификацию тождеств в системе $\mathbf{Q^+}$ к мысленно производимым простым манипуляциям с прямоугольниками. Лично я как увидел тождество $(x \bullet x) \circ (x \bullet x) = x$, то вот так его сразу в уме и верифицировал.

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

К примеру,

$$ x \circ x = 2x; \, x \bullet x = x/2 $$

[juna]

Можно, кстати, не отказываться от идемпотентных операций, а ввести их дополнительно в систему:
$x\oplus y=(x\circ x)\bullet (y\circ y)=\frac{x+y}{2}$
$x\otimes y=(x\bullet x)\circ (y\bullet y)=\frac{2xy}{x+y}$
и обратно
$(x\oplus y)\bullet (x \oplus y)=x\bullet y$
$(x\otimes y)\circ(x \otimes y)=x\circ y$
Возможно это поможет аксиомам 8, 9. Например, пользуясь идемпотентностью, можно упрощать
$x\otimes y=(x\otimes y)\otimes (x\otimes y)=((x \bullet x)\circ(y \bullet y))\otimes((x \bullet x)\circ(y \bullet y))=(((x \bullet x)\circ(y \bullet y))\bullet ((x \bullet x)\circ(y \bullet y))\circ(((x \bullet x)\circ(y \bullet y)))\bullet ((x \bullet x)\circ(y \bullet y)))$

[lofar]

Профессор Снэйп писал(а):

Н-да... пока что пытаюсь построить конечную модель тождеств 1 -- 9. Есть одноэлементная модель, это без базара. А ещё какие-нибудь есть?

Возьмите $\mathbb Z_3^n$; $\circ=\bullet=+$; $\overline{\cdot}=id$. Вообще подойдет любая комутативная полугруппа с тождеством $a^4=a$.

Откровенно говоря, не понимаю интереса к этой структуре. Никакого чуда в имеющейся двойственности нет. Так можно поступить с любой полугруппой $(H,\circ)$. Берем любую инволютивную биекцию $f\colon H\to H$ и по определению полагаем $a\bullet b = f(f(a)\circ f(b))$. Полученная система будет иметь двойственность в смысле аксиом 1-7. В зависимости от особенностей $f$ могут появиться еще какие-нибудь тождества, вроде аксиом 8 и 9. И что?