Эндоморфизмы алгебры

[Memento]

На конечном множестве чисел задана алгебра с единственной бинарной операцией. Каким образом можно найти все ее эндоморфизмы?

[bot]

Найти образующие и поперебирать, куда что послать. А конкретность есть?

[Memento]

Носителем является $X=\{1, 2, 3, 4, 5\}$, сигнатура $\Omega=\{*\},\, x*y=x^y$, если $x^y \leq 5,\,5$ — в противном случае

[Memento]

Системой образующих будет 1, 2, 3?

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

Можно совсем тупо: перебрать все отображения $X$ в себя и для каждого проверить, сохраняется ли операция. Вручную не получится (всё же $5^5 = 3125$ - это довольно много), но компутер справится. Надо будет лишь чуть-чуть попрограммировать.

[bot]

Ну, многое можно отбросить сразу. Так как при эндоморфизме идемпотент переходит в идемпотент, то 1 переходит либо в 1 либо в 5. Если в 5, то все остальные тоже в 5. Отображение $x\to 5$ является эндоморфизмом. Теперь при всех остальных эндоморфизмах 1 идёт в 1. Уже легче. Берём 2, если она идёт в 1, то 4=2*2 и 5=2*4 - тоже в 1. Так как 3*4=5, то 3 в 1. Всё в 1 - это эндоморфизм. Пусть 2 идёт в 2 ...

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

bot в сообщении #548211 писал(а):

Ну, многое можно отбросить сразу...

Если программировать, то можно и не отбрасывать. Сила есть - ума не надо!

Ну а так, конечно, да... Мне в Ваших рассуждениях один момент непонятен.

bot в сообщении #548211 писал(а):

1 переходит либо в 1 либо в 5. Если в 5, то все остальные тоже в 5.

Почему это так?

-- Ср мар 14, 2012 15:17:34 --

Если $1$ перейдёт в $5$, а все остальные в $1$, то вроде ничего не нарушается.

[Memento]

Написал программу для поиска "в лоб", нашлось 1532 эндоморфизма. Это правдоподобно вообще?

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

Memento в сообщении #548249 писал(а):

Написал программу для поиска "в лоб", нашлось 1532 эндоморфизма. Это правдоподобно вообще?

Да почему бы и нет?

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

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

Можно ещё (как я обычно делаю) взять пару алгебраических систем поменьше или "порегулярнее", для которых ответ заранее известен. И посмотреть, выдаёт ли прога на них правильные результаты. Если да, то с логикой в программе скорее всего всё в порядке.

А ещё можно позапускать прогу в "пошаговом режиме" и просмотреть внимательно, что она делает.

[Memento]

Я уже проверил несколько отображений, операция сохраняется.

Сейчас на всякий скучай протестирую на меньшей основе. Спасибо за помощь.

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

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

-- Ср мар 14, 2012 18:33:09 --

Memento в сообщении #548266 писал(а):

на всякий скучай

Хорошая опечатка

[Memento]

Я так уже и сделал, вывел поток в файлик.

Ага, занятие для скучного холодного весеннего вечера

[bot]

Профессор Снэйп в сообщении #548218 писал(а):

Если перейдёт в , а все остальные в , то вроде ничего не нарушается

$1'=5 \Rightarrow x'=(x*1)'=x'*1'=x'*5=5$

Memento в сообщении #548249 писал(а):

Написал программу для поиска "в лоб", нашлось 1532 эндоморфизма. Это правдоподобно вообще

Это заведомо неверно. Порождающих у нас 3, каждое можно послать в 5 мест - итого получаем максимум 125 эндоморфизмов. Если начать с того места, где я приостановилось то этот максимум уже уменьшен до 26, на самом деле заведомо меньше и перебирать тупо ещё рано, так как форсинг ещё не исчерпан. Если 2'=2, то 4'=(2*2)'=2'*2'=2*2=4 и 5'=...=5, тройку отсылаем произвольно и проверяем - нельзя 3'=1,2. Если 2'=3, то 4'=5, 5'=5 ...

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

bot в сообщении #548274 писал(а):

$1'=5 \Rightarrow x'=(x*1)'=x'*1'=x'*5=5$

Пардон, но Вы не правы. Если $x' = 1$, то и $x' * 5 = 1$. А $x' = 1$ для всех $x \neq 1$.

-- Ср мар 14, 2012 22:17:34 --

bot в сообщении #548274 писал(а):

Это заведомо неверно. Порождающих у нас 3, каждое можно послать в 5 мест - итого получаем максимум 125 эндоморфизмов.

А вот с этим, пожалуй, стоит согласиться. Как-то сразу не подумал

[bot]

Профессор Снэйп в сообщении #548347 писал(а):

Пардон, но Вы не правы.

Признаю - засбоило, звёздочку местами стал принимать за обычное умножение с обрезанием. Тогда чуть побольше будет.
1) 1'=5, тогда $(\forall x)(x'=1 \vee x'=5)$. Если 2'=1, то 4'=1 и 5'=1, а 3' либо 1 либо 5 - проверяем. Если 2'=5, то 4'=5, 5'=5, а 3' либо 1 либо 5 - проверяем.
2) 1'=1, 2'=1, 4'=1, 5'=1, 3'=?
3) 1'=1, 2'=2, 4'=4, 5'=5, 3'=?
4) 1'=1, 2'=3, 4'=5, 5'=5, 3'=?
5) 1'=1, 2'=4, 4'=5, 5'=5, 3'=?
6) 1'=1, 2'=5, 4'=5, 5'=5, 3'=?

-- Чт мар 15, 2012 00:19:32 --