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

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

Интересная статья в контексте Stern-Brocot tree:
"Exact arithmetic on the Stern-Brocot tree" Niqui M. Journal of Discrete Algorithms 5(2): 356-379, 2007.
http://portal.acm.org/citation.cfm?id=1240588

Цитата:

ABSTRACT
In this paper we present the Stern-Brocot tree as a basis for performing exact arithmetic on rational numbers. There exists an elegant binary representation for positive rational numbers based on this tree [Graham et al., Concrete Mathematics, 1994]. We will study this representation by investigating various algorithms to perform exact rational arithmetic using an adaptation of the homographic and the quadratic algorithms that were first proposed by Gosper for computing with continued fractions. We will show generalisations of homographic and quadratic algorithms to multilinear forms in n variables. Finally, we show an application of the algorithms for evaluating polynomials.

Кто-нибудь может поспособствовать в ее получении?

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

Хорошо известна тесная связь Stern-Brocot tree с цепными дробями. Относительно последних считается, что над рациональными числами, представленными своими разложениями в цепную дробь, трудно выполнять общепринятые арифметические действия.
См. например, Хинчин А. Я. "Цепные дроби". М., Физматлит, 1978, сс. 28 — 30:
http://www.px-pict.com/7/4/4/4.html

Или, может быть, что-либо в этом плане уже изменилось?

[juna]

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

Интересная статья в контексте Stern-Brocot tree:
"Exact arithmetic on the Stern-Brocot tree" Niqui M. Journal of Discrete Algorithms 5(2): 356-379, 2007.

Действительно интересная, судя по abstract.

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

Кто-нибудь может поспособствовать в ее получении?

Тоже поддерживаю и обращаюсь с просьбой к могущим.

[shwedka]

забирайте на
http://rapidshare.com/files/191947809/niqui.pdf.html

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

shwedka, большое спасибо.

[juna]

Большое спасибо!
P.S. Уважаемая shwedka - Вы всемогущая.

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

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

А вот элементы $0$ и $\infty$ -– не определимы в $\mathbf{Q^+}$, поэтому, если мы хотим говорить о них, то должны явно добавить их в сигнатуру системы, что, пользуясь случаем, я и делаю:

$\mathbf{Q^+_{\, 0, \infty}} = \langle \, \mathrm{Q^+}, \bullet\,, \circ\,, \overline{\phantom{a}}\,, 0\,, \infty \rangle$

И, естественно, добавить еще аксиомы вида:
$x \bullet 0 = x\,, \; x \circ \infty = x \,;$
$x \bullet \infty = \infty\,, \; x \circ 0 = 0 \,;$
$\overline{0} = \infty\,, \; \overline{\infty} = 0\,;$

(см. http://dxdy.ru/topic16277-45.html)
Двойственность, имеющуюся в системе $\mathbf{Q^+_{\, 0, \infty}}$, можно сравнивать не только с двойственностью в булевой алгебре, но и с двойственностью в топологической булевой алгебре, где она имеет место между оператором $\Diamond$ замыкания и оператором $\Box$ взятия внутренности:
http://en.wikipedia.org/wiki/Topological_Boolean_algebra
http://en.wikipedia.org/wiki/Interior_algebra
http://en.wikipedia.org/wiki/Closure_operator
http://en.wikipedia.org/wiki/Kuratowski_closure_axioms

Мы используем символ $\Diamond$ для оператора замыкания, а символ $\Box$ -- для оператора взятия внутренности топологической булевой алгебры имея в виду связь между топологической булевой алгеброй и системой модальной логики $S4$, в которой модальные операторы $\Diamond$ “возможности” и $\Box$ “необходимости” соответствуют указанным операторам в топологической булевой алгебре.
http://en.wikipedia.org/wiki/Modal_logic

Если ассоциировать операторы $H$ и $V$ из алгебраической системы $\mathbf{Q^+_{\, 0, \infty}}$ с операторами $\Diamond$ замыкания и $\Box$ взятия внутренности в топологической булевой алгебре,
то легко убедиться, что имеют место следующие аналогии:
$\forall x [x \subseteq \Diamond (x)] \; \longleftrightarrow \; \forall x [x \le H(x)];$
$\forall x [\Box(x) \subseteq x] \; \longleftrightarrow \; \forall x [V(x) \le x];$

$\forall x\forall y \{(x \subseteq y) \Rightarrow \; [\Diamond (x) \subseteq \Diamond (y)]\} \; \longleftrightarrow \; $
$\forall x\forall y \{(x \le y) \Rightarrow \; [H(x) \le H(y)]\};$

$\forall x\forall y \{(x \subseteq y) \Rightarrow \; [\Box (x) \subseteq \Box (y)]\} \; \longleftrightarrow \; $
$\forall x\forall y \{(x \le y) \Rightarrow \; [V(x) \le V(y)]\};$

“унарные” законы де Моргана:
$\forall x [\overline{\Diamond (x)} = \Box (\overline{x})] \; \longleftrightarrow \; \forall x [\overline{H(x)} = V(\overline{x})];$
$\forall x [\overline{\Box (x)} = \Diamond (\overline{x})] \; \longleftrightarrow \; \forall x [\overline{V(x)} = H(\overline{x})];$

$\forall x [\Diamond (x) = \overline{\Box (\overline{x})}] \; \longleftrightarrow \; \forall x [H(x) = \overline{V(\overline{x})}];$
$\forall x [\Box (x) = \overline{\Diamond (\overline{x})}] \; \longleftrightarrow \; \forall x [V(x) = \overline{H(\overline{x})}].$

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

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

А вот говорят еще, например, что булева алгебра – это “алгебра мысли” (или “алгебра логики”). И что она придумана Джорджем Булем специально для того, чтобы формализовать “законы мышления”
http://plato.stanford.edu/entries/algebra-logic-tradition/
http://en.wikipedia.org/wiki/George_Boole
Но “алгебра логики” имеет также и “числовую” модель:
http://www.px-pict.com/9/5/1/3/1.html
причем операции этой модели были определены уже в самом первом учебнике по теории чисел – в VII книге “Начал”:
http://www.px-pict.com/7/3/1/8.html
Т. е. получается, что “алгебра Буля” была по существу определена более чем за 2000 лет до самого Буля (во времена, когда и Платон еще не родился).

И чего поделывает “алгебра мысли” в теории чисел? :)

P.S. В свете вышесказанного было бы логично в основу аксиоматики теории натуральных чисел положить аксиоматику теории дистрибутивных решеток:
http://en.wikipedia.org/wiki/Distributive_lattice

Дистрибутивная решетка на множестве натуральных чисел, порождаемая операциями НОД и НОК, естественным образом обобщается до соответствующей дистрибутивной решетки на множестве положительных рациональных чисел:
http://www.px-pict.com/9/5/2/6/1/1.html
(пример 4 на этой странице)

-- Ср июл 01, 2009 04:17:06 --

Значит, мы можем промоделировать эту дистрибутивную решетку внутри системы $\mathbf{Q^+}$:

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

Например, если определить систему: $\mathbf{Q^+} = \langle \, \mathrm{Q^+}, \bullet\,, \circ\,, \overline{\phantom{a}} \rangle$,
где $\mathrm{Q^+}$ есть множество положительных рациональных чисел;
$\bullet$ есть бинарная операция на множестве $\mathrm{Q^+}$, определяемая как $x \bullet y = x + y$;
$\circ$ есть бинарная операция на множестве $\mathrm{Q^+}$, определяемая как $x \circ y = \dfrac{xy}{x + y}$;
$\overline{\phantom{a}}$ есть унарная операция на множестве $\mathrm{Q^+}$, определяемая как $\overline{x} = \dfrac1{x}$;
то в системе $\mathbf{Q^+}$ будут справедливы многие законы, имеющие место быть в булевой алгебре, например, законы де Моргана: $\overline{x \bullet y} = \overline{x} \circ \overline{y}$ и $\overline{x \circ y} = \overline{x} \bullet \overline{y}$.

Если согласиться, что операцию умножения внутри системы $\mathbf{Q^+}$ мы все-таки определили:

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

И все же операция $\cdot$ умножения в системе $\mathbf{Q^+}$ определяется вполне стандартным образом (для первопорядковых теорий с равенством). Для краткости определим тернарный предикат $R(u, x, y)$:
$\forall u\forall x\forall y\{R(u, x, y) \equiv [(x \bullet 1) \circ (u \bullet y) = (x \circ u) \bullet (1 \circ y)]\}$.

Постулируем две аксиомы:
$\forall x\forall y\exists u R(u, x, y)$;
$\forall x\forall y\forall u_1\forall u_2 \{R(u_1, x, y) \& R(u_2, x, y) \Rightarrow (u_1 = u_2)\}$.

Введем новый бинарный функциональный символ $\cdot$ и добавим аксиому:
$\forall x\forall y R((x \cdot y), x, y)$,

После этого мы можем утверждать, что определили в системе $\mathbf{Q^+}$ операцию $\cdot$ умножения.

Т. е. после этих доопределений $\mathbf{Q^+}$ становится решеточно-упорядоченной абелевой группой относительно операции умножения.

-- Ср июл 01, 2009 04:38:29 --

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

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

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

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

Дожали-ли таки мы $\mathbf{Q^+}$ до дистрибутивной решетки. :)
Стало быть и теорема Стоуна о представлении здесь рулит.

-- Ср июл 01, 2009 04:45:54 --

Решетка интересная, а вот в списке характерных дистрибутивных решеток со страницы:
http://en.wikipedia.org/wiki/Distributive_lattice
ее нет.

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

Интересует также двойственность между векторами и ковекторами.
Точнее, интересуют эффектные визуализации векторно-ковекторных конструкций.

Я уже приводил кое-какие соображения на этот счет для двумерного векторного пространства над полем действительных чисел:
http://forum.exler.ru/arc/index.php?showtopic=127705

Однако, в настоящее время интересуют визуализации векторно-ковекторных конструкций для $n$-мерного векторного пространства над $GF(2)$. Как можно это сделать?

[Lia]

Тема перемещена из форума «Дискуссионные темы (М)» в форум «Карантин»
по следующим причинам:

По просьбе ТС.

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

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

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

Результат попытки использования "гиперболических" комплексных чисел для $k(\sqrt{2})$ (и родственных систем) по аналогии с тем, как Гаусс использовал обычные комплексные числа (в интерпретации Ф. Клейна):
http://www.px-pict.com/7/3/1/15/3/1/2/2.html
будет представлен несколько позже. Поскольку отрицательные рациональные и ирациональные числа неспецифичны для муз. теории (а специфичны только положительные рациональные и ирациональные числа, математически моделирующие музыкальные интервалы), все построения нужно будет в конце концов адаптировать к первому квадранту координатной плоскости.

В свете имеющейся в системе $\mathbf{R^+}$ двойственности, наряду с операцией взятия сопряженного числа, переводящего $a + b\sqrt{d}$ в $a - b\sqrt{d}$ (мы пока ограничиваемся для простоты случаем $d = 2$), можно попробовать интенсивно использовать операцию взятия "двойственного" иррационального числа по отношению к данному ирациональному числу. Например, числа $\alpha = \sqrt{2} + 1$ и $\beta = \sqrt{2} - 1$ будут двойственными друг по отношению к другу, поскольку определяются двойственными друг по отношению к другу уравнениями: $z = [H(1)]\bullet\overline{z}$ и $z = [V(1)]\circ\overline{z}$, соответственно.

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

ddn писал(а):

В свете всего перечисленного я не вижу чем $\mathbf{R}^+$ отличается от $\mathbf{Q}^+$, ну разве что отсутствием порождаемости элементов из $1$.

А еще, например, в системе $\mathbf{R^+}$ можно определить два “золотых” числа $\alpha$ и $\beta$:
$\alpha = \dfrac{\sqrt{5} + 1}{2}\,, \;\; \beta = \dfrac{\sqrt{5} - 1}{2}$
при помощи двух двойственных друг по отношению к другу соотношений:
$x = 1 \bullet \overline{x}\,, \;\; y = 1 \circ \overline{y}\,.$

А в системе $\mathbf{Q^+}$ указанные уравнения не будут иметь решений.

-- Пт июн 17, 2016 16:36:55 --

ddn в сообщении #145059 писал(а):

В свете всего перечисленного я не вижу чем $\mathbf{R}^+$ отличается от $\mathbf{Q}^+$, ну разве что отсутствием порождаемости элементов из $1$.

Если легализовать понятие "бесконечных термов" в мат. логике, то порождаемость из $1$ сохранится и для иррациональных чисел. О бесконечно длинных формулах в мат. логике упоминают, например, Расева и Сикорский в Предисловии к своей монографии:
http://www.px-pict.com/9/6/2/8/3/0.html
и Вы сами о них упоминаете:

ddn в сообщении #145059 писал(а):

... либо аксиома бесконечной длины (есть и такие формулы) типа:
$\forall x\left(\bigvee\limits_{n\in\mathbb{N}_0}\left(\bigvee\limits_{\phi_{\cdot}\in(\bar n\to\{V,H\})}(\bigcirc\limits_{i=1}^n\phi_{i})(1)=x\right)\right)$
(сокращенная запись)

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

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

Если легализовать понятие "бесконечных термов" в мат. логике, то порождаемость из $1$ сохранится и для иррациональных чисел.

И можно будет проводить рассуждения о термах, ассоцированных с бесконечными цепными дробями, которые теперь проводятся с использованием понятия предела. Как, например, у Хованского:
http://www.px-pict.com/7/4/4/9/1/1/8.html

[epros]

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

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

Если легализовать понятие "бесконечных термов" в мат. логике, то порождаемость из $1$ сохранится и для иррациональных чисел.

И можно будет проводить рассуждения о термах, ассоцированных с бесконечными цепными дробями, которые теперь проводятся с использованием понятия предела. Как, например, у Хованского:
http://www.px-pict.com/7/4/4/9/1/1/8.html

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

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

epros в сообщении #1132764 писал(а):

... всё равно придётся прибегать к каким-то конечным формулам в языке мета-теории.

Ну, так это в языке мета-теории. А в языке теории, выражение, помещенное в самом начале пункта 1 у Хованского:
http://www.px-pict.com/7/4/4/9/1/1.html
является, ведь, именно бесконечным термом по своему смыслу.

-- Вс июн 19, 2016 23:51:59 --

Понятие "бесконечных термов" ("infinite terms") в мат. логике встречается. Например:
Helmut Schwichtenberg.
Finite notations for infinite terms.
http://www.sciencedirect.com/science/ar ... 7297000730

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

epros в сообщении #1132764 писал(а):

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

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

... в языке теории, выражение, помещенное в самом начале пункта 1 у Хованского:
http://www.px-pict.com/7/4/4/9/1/1.html
является, ведь, именно бесконечным термом по своему смыслу.

Хотя, возможно, что здесь более корректно следовало бы говорить о "частичном объекте" в смысле Д. Скотта:
http://www.px-pict.com/9/6/4/7/4/1/10.html
Когда имеется информация только о некоторых коэффициентах бесконечной цепной дроби, но не о всех.
О концепции Д. Скотта:
https://en.wikipedia.org/wiki/Domain_theory
https://en.wikipedia.org/wiki/Denotational_semantics

-- Ср июн 22, 2016 23:52:24 --

С обсуждаемыми в данной теме системами $\mathrm{Q^+}$ и $\mathrm{R^+}$ можно естественным образом ассоциировать "домены" в смысле Скотта. При их определении я буду пользоваться приведенной ниже (на примере) процедурой трансляции цепных дробей в термы некоторой связанной с системами $\mathrm{Q^+}$ и $\mathrm{R^+}$ теории:
http://www.px-pict.com/preprints/grundlagen/12.html
А также редукцией этих термов к "позитивной" нормальной форме.

[epros]

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

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

... в языке теории, выражение, помещенное в самом начале пункта 1 у Хованского:
http://www.px-pict.com/7/4/4/9/1/1.html
является, ведь, именно бесконечным термом по своему смыслу.

Там конечное количество буковок. К тому же это вообще не терм, ибо использование троеточий грамматикой не определено. Вообще, если мы поставим троеточие после какого-нибудь $1+2+3$, то это не значит, что мы определили бесконечный терм.