2014 dxdy logo

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

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





Начать новую тему Ответить на тему На страницу 1, 2, 3, 4, 5 ... 7  След.
 
 Двойственность в булевой алгебре и не только
Сообщение16.09.2008, 12:29 


20/03/08
421
Минск
О чем свидетельствует наличие “двойственности” в математической теории или в структурах, которые она описывает? (в такой, например, как булева алгебра)?
Только лишь о том, что некоторой теореме (или какому-либо понятию) такой теории может быть сопоставлена “двойственная”? Или же существует и некий более глубокий смысл у понятия “двойственность” или “duality”?

Например, если определить систему: $\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}$.

Означает ли это, что в системе положительных рациональных чисел присутствует феномен “двойственности”?

 Профиль  
                  
 
 
Сообщение16.09.2008, 12:44 


29/06/08

137
Россия
Свободный Художник в сообщении #144753 писал(а):
Или же существует и некий более глубокий смысл у понятия “двойственность” или “duality”?

Вы имеете в виду более глубокий математический смысл или ещё глубже? ;) Глубже уже идет, как ни крути, философия...

 Профиль  
                  
 
 
Сообщение16.09.2008, 17:06 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
Забавная алгебраическая система, я раньше с подобным не встречался.

Боюсь, что тождества $\overline{x \bullet y} = \overline{x} \circ \overline{y}$, $\overline{x \circ y} = \overline{x} \bullet \overline{y}$ и $\overline{\overline{x}} = x$ --- это единственное, что есть общего у полученной системы с алгеброй множеств (не считая довольно часто встречающихся коммутативности и ассоциативности бинарных операций). Прежде всего нет идемпотентности, то есть $x \bullet x \neq x \neq x \circ x$, а идемпотентность --- одно из самых характерных свойств теоретико-множественных операций, задающее их уникальную специфику. Далее, отсутствуют нейтральные элементы, то есть ни для какого $e \in \mathrm{Q^+}$ не выполняются тождества $x \bullet e = x$, $x \circ e = x$. Наконец, не выполняется ни одно из тождеств дистрибутивности: $x \circ (y \bullet z) = (x \circ y) \bullet (x \circ z)$, $x \bullet (y \circ z) = (x \bullet y) \circ (x \bullet z)$. Так что с утверждением

Свободный Художник писал(а):
...в системе $\mathbf{Q^+}$ будут справедливы многие законы, имеющие место быть в булевой алгебре...


я, пожалуй, не соглашусь. Больше всего мне здесь не нравится слово "многие" :)

"Двойственность" --- довольно широкое понятие, под ним в разных местах понимается разное. В векторных пространствах одно, в частичных порядках другое, в булевых алгебрах третье. Поскольку здесь Вы аппелируете к булевым алгебрам, то я полагаю, что под двойственностью Вы понимаете следующий факт: все тождества, имеющие место в $\mathbf{Q^+}$, останутся верными при замене $\bullet$ на $\circ$ и наоборот. Этот факт, безусловно, верен, ибо отображение $x \mapsto \overline{x}$ есть биекция $\mathrm{Q^+}$ на себя, "меняющая местами" бинарные операции. Так что феномен однозначно присутствует :)

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

P. S. Было бы очень интересно попытаться найти список аксиом $\mathbf{Q^+}$. Заняться, что ли, на досуге :)

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

Итак, предлагаю следующий список тождеств (алгебры с двумя бинарными операциями $\circ$, $\bullet$ и одной бинарной операцией $\overline{\phantom{x}}$):

1) $x \circ (y \circ z) = (x \circ y) \circ z$;
2) $x \bullet (y \bullet z) = (x \bullet y) \bullet z$;
3) $x \circ y = y \circ x$;
4) $x \bullet y = y \bullet x$;
5) $\overline{\overline{x}} = x$;
6) $\overline{x \circ y} = \overline{x} \bullet \overline{y}$;
7) $\overline{x \bullet y} = \overline{x} \circ \overline{y}$;
8) $(x \circ x) \bullet (x \circ x) = x$;
9) $(x \bullet x) \circ (x \bullet x) = x$.

Все эти тождества выполняются на $\mathbf{Q^+}$. Они не являются независимыми (к примеру, $5+6+7+1 \Rightarrow 2$ и т. п., вообще, тождества $5$, $6$ и $7$ влекут "двойственность"). Насколько они "достаточны" для задания $\mathbf{Q^+}$? То есть какие свойства $\mathbf{Q^+}$ из них можно вывести, какие нельзя? Какие ещё тождества, "задающие" $\mathbf{Q^+}$, было бы естественным добавить в этот список?

 Профиль  
                  
 
 
Сообщение17.09.2008, 00:29 


20/03/08
421
Минск
Профессор Снэйп писал(а):
Боюсь, что тождества $\overline{x \bullet y} = \overline{x} \circ \overline{y}$, $\overline{x \circ y} = \overline{x} \bullet \overline{y}$ и $\overline{\overline{x}} = x$ --- это единственное, что есть общего у полученной системы с алгеброй множеств (не считая довольно часто встречающихся коммутативности и ассоциативности бинарных операций). Прежде всего нет идемпотентности, то есть $x \bullet x \neq x \neq x \circ x$, а идемпотентность --- одно из самых характерных свойств теоретико-множественных операций, задающее их уникальную специфику... Наконец, не выполняется ни одно из тождеств дистрибутивности: $x \circ (y \bullet z) = (x \circ y) \bullet (x \circ z)$, $x \bullet (y \circ z) = (x \bullet y) \circ (x \bullet z)$.

Жаль, конечно, идемпотентные и дистрибутивные законы. Тем не менее, у системы $\mathbf{Q^+}$ есть и свои эксклюзивные “фичи”, делающие ее в каком-то смысле даже более интересной системой, чем булевы алгебры.

Например, для $\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$

В каком-то смысле система $\mathbf{Q^+}$ удваивает все, что есть в арифметике Пресбургера:
http://mathworld.wolfram.com/PresburgerArithmetic.html
http://en.wikipedia.org/wiki/Presburger_arithmetic

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

 Профиль  
                  
 
 
Сообщение17.09.2008, 17:24 


20/03/08
421
Минск
У системы $\mathbf{Q^+}$ есть несколько интересных интерпретаций, в том числе очевидная “электротехническая” интерпретация, в которой операция $\bullet$ ассоциируется с последовательным соединением проводников, а операция $\circ$ ассоциируется с параллельным соединением проводников.

 Профиль  
                  
 
 
Сообщение17.09.2008, 22:49 


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

Профессор Снэйп писал(а):
Насколько они "достаточны" для задания $\mathbf{Q^+}$? То есть какие свойства $\mathbf{Q^+}$ из них можно вывести, какие нельзя? Какие ещё тождества, "задающие" $\mathbf{Q^+}$, было бы естественным добавить в этот список?
Систему $\mathbf{Q}^+$ нельзя характеризовать с помощью конечного числа формул первого порядка (с кванторами над числами, но не над множествами чисел). Чтобы отличить $\mathbf{Q}^+$ от $\mathbf{R}^+$ требуется сформулировать конечную порожденность из $1$ каждого элемента, для чего требуется либо принцип индукции - который есть схема бесконечного числа аксиом, либо аксиома бесконечной длины (есть и такие формулы) типа:
$\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)$
(сокращенная запись)

 Профиль  
                  
 
 
Сообщение18.09.2008, 17:39 


20/03/08
421
Минск
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^+}$ указанные уравнения не будут иметь решений.

 Профиль  
                  
 
 
Сообщение18.09.2008, 22:40 


06/07/07
212
Свободный Художник писал(а):
А еще, например, в системе $\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^+}$ указанные уравнения не будут иметь решений.
Аналогично следует постулировать невозможность решения в $\mathbf{Q}^+$ всех неприводимых алгебраических уравнений степени выше $1$, чтобы отличить полуполе $\mathbf{Q}^+$ от ВСЕХ его конечных расширений при добавлении иррациональных алгебраических чисел - а это бесконечное число аксиом.
Хотя отличить $\mathbf{Q}^+$ от каждого такого алгебраически расширенного полуполя по отдельности можно и с помощью конечного числа аксиом, но если взять трансцендентный элемент, то расширение $\mathbf{Q}^+$ с ним будет конечно неотличимо от $\mathbf{Q}^+$.

 Профиль  
                  
 
 
Сообщение19.09.2008, 04:41 


12/09/08

2262
Профессор Снэйп в сообщении #144790 писал(а):
Итак, предлагаю следующий список тождеств (алгебры с двумя бинарными операциями $\circ$, $\bullet$ и одной бинарной операцией $\overline{\phantom{x}}$):

Есть еще одно: $x\circ \overline{x} = x\bullet \overline{x}$. Похоже, оно не выводится из остальных.

Кстати, оно мешает попoлнить $\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}$,
поскольку получится $0 = 0 \circ \overline{0} = 0 \bullet \overline{0} = \overline{0}$ и следовательно $x = x \circ \overline{0} =  x \circ 0 = 0$.

 Профиль  
                  
 
 
Сообщение19.09.2008, 13:22 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
ddn писал(а):
В свете всего перечисленного я не вижу чем $\mathbf{R}^+$ отличается от $\mathbf{Q}^+$, ну разве что отсутствием порождаемости элементов из $1$.


Мощностью отличаются :)

Ну и ниже отмечается также, что они даже не элементарно эквивалентны. А вот будут ли на этих двух моделях выполняться одни и те же тождества, я не знаю. Думать лень :?

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

вздымщик Цыпа писал(а):
Есть еще одно: $x\circ \overline{x} = x\bullet \overline{x}$. Похоже, оно не выводится из остальных.


??? Конечно не выводится. Оно просто неверно :(

К примеру, $\overline{1} = 1$, $1 \circ 1 = 1/2$, $1 \bullet 1 = 2$.

 Профиль  
                  
 
 
Сообщение19.09.2008, 14:16 


12/09/08

2262
Профессор Снэйп в сообщении #145300 писал(а):
??? Конечно не выводится. Оно просто неверно Sad
Упс. Промахнулся. Под утро в какой-то момент приглючилось, что $$x\circ y = \frac{x + y}{xy}$$.

Тогда пополнить ничего не мешает :)

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

Предлагаю пополнить $\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}$
Еще можно для каждого эленента $x$ определить $\widetilde{x}$, такое, что $x \bullet \widetilde{x} = 0$. Тогда
$\widetilde{\overline{x}} = \overline{\widetilde{x}}$
$\widetilde{0} = 0$
$\widetilde{\overline{0}} = \overline{0}$
$x \circ \widetilde{x} = \overline{0}$
$\widetilde{x \circ y} = \widetilde{x} \circ \widetilde{y}$
$\widetilde{x \bullet y} = \widetilde{x} \bullet \widetilde{y}$
Т.е. $\widetilde{x}$ — элемент обратный $x$ относительно обеих операций одновременно.
Вроде все согласуется, только у уравнвния $x = \overline{x}$ появляется еще одно решение: $\widetilde{1}$, a уравнение $x = \widetilde{\overline{x}}$ решений не имеет, но можно и их добавить :).

 Профиль  
                  
 
 
Сообщение19.09.2008, 20:15 
Заслуженный участник
Аватара пользователя


07/03/06
1716
Москва
Может есть смысл немного подправить введенные операции:
$x \circ y = \frac{2xy}{x+y}$;
$x \bullet y=2x+2y$.
Все сохранится, но появится еще идемпотентность $ x\circ x=x$.

 Профиль  
                  
 
 
Сообщение19.09.2008, 22:01 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
juna писал(а):
Может есть смысл немного подправить введенные операции:
$x \circ y = \frac{2xy}{x+y}$;
$x \bullet y=2x+2y$.
Все сохранится, но появится еще идемпотентность $ x\circ x=x$.


Не сохранится :(

$$
\overline{x \circ y} = \frac{x+y}{2xy} = \frac{1}{2} \left( \frac{1}{x} + \frac{1}{y} \right)
\neq 2 \left(\frac{1}{x} + \frac{1}{y} \right) = \overline{x} \bullet \overline{y}
$$

 Профиль  
                  
 
 
Сообщение19.09.2008, 22:32 
Заслуженный участник
Аватара пользователя


07/03/06
1716
Москва
Вы правы, так будет даже идемпотентность
$x \bullet y=\frac{x+y}{2}$

 Профиль  
                  
 
 
Сообщение20.09.2008, 08:20 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
juna писал(а):
Вы правы, так будет даже идемпотентность
$x \bullet y=\frac{x+y}{2}$


Да, при

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

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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 93 ]  На страницу 1, 2, 3, 4, 5 ... 7  След.

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: gris


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group