Неассоциативность операции

[AlexDem]

Спасибо Вам на добром слове

Тему, конечно, можно переместить или вообще удалить, чтоб не позорить честь - я разобрался.

[Someone]

AlexDem писал(а):

По-моему, Ваш пример противоречив (с той позиции, с которой я подхожу). Запишу соответствующие ему перестановки: ...

Вы заблуждаетесь. Перестановки (подстановки) - это отображения (вообще-то, даже взаимно однозначные, чего в данном примере не наблюдается), их композиция ассоциативна. А в примере AD элементы $0$ и $1$ нельзя интерпретировать как подстановки.

[bot]

Если неассоциативных операций не бывает, то у меня нет ни одной работы по математике.
А как вам понравится такая задачка, почерпнута из реальной статьи, на которую мне шеф ещё в студенчестве дал написать рецензию.

Определение. Группоид G назовём антиассоциативным, если равенство $x(yz)=(xy)z$ не выполняется ни для каких значений переменных.
Автор интересовался возможными порядками конечных антиассоциативных группоидов и, наконец, соорудил пример порядка где-то около 20.
Мой ответ был таков: для любого n>1. Доказательство - одна строчка.

[AlexDem]

Нет, мне всё же кажется, что я нашёл верный ответ на свой вопрос. Возможно, определение сейчас поменялось, но у меня перед глазами кгига Сушкевича "Теория обобщенных групп", где на с.9 вводятся подстановки. У него рассматриваются случаи, когда во втором ряду элементы дублируются (а значит обратного отображения нет) - они называются конечными обобщёнными подстановками. Такие подстановки соответствуют полугруппам.

Если бы операцию нельзя было рассматривать как отображение, это означало бы, что существует такое преобразование множества $Z$ в себя, которое отсутствует в симметрической полугруппе $F$. А там по определению есть они все. Однако, никто не обещал, что суперпозиция на $F$ даст подполугруппу, изоморфную $Z$ относительно рассматриваемой операции. Но возможны и другие операции над функциями из $F$, отличные от суперпозиции (в том числе и неассоциативные) - и с такой операцией изоморфизм можно установить.

[Профессор Снэйп]

bot писал(а):

Определение. Группоид G назовём антиассоциативным, если равенство $x(yz)=(xy)z$ не выполняется ни для каких значений переменных.
Автор интересовался возможными порядками конечных антиассоциативных группоидов и, наконец, соорудил пример порядка где-то около 20.
Мой ответ был таков: для любого n>1. Доказательство - одна строчка.

Хе-хе. В $\mathbb{Z}_n$ определяем $x \ast y = x + 1$. Тогда $x \ast (y \ast z) = x + 1 \neq x + 2 = (x \ast y) \ast z$. И правда в одну строчку!

[AlexDem]

Хм, а я начал было граф рисовать. По-моему, если там две операции одинаковый путь имеют, то ассоциативность нарушится - так было в примере AD и у Профессор Снэйп - та же история, все пути совпадают.

[AD]

AlexDem писал(а):

Ваш пример противоречив (с той позиции, с которой я подхожу).

Видимо, я плохо понимаю Вашу позицию, потому что противоречий быть не может, потому что в группоиде никаких аксиом на операции не налагается. Или в смысле что он - контрпример?

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

Профессор Снэйп писал(а):

Какого х... вся эта х.... делает в разделе "помогите решить/разобраться"?! В дискуссионные её, там ферматикам раздолье.

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

[AlexDem]

Дело в том, что в данном случае я ошибочно предположил, что раз операция представима отображением, то такой группоид обязательно должен быть изоморфен подполугруппе $<F,*>$, но упустил из виду то обстоятельство, что на множестве $F$ может быть введена не только операция суперпозиции, но и какая-нибудь другая, в том числе - неассоциативная. По крайней мере, мне так сейчас видится этот вопрос.

[AD]

Да, наверное, это оно. Только вот это не отменяет вопрос про "синтаксис" и "семантику". Вот ваш пример с операцией отрицания, которая неассоциативна, но неким естественным образом соответствует операции сложения. Может быть, формализовать этот естественное соответствие - и группоидам придёт конец (с точностью до этого соответствия)?

[AlexDem]

Нет, теперь уже не выйдет . Тем более, что Ваш пример как раз доказывает, что синтаксис тут ни при чём.

[AD]

Ну типа там утверждение, что "всякую бинарную операцию можно выразить через какую-нибудь ассоциативную бинарную операцию или "обратную" к ней"? Или так: "для каждого вычитания найдётся своё сложение"? По-моему, занятное занятие.

[Профессор Снэйп]

Тогда вот вопрос, близкий к теме.

Сколько всего существует различных ассоциативных бинарных операций на конечном множестве, состоящем из $n$ элементов?

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

Хм... Насколько я понял, точный ответ неизвестен даже для $n=8$.

http://www.research.att.com/~njas/sequences/A023814

Для $n = 7$ имеем $7743056064$ ассоциативных операций и $7^{7^2} = 256923577521058878088611477224235621321607$ всех операций. Неассоциативных операций получается во много-много раз больше, чем ассоциативных. Значит, далеко не каждую неассоциативную операцию можно получить из ассоциативной

[AD]

Профессор Снэйп писал(а):

точный ответ неизвестен даже для $n=8$.

Жесть ...

Профессор Снэйп писал(а):

Неассоциативных операций получается во много-много раз больше, чем ассоциативных.

И асимптотика, небось, не в нашу пользу ... Да, значит, надо посвободнее соответствие сочинять. Чтобы одна ассоциативная операция обслуживала очень много неассоциативных. Ну да ладно, это уже для умных.

[Профессор Снэйп]

AD писал(а):

Да, значит, надо посвободнее соответствие сочинять. Чтобы одна ассоциативная операция обслуживала очень много неассоциативных. Ну да ладно, это уже для умных.

Прежде чем вести разговоры о том, что "для умных", а что нет, полезно было бы зафиксировать чёткую постановку проблемы, со всеми необходимыми определениями.

Что Вас интересует? Можно ли любую бинарную операцию на произвольном множестве определить через некоторую ассоциативную операцию (или операции)? Прежде чем отвечать на этот вопрос, нужно зафиксировать формальный смысл того, что значит "одна операция определяется через другую".

Вас интересует определение бинарных операций через суперпозиции конечного числа ассоциативных бинарных операций? Или может быть вопрос о том, можно ли задать произвольную бинарную операцию через уравнение, использующее символы ассоциативных бинарных операций, как неявную функцию (типа как мы задаём разность $a-b$ через решение уравнения $a = x+b$). Или что-то третье?

Первые два вопроса --- это уже интересные задачи, над ними можно подумать. Для начала предлагаю описать класс (не обязательно бинарных) операций на $\mathbb{Z}_n$, выразимых при помощи сложения и суперпозиций (ну и ещё проекций, про них часто забывают, однако без них с формальной точки зрения далеко не уедешь).

Пусть $X$ --- произвольное множество, $g(y_1, \ldots, y_n)$ --- некоторая $n$-местная операция на $X$ (то есть отображение из $X^n$ в $X$). Пусть также $h_1(x_1, \ldots, x_k), \ldots, h_n(x_1, \ldots, x_k)$ --- $n$ штук $k$-местных операций на $X$. Мы говорим, что $k$-местная операция $f$ задаётся при помощи суперпозиции из операций $g, h_1, \ldots, h_n$, если её значение на произвольном наборе $x_1, \ldots, x_k \in X$ определяется равенством:

$$ f(x_1, \ldots, x_k) = g(h_1(x_1, \ldots, x_k), \ldots, h_n(x_1, \ldots, x_k)) $$

Пусть $X = \mathbb{Z}_n$, $f(x,y) = x + y$ и $I_n^k(x_1, \ldots, x_n) = x_k$ для всех натуральных $n \geqslant 1$ и $k$ от $1$ до $n$. Какие операции на $X$ можно построить суперпозициями, исходя из этих функций? Ясно, что далеко не все. Например, умножение этим способом не задашь. А через умножение и проекции, наоборот, нельзя выразить сложение. Можно также довольно легко придумать операцию, которую нельзя выразить через сложение, умножение и проекции? Ну и т. д., в том же духе...

[AD]

Ну я и говорю: точное фиксирование проблемы - это уже для умных. Чтобы они так прикинули, при каком способе выражения операций через другие всё может получиться, чтобы ушли от тривиальностей и дальше уже пытались что-то доказать.

Не могу сказать, что интересует что-то конкретное, но вопросы мне показались любопытными. То есть я над этим вряд ли буду серьезно думать. В слова "для умных" вкладывался именно этот смысл.