2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6, 7  След.
 
 
Сообщение22.09.2008, 03:31 
Заморожен
Аватара пользователя


18/12/07
8774
Новосибирск
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$ (понятно какая, лень выписывать). Ну и т. д., и т. п.

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


18/12/07
8774
Новосибирск
И всё-таки, вернёмся в $\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$.

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

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

 Профиль  
                  
 
 
Сообщение22.09.2008, 13:26 


20/03/08
421
Минск
Профессор Снэйп писал(а):
Стало очень интересно: можно ли выразить обычное умножение $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}$.

 Профиль  
                  
 
 
Сообщение22.09.2008, 19:50 


20/03/08
421
Минск
Свободный Художник писал(а):
Произведение $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^+}$) и охарактеризовать его роль в системе при помощи указанного универсального тождества, рассматриваемого в качестве новой аксиомы.

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


07/03/06
1892
Москва
Речь идет о непредставимости умножения термом фиксированной длины. То, что при стремлении одной переменной $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$

 Профиль  
                  
 
 
Сообщение24.09.2008, 20:29 


20/03/08
421
Минск
Свободный Художник в сообщении #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}$ для системы выбрана в честь этого деревца).

 Профиль  
                  
 
 
Сообщение07.10.2008, 07:33 


20/03/08
421
Минск
Профессор Снэйп писал(а):
И всё-таки, вернёмся в $\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$ возникают проблемы. :)

 Профиль  
                  
 
 
Сообщение08.10.2008, 14:28 


20/03/08
421
Минск
Свободный Художник писал(а):
Кстати говоря, система с двумя унарными операциями $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}$ отношение $<$ строгого линейного порядка.

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


07/03/06
1892
Москва
Свободный Художник в сообщении #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}$
Есть ли еще какие-нибудь интересные свойства у этого морфизма?

 Профиль  
                  
 
 
Сообщение09.10.2008, 12:42 


20/03/08
421
Минск
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}}$.

 Профиль  
                  
 
 
Сообщение09.10.2008, 19:44 


20/03/08
421
Минск
Свободный Художник писал(а):
Свободный Художник в сообщении #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}$, изоморфна свободной полугруппе с двумя образующими.

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


07/03/06
1892
Москва
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$

 Профиль  
                  
 
 
Сообщение10.10.2008, 11:46 


20/03/08
421
Минск
juna писал(а):
juna в сообщении #149400 писал(а):
... из заданного рационального числа построить его аналог в системе $\mathbf {SBT}$.

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

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

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

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


07/03/06
1892
Москва
Свободный Художник в сообщении #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. Само по себе, в этом нет ничего удивительного, но интересно.

 Профиль  
                  
 
 
Сообщение13.10.2008, 13:30 


20/03/08
421
Минск
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

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

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



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

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


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

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