Аппликация лямбда-термов ассоциативна или нет?

[Sonic86]

Аппликация лямбда-термов ассоциативна или нет?
В Пирсе написано, что $a \ b \ c$ понимается левоассоциативно: $(a \ b) \ c$. И мне кажется, что у меня есть примеры лямбда-термов, которые неассоциативны. Просто если они неассоциативны, то какие это функции?
А если ассоциативны, то давайте я примеры приведу, а Вы у меня ошибки найдете.

[Xaositect]

Аппликация неассоциативна, разумеется. Например, $KKIxy = Kxy = x$, $K(KI)xy = KIy = I$.

[arseniiv]

(Собственно, ведь когда операция $*$ неассоциативна, и возникает нужда сказать, лево- или правоассоциативно стоит понимать записи $a_1*a_2*\ldots*a_n$, если они спасают от скобок. Правда, тут сразу контрпример: если рассказывать об ассоциативной операции языку программирования, придётся всё равно сказать, как её ассоциировать при разборе, если это не какой-то супер-язык, который решает, что есть смысл расставлять скобки в выражении с заведомо ему известно ассоциативной операцией по-разному в зависимости от чего-то.)

[Sonic86]

О, у меня мозги заработали. Проверка:
$g(f(x)) = (g \circ f)(x) = g \ (f \ x)\Rightarrow$
$g \circ f = \lambda x (g \ (f \ x))$
$h \circ (g \circ f) = (h \circ g) \circ f \Leftrightarrow$
$h \circ (\lambda x (g \ (f \ x))) = (\lambda x (h \ (g \ x))) \circ f \Leftrightarrow$
$\lambda x (h \ ((\lambda x (g \ (f \ x))) \ x)) = \lambda x (\lambda x (h \ (g \ x)) (f \ x)) \Leftrightarrow$
делаем аппликацию внутри с обеих сторон:
$\lambda x (h \ (g \ (f \ x)))= \lambda x (h \ (g \ (f \ x))) \Leftrightarrow$
получается просто тождество
(а я чего-то сначала подумал, что будет $(h \ (g \ f)) = ((h \ g) \ f)$. Значит композиция функций и аппликация - разные вещи)
Спасибо!

[artey]

Xaositect в сообщении #1179845 писал(а):

Аппликация неассоциативна, разумеется. Например, $KKIxy = Kxy = x$, $K(KI)xy = KIy = I$.

Здравствуйте, объясните пожалуйста подробнее данные равенства. Нашел, что $Ix = x,Kxy = x$, но не понимаю, как получается первая их часть, точнее $KKIxy = Kxy$ и $K(KI)xy = KIy$ - что к чему применяется и в какой последовательности. Я так понял, что первое равенство - это левоассоциативность, а второе - правоассоциативность. И не могли бы привести другие примеры, показывающие не ассоциативность?

[arseniiv]

$abcdef$ — это сокращение для $((((ab)c)d)e)f$. Соответственно, $KKIxy \equiv (KKI)xy = Kxy$, потому что $KKI = K$, и $K(KI)xy \equiv (K(KI)x)y = KIy$, потому что $K(KI)x = KI$.

artey в сообщении #1315247 писал(а):

И не могли бы привести другие примеры, показывающие не ассоциативность?

Практически любой взятый с потолка пример её покажет, попробуйте. И вообще она более-менее естественна из смысла аппликации.

[artey]

arseniiv в сообщении #1315324 писал(а):

Практически любой взятый с потолка пример её покажет, попробуйте. И вообще она более-менее естественна из смысла аппликации.

Спасибо за пояснение. Вот взял такой пример, проверьте пожалуйста на правильность: $W \equiv \lambda xy.xyy $ $WIWxy \equiv (WIW)xy = (IW)W)xy = (WWx)y = (Wxx)y = xxxy$ и $WI(Wx)y \equiv (W(IW)x)y = (I(Wx)x)y = (W(xx)y) = xxyy$

[arseniiv]

Во втором ошибка, $WI(Wx) \equiv (WI)(Wx)$ редуцируется в $I(Wx)(Wx)$ и под конец останавливается на $x(Wx)(Wx)$.

-- Вс май 27, 2018 20:10:38 --

Т. е. вы наверно сразу хотели написать $W(IW)xy$, но поставили скобки немного не там?

[artey]

Вот так $W(IW)xy \equiv (W(IW)x)y = (I(Wx)x)y = (W(xx)y) = xxyy$ ?

[arseniiv]

$(W(IW)x)y = (IW)xxy = Wxxy = xxxy.$

[artey]

arseniiv в сообщении #1315378 писал(а):

$(W(IW)x)y = (IW)xxy = Wxxy = xxxy.$

Тогда получается, что ассоциативны.

[arseniiv]

Ассоциативность операции $*$ — это когда для всех троек элементов выполняется $(a*b)*c = a*(b*c)$. Если хотя бы для одной не выполняется, а для остальных да, ассоциативности всё равно уже нет. Тем более что в данном случае бесконечно много троек термов $a,b,c$, для которых $(ab)c \ne a(bc)$ (и не только при $a = K$).

[artey]

arseniiv в сообщении #1315378 писал(а):

$(IW)xxy = Wxxy = xxxy.$

Почему вы так скобки расставили, а не так: $(I(Wx)x)y$ мы же смотрим правоассоциативность.

Почему ассоциативности не будет, если получается что

artey в сообщении #1315360 писал(а):

$WIWxy \equiv (WIW)xy = (IW)W)xy = (WWx)y = (Wxx)y = xxxy$

и

arseniiv в сообщении #1315378 писал(а):

$(W(IW)x)y = (IW)xxy = Wxxy = xxxy.$

.
Что то я совсем запутался. Можете пожалуйста вот для этого $WIWxy$ примера правильно расписать оба равенства.

[arseniiv]

Давайте с начала. Здесь рассматриваются три каких-то терма $a, b, c$ таких, чтобы, предположительно, $(ab)c \ne a(bc)$. Чтобы проще было убедиться в неравенстве, к рассматриваемым комбинаторам $(ab)c, a(bc)$ ещё применяется достаточное число переменных — $x, y$ в нашем случае. Скобки не нужно пытаться ставить каким-то особым образом в обход обычных правил больше нигде кроме этих уже готовых выражений (где они тоже поставлены вполне сознательно и не в обход правил вычисления). Ниже, так уж и быть, я укажу все скобки, не пользуясь соглашением об их левоассоциативной расстановке.

Итак, мы берём $(a, b, c) = (W, I, W)$ и получаем

$$(((ab)c)x)y = (((WI)W)x)y = (((IW)W)x)y = ((WW)x)y = ((Wx)x)y = ((xx)x)y$$

и

$$((a(bc))x)y = ((W(IW))x)y = (((IW)x)x)y = ((Wx)x)y = ((xx)x)y.$$

Недоразумение устранено? Если нет, опишите точнее, в чём оно состоит, а то непонятно.