2014 dxdy logo

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

Математика, Физика, Computer Science, Machine Learning, 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
215
В свете всего перечисленного я не вижу чем $\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
215
Свободный Художник писал(а):
А еще, например, в системе $\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
1898
Москва
Может есть смысл немного подправить введенные операции:
$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
1898
Москва
Вы правы, так будет даже идемпотентность
$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  След.

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



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

Сейчас этот форум просматривают: нет зарегистрированных пользователей


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

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