Коммутативно, но не ассоциативно

[bnovikov]

gris в сообщении #507354 писал(а):

bnovikov, вот уж отнюдь. Раcсмотрим 15 равноудалённых на расстояние 1 профессорских кошек и на таком же расстоянии расположим числа 0 и 1. Расстояние будет операцией на объединённом множестве.

gris, отнюдь не отнюдь.
Если Вы кошек заменили на числа, то Ваше "объединённое множество" состоит из двух элементов: 0 и 1. А против того, чтобы рассматривать расстояние между числами как операцию, я не возражал. Если же Вы считаете, что Ваше "объединённое множество" состоит из 16 элементов, то трюк с нулями и единицами ни к чему не приводит. Кошки остались кошками, просто Вы навесили им бирки с номерами.

[gris]

Всё это, разумеется, шутка, но тем не менее. Расмотрим множество, состоящее их 15 кошек, сами знаете кому принадлежащих, и объединим его с действительными числами 0 и 1. То есть всего 17 элементов. Введём на нём дискретную метрику. Так вот, расстояние между двумя элементами равно либо 0, либо 1, то есть является элементом множества. А значит, это операция. Конечно, Вы можете сказать, что это другие 0 и 1, но и на это найдутся уточнения.

[bnovikov]

gris в сообщении #507628 писал(а):

Конечно, Вы можете сказать, что это другие 0 и 1, но и на это найдутся уточнения.

Не скажу. Так я согласен. Извините за то, что неправильно понял.

[gris]

bnovikov, ну Вы прямо меня смущаете, честное слово. Я даже готов заменить кошек на что-нибудь более топологичное

[bnovikov]

gris в сообщении #507789 писал(а):

bnovikov, ну Вы прямо меня смущаете, честное слово. Я даже готов заменить кошек на что-нибудь более топологичное

Не заменяйте. Я в топологии не разбираюсь.

На самом деле в том, что Вы делаете, есть один небольшой недостаток - неестественность. Вы имеете отображение $A\times A\to B$ и хотите расширить его до операции $(A\cup B)\times (A\cup B)\to A\cup B$. Но тогда появляется отображение $A\times B\to B$, т.е. Вам нужно определять расстояние от кошки до 1, что, согласитесь, выглядит неэстетично.

Более серьезный аналог - умножение кольца на модуль, $R\times M\to M$. Попробуйте продолжить его до $(R\cup M)\times (R\cup M)\to R\cup M$!

[gris]

Расстояние от кошки до 1 равно 1, метрика-то дискретная. (Кошки и у Профессора сидят в вершинах многомерного правильного тетраэдра.) Другое дело, что она совпадает с метрикой $\mathrm R$, ограниченной на $\{0;1\}$. Ну да ладно. Это, повторюсь, не более, чем шутка.

Меня во всём этом интересовал вопрос с матрицей, определяющей операции на конечном множестве. Какова вероятность, что случайно заполненная матрица определит ассоциативную операцию. Ответ я пока получил только для нескольких первых значений числа элементов множества, так как никакого алгоритма, кроме тупого перебора, не придумал. Найти хотя бы необходимые условия.

[bnovikov]

gris в сообщении #507837 писал(а):

Меня во всём этом интересовал вопрос с матрицей, определяющей операции на конечном множестве. Какова вероятность, что случайно заполненная матрица определит ассоциативную операцию. Ответ я пока получил только для нескольких первых значений числа элементов множества, так как никакого алгоритма, кроме тупого перебора, не придумал. Найти хотя бы необходимые условия.

А зачем Вам это?

[gris]

не хотелось бы оффтопить в теме, но, возможно, и сам автор работает над подобным вопросом. Ассоциативные операции на конечных множествах очень важны при моделировании некоторых процессов. Разумеется, интересуют не совершенно случайные матрицы операций, а отвечающие некоторым требованиям. Например: результатом операции могут служить только 2 или три элемента множества, результатом операции является один из операндов или так называемых "друзей" операнда, ну и тому подобное.
И ассоциативность операции всегда является необходимым условием.
Генерировать матрицы, отвечающие всем прочим условиям, несложно, а вот проверка на ассоциативность занимает много времени. Для числа объектов больше 20 генерация подходящей матрицы может занимать в 100 раз больше времени, чем последующее моделирование процесса с обработкой результатов. Поэтому так необходимы хоть какие-нибудь необходимые условия ассоциативности.
Вот.

worm2, спасибо!

+ bnovikov, и Вам спасибо.
На самом деле мне алгебраичная строгость и не нужна, достаточно "приближённой" ассоциативности, просто интересно стало.

[worm2]

gris, взгляните на Light's associativity test.

[bnovikov]

gris в сообщении #507869 писал(а):

Ассоциативные операции на конечных множествах очень важны при моделировании некоторых процессов.

(Оффтоп)

Понятно. Первым делом нужно все-таки говорить не о матрицах, а о полугруппах. Насколько я понял, Вас интересуют два вопроса.

1) Какова доля полугрупп данного порядка среди группоидов того же порядка (разумеется, оценка)?

Ответ зависит от цвета кошки: все полугруппы или с точностью до изоморфизма?

Если с точностью до изоморфизма, то этого не знает никто (хотя работы в этом направлении есть).

Если все, тогда стоит посмотреть статью

D.J. Kleitman, B.R. Rothschild, J.H. Spencer, The number of
semigroups of order n. Proc. Amer. Math. Soc. 55(1976),
227–232.

2) Как определить, ассоциативен ли группоид?

Light's associativity test, который Вам дал worm2 - это общий алгоритм, который, конечно, не всегда хорош. Нужно выяснить, какие именно полугруппы появляются у Вас, и для них искать алгоритм. Например, полугруппы, у которых "результатом операции является один из операндов" должны описываться достаточно легко (и наверняка уже описаны).