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

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

AD писал(а):

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

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

Не помню, кто сказал

Цитата:

Плох тот солдат, который не мечтает стать генералом

[AD]

Это да. Только постепенно, хорошо? Я просто пока немного не из этой области, мне бы первую в жизни курсовую сочинить сначала ...

Кстати, что-то в Куроше было по поводу вездесущности ассоциативности. Там под конец доказывалось, что любое множество с любой системой операций можно построить внутри некой полугруппы, в которой n-арные операции $f(x_1,\ldots,x_n)$ из нашей системы представляются в виде $\tilde{f}*x_1*\ldots*x_n$, где $\tilde f$ - некоторый элемент полугруппы, поставленный в соответствие операции $f$, а $*$ - умножение в этой полугруппе (это всё называлось "специальное точное представление").

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

Так. Если мы берём полугруппу $\langle S, \ast \rangle$ с $n$-элементным носителем $S$, то существует ровно $n$ унарных операций вида $f(x) = \tilde{f} \ast x$, а всего унарных операций на $S$ ровно $n^n$. Значит, далеко не любая операция на $S$ представима в указанном виде.

Но, возможно, здесь имелось в виду что-то вроде следующего. Пусть $\langle X, f_1, \ldots, f_n \rangle$ --- произвольная алгебраическая стстема с $n$ операциями (произвольной арности каждая). Тогда существует полугруппа $\langle S, \ast \rangle$, в ней подполугруппа (или даже просто подмножество) $H \subseteq S$ и элементы $\tilde{f}_1, \ldots, \tilde{f}_n \in S$, такие что

1) для произвольных $i \in [1,n]$ и $x_1, \ldots, x_{m_i} \in H$ имеет место $\tilde{f}_i \ast x_1 \ast \ldots \ast x_{m_i} \in H$;

2) Если для всех $i \in [1,n]$ и $x_1, \ldots, x_{m_i} \in H$ положить $g_i(x_1, \ldots, x_{m_i}) = \tilde{f}_i \ast x_1 \ast \ldots \ast x_{m_i}$, то алгебраические системы $\langle X, f_1, \ldots, f_n \rangle$ и $\langle H, g_1, \ldots, g_n \rangle$ изоморфны.

Если это правда, то, это, наверное, нетривиальный результат. Надо помыслить

[AD]

Да, примерно так вроде бы. Ясно, что "вкладывается", а не "равна". Даже вроде бы конечность числа операций не требуется.

[bot]

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

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

По сути оно и есть - правда пришёл тогда к этому окольным путём: класс антиассоциативных группоидов, дополненный единичным группоидом, является квазимногообразием, определяемым квазитождеством $x\cdot yz=xy\cdot z \rightarrow u=v$. Отсюда ясно, что это квазимногообразие замкнуто относительно взятия гомоморфных прообразов. Эти прообразы легко построить "раздвоением" одного элемента. Такисм образом достаточно построить антиассоциативный двухэлементный группоид. Построил (он же одномоментно строится), глянул на него, и вуаля:
Берём любое отображение $x \rightarrow x'$ с условием $\forall x (x''\ne x')$ и полагаем $xy=x'$. В итоге, множество значений искомой операции можно выбрать даже двухэлементным.

Цитата:

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

Какие-то циферки там кривые - сразу в глаза бросается при n=2 одна, это же бред, что кроме группы нет других полугрупп? Конечно есть - с нулевым умножением, к примеру. Видимо это что-то другое. Что такое "labeled semigroup"?
В своё время сам на БЭСМ-6 считал их до 5-го порядка, четырёхэлементных - 126, а 5-элементных 1160, вроде так помнится - с точностью до изоморфизмов и антиизоморфизмов.
Потом, когда мне уж и не надо было, мне прислали американскый список до 6-го порядка (или до 7-го? - надо глянуть) - до 5-го порядка не было расхождений, если несчитать, что у них элементы - буковки, а у меня циферки, даже порядок перечисления совпал, стало быть лексикографикой одинаковой пользовались.
Если с 70-х в этом вопросе нет никаких продвижений, то он никому не нужен, да и гробовой он. Уж очень там мощности классов разбиения по изо(анти)изоморфизму вариабельны.

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

bot писал(а):

Какие-то циферки там кривые - сразу в глаза бросается при n=2 одна, это же бред, что кроме группы нет других полугрупп? Конечно есть - с нулевым умножением, к примеру. Видимо это что-то другое. Что такое "labeled semigroup"?

"Там", Александр Дмитриевич, "циферки" абсолютно правильные. Просто нормальные люди начинают считать с нуля. Имеется 1 способ задать ассоциативную бинарную операцию на пустом множестве, 1 способ на одноэлементном, 8 способов на двухэлементном, 113 способов на трёхэлементном и т. д.

"Labeled semigroup" --- это "размеченная" полугруппа. Другими словами, каждый элемент выделяют уникальным унарным предикатом ("меткой") и смотрят уже количество таких структур с точностью до изоморфизма. Это то же самое, что считать различные операции, которые на фиксированном $n$-элементном множестве задают полугруппу. Причём если операции разные, то и считать их надо за разные, даже если полугруппы получаются изоморфными. То есть не количество $n$-элементных полугрупп с точностью до изоморфизма считаем, а просто количество полугрупп с фиксированным $n$-элементным носителем.

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

bot писал(а):

В своё время сам на БЭСМ-6 считал их до 5-го порядка, четырёхэлементных - 126, а 5-элементных 1160, вроде так помнится - с точностью до изоморфизмов и антиизоморфизмов.
Потом, когда мне уж и не надо было, мне прислали американскый список до 6-го порядка (или до 7-го? - надо глянуть) - до 5-го порядка не было расхождений, если несчитать, что у них элементы - буковки, а у меня циферки, даже порядок перечисления совпал, стало быть лексикографикой одинаковой пользовались.
Если с 70-х в этом вопросе нет никаких продвижений, то он никому не нужен, да и гробовой он. Уж очень там мощности классов разбиения по изо(анти)изоморфизму вариабельны.

А вот то, что Вы тогда считали: http://www.research.att.com/~njas/sequences/A001423

В настоящий момент известны значения вплоть до восьмого порядка

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

AD писал(а):

Да, примерно так вроде бы. Ясно, что "вкладывается", а не "равна". Даже вроде бы конечность числа операций не требуется.

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

Пусть $X$ --- произвольное множество. Пусть $S$ --- это множество всех унарных операций на $X$. Тогда $S$ образует полугруппу относительно композиции.

Для $x \in X$ через $f_x$ обозначим унарную операцию на $X$, отображающую каждый элемент $X$ в $x$.

Соответствие $x \mapsto f_x$ вкладывает $X$ в $S$ и можно отождествлять $X$ с образом этого соотвествия.

Теперь для произвольного $s \in S$ имеем $s \circ f_x = f_{s(x)}$. И всё, похоже

У-у-у, как всё просто! И общий случай, по моему, нисколько не сложнее!! Да, не нужен нам Курош, мы и сами с усами!!!

[AlexDem]

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

И всё, похоже

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

[AlexDem]

Разобрался вчера по дороге в чём было дело... Там в последнем равенстве порядок множителей обратный $s \circ f_x$, я внимания не обратил и поэтому при проверке на бинарных операциях на автомате перепутал правый с левым нулём, так что любое выражение равнялось первому множителю.

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

AlexDem писал(а):

Разобрался вчера по дороге в чём было дело...

Ну раз разобрались, то и отвечать на вопрос, думаю, не требуется.

AlexDem писал(а):

Там в последнем равенстве порядок множителей обратный $s \circ f_x$, я внимания не обратил и поэтому при проверке на бинарных операциях на автомате перепутал правый с левым нулём, так что любое выражение равнялось первому множителю.

Насколько я знаю, общепринятого соглашения относительно порядка множителей при композиции вообще нет. Допустим, $f$ --- это функция из $A$ в $B$, а $g$ --- функция из $B$ в $C$. Их композиция --- это функция из $A$ в $C$. Иногда эту композицию записывают как $f \circ g$, а иногда --- как $g \circ f$, в разных книгах я встречал по разному. Первая запись удобна тем, что порядок функций в композиции совпадает с порядком стрелок и при работе с диаграммами не надо ничего "переворачивать". Вторая удобна тем, что не нужно ничего "переворачивать" при записи значений функций на аргументах: например, $(g \circ f)(a) = g(f(a))$ для $a \in A$.

В любом случае для данной задачи порядок не важен, поскольку если он не нравится, то его всегда можно "перевернуть".

[AD]

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

У-у-у, как всё просто! И общий случай, по моему, нисколько не сложнее!! Да, не нужен нам Курош, мы и сами с усами!!!

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

[AlexDem]

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

Насколько я знаю, общепринятого соглашения относительно порядка множителей при композиции вообще нет.

Ага. Было бы, наверно, удобно функцию записывать в виде $y = (x)f$ вместо $y = f(x)$, тогда бы прямой порядок был естественным .

А вот по ходу - во что можно вложить подобным образом (через $\tilde f * x * y$) симметрическую полугруппу кроме другой полугруппы? В группу явно нельзя из-за сокращений, в некоторый неассоциативный группоид - можно: добавляем к исходной полугруппе новый элемент $x$ и на данном элементе модифицируем операцию (бывшую суперпозицией) таким образом, чтобы $xy = x +1$, тогда в качестве $\tilde f$ достаточно взять бывшую единицу. Так?

[lofar]

AlexDem писал(а):

Было бы, наверно, удобно функцию записывать в виде $y = (x)f$ вместо $y = f(x)$, тогда бы прямой порядок был естественным .

Так иногда и поступают.

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

AlexDem писал(а):

А вот по ходу - во что можно вложить подобным образом (через $\tilde f * x * y$) симметрическую полугруппу кроме другой полугруппы? В группу явно нельзя из-за сокращений, в некоторый неассоциативный группоид - можно: добавляем к исходной полугруппе новый элемент $x$ и на данном элементе модифицируем операцию (бывшую суперпозицией) таким образом, чтобы $xy = x +1$, тогда в качестве $\tilde f$ достаточно взять бывшую единицу. Так?

Ну да. Если я всё правильно понял, то вроде все рассуждения корректны.

Единственное что --- непонятно, откуда плюс и единица возьмутся, их надо дополнительно определять. А затем кроме $xy=x+1$ надо будет ещё доопределить, чему равно $yx$. Но все эти трудности, безусловно, преодолимы. То, что любую полугруппу (в нашем случае даже моноид) можно вложить в качестве подмодели в неассоциативный группоид (при необходимости даже с сохранением единицы) не подлежит сомнению.

К чему Вы хотите прийти?

[AlexDem]

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

Единственное что

Согласен с Вами. В принципе, здесь эта "+1" определяет просто некоторый "следующий за $x$ элемент" - можно выбрать любой из исходной полугруппы. Значения $yx$ тоже можно выбрать произвольно.

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

К чему Вы хотите прийти?

Это по поводу вездесущности ассоциативности, о которой говорил AD. Получается, что точно также можно говорить и о вездесущности неассоциативности .

[AlexDem]

AD в сообщении #100356 писал(а):

Кстати, что-то в Куроше было по поводу вездесущности ассоциативности. Там под конец доказывалось, что любое множество с любой системой операций можно построить внутри некой полугруппы, в которой n-арные операции $f(x_1,\ldots,x_n)$ из нашей системы представляются в виде $\tilde{f}*x_1*\ldots*x_n$, где $\tilde f$ - некоторый элемент полугруппы, поставленный в соответствие операции $f$, а $*$ - умножение в этой полугруппе (это всё называлось "специальное точное представление").

Объясните, пожалуйста. Пытаюсь указанным выше образом представить умножение $a \cdot b \cdot c$ некоторого группоида с единицей. Пишу:

$$a \cdot b = \tilde f * a * b,$$

но в то же время:

$$a \cdot b \cdot e = \tilde f * (\tilde f * a * b) * e = \tilde f^2 * a * b.$$

Откуда $\tilde f^2 = \tilde f$. Что я делаю не так? В Куроше примеров нет, а в приводимом доказательстве есть пара неясных моментов, которые мешают разобраться.