поправка про экспоненциал

[thedeemon]

Я в недавнем посте в одном месте наврал, а меня не поправили. Если мы возьмем категорию, в которой объекты - натуральные числа, а стрелка соединяет два числа, когда первое делится на второе (это обычное частично упорядоченное множество), и мы хотим определить экспоненциал:

Comments

[ex_juan_gan]

А можно сначала определение экспоненциала в студию? Это не сопряженный к декартову произведению? А декартово произведение там есть?

[thedeemon]

The functor exp(A,*) is defined as the right adjoint
functor of * x A.

Из Хагино:

[ex_juan_gan]

А, ну то есть, действительно, произведение - это lcm.

A×B = (A/gcd(A,B))*gcd(A,B)*(B/gcd(A,B))

Я думаю, exp(A,B) = B/gcd(A,B)

[thedeemon]

AxB = lcm(A,B) = A*B/gcd(A,B)

B/gcd(A,B) для exp не годится. Тот же пример: A=70, B=100. B/gcd(A,B) = 10, но Ax10 = 70, не делится на B, а должно. Правильное значение exp(70,100)=100.

[udpn]

Я тут в процессе размышления. Знайте, вы не один :)

a >= b ~ as % bs == 0
exists a < b ~ as % bs != 0
min(a, b) ~ gcd(as, bs)
max(a, b) ~ lcm(as, bs)
a + b ~ as * bs
a - b ~ as / bs
if(a < b, b, 0) ~ ?

70 = (1 0 1 1)
100 = (2 0 2 0)
10 = (1 0 1 0) = gcd(a, b)
7 = (0 0 0 1) = a / gcd(a, b)
10 = (1 0 1 0) = b / gcd(a, b)
100 = (2 0 2 0) = exp(a, b)

30 = (1 1 1 0)
35 = (0 0 1 1)
5 = (0 0 1 0) = gcd(a, b)
6 = (1 1 0 0) = a / gcd(a, b)
7 = (0 0 0 1) = b / gcd(a, b)
7 = (0 0 0 1) = exp(a, b)

http://codepad.org/W9ihbNT2

[udpn]

forall a >= b ~ as % bs == 0

[udpn]

sharpc сказал, что из gcd, lcm и степеней a, b это сделать невозможно, и полил меня каким-то функаном про бесконечномерное пространство представлений, и про то, что с помощью конечной формулы можно представить только подпространство, построенное на конечном количестве векторов. Я ничего не понял и не поверил за отсутствием формального доказательства.

Некоторое упрощение скрипта. Теперь я пытаюсь только найти представление if(a < b, b, 0) через min, max, _+_, _-_. Попробуй запустить под нормальным хаскеллом, у меня на кодепаде таймаут.

http://codepad.org/q17DtVh5

[akuklev]

> Вопрос: можно ли эту функцию выразить без явного разложения на множители? Например, через формулу с gcd, lcm и арифметическими операциями.

Осмысленные арифметические операции тут получается только умножение и деление, как сформулировал udpn в своём посту. И получается что нельзя, см. http://udpn.livejournal.com/69157.html?thread=888869#t888869.

А в конце там человек вообще офигенное доказательство через непрерывность привёл.

[akuklev]

Зато можно, если есть функция sgn (в комментах у udpn есть вариант, который очевидным образом переписывается через сигнум), то есть соответственно нужны рациональные числа и функция, которая находит выражение числа через несократимую дробь и возвращает произведение числителя и знаменателя.