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

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

lofar писал(а):

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

С тем, в двойственности нет никакого чуда, согласен на все 100. Интерес вызывает, собственно, не она. Просто система как-то хорошо выглядит: рациональные числа, естественная операция сложения, инверсия тоже естественная... Ну и сразу интерес: ну-ка, ну-ка, а что там вообще будет присутствовать, вдруг это система из какого-то известного класса, или она даёт новый интересный класс?!

Так-то систем с "двойственностью" наплодить можно кучу. Вот очень простая. Носитель --- множество $\mathbb{Z}$, $\overline{x} = -x$, $x \circ y = xy$, $x \bullet y = -xy$. Или так: носитель --- то же $\mathbb{Z}$, $\overline{x}$ меняет местами стоящие рядом чётный и нечётный элементы, $x \circ y = x + y$, $x \bullet y = \ldots$ (понятно какая, лень выписывать). Ну и т. д., и т. п.

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

И всё-таки, вернёмся в $\mathbf{Q^+}$.

Стало очень интересно: можно ли выразить обычное умножение $x \cdot y$ через $x \circ y$, $x \bullet y$ и $\overline{x}$? Вроде бы доказал, что нельзя.

Пусть $t(x_1, \ldots, x_k)$ --- терм, составленный при помощи упомянутых операций, все переменные которого содержатся в наборе $x_1, \ldots, x_k$. Этот терм можно естественным образом отождествить с некоторой функцией из $(Q^+)^k$ в $Q^+$.

Лемма 1: Существуют константы $C, D > 0$, такие что $\frac{C}{x} < t(x,\ldots,x) < Dx$ при всех $x > 1$.

Доказательство. Индукция по длине терма.

1) $t$ есть переменная. Тогда можно взять $C=1$ и $D=2$.

2) $t = t_1 \circ t_2$. Пусть $C_1, D_1, C_2$ и $D_2$ --- нужные константы для термов $t_1$ и $t_2$ соответственно. Достаточно положить $C = C_1 + C_2$ и $D = D_1 + D_2$.

3) $t = \overline{t}_1$. Пусть $C_1$ и $D_1$ --- константы для $t_1$. Легко видеть, что для $t$ подходят константы $C = 1/D_1$ и $D = 1/C_1$.

4) $t = t_1 \bullet t_2$. Этот случай сводится к двум предыдущим, так как $t = \overline{\overline{t}_1 \circ \overline{t}_2}$ (последнее равенство понимается как равенство значений функций, а не как равенство термов). $\qed$.

Невозможность представления функции $x \cdot y$ теперь легко следует из леммы, так как для этой функции не существует константы $D$.

Жаль, конечно. Умножение бы много позволило сделать

Аналогично лемме 1 легко доказывается

Лемма 2: Для произвольного $t(x_1, \ldots, x_k)$ имеем

$$ t(x, \ldots, x) \sim C/x \text{ или } t(x, \ldots, x) \sim Cx $$

при некоторой $C \in Q^+$ и $x \to +\infty$.

Доказательство почти аналогично, так что писать не буду.

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

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

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

Стало очень интересно: можно ли выразить обычное умножение $x \cdot y$ через $x \circ y$, $x \bullet y$ и $\overline{x}$? Вроде бы доказал, что нельзя.

Произведение $u$ двух элементов $x$ и $y$ можно определить как корень уравнения:
$(x \bullet 1) \circ (u \bullet y) = (x \circ u) \bullet (1 \circ y)$
При подстановке в указанное уравнение $u = xy$ обе его части оказываются равными выражению $\dfrac{y(x + 1)}{y + 1}$.

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

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

Произведение $u$ двух элементов $x$ и $y$ можно определить как корень уравнения:
$(x \bullet 1) \circ (u \bullet y) = (x \circ u) \bullet (1 \circ y)$
При подстановке в указанное уравнение $u = xy$ обе его части оказываются равными выражению $\dfrac{y(x + 1)}{y + 1}$.

В частности, при $y = \overline{x}$ и $u = 1$ получаем универсальное тождество:
$(x \bullet 1) \circ (1 \bullet \overline{x}) = (x \circ 1) \bullet (1 \circ \overline{x})$.

В принципе, мы могли бы с самого начала добавить выделенный элемент $1$ в сигнатуру системы $\mathbf{Q^+}$ (или $\mathbf{R^+}$) и охарактеризовать его роль в системе при помощи указанного универсального тождества, рассматриваемого в качестве новой аксиомы.

[juna]

Речь идет о непредставимости умножения термом фиксированной длины. То, что при стремлении одной переменной $x$ к бесконечности получаем ограничение сверху как $O(x)$ вполне очевидно и следует из того, что $\infty$ единица моноида $<\mathbb Q^+,\circ>$. Соответственно, если выражению $x\cdot y$ сопоставлен терм $t(x,y)$, то во всех частях, где переменная $x$ связана операцией $\circ$ получаем либо константу, либо $cx$, где $c$ - константа, зависящая от терма и независящая от $y$. В тоже время $x\cdot y$ ограничена сверху $O(x^2)$. Отсюда, кстати, очевидно, что для многих переменных, стремящихся к бесконечности такого ограничения не будет.
Ваше же тождество в более общем виде я уже приводил $(y \bullet z)\circ(\overline{y}\bullet \overline {z}})=(y\circ \overline{z})\bullet (\overline{y}\circ z)$.Возьмите $y=1,z=x$

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

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

Например, для $\mathbf{Q^+}$ являются справедливыми, очевидно, следующие два утверждения:
(1) Существует элемент, удовлетворяющий условию $\overline{x} = x$;
(2) Такой элемент единственен.
Положив этому элементу естественное имя 1, мы можем определить две двойственные друг по отношению к другу унарные операции: $H(x) = x \bullet 1$ и $V(x) = x \circ 1$.
Затем при помощи этих двух унарных операций H и V, примененных в различных комбинациях к 1, мы, как можно показать, можем получить все положительные рациональныечисла, причем разным комбинациям будут соответствовать разные числа.
Например, $V(H(H(1))) = 3/4$

Кстати говоря, система с двумя унарными операциями $V$ и $H$, основанная на системе $\mathbf{Q^+}$, также весьма интересна (обозначим ее $\mathbf{SBT}$):
$\mathbf{SBT} = \langle \, \mathrm{SBT}, V, H, 1 \rangle$,
где $\mathrm{SBT}$ есть снова множество положительных рациональных чисел;
$V$ и $H$ есть унарные операции на множестве $\mathrm{SBT}$, определяемые как указано выше;
$1$ есть выделенный элемент во множестве $\mathrm{SBT}$.

Во-первых, $\mathbf{SBT}$ есть абсолютно свободная алгебра с двумя унарными операциями и одним выделенным элементом;
во-вторых, система $\mathbf{SBT}$ может служить основой для анализа различных соотношений, возникающих в контексте Stern-Brocot Tree:
http://mathworld.wolfram.com/Stern-BrocotTree.html
http://www.cut-the-knot.org/blue/Stern.shtml
http://en.wikipedia.org/wiki/Stern-Brocot_tree

(аббревиатура $\mathbf{SBT}$ для системы выбрана в честь этого деревца).

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

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

И всё-таки, вернёмся в $\mathbf{Q^+}$.

Стало очень интересно: можно ли выразить обычное умножение $x \cdot y$ через $x \circ y$, $x \bullet y$ и $\overline{x}$? Вроде бы доказал, что нельзя.

juna в сообщении #146046 писал(а):

Речь идет о непредставимости умножения термом фиксированной длины.

Да, термом конечной длины представить умножение нельзя.
Но можно попробовать определить умножение в $\mathbf{Q^+}$ “рекурсивно”, имея в виду, что операции $V$ и $H$ играют в $\mathbf{Q^+}$ роль, аналогичную роли функции-последователя $s(x) = x + 1$ в арифметике Пеано.

В арифметике Пеано операция умножения определяется рекурсивно при помощи аксиомы:
$x \cdot s(y) = (x \cdot y) + x$.
Соответствующие равенства
$x \cdot H(y) = (x \cdot y) \bullet x$ и $x \cdot V(y) = (x \cdot y) \circ x$
в системе $\mathbf{Q^+}$ справедливы, как легко убедиться.

Правда, при рекурсивном определении операций $\bullet$ и $\circ$ возникают проблемы.

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

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

Кстати говоря, система с двумя унарными операциями $V$ и $H$, основанная на системе $\mathbf{Q^+}$, также весьма интересна (обозначим ее $\mathbf{SBT}$):
$\mathbf{SBT} = \langle \, \mathrm{SBT}, V, H, 1 \rangle$,
где $\mathrm{SBT}$ есть снова множество положительных рациональных чисел;
$V$ и $H$ есть унарные операции на множестве $\mathrm{SBT}$, определяемые как указано выше;
$1$ есть выделенный элемент во множестве $\mathrm{SBT}$.

Кажется, в системе $\mathbf{SBT}$ можно очень просто определить отношение $<$ строгого линейного порядка на множестве положительных рациональных чисел. Для этого достаточно постулировать следующие “определяющие соотношения” (которые, очевидно, справедливы при указанной интерпретации операций $V$ и $H$):
(v1). Для любого $x, V(x) < 1$,
(h1). Для любого $x, 1 < H(x)$,
(v2). Если $x < y$, то $V(x) < V(y)$,
(h2). Если $x < y$, то $H(x) < H(y)$,
(trans). Если $x < y$ и $y < z$, то $x < z$.

Докажем, например, что $\dfrac4{7} < \dfrac2{3}$.
$V(H(1)) = \dfrac2{3}$; $V(H(V(V(1)))) = \dfrac4{7}$.

Доказательство.
(1) Для любого $x, V(x) < 1$ -- аксиома (v1);
(2) $V(V(1)) < 1$ -- из (1);
(3) $H(V(V(1))) < H(1)$ -- из (2) по аксиоме (h2);
(4) $V(H(V(V(1)))) < V(H(1))$ -- из (3) по аксиоме (v2).

Поскольку все “определяющие соотношения” являются хорновскими дизъюнктами, то их можно рассматривать как “логическую программу”:
http://www.px-pict.com/9/6/4/4.html,
рекурсивно определяющую на множестве всех основных термов системы $\mathbf{SBT}$ отношение $<$ строгого линейного порядка.

[juna]

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

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

Да, между $\mathbb Q^+$\{1} и $\mathbf {SBT}$ изоморфизм. Для простоты упустим единицу и скобки, подразумевая, что операции выполняем справа налево, тогда запись вида $HVHHHV...$ - это другая форма записи рациональных чисел. Интересно исследовать закономерности обратного отображения - из заданного рационального числа построить его аналог в системе $\mathbf {SBT}$. Вот некоторые совсем простые закономерности:
$V^n=H^{-n}$
$(HV)^n=(VH)^{-n}$
$VH^n=\frac{n+1}{n+2}$
Есть ли еще какие-нибудь интересные свойства у этого морфизма?

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

juna писал(а):

Да, между $\mathbb Q^+$\{1} и $\mathbf {SBT}$ изоморфизм. Для простоты упустим единицу и скобки, подразумевая, что операции выполняем справа налево, тогда запись вида $HVHHHV...$ - это другая форма записи рациональных чисел. Интересно исследовать закономерности обратного отображения - из заданного рационального числа построить его аналог в системе $\mathbf {SBT}$. Вот некоторые совсем простые закономерности:
$V^n=H^{-n}$
$(HV)^n=(VH)^{-n}$
$VH^n=\frac{n+1}{n+2}$
Есть ли еще какие-нибудь интересные свойства у этого морфизма?

Вот известный факт. Пусть $F_n$ -- числа Фибоначчи: $F_1 = 1, F_2 = 1, F_3 = 2$ и т. д.
Тогда $(VH)^n = \dfrac{F_{2n + 1}}{F_{2n + 2}}$ и, соответственно, $(HV)^n = \dfrac{F_{2n + 2}}{F_{2n + 1}}$.

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

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

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

Например, для $\mathbf{Q^+}$ являются справедливыми, очевидно, следующие два утверждения:
(1) Существует элемент, удовлетворяющий условию $\overline{x} = x$;
(2) Такой элемент единственен.
Положив этому элементу естественное имя 1, мы можем определить две двойственные друг по отношению к другу унарные операции: $H(x) = x \bullet 1$ и $V(x) = x \circ 1$.
Затем при помощи этих двух унарных операций H и V, примененных в различных комбинациях к 1, мы, как можно показать, можем получить все положительные рациональныечисла, причем разным комбинациям будут соответствовать разные числа.
Например, $V(H(H(1))) = 3/4$

Кстати говоря, система с двумя унарными операциями $V$ и $H$, основанная на системе $\mathbf{Q^+}$, также весьма интересна (обозначим ее $\mathbf{SBT}$):
$\mathbf{SBT} = \langle \, \mathrm{SBT}, V, H, 1 \rangle$,
где $\mathrm{SBT}$ есть снова множество положительных рациональных чисел;
$V$ и $H$ есть унарные операции на множестве $\mathrm{SBT}$, определяемые как указано выше;
$1$ есть выделенный элемент во множестве $\mathrm{SBT}$.

Для $\mathbf{SBT}$ есть еще следующая “векторно-матричная” модель $\mathbf{SBT^{Matr}}$:
$\mathbf{SBT^{Matr}} = \langle \, \mathrm{SBT^{Matr}}, V, H, 1 \rangle$,
где $\mathrm{SBT^{Matr}}$ есть множество всех векторов вида $\begin{pmatrix}m\\n \end{pmatrix}$, где $m$ и $n$ есть пара взаимно-простых натуральных чисел (которая может также интерпретироваться как несократимая дробь $\dfrac m{n}$);
$V$ есть матрица $\begin{pmatrix}1 & 0\\1 & 1\end{pmatrix}$;
$H$ есть матрица $\begin{pmatrix}1 & 1\\0 & 1\end{pmatrix}$;
$1$ есть вектор $\begin{pmatrix}1\\1 \end{pmatrix}$.

Применению операций $V$ и $H$ к некоторому элементу множества $\mathrm{SBT}$ системы $\mathbf{SBT}$ отвечает умножение матрицы на вектор в системе $\mathbf{SBT^{Matr}}$.

Полугруппа унимодулярных матриц, порожденная матрицами $\begin{pmatrix}1 & 0\\1 & 1\end{pmatrix}$ и $\begin{pmatrix}1 & 1\\0 & 1\end{pmatrix}$, изоморфна свободной полугруппе с двумя образующими.

[juna]

juna в сообщении #149400 писал(а):

... из заданного рационального числа построить его аналог в системе $\mathbf {SBT}$.

Этот алгоритм очень прост. Используем
$V(\frac{p}{q})=\frac{p}{p+q}$
$H(\frac{p}{q})=\frac{p+q}{q}$
Если на текущем шаге имеем правильную дробь, то используем операцию $V$, в противном случае $H$. Например, нужно найти аналог числа $\frac{7}{19}$. Имеем
$\frac{7}{19}=V(\frac{7}{12})=VV(\frac{7}{5})=VVH(\frac{2}{5})=VVHV(\frac{2}{3})=VVHVV(\frac{2}{1})=VVHVVH$

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

juna писал(а):

juna в сообщении #149400 писал(а):

... из заданного рационального числа построить его аналог в системе $\mathbf {SBT}$.

Этот алгоритм очень прост...

Он даже запрограммирован.
http://www.px-pict.com/10/4/4/1.html
(Самый первый калькулятор на этой странице)
Если в этом калькуляторе в поле “Аргумент x операции” ввести Числитель = 7 и Знаменатель = 19, после чего нажать кнопку “Вычислить”, то в поле “Программа” окажется именно последовательность $VVHVVH$.

Если же в среднем калькуляторе на указанной странице в поле “Программа” ввести последовательность $VVHVVH$ и нажать кнопку “Вычислить”, то в качестве результата получим дробь $\frac 7{19}$ (т. е. реализуется обратное преобразование).

[juna]

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

Он даже запрограммирован. Smile

С этим нет проблем. Вот lisp-code:

(defun Number_To_HV (p q)
   (cond 
      ((and (= p 2) (= q 1))(list 'H))
      ((= p q ) nil)
      ((< p q) (cons 'V (Number_To_HV p (- q p))))
      ((> p q) (cons 'H (Number_To_HV (- p q) q)))))

(defun HV_To_Number (L) 
   (cond
      ((and (Null (cdr L)) (eq (car L) 'H)) 2)
      ((and (Null (cdr L)) (eq (car L) 'V)) (/ 1 2))
      ((eq (car L) 'H) (+ 1 (HV_To_Number(cdr L))))
      ((eq (car L) 'V) (/ (HV_To_Number (cdr L)) (+ 1 (HV_To_Number(cdr L)))))))

По краткости и лаконичности очень привлекателен.

Добавлено спустя 1 час 59 минут 56 секунд:

Кстати, если рассматривать различные степени заданной последовательности в системе $\mathbf {SBT}$ приходим к различным рекурентным соотношениям. Например, рассмотрим $(VVH)^n$
$n=1, p=2, q=5$
$n=2, p=7, q=19$
$n=3, p=26, q=71$
$n=4, p=97, q=265$
$n=5, p=362, q=989$
$n=6, p=1351, q=3691$
Числители соответствуют последовательности A001075, знаменатели A001834. Само по себе, в этом нет ничего удивительного, но интересно.

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

juna писал(а):

Кстати, если рассматривать различные степени заданной последовательности в системе $\mathbf {SBT}$ приходим к различным рекурентным соотношениям. Например, рассмотрим $(VVH)^n$ ...

Такого рода степени в системе $\mathbf{SBT}$ связаны с разложением некоторой квадратичной иррациональности в бесконечную цепную дробь. Это вполне понятно, если принять во внимание, что Stern-Brocot Tree, ассоциированное с системой $\mathbf{SBT}$, тесно связано с разложением чисел в цепные дроби и с подходящими дробями для таких дробей.

Конкретно степени последовательности $VVH$ в системе $\mathbf{SBT}$ связаны с разложением в бесконечную цепную дробь квадратичной иррациональности $\beta = \dfrac{\sqrt{3} - 1}{2}$.
Легко проверить, что $\beta $ удовлетворяет уравнению $\beta = V(V(H(\beta)))$, или, что эквивалентно, уравнению:
$\beta = \dfrac1{2 + \dfrac1{1 + \beta}}$,
или, что эквивалентно, уравнению: $2\beta^2 + 2\beta - 1 = 0$.

Последовательность рациональных чисел $VVH = \dfrac2{5}, \; (VVH)^2 = \dfrac7{19}, \; (VVH)^3 = \dfrac{26}{71} \; $ и т. д. представляет собой монотонно убывающую последовательность подходящих дробей к бесконечной периодической цепной дроби, в которую разлагается квадратичная иррациональность $\beta = \dfrac{\sqrt{3} - 1}{2}$.

Подробно о разложении квадратичных иррациональностей в цепные дроби написано у
Г. Дэвенпорт. Высшая арифметика. М., Наука, 1965.
http://eqworld.ipmnet.ru/ru/library/mathematics/numtheory.htm